Relacje
Relacjami binarnymi (dwuargumentowymi) nazywamy pary (A, R) takie, że R ⊆ A2. Zbiór A nazywamy dziedziną takiej relacji.
Dla dowolnego zbioru A
A1 = A
An+1 = An × A
Niech (A, R) - relacja binarna.
(A, R) jest zwrotna ⇔Df ∀x∈A (x, x)∈R
(A, R) jest symetryczna ⇔Df ∀x ∀y [(x, y)∈R ⇒ (y, x)∈R]
(A, R) jest przechodnia ⇔Df ∀x ∀y ∀z {[(x, y)∈R ∧ (y, z)∈R] ⇒ (x, z)∈R}
Zwrotność zależy od dziedziny - musimy wskazać dziedzinę, aby własność miała sens. Symetryczność i przechodniość nie zależą od dziedziny - własność R-a (jeśli R ma parę (x, y), to ma w sobie i (y, x)).
(A, R) jest równoważnościowa ⇔Df (A, R) jest zwrotna, symetryczna i przechodnia
Rozpatrywanie zjawisk z punktu widzenia tylko pewnych jakości, tzn. z dokładnością do pewnej równoważności.
Niech (A, R) będzie równoważnością, x∈A. Zbiór [x]R = {y∈A: (x, y)∈R} nazywamy klasą abstrakcji elementu x względem R.
R jednoznacznie wyznacza A.
Ze zwrotności wynika zupełność (Ux = A), z symetryczności i przechodniości wynika rozłączność.
Podział (logiczny) zbioru wyznacza relację równoważności i odwrotnie.
Podziałem zbioru A nazywamy rodzinę zbiorów B ⊆ P(A) taką, że:
1. ∅∉B
2. UB = A
3. ∀x, y∈B (x ∩ y ≠ ∅ ⇒ x = y)
Niech (A, R) będzie równoważnością, B = {[x]R: x∈A}. Wówczas B jest podziałem A.
[x] jest niepusta, zawiera przynajmniej x.
Niech x, y∈B takie, że x ∩ y ≠ ∅. Wówczas ∃z z∈x ∩ y, z∈x ∧ z∈y. Dowodzimy, że x = y.
(⊆) Niech w∈x. ∃w0∈a w∈[w0]R oraz z∈[w0]R. Stąd (z, w0)∈R i (w, w0)∈R. Z symetryczności i przechodniości (z, w)∈R. Ponadto istnieje w1 takie, że y = [w1]R. Stąd mamy (z, w1)∈R i z przechodniości i symetryczności mamy (w, w1)∈R, czyli w∈[w1]R = y.
(⊇) Analogicznie. □
(A, R) jest asymetryczna ⇔Df ∀x ∀y {[(x, y)∈R ∧ (y, x)∈R] ⇒ x = y}
(A, R) jest spójna ⇔Df ∀x, y∈A [(x, y)∈R ∨ (y, x)∈R] (dowolne 2 elementy są ze sobą porównywalne)
(A, R) jest porządkiem ⇔Df (A, R) jest zwrotna, asymetryczna i przechodnia
(porządek częściowy i nieostry). A ⊆ P(B), A - rodzina zbiorów, B - dowolny zbiór. (?)
R = {(x, y)∈A2: x ≤ y}
Para (A, R) jest porządkiem
(A, R) jest porządkiem liniowym ⇔df (A, R) jest porządkiem i jest spójny
Niech (A, R) będzie porządkiem, x, y∈A. Wówczas piszemy (umowa notacyjna) x ≤Ry zamiast (x, y)∈R.
Niech (A, R) będzie porządkiem, x, y∈A. Wówczas piszemy (umowa notacyjna)
(…)
… zawsze jest dobry, np. ({0, 1, 2, 3, 4}, ≤)
≤|A = ≤ ∩ A2 (2, ≤) - nie
(A skończony, ≤|A) - tak
(<0, 1〉, ≤) - nie Zielone i czerwone liczby naturalne - dobry porządek.
Przykład struktury, dla której działa zasada minimum, a nie zasada indukcji Dedekinda - można by udowodnić, że każda liczba jest zielona.
To nie jest ciąg, lecz konstrukcja teoriomnogościowa.
U = {z, c} × N
R = {((a, n), (b, k))∈U2: (a = b ∧ n ≤ k…
… (A, R) jest porządkiem
(A, R) jest porządkiem liniowym ⇔df (A, R) jest porządkiem i jest spójny
Niech (A, R) będzie porządkiem, x, y∈A. Wówczas piszemy (umowa notacyjna) x ≤Ry zamiast (x, y)∈R.
Niech (A, R) będzie porządkiem, x, y∈A. Wówczas piszemy (umowa notacyjna) x <Ry zamiast (x, y)∈R ∧ x ≠ y.
Dobre porządki to porządki liniowe spełniające zasadę minimum.
(A, R) jest dobrym porządkiem (zbiór…
... zobacz całą notatkę
Komentarze użytkowników (0)