Relacja równoważności: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
→Definicja: poprawa zapisu matematycznego na bardziej formalny |
→Przykłady: sortowanie, wincyj przykładów |
||
Linia 50:
== Przykłady ==
* W dowolnym zbiorze <math>X \,</math> zdefiniowana jest relacja:▼
* W zbiorze <math>A=\{1,2,3,4,5,6,7\} \,</math> określona jest relacja: <math>x \equiv y</math> wtedy i tylko wtedy, gdy <math>x \,</math> i <math>y \,</math> dają taką samą [[twierdzenie o dzieleniu z resztą|resztę z dzielenia]] przez 3. Pokazuje się, że jest to relacja równoważności, jej klasami abstrakcji są:▼
*: <math>x\ R\ y\;</math> wtedy i tylko wtedy, gdy <math>x = y\;</math>.▼
: Jest to istotnie relacja równoważności nazywana '''[[równość (matematyka)|równością]]'''. Klasami abstrakcji są [[Zbiór jednoelementowy|zbiory jednoelementowe]] (singletony) <math>\{x\} \,</math>.▼
▲* W zbiorze <math>A=\{1,2,3,4,5,6,7\} \,</math> określona jest relacja: <math>x \equiv y</math> wtedy i tylko wtedy, gdy <math>x \,</math> i <math>y \,</math> dają taką samą [[twierdzenie o dzieleniu z resztą|resztę z dzielenia]] przez 3 ([[Arytmetyka modularna|kongruencja modulo 3). Pokazuje się, że jest to relacja równoważności
*: <math>[1] = [4] = [7] = \{1,4,7\} \,</math>
*: <math>[2] = [5] = \{2,5\} \,</math>
Linia 56 ⟶ 59:
: Poszczególne warstwy są rozłączne, a przestrzenią ilorazową jest zbiór:
:: <math>A/_\equiv = \Big\{\{1,4,7\}, \{2,5\}, \{3,6\}\Big\}</math>
* W zbiorze wszystkich samolotów istnieje relacja równoważności: dwa [[samolot]]y są równoważne, gdy mogą przewieźć tę samą liczbę pasażerów. Klasą abstrakcji danego samolotu zabierającego na pokład równo 50 osób jest zbiór wszystkich samolotów mogących przewieźć dokładnie 50 osób.▼
▲* W dowolnym zbiorze <math>X \,</math> zdefiniowana jest relacja:
▲*: <math>x\ R\ y\;</math> wtedy i tylko wtedy, gdy <math>x = y\;</math>.
▲: Jest to istotnie relacja równoważności nazywana '''[[równość (matematyka)|równością]]'''. Klasami abstrakcji są zbiory jednoelementowe <math>\{x\} \,</math>.
* W [[geometria|geometrii]] relacjami równoważności są m.in. [[przystawanie (geometria)|przystawanie]] i [[podobieństwo]].
* W zbiorze prostych na płaszczyźnie określona jest [[równoległość|relacja równoległości]]: proste <math>a \,</math> i <math>b \,</math> są równoważne, gdy są równoległe. Klasami abstrakcji są tu zbiory prostych równoległych (tzw. [[kierunek|kierunki]]).▼
* Każdy [[izomorfizm]] wprowadza relację równoważności uznającą struktury danej teorii za nierozróżnialne (mające te same własności).▼
* W [[algebra liniowa|algebrze liniowej]]: [[Liniowo zależny układ wektorów|liniowa zależność]] wektorów jest relacją równoważności. Klasami abstrakcji są tutaj kierunki (proste) – jednowymiarowe podprzestrzenie liniowe.
▲*
* W dowolnym [[graf (matematyka)|grafie]] nieskierowanym <math>(V, E) \,</math> zdefiniujmy relację na wierzchołkach:
*: <math>x\ R\ y</math>, gdy istnieje [[ścieżka (teoria grafów)|ścieżka]] z <math>x \,</math> do <math>y \,</math> (być może jest to ścieżka pusta, jeżeli <math>x=y \,</math>).
: Wyznaczony przez tę relację podział nazywa się podziałem grafu na [[spójna składowa grafu|spójne składowe]]<ref name=wilson>{{Cytuj książkę|nazwisko=Wilson|imię=Robert|tytuł=Wprowadzenie do teorii grafów|wydawca=[[Wydawnictwo Naukowe PWN]]|strony=30, 41|rok=1985}}</ref>.
* Podobną relację określa się w [[graf skierowany|grafach skierowanych]]: określamy, że <math>x\ S\ y</math>, gdy istnieją ścieżki z <math>x \,</math> do <math>y \,</math> i z <math>y \,</math> do <math>x \,</math>. Relacja <math>S \,</math> daje w wyniku podział grafu na [[składowa silnie spójna|silnie spójne składowe]].
▲* W zbiorze wszystkich samolotów istnieje relacja równoważności: dwa [[samolot]]y są równoważne, gdy mogą przewieźć tę samą liczbę pasażerów. Klasą abstrakcji danego samolotu zabierającego na pokład równo 50 osób jest zbiór wszystkich samolotów mogących przewieźć dokładnie 50 osób.
▲* W zbiorze prostych na płaszczyźnie określona jest [[równoległość|relacja równoległości]]: proste <math>a \,</math> i <math>b \,</math> są równoważne, gdy są równoległe. Klasami abstrakcji są tu zbiory prostych równoległych (tzw. [[kierunek|kierunki]]).
== Tworzenie struktur ==
| |||