11.1 Kraty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
11.2 Algebry Boole’a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Literatura

115

Zakaz rozpowszechniania bez zgody autora

Podstawowe pojęcia teorii mnogości — postulaty.

Teoria mnogości (teoria zbiorów), zainicjowana została w drugiej połowie XIX wieku,
przez matematyka Georga Cantora (1873, Jour. f. d. r. u. a. Math. (Crelles Journal),
vol. 77, 1874). Nieaksjomatyczna prezentacja teorii mnogości czasami zwana jest naiwną,
gdyż pewne zagadnienia w niej prezentowane są w sposób intuicyjny.

Z uwagi na paradoksy teorii mnogości — w jej intuicyjej wersji — podjęto próby (Ernst

Zermelo, 1905–1907, Math. Ann., vol. 65, 1908) sformułowania teorii mnogości w sposób
aksjomatyczny.

Abraham Fraenkel (1921, Math. Ann., vol. 86, 1922) i Thoralf Skolem (Matemati-

kerkong. i Hel., 1923; Skolem sprecyzował warunki nakładane na własność w aksjomacie
podzbiorów) uzupełnili aksjomatykę Zermelo o schemat aksjomatu zastępowania wzmac-
niając w ten sposób tzw. aksjomat podzbiorów lub wycinania (Axiom der Aussonderung).

D. Mirimanoﬀ (L’Enseig. Math., vol. 19, 1917), J. von Neumann (Jour. f. d. r. u. a.

Math., vol. 154, 1925 i vol. 160, 1929) i E. Zermelo (Fund. Math., vol. 16, 1930) roz-
patrywali aksjomat regularności (ufundowania). Ponadto Zermelo sformułował aksjomat
wyboru (1903, Math. Ann., vol. 59, 1904) przydatny w szeregu metatwierdzeń (ozn. AC
od „axiom of choice”).

∗

1.1

Wprowadzenie

Dla oznaczenia zbiorów będziemy zazwyczaj stosować wielkie litery z początku alfabetu,
czyli A, B, C itd.

Zbiory to intuicyjnie kolekcje pewnych obiektów. Obiekty te zwane są elementami

danego zbioru. Relacja należenia jest drugim (obok pojęcia zbioru) pojęciem pierwotnym
teorii mnogości. Relację należenia elementu do zbioru oznaczamy przez „∈”.

Pamiętajmy, że elementami zbiorów mogą być także zbiory. Czasami zbiór, którego

elementami są same zbiory, zwany jest rodziną (zbiorów ).

W tzw. czystej teorii mnogości występują właśnie tylko zbiory.
Rozpatrywane są również wersje teorii mnogości, w których mamy nie tylko zbiory.

Elementy, które nie są zbiorami zwane są urelementami (atomami).

W dalszej części wykładu przypomnimy podstawowe pojęcia teorii mnogości (takie

jak np. relacja, funkcja, liczba kardynalna itp.).

∗

Zdanie „a jest elementem (należy do) zbioru A” zapisujemy symbolicznie: „a ∈ A”.
Zdanie „a nie jest elementem (nie należy do) zbioru A” zapisujemy skrótowo: „a 6∈ A”.
Zbiory symbolicznie przedstawiamy za pomocą okręgów — diagramów Venna:

Zakaz rozpowszechniania bez zgody autora

1.2

Aksjomaty teorii mnogości.

1.2.1 Aksjomat zbioru pustego.

Szczególną rolę odgrywa zbiór pusty (ozn. ∅), który można scharakteryzować jako zbiór
nie posiadający żadnych elementów.

Symbolicznie:

∃

∀

x 6∈ A.

(Aks ∅)

Stwierdzenie to jest aksjomatem, bądź twierdzeniem — w zależności od sformułowania

teorii mnogości; jest to tzw. aksjomat zbioru pustego. Zbiór posty to taki zbiór A, że

∀

x 6∈ A

(Własn ∅)

Dalej zauważymy, że istnieje tylko jeden zbiór pusty i dlatego prawomocne jest stosowanie
jakiegoś oznaczenia, zwykle używa się w tym kontekście: ‘∅’.

W wyróżnionym powyższej wzorze zastosowano kwantyﬁkatory:
duży (ogólny, generalny) — ∀, zapis:

∀

czytaj jako: „dla każdego x”

mały (szczegółowy, egzystencjalny) — ∃; zapis:

∃

czytaj jako: „istnieje x [takie że]”.

∗

Jak już wspomniano, w ramach teorii mnogości można rozpatrywać atomy. One również
nie mają żadnych elementów, ale nie są zbiorami. Zgodnie z naszą konwencją użycie
wielkiej litery w sformułowaniu warunku dla zbioru pustego informuje nas o tym, że
obiekt, o którym mowa, jest zbiorem.

1.2.2 Aksjomat ekstensjonalności.

Fakt, że zbiory są identyczne (równe) oznaczamy: A = B

Ważnym postulatem jest aksjomat ekstensjonalności mówiący, kiedy zbioru są równe:

∀

(x ∈ A ⇔ x ∈ B) ⇒ A = B

(EKST)

Jeśli zbiory A i B mają te same elementy, to są równe, czyli A = B.

Przypomnijmy, że powyżej użyte spójniki deﬁniowane są następująco:

p q p ⇒ q
1 1

1 0

0 1

0 0

p q p ⇔ q
1 1

1 0

0 1

0 0

Zakaz rozpowszechniania bez zgody autora

gdzie 0 oznacza fałsz, zaś 1 prawdę.

W naiwnej teorii mnogości zwykle milcząco zakłada się (tzw. logiczne) aksjomaty

identyczności:

1. Każdy obiekt jest identyczny sam ze sobą.
2. Dla dowolnych obiektów, jeśli jeden obiekt jest identyczny z drugim, to ten drugi

jest identyczny z pierwszym.

3. Dla dowolnych obiektów, jeśli jeden obiekt jest identyczny z drugim a drugi z

trzecim, to pierwszy z nich jest identyczny z ostatnim.

4. Dla dowolnych x, y jeżeli x = y, to jeśli x jest zbiorem, to y również.
5. Dla dowolnych x, y jeśli x = y, to jeśli x jest elementem pewnego zbioru, to y

również.

6. Dla dowolnych x, y, z jeżeli x = y, to jeśli z jest elementem x, to również z jest

elementem y.

Warunki 1 i 3 w odniesieniu do zbiorów można udowodnić stosując warunki 2, 6 oraz

własności logiki klasycznej.

W dalszej części zdeﬁniujemy podstawowe działania na zbiorach i podamy przykłady

własności działań.

Deﬁnicja 1.1. Zbiór A jest zawarty w zbiorze B (inaczej: A jest podzbiorem B lub B
jest nadzbiorem A; ozn. A ⊆ B) wtw każdy element zbioru A jest elementem zbioru B
[czyli równoważnie: dla każdego x (x ∈ A ⇒ x ∈ B)]. Relację ⊆ zwie się inkluzją.

Graﬁcznie taką sytuację można przedstawić następująco:

A ⊆ B

Przykład 1.2. Zbiór wszystkich Polaków jest zawarty w zbiorze wszystkich ludzi.

Mamy następujące obserwacje:

Lemat 1.3. Dla dowolnych zbiorów A, B, C:

inkl. 1 A ⊆ A,
inkl. 2 Jeśli A ⊆ B i B ⊆ C, to A ⊆ C.

Z deﬁnicji zawierania, na mocy przyjętych aksjomatów widać, że dwa zbiory są iden-

tyczne wtw wzajemnie się w sobie zawierają. Również dzięki rozumowaniu opartemu na
logice klasycznej, na mocy warunków 2 i 6 łatwo dowodzi się, że w warunku (EKST)
zamiast „⇒” można wstawić „⇔”. Mamy więc:

Lemat 1.4. Zbiory są identyczne (równe) wtw mają te same elementy, dokładniej: każdy
element pierwszego zbioru jest również elementem drugiego zbioru i na odwrót, czyli każdy
element drugiego zbioru jest również elementem pierwszego zbioru; symbolicznie

A = B wtw (A ⊆ B ∧ B ⊆ A).

A = B ⇔ ∀

(x ∈ A ⇔ x ∈ B)

(EKST

)

Zakaz rozpowszechniania bez zgody autora

Przywołajmy deﬁnicję koniunkcji:

p q p ∧ q
1 1

1 0

0 1

0 0

Oznaczenie 1.5. Jeśli dla danych zbiorów A i B zachodzi A ⊆ B, ale nie zachodzi
B ⊆ A, to piszemy: „A B”.

Posługując się wprowadzonymi postulatami można pokazać, że:

Twierdzenie 1.6. Istnieje dokładnie jeden zbiór pusty.

Dowód. Istotnie, niech zarówno ∅

jak i ∅

ma własność (Własn ∅). Pokażemy, że ∅

∅

. W tym celu należy wykazać, że zachodzi warunek:

dla każdego obiektu x, x jest on elementem ∅

wtw x jest elementem ∅

Ale z deﬁnicji ∅

dla każdego obiektu obie strony równoważności są fałszywe. Zatem

dla każdego obiektu powyższa równoważność ta jest prawdziwa. Dowodzona teza wynika
z (EKST).

Podobnie — tym razem ze względu na fałszywość poprzednika implikacji — uzasad-

niamy, że:

Twierdzenie 1.7.
∅

⊆ A, czyli zbiór pusty jest podzbiorem każdego zbioru.

1.2.3 Aksjomat pary.

Dla dowolnych x i y istnieje zbiór, którego elementami są x oraz y, i nic ponadto.

Należy odróżnić zbiór, którego elementami są dane x i y, od tzw. pary uporządkowanej.
Ten pierwszy zapisuje się jako

{x, y},

zaś w przypadku pary uporządkowanej stosuje się zapis:

hx, yi.

Do pojęcia pary uporządkowanej wrócimy w dalszej części naszych rozważań. Dodajmy,
że w powyższym zapisie x i y mogą być nazwami dowolnych obiektów rozpatrywanego
uniwersum, czyli nazwami zbiorów lub nazwami urelementów.

Przypomnijmy, że wprowadzony powyżej sposób oznaczania pary przyjęto również

stosować dla zapisania nazw zbiorów, które mają skończoną liczbę elementów: ujmujemy
nazwy elementów w klamrowe nawiasy i oddzielamy przecinkami np. {2, -3, 8, 2}.

W tym kontekście wypisanie nazwy obiektu równoznaczne jest zaliczeniem owego

obiektu do elementów zbioru.

Z ekstensjonalności wynika między innymi, że jeśli wypisujemy elementy zbioru skoń-

czonego, to nie ważna jest kolejność ich wymieniania, ani ewentualne powtórzenia.

∗

Zakaz rozpowszechniania bez zgody autora

1.2.4 (Schemat) Aksjomat(u) zastępowania, (podstawiania).

Jeśli ϕ jest predykatem od dwóch zmiennych wolnych

jednoznacznym na X (przyporząd-

kowującym każdemu obiektowi ze zbioru X co najwyżej jeden obiekt), to istnieje zbiór
złożony dokładnie ze wszystkich obiektów przyporządkowywanych przez ϕ elementom
zbioru X.

Symbolicznie

∀

(x ∈ X ∧ ϕ(x, y) ∧ ϕ(x, z) ⇒ y = z) ⇒ ∃

∀

(w ∈ A ⇔ ∃v(ϕ(v, w) ∧ v ∈ X))

∗

1.2.5 Aksjomat wyróżniania (aksjomat podzbiorów).

Dla każdego zbioru A istnieje zbiór B złożony z tych i tylko tych elementów x zbioru A,
które mają pewną ustaloną własność ϕ, czyli dla każdego zbioru A istnieje jego podzbiór
B, taki że B = {x ∈ A : ϕ(x)}.

∗

1.2.6 Aksjomat regularności (ufundowania).

Najpierw wprowadźmy pojęcie zbiorów rozłącznych:

Deﬁnicja 1.8. Dwa zbiory są rozłączne wtw nie mają żadnego elementu wspólnego.

Każdy niepusty zbiór X ma element, który jest rozłączny z samym X.

∗

1.2.7 Aksjomat sumy.

Dla dowolnej rodziny zbiorów R istnieje zbiór U , do którego należą dokładnie te elementy
x, które należą do co najmniej jednego spośród zbiorów, które są elementami rodziny R.

Do sumy zbiorów jeszcze wrócimy.

∗

Dla każdego zbioru X istnieje zbiór potęgowy:

1.2.8 Aksjomat zbioru potęgowego.

Dla każdego zbioru X istnieje zbiór potęgowy oznaczany przez P(X) bądź 2

, którego

elementami są wszystkie podzbiory X i nic ponadto.

∗

Zmienna wolna to taka zmienna, której przynajmniej jedno wystąpienie nie jest związane przez żaden

kwantyﬁkator z tą właśnie zmienną podkwantyﬁkatorową. Predykat, to przykład funktora, czyli wyra-
żenia niesamoistnego, które wraz z pewnymi, bardziej podstawowymi wyrażeniami, tworzy wyrażenie
złożone; w szczególności predykat łączy się z tzw. nazwami a tworzy zdanie, predykatem jest identycz-
ność — “. . . równa się . . . ”.

Zakaz rozpowszechniania bez zgody autora

1.2.9 Aksjomat wyboru.

Dla dowolnej rodziny niepustych zbiorów parami rozłącznych istnieje zbiór, który ma
dokładnie po jednym elemencie wspólnym z każdym spośród zbiorów rzeczonej rodziny.

∗

1.2.10 Aksjomat nieskończoności.

Istnieje zbiór Y , którego elementem jest ∅ oraz dla każdego elementu X zbioru Y istnieje
element X

′

(zbioru Y ) składający się za wszystkich elementów zbioru X oraz samego X

jako elementu.

{∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}} . . . }

Jeśli zbiór pusty zinterpretujemy jako 0, to najmniejszym takim zbiorem jest zbiór

wszystkich liczb naturalnych.

∗

‘Z’, ‘Q’ i ‘R’ oznaczają odpowiednio zbiór wszystkich liczb całkowitych, zbiór wszyst-

kich liczb wymiernych oraz zbiór wszystkich liczb rzeczywistych. Zbiory te można ‘wy-
generować’ w ramach teorii mnogości.

Poniżej zamieszczamy pewne znane fakty, przydatne na ćwiczeniach. Przypomnijmy,

że dla dowolnych m, n ∈ Z:

m|n wtw istnieje k ∈ Z, takie że m · k = n

Czytamy: “m dzieli n” lub “m jest podzielnikiem n”.

Deﬁnicja 1.9. Mówimy, że x

∈ X jest miejscem zerowym funkcji f : X −→ R wtw

f (x

) = 0.

Twierdzenie 1.10. Niech dany będzie wielomian o współczynnikach całkowitych w(x) =
a

+ · · · + a

+ a

, gdzie a

6= 0. Dla dowolnego x, jeśli x ∈ Q i x jest miejscem

zerowym wielomianu w, to istnieją liczby p, q ∈ Z, takie że p|a

, q|a

oraz x =

p
q

Mamy stąd dwa wnioski:

Wniosek 1.11. Niech dany będzie wielomian o współczynnikach całkowitych w(x) =
a

+ · · · + a

+ a

, gdzie a

6= 0. Jeśli dla dowolnych p, q ∈ Z, takich że p|a

, q|a

liczba

p
q

nie jest miejscem zerowym wielomianu w, to nie istnieje pierwiastek wymierny

wielomianu w.

Wniosek 1.12. Niech dany będzie wielomian o współczynnikach całkowitych w(x) =
a

+ · · · + a

+ a

, gdzie a

6= 0. Dla dowolnego x

, jeśli x

∈ Z i x

jest miejscem

zerowym wielomianu w, to x

jest podzielnikiem wyrazu wolnego, czyli a

Przypomnijmy też

Twierdzenie 1.13 (Schemat Hornera). Jeśli dany jest funkcja wielomianowa w(x) =
a

+ · · · + a

+ a

, to wartość w(x

) = x

· (· · · · (x

· (x

· a

+ a

n−

) + a

n−

) . . . ) + a

co można zapisać:

—

n−

. . .

= a

= x

· y

+ a

n−

. . .

= x

· y

n−

+ a

w(x

) = x

· y

+ a

Zakaz rozpowszechniania bez zgody autora

Ćwiczenie 1.14. Wskaż elementy zbiorów:

A = {x ∈ Q : x

− 6x + 5 = 0}

B = {x ∈ Q : x

+ 3x

− 6x + 5 = 0}.

Wyrazem wolnym pierwszego wielomianu jest 5. Jedynymi podzielnikami liczby 5 są:

1, −1, 5, −5.

—

−6

1 · 1 + 0 = 1

1 · 1 + (−6) = −5

1 · (−5) + 5 = 0.

Zatem 1 jest miejscem zerowym rozważanej funkcji. Na mocy twierdzenia B´ezout wielo-
mian nasz jest podzielny przez x − 1. Otrzymane w drugim wierszu liczby znajdujące się
odpowiednio pod współczynnikami wielomianu wyjściowego:

1, 1, 1, −5

są właśnie współczynnikami wielomianu będącego ilorazem wielomianu wyjściowego i
dwumianu x − 1. Mamy więc:

− 6x + 5 = (x

+ x

+ x − 5) · (x − 1)

zatem

− 6x + 5 = 0 wtw (x

+ x

+ x − 5) = 0 lub x − 1 = 0

Procedurę możemy powtórzyć. Znów podzielnikami wyrazu wolnego, czyli liczby −5 są:
1, −1, 5, −5.

—

−5

1 · 1 + 1 = 2

1 · 2 + 1 = 3

1 · 3 + (−5) = −2.

−1

(−1) · 1 + 1 = 0

(−1) · 0 + 1 = 1

(−1) · 1 + (−5) = −6.

5 · 1 + 1 = 6

5 · 6 + 1 = 31

5 · 31 + (−5) = 150.

−5

(−5) · 1 + 1 = −4

(−5) · (−4) + 1 = 21

(−5) · 21 + (−5) = −110.

Widać, że rozpatrywany wielomian nie ma więcej pierwiastków wymiernych. Czyli A =
{1}.

Zakaz rozpowszechniania bez zgody autora

Podstawowe działania na zbiorach

Deﬁnicja 2.1. Sumą zbiorów A, B jest zbiór A ∪ B tych wszystkich elementów, które
należą do zbioru A lub należą do zbioru B.

Przykład 2.2. Sumą zbioru liczb parzystych oraz zbioru wielokrotności liczby 3 jest
zbiór liczb podzielnych przez 2 lub 3.

A ∪ B

Przypomnijmy

Deﬁnicja 2.3. Sumą dowolnej rodziny zbiorów

A jest zbiór

A tych wszystkich obiek-

tów, które należą przynajmniej do jednego zbioru B, takiego że B ∈ A, czyli

x ∈

[

A ⇐⇒ istnieje B ∈ A, takie że x ∈ B

Deﬁnicja 2.4. Przekrojem (inaczej iloczynem (mnogościowym) lub częścią wspólną)
zbiorów A i B jest zbiór A ∩ B tych elementów, które należą zarówno do zbioru A jak
i B.

Przykład 2.5. Przekrojem zbioru rombów i prostokątów jest zbiór kwadratów.

A ∩ B

Podobnie jak w przypadku sumy, także iloczyn zbiorów można uogólnić.

Deﬁnicja 2.6. Przekrojem dowolnej rodziny zbiorów A jest zbiór

A tych wszystkich

elementów, które należą do każdego spośród zbiorów należących do A, czyli

x ∈

A ⇐⇒ dla każdego B ∈ A : x ∈ B

Deﬁnicja 2.7. Różnicą zbiorów A i B jest zbiór A\B tych wszystkich elementów, które
należą do zbioru A i jednocześnie nie należą do zbioru B.

Przykład 2.8. Różnicą zbioru wszystkich prostokątów i zbioru wszystkich rombów jest
zbiór wszystkich prostokątów o dokładnie dwóch osiach symetrii.

A\B

Zgodnie z umową jeśli elementami zbioru są same zbiory, to mówimy o nim „rodzina zbiorów”.

Zakaz rozpowszechniania bez zgody autora

Deﬁnicja 2.9. Dopełnieniem (uzupełnieniem) zbioru A względem ustalonego uniwersum
Ω jest to zbiór A

′

tych elementów, które należą do zbioru Ω i jednocześnie nie należą do

zbioru A (A

′

:= Ω\A).

Przykład 2.10. Dopełnienie zbioru wszystkich drzew iglastych względem uniwersum
wszystkich drzew to zbiór drzew liściastych.

A’

Stosując prawa logiki oraz wprowadzone deﬁnicje dowodzi się, że dla dowolnych zbio-

rów zachodzą następujące równości:

Wybrane własności sumy

(sum. 1) A = A ∪ A

idempotentność

(sum. 2) A ⊆ A ∪ B
(sum. 3) B ⊆ A ∪ B
(sum. 4) A ∪ B = B ∪ A

przemienność

(sum. 5) A ∪ (B ∪ C) = (A ∪ B) ∪ C

łączność

(sum. 6) A ∪ ∅ = A

moduł dodawania

(sum. 7)

A ⊆ B

A ∪ C ⊆ B ∪ C

A ⊆ B

C ∪ A ⊆ C ∪ B

monotoniczność

(sum. 8) A ⊆ B, C ⊆ D

A ∪ C ⊆ B ∪ D

A ⊆ B, C ⊆ B

A ∪ C ⊆ B

monotoniczność

(sum. 9) A ⊆ B wtw A ∪ B = B

Wybrane własności pojęcia przekroju:

(przekr. 1) A = A ∩ A

idempotentność

(przekr. 2) A ∩ B ⊆ A
(przekr. 3) A ∩ B ⊆ B
(przekr. 4) A ∩ B = B ∩ A

przemienność

(przekr. 5) A ∩ (B ∩ C) = (A ∩ B) ∩ C

łączność

(przekr. 6) A ∩ ∅ = ∅

(przekr. 7)

A ⊆ B

A ∩ C ⊆ B ∩ C

A ⊆ B

C ∩ A ⊆ C ∩ B

monotoniczność

(przekr. 8) A ⊆ B, C ⊆ D

A ∩ C ⊆ B ∩ D

A ⊆ B, A ⊆ D

A ⊆ B ∩ D

monotoniczność

(przekr. 9) A ⊆ B wtw A ∩ B = A

Zakaz rozpowszechniania bez zgody autora

Wybrane własności różnicy:

(różn. 1) A\B ⊆ A
(różn. 2) ∅ = A\A
(różn. 3) A = A\∅

(różn. 4)

A ⊆ B

A\C ⊆ B\C

(różn. 5)

A ⊆ B

C\B ⊆ C\A

(różn. 6) A ⊆ B, C ⊆ D

A\D ⊆ B\C

(różn. 7) A ⊆ B wtw A\B = ∅

Wykład 12 marca 2014

Wybrane własności wyrażone za pomocą różnych działań

(psr. 1) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

rozdzielność sumy względem przekroju

(psr. 2) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

rozdzielność przekroju względem sumy

(psr. 3) A ∪ (A ∩ B) = A

absorpcja

(psr. 4) A ∩ (A ∪ B) = A

absorpcja

(psr. 5) A\(B ∩ C) = (A\B) ∪ (A\C)

pierwsze prawo de Morgana

(psr. 6) A\(B ∪ C) = (A\B) ∩ (A\C)

drugie prawo de Morgana

(psr. 7) (A\B)\C = (A\B) ∩ (A\C)
(psr. 8) (A\B)\C = A\(B ∪ C)
(psr. 9) A\(A\B) = (A ∩ B)

(psr. 10) A ∪ (B\A) = A ∪ B
(psr. 11) A ∪ B = B wtw A ∩ B = A

2.1

Uzasadnienia wybranych własności działań na zbiorach

Uzasadnienia własności (sum.1)–(sum.9) podano na wykładzie. Mamy przykładowo:

Ad (sum.4). Pokażemy, że dla dowolnego x, jeśli x ∈ A ∪ B, to x ∈ B ∪ A. Weźmy

dowolne x. Załóżmy, że x ∈ A ∪ B, czyli x ∈ A lub x ∈ B, innymi słowy co najmniej
jedno spośród zdań x ∈ A, x ∈ B jest prawdziwe. Zatem co najmniej jedno ze zdań
x ∈ B, x ∈ A jest prawdziwe. Wobec tego x ∈ B lub x ∈ A, czyli x ∈ B ∪ A. Ponieważ x
było zupełnie dowolne, więc istotnie pokazaliśmy, że A ∪ B ⊆ B ∪ A. Ponieważ zbiory A i
B są dowolne (nie są w żaden sposób wyróżnione), więc otrzymujemy, że B ∪ A ⊆ A ∪ B.
Pokazaliśmy więc równość, gdyż wiemy, na mocy lematu 1.4, że równość dla zbiorów
zachodzi wtw zachodzą obie inkluzje.

Własności (przekr.1)–(przekr.9) — proste ćwiczenie.
Własności (różn.1)–(różn.7) — umówione na wykładzie.
Podajemy uzasadnienia własności ‘psr’:

Dowód.

Ad (psr. 1). „⊆” Weźmy dowolne x.

Zachodzi:
x ∈ A ∪ (B ∩ C) wtw x ∈ A ∨ x ∈ (B ∩ C). Rozważmy dwa przypadki:

◦

. x ∈ A. Ponieważ A ⊆ A ∪ B i A ⊆ A ∪ C, zatem x ∈ A ∪ B ∧ x ∈ A ∪ C, czyli

x ∈ (A ∪ B) ∩ (A ∪ C).

Zakaz rozpowszechniania bez zgody autora

◦

. x ∈ (B ∩ C). Zatem x ∈ B ∧ x ∈ C. Ponieważ B ⊆ A ∪ B i C ⊆ A ∪ C, wobec tego

x ∈ A ∪ B ∧ x ∈ A ∪ C. Czyli x ∈ (A ∪ B) ∩ (A ∪ C).

W każdym z dwóch możliwych przypadków zachodzi x ∈ (A ∪ B) ∩ (A ∪ C), zatem
inkluzja została wykazana.

„⊇” Weźmy dowolne x i załóżmy, że x ∈ (A ∪ B) ∩ (A ∪ C), czyli że x ∈ (A ∪ B) ∧ x ∈

(A ∪ C), stąd mamy: (x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C). Rozważmy pierwszą składową:
(x ∈ A ∨ x ∈ B). Mamy na jej podstawie dwa przypadki:

◦

. x ∈ A. Ponieważ A ⊆ A ∪ (B ∩ C), zatem x ∈ A ∪ (B ∩ C).

◦

. x ∈ B. Znów przeanalizujmy dwa podprzypadki.

a) x ∈ A, to rozumując jak w przypadku 1

◦

otrzymujemy, że x ∈ A ∪ (B ∩ C).

b) x 6∈ A, to z faktu, że x ∈ A ∨ x ∈ C mamy, że x ∈ C. Resumując, w tym

przypadku mamy, że x ∈ B i x ∈ C, równoważnie x ∈ B ∩ C, ponieważ
(B ∩ C) ⊆ A ∪ (B ∩ C), więc x ∈ A ∪ (B ∩ C).

Tak więc w każdym z przypadków mamy: x ∈ A ∪ (B ∩ C).

Dowód można również przeprowadzić w oparciu o wyrażenie p∨(q∧r) ⇔ (p∨q)∧(p∨r),

które daje zdanie prawdziwe dla dowolnych zdań p i q.

To właśnie korzystając z tautologii klasycznej — tym razem z wyrażenia p ∧ (q ∨ r) ⇔

(p ∧ q) ∨ (p ∧ r) — uzasadnimy kolejną własność (patrz drugi sposób).

Ad (psr. 2). I sposób.

(⊆) Weźmy zatem dowolne x i załóżmy, że x ∈ A ∩ (B ∪ C), czyli na mocy deﬁnicji

przekroju x ∈ A i x ∈ (B ∪ C). Z kolei na mocy deﬁnicji sumy, znaczy to, że x ∈ B lub
x ∈ C. Rozważymy dwa przypadki. W każdym z nich można korzystać z informacji, że
x ∈ A.
1

◦

. x ∈ B. Mamy stąd kolejno:

x ∈ A i x ∈ B — przywołaliśmy informa-
cję, że x ∈ A
x ∈ A ∩ B — na mocy deﬁnicji przekroju
x ∈ A∩B lub x ∈ A∩C — jest to prawda,
gdyż samo stwierdzenie, że x ∈ A∩B jest
prawdziwe.

◦

. x ∈ C. Mamy stąd kolejno:

x ∈ A i x ∈ C — przywołaliśmy informa-
cję, że x ∈ A
x ∈ A ∩ C — na mocy deﬁnicji przekroju
x ∈ A∩B lub x ∈ A∩C — jest to prawda,
gdyż samo stwierdzenie, że jest x ∈ A∩C
prawdziwe.

}

x ∈ (A ∩ B) ∪ (A ∩ C) — w obu przypadkach na mocy deﬁnicji działania sumy.

(⊇) Pokażemy, że dla dowolnego x, jeśli x ∈ (A ∩ B) ∪ (A ∩ C), to x ∈ A ∩ (B ∪ C)
Weźmy więc dowolne x i załóżmy, że x ∈ (A ∩ B) ∪ (A ∩ C), czyli x ∈ (A ∩ B) lub

x ∈ (A ∩ C), Rozważmy dwa przypadki:

◦

. x ∈ (A ∩ B)

x ∈ A i x ∈ B — z deﬁnicji przekroju
x ∈ B — wobec powyższego
x ∈ B lub x ∈ C — skoro x ∈ B

◦

. x ∈ (A ∩ C)

x ∈ A i x ∈ C — z deﬁnicji przekroju
x ∈ C — z powyższego
x ∈ B lub x ∈ C — skoro x ∈ C

}

x ∈ B ∪ C — na mocy deﬁnicji sumy

x ∈ A i x ∈ B ∪ C — w obu przypadkach powołujemy się na fakt, że x ∈ A

x ∈ A ∩ (B ∪ C) — z powyższej obserwacji i deﬁnicji przykroju

Zakaz rozpowszechniania bez zgody autora

II sposób. Weźmy dowolne x.
Zachodzi:
x ∈ A ∩ (B ∪ C) wtw x ∈ A ∧ x ∈ (B ∪ C) wtw x ∈ A ∧ (x ∈ B ∨ x ∈ C) wtw [ze

względu na ogólnie prawdziwe wyrażenie p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)] (x ∈ A ∧ x ∈
B) ∨ (x ∈ A ∧ x ∈ C) wtw (x ∈ A ∩ B) ∨ (x ∈ A ∩ C) wtw x ∈ (A ∩ B) ∪ (A ∩ C).

Ad (psr. 3). Mamy, że A ⊆ A oraz A ∩ B ⊆ A (własność (przekr. 2) ze strony 11).

Stąd mamy na mocy własności (sum. 8) otrzymujemy, że A ∪ (A ∩ B) ⊆ A ∪ A, czyli

ze względu na przechodniość inkluzji inkl. 2 i własność sum. 1 mamy, że A ∪ (A ∩ B) ⊆ A.
Inkluzja odwrotna jest oczywista na mocy sum. 2.

Ad (psr. 4). Na mocy własności (przekr. 2) zachodzi inkluzja A ∩ (A ∪ B) ⊆ A.

Dla wykazania inkluzji odwrotnej zauważmy, że A ⊆ A oraz A ⊆ (A ∪ B) (wła-

sność sum. 2 ze strony 11). Stąd na mocy warunku monotoniczności (przekr. 8) mamy
poszukiwaną inkluzję: A ⊆ A ∩ (A ∪ B).

Ad (psr. 5). Weźmy dowolne x.

Mamy:
x ∈ A\(B ∩ C) wtw x ∈ A ∧ ∼ x ∈ (B ∩ C) wtw x ∈ A ∧ ∼(x ∈ B ∧ x ∈ C) wtw [ze

względu na ogólnie prawdziwe wyrażenie ∼(p∧q) ⇔ ∼ p∨∼ q] x ∈ A∧(∼ x ∈ B∨∼ x ∈ C)
wtw [ze względu na tautologiczność wyrażenia p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)]

(x ∈ A ∧ ∼ x ∈ B) ∨ (x ∈ A ∧ ∼ x ∈ C) wtw (x ∈ A ∧ x 6∈ B) ∨ (x ∈ A ∧ x 6∈ C) wtw

x ∈ (A\B) ∨ x ∈ (A\C) wtw x ∈ (A\B) ∪ (A\C).

Ad (psr. 6). Weźmy dowolne x.

Zachodzi:
x ∈ A\(B ∪ C) wtw x ∈ A ∧ ∼ x ∈ (B ∪ C) wtw x ∈ A ∧ ∼(x ∈ B ∨ x ∈ C) wtw [ze

względu na ogólnie prawdziwe wyrażenie ∼(p∨q) ⇔ ∼ p∧∼ q] x ∈ A∧(∼ x ∈ B∧∼ x ∈ C)
wtw [dołączenie prawdziwego czynnika] x ∈ A ∧ (∼ x ∈ B ∧ x ∈ A ∧ ∼ x ∈ C) wtw [ze
względu na możliwość innego ustawienia nawiasów — tzw. łączność] (x ∈ A ∧ ∼ x ∈
B) ∧ (x ∈ A ∧ ∼ x ∈ C) wtw x ∈ (A\B) ∧ x ∈ (A\C) wtw x ∈ (A\B) ∩ (A\C).

Ad (psr. 8). Weźmy dowolne x; mamy:

x ∈ (A\B)\C wtw x ∈ (A\B) ∧ x 6∈ C wtw x ∈ A ∧ x 6∈ B ∧ x 6∈ C wtw x ∈ A ∧ ∼ x ∈

B ∧ ∼ x ∈ C wtw [z uwagi na fakt, że wyrażenie ∼ p ∧ ∼ q ⇔ ∼(p ∨ q) jest prawdziwe
dla dowolnych zdań p i q] x ∈ A ∧ ∼(x ∈ B ∨ x ∈ C) wtw x ∈ A ∧ ∼ x ∈ (B ∪ C) wtw
x ∈ A\(B ∪ C)

Ad (psr. 9). Weźmy dowolne x; mamy:

x ∈ A\(A\B) wtw x ∈ A ∧ x 6∈ (A\B) wtw x ∈ A ∧ ∼ x ∈ (A\B) wtw x ∈ A ∧ ∼(x ∈

A ∧ x 6∈ B) wtw [z uwagi na fakt, że wyrażenie ∼(p ∧ ∼ q) ⇔ (∼ p ∨ q) jest prawdziwe
dla dowolnych zdań p i q] x ∈ A ∧ (x 6∈ A ∨ x ∈ B) wtw [z uwagi na fakt, że wyrażenie
(p ∧ (∼ p ∨ q)) ⇔ (p ∧ q) jest prawdziwe dla dowolnych zdań p i q] x ∈ A ∧ x ∈ B wtw
x ∈ A ∩ B.

Jako podsumowanie rozważmy jeszcze przypadek (psr 10):

Ad (psr 10). Pokazujemy inkluzję ‘z lewej do prawej’. Na mocy (różn. 1) mamy, że B\A ⊆

B, ponadto A ⊆ A, zatem dzięki (sum.8) otrzymujemy, że A ∪ (B\A) ⊆ A ∪ B.

Dla dowodu inkluzji odwrotnej rozpatrzmy dowolne x i załóżmy, że x ∈ A ∪ B.

Rozważmy dwa przypadki:

◦

. x ∈ A. Ale wówczas z uwagi na fakt (sum. 2) mamy, że A ⊆ A ∪ (B\A), stąd zaś

x ∈ A ∪ (B\A.

◦

. x 6∈ A. Skoro jednak x ∈ A ∪ B, więc x ∈ B. Reasumując, x ∈ B i x 6∈ A, czyli na

mocy deﬁnicji 2.7 wnioskujemy, że x ∈ B \ A, a przez własność (sum. 3) otrzymujemy,

Zakaz rozpowszechniania bez zgody autora

iż x ∈ A ∪ (B\A.

Ponieważ dla dowolnego x musi zajść albo przypadek 1.

◦

albo 2.

◦

, więc x ∈ A∪(B\A.

Ad (psr 11). Wynika z (sum. 9) i (przekr. 9).

Przypomnijmy ogólną metodą sprawdzania tautologiczności wyrażenia zdaniowego

(tzw. formuły). Rozważamy wszystkie wyrażenia składowe (począwszy od zmiennych)
i umieszczamy je w nagłówkach kolumn. W wierszach zapisujemy wszystkie kombina-
cje wartości logicznych jakie mogą sie zdarzyć dla zmiennych występujących w danym
wyrażeniu. Owych kombinacji jest 2

, dla n zmiennych.

p q r q ∨ r p ∧ q p ∧ r p ∧ (q ∨ r) (p ∧ q) ∨ (p ∧ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
1 1 1

1 1 0

1 0 1

1 0 0

0 1 1

0 1 0

0 0 1

0 0 0

Wybrane własności dopełnienia względem ustalonego uniwersum Ω; dla dowolnych

A i B będących podzbiorami Ω:

dopełn. 1. Ω

′

= ∅

dopełn. 2. ∅

′

= Ω

dopełn. 3. A

′′

= A

odp. prawo podwójnego przeczenia

dopełn. 4. (A ∩ B)

′

= A

′

∪ B

′

pierwsze prawo de Morgana

dopełn. 5. (A ∪ B)

′

= A

′

∩ B

′

drugie prawo de Morgana

dopełn. 6. A ∪ A

′

= Ω

odp. prawa wyłączonego środka

dopełn. 7. A ∩ A

′

= ∅

odp. prawa sprzeczności

dopełn. 8.

A ⊆ B

′

⊆ A

′

kontrapozycja

dopełn. 9. A\B = A ∩ B

′

dopełn. 10. A ⊆ B wtw A ∩ B

′

= ∅

Dowód.

Ad (dopełn. 1). Należy wykazać, że Ω\Ω = ∅ a to jest szczególnym przypadkiem warunku

różn. 2.

Ad (dopełn. 2). Wystarczy wykazać, że Ω = Ω\∅ a to jest szczególnym przypadkiem

warunku różn. 3.

Ad (dopełn. 3). Mamy A

′′

= Ω\A

′

= Ω\(Ω\A). Na mocy warunku psr. 9 zachodzi rów-

ność Ω\(Ω\A) = Ω ∩ A. Z kolei stosując (przekr. 4) i (przekr. 9) otrzymujemy: A ∩ Ω =
Ω ∩ A = A, gdyż A ⊆ Ω.

Ad (dopełn. 4). Wynika wprost z psr. 5.
Ad (dopełn. 5). Wynika wprost z psr. 6.

Zakaz rozpowszechniania bez zgody autora

Ad (dopełn. 6). Mamy A ⊆ Ω — z założenia oraz Ω\A ⊆ Ω — na mocy różn. 1. Stąd przez

monotoniczność i idempotentość sumy uzyskujemy inkluzję z lewej do prawej.

Dla wykazania inkluzji odwrotnej wystarczy zauważyć, że jeśli x ∈ Ω, to zachodzą

dwie możliwości: albo x ∈ A albo x 6∈ A. W pierwszym przypadku x ∈ A ∪ (Ω\A), zaś w
drugim x ∈ Ω\A, czyli znów x ∈ (A ∪ Ω\A).

Ad (dopełn. 7). Inkluzja z prawej do lewej jest prawdziwa na mocy twierdzenia 1.7.

Weźmy dowolne x. Mamy wykazać, że zachodzi implikacja

x ∈ A ∩ A

′

⇒ x ∈ ∅.

Ale warunek x ∈ A ∩ A

′

ze względy na fakt, że A ⊆ Ω jest równoważny temu, że

x ∈ A ∧ x ∈ Ω ∧ ∼ x ∈ A a zdanie to jest fałszywe dla dowolnych x i A.

Ad (dopełn. 8). Wynika wprost z (różn. 5).
Ad (dopełn. 9). Wynika z faktu, że A ⊆ Ω. Istotnie jeśli x ∈ A\B, czyli równoważnie

x ∈ A ∧ x 6∈ B, to skoro A ⊆ Ω, zatem x ∈ A ∧ x ∈ Ω ∧ x 6∈ B, stąd zaś mamy:
x ∈ A ∧ x ∈ Ω\B tj. x ∈ A ∧ x ∈ B

′

, innymi słowy x ∈ A ∩ B

′

. Inkluzję odwrotną

dowodzimy postępując w powyższej dedukcji od końca, wystarczy przy tym zauważyć,
ze jeśli x ∈ A ∧ x ∈ Ω ∧ x 6∈ B, to przez pominięcie informacji ‘x ∈ Ω’ dostaniemy
prawdziwe stwierdzenie: x ∈ A ∧ x 6∈ B.

Ad (dopełn. 10). Wynika wprost z własności (różn.7) i (dopełn.9).

Wykazując prawdziwość przytoczonych warunków można też posłużyć się podanymi

uprzednio ilustracjami graﬁcznymi (diagramami Venna).

Zakaz rozpowszechniania bez zgody autora

Zaprezentujemy metodę diagramów Venna na przykładzie wybranych równości. Wy-

kazując ich prawdziwość zawsze rozpatrujemy najbardziej ogólną sytuację jaka może się
zdarzyć, jeśli chodzi o wzajemne odniesienia zbiorów występujących po obu stronach
równości. W przypadku dwóch zbiorów wyjściowy diagram wygląda następująco:

Zakaz rozpowszechniania bez zgody autora

Zaprezentujemy metodę diagramów Venna na przykładzie wybranych równości. Wy-

Zakaz rozpowszechniania bez zgody autora

Zaprezentujemy metodę diagramów Venna na przykładzie wybranych równości. Wy-

Rozważmy

A\(A\B) = A ∩ B

Zakaz rozpowszechniania bez zgody autora

Przedstawmy na diagramie obie strony równości: A\(A\B) = A ∩ B

Zakaz rozpowszechniania bez zgody autora

Najpierw przedstawmy A\(A\B), zaczynamy od wskazania zbioru w nawiasie (A\B).

Zakaz rozpowszechniania bez zgody autora

Teraz możemy przedstawić lewą stronę równości: A\(A\B)

Zakaz rozpowszechniania bez zgody autora

Przedstawmy na diagramie prawą stronę równości, czyli A ∩ B

Zakaz rozpowszechniania bez zgody autora

Przez porównanie obu diagramów widzimy, że równość zachodzi.

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

W przypadku trzech zbiorów rozpatrujemy następujący diagram:

Zakaz rozpowszechniania bez zgody autora

Rozważmy równość A\(B ∩ C) = (A\B) ∪ (A\C).

Zakaz rozpowszechniania bez zgody autora

Zaczynamy od zbioru w nawiasie po lewej stronie równości.

Zakaz rozpowszechniania bez zgody autora

Zbiór występujący po lewej stronie, czyli A\(B ∩ C):

Zakaz rozpowszechniania bez zgody autora

Przedstawiamy zbiór z pierwszego nawiasu (A\B).

Zakaz rozpowszechniania bez zgody autora

Przedstawiamy zbiór z pierwszego nawiasu (A\C).

Zakaz rozpowszechniania bez zgody autora

Suma zbiorów w nawiasach (A\B) ∪ (A\C).

Zakaz rozpowszechniania bez zgody autora

Równość A\(B ∩ C) = (A\B) ∪ (A\C) zachodzi.

Zakaz rozpowszechniania bez zgody autora

19.03.2014

Relacje i funkcje

3.1

Para uporządkowana

Jednym z podstawowych pojęć teorii mnogości jest para uporządkowana. W jej przy-
padku istotna jest kolejność wyrazów (w odróżnieniu do zbioru dwuelementowego, w
którym porządek wypisywania elementów nie ma znaczenia). Warunek istotności kolej-
ności spełnia następująca konstrukcja pary uporządkowanej o wyrazach a i b (ozn. ha, bi):
{{a}, {a, b}}. Obiekty a oraz b zwiemy wyrazami pary uporządkowanej ha, bi. Pierwszy
wyraz pary nazywany jest niekiedy poprzednikiem zaś drugi następnikiem pary.

Mamy następujący:

Lemat 3.1. Dla dowolnych a, b, c, d zachodzi:

ha, bi = hc, di wtw a = c ∧ b = d

Dowód. Implikacja ‘z prawej do lewej’ jest oczywista. Istotnie, jeśli a = c ∧ b = d, to
na mocy ekstensjonalności mamy: {a} = {c} oraz {a, b} = {c, d}, czyli {{a}, {a, b}} =
{{c}, {c, d}}, zatem ha, bi = hc, di.

Dla wykazania implikacji ‘z lewej do prawej’ załóżmy, że ha, bi = hc, di, czyli że

{{a}, {a, b}} = {{c}, {c, d}},

i rozpatrzmy dwa przypadki:

◦

a = b. Mamy, co następuje:
ha, bi = {{a}, {a, b}} = {{a}, {a, a}} = {{a}, {a}} = {{a}} = {{c}, {c, d}}. Stąd
zaś mamy na mocy własności równości, że {c} ∈ {{a}} oraz {c, d} ∈ {{a}}, czyli
{c} = {a} oraz {c, d} = {a} a to znaczy, że c = a, c ∈ {a} i d ∈ {a}, innymi słowy
a = c i d = a, skąd na mocy założenia, że a = b wnosimy, iż b = a = c = d.

◦

a 6= b. Stąd mamy, że {a} 6= {a, b}. Zauważmy, że gdyby {c} = {a, b}, mielibyśmy,
że a ∈ {c} i b ∈ {c}, co znaczyłoby, że a = c = b, wbrew założeniu o a i b. Zatem
{c} 6= {a, b}, wobec założenia wyjściowego mamy, że {a} = {c} oraz {a, b} = {c, d}.
Z pierwszej równości natychmiast otrzymujemy, że a = c. Gdyby b 6= d, to skoro
{a, b} = {c, d}, otrzymujemy, że b ∈ {c, d}, czyli b = c, ale wobec ustalenia, że
a = c, mielibyśmy, że b = c = a, znów otrzymując sprzeczność z założeniem o a i
b. Zatem b = d.

Odnotujmy (uzasadnienie na wykładzie)

Fakt 3.2. Dla dowolnych a, b należących do uniwersum rozważań, para ha, bi jest dobrze
określonym zbiorem, innymi słowy jej istnienie jest zagwarantowane przez aksjomaty
teorii mnogości.

3.2

Iloczyn kartezjański

Korzystając z wprowadzonej deﬁnicji określimy iloczyn kartezjański (inaczej produkt kar-
tezjański lub w skrócie produkt) dwóch zbiorów:

Zakaz rozpowszechniania bez zgody autora

Deﬁnicja 3.3. Iloczynem kartezjańskim zbiorów A i B (ozn. A × B) nazywamy zbiór
wszystkich par uporządkowanych ha, bi, gdzie a ∈ A oraz b ∈ B; czyli

x ∈ A × B wtw

x = ha, bi, gdzie a ∈ A ∧ b ∈ B

Fakt 3.4. A × B jest dobrze określonym zbiorem, innymi słowy jego istnienie jest za-
gwarantowane przez aksjomaty teorii mnogości.

3.3

Relacje dwuargumentowe (binarne) i n-argumentowe

Deﬁnicja 3.5. Relacją dwuargumentową (binarną, dwuczłonową) R określoną na zbiorze
A o wartościach w B (inaczej: relacją dwuczłonową w produkcie A × B) nazywamy każdy
podzbiór produktu A×B. Jeśli para uporządkowana ha, bi ∈ R, to mówimy, że a pozostaje
(lub „ jest”) w relacji R do b i zapisujemy aRb. Jeśli R ⊆ A × A, to mówimy, że R jest
określana „na” lub „w” (zbiorze) A.

Analogicznie można zdeﬁniować relację n−argumentową, przy czym należy się po-

służyć pojęciem produktu rodziny zbiorów {A

, . . . , A

} (produktu zbiorów A

, . . . , A

Wystarczy w tym celu rozpatrzeć n-ki uporządkowane. Deﬁniujemy je indukcyjnie za
pomocą poznanego już pojęcia pary uporządkowanej:

, . . . , a

i := hha

, . . . a

n−

i, a

i, gdzie n  3 oraz a

∈ A

, dla każdego 1 ¬ i ¬ n.

Deﬁnicja 3.6. Dla dowolnego n > 2, produktem n zbiorów A

, . . . , A

nazywamy zbiór:

× · · · × A

= {ha

, . . . , a

i : a

∈ A

, dla każdego 1 ¬ i ¬ n.}

Deﬁnicja 3.7. Dla dowolnego n > 2, n−tą potęgą kartezjańską zbioru A (ozn. A

) jest

zbiór A × · · · × A

}

Deﬁnicja 3.8.

1. Relacją n−argumentową w produkcie A

× · · · × A

nazywamy

każdy podzbiór zbioru A

× · · · × A

2. Relacją n−argumentową w zbiorze A nazywamy każdy podzbiór zbioru A

Czasami przyjmuje się, że A

= A i w takim ujęciu zbiór A jest swoją pierwszą potęgą

kartezjańską a każdy podzbiór zbioru A jest relacją 1-argumentową (1-członową).

Wybiegając nieco w przód dodajmy, że rozpatruje się też produkty nieskończonej

liczby zbiorów {A

}

i∈I

, które można wyobrażać sobie — jeśli zbiór I można ‘policzyć’

liczbami naturalnymi — jako zbiory ciągów nieskończonych o wyrazach należących do
poszczególnych zbiorów

. Formalnie elementami takiego produktu są funkcje (zob. def.

3.13, na s. 40) postaci f : I −→

i∈I

, przy czym f (i) ∈ A

dla każdego i ∈ I.

Deﬁnicja 3.9.

• Relacją diagonalną (identycznościową) na danym zbiorze A nazy-

wamy relację: ∆

= {ha, ai; a ∈ A}

• Relacją pełną na (w) danym zbiorze A nazywamy relację: A

= {ha, bi; a, b ∈ A}

Deﬁnicja 3.10. Niech R ⊆ A × B. Podzbiór zbioru A złożony z elementów, które są
w relacji R do pewnego elementu należącego do B, nazywamy dziedziną R (ozn. D(R)).
Podzbiór zbioru B złożony z tych elementów b, dla których istnieje element a zbioru A,
będący w relacji R do b, nazywamy zbiorem wartości relacji

R (ozn. D

∗

(R))

Niestety ta metafora ‘nie działa’ gdy rodzina nie da się przeliczyć liczbami naturalnymi.

Często zbiór wartości relacji zwany jest przeciwdziedziną.

Za: Onyszkiewicz, Elementy logiki i teorii mnogości w zadaniach.

Zakaz rozpowszechniania bez zgody autora

Deﬁnicja 3.11. Złożeniem relacji R ⊆ A×B i S ⊆ B×C jest relacja będąca podzbiorem
A × C oznaczana R ◦ S, przy czym dla dowolnych a ∈ A oraz c ∈ C:

aR ◦ Sc

def.

⇐⇒ ∃

(aRb ∧ bSc).

Deﬁnicja 3.12. Konwersem (relacją odwrotną do) relacji R ⊆ A × B jest relacja R

−

⊆

B × A, przy czym dla dowolnych a ∈ A oraz b ∈ B:

−

def.

⇐⇒ aRb.

Deﬁnicja 3.13.

1. Relację dwuczłonową f (określoną) w produkcie A×B nazywamy

funkcją

określoną na zbiorze A o wartościach w B (ozn. f : A −→ B) wtw każdy

element zbioru A jest w relacji f do dokładnie jednego elementu zbioru B. Zbiór
A jest dziedziną, jego elementy — argumentami, zaś zbiorem wartości funkcji f jest
zbiór tych elementów b zbioru B, dla których istnieje element a ∈ A, taki że af b.

2. Niech relacja f ⊆ A × B będzie funkcją, a ∈ A oraz a pozostaje w relacji f do

b ∈ B. Element b nazywamy wartością funkcji f od (inaczej: ‘dla’) argumentu a
(jeszcze inaczej: wartością funkcji na argumencie a) i oznaczamy go: ‘f (a)’.

Do pojęcia funkcji będziemy wracać wielokrotnie.

3.4

Diagramy relacji

Relację można przedstawić na kilka sposobów.

Niech dany będzie zbiór A = {1, 2, 3, 4}. Rozpatrzmy relację R ⊆ A

określoną na-

stępująco:

R = {h1, 2i, h1, 3i, h2, 4i, h2, 2i}

Możemy przedstawić ją w tabeli:

R 1

× ×

3
4

bądź za pomocą diagramów stosowanych czasami dla zobrazowania funkcji (Rysunek 1).

Rysunek 1.

Inaczej: relacją jednoznaczną.

Jeśli b jest wartością funkcji f od argumentu a, to piszemy f (a) = b. Oczywiście gdyby nie był

spełniony warunek jedyności, nie moglibyśmy stosować znaku „=”, gdyż na ogół do jednego elementu a
może pozostawać w relacji wiele wartości.

Zakaz rozpowszechniania bez zgody autora

Czy też stosując diagramy (patrz Rysunek 2) nawiązujące do tzw. diagramów Hasse-

go, stosowanych w teorii tzw. posetów, czyli zbiorów częściowo-uporządkowanych (patrz
sekcja 5 and stronie 59).

Rysunek 2.

Deﬁnicja 3.14. Niech dany będzie produkt A

× · · · × A

n zbiorów A

, . . . , A

. i-tą

dziedziną relacji R w produkcie A

× · · · × A

nazywamy zbiór :

(R) = {a ∈ A

: istnieją a

∈ A

, . . . , a

i−

∈ A

i−

, a

∈ A

, a

∈ A

, takie że

, . . . , a

i−

, a, a

, . . . , a

i ∈ R}.

Uwaga 3.15. W przypadku relacji binarnych dziedzina jest tożsama z pierwszą dziedzi-
ną, zaś zbiór wartości — z drugą.

Deﬁnicja 3.16. Niech R ⊆ A × B.

1. Polem relacji R nazywamy sumę dziedziny i zbioru wartości relacji R.
2. R

′

= (A × B)\R.

Wykład 26 marca 2014

3.5

Wybrane własności wprowadzonych działań

Twierdzenie 3.17. (produkt. 1) ∅ × A = ∅ = A × ∅

(produkt. 2) A ⊆ B, C ⊆ D

A × C ⊆ B × D

monotoniczność

(produkt. 3)

A ⊆ B

A × C ⊆ B × C

A ⊆ B

C × A ⊆ C × B

monotoniczność

(produkt. 4) A × (B ∪ C) = (A × B) ∪ (A × C)
(produkt. 5) (B ∪ C) × A = (B × A) ∪ (C × A)
(produkt. 6) (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D)
(produkt. 7) Jeśli (C ⊆ A ∨ B ⊆ D) i (D ⊆ B ∨ A ⊆ C),

to (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D)

(produkt. 8) (A ∪ C) × (B ∪ D) = (A × B) ∪ (A × D) ∪ (C × B) ∪ (C × D)

(produkt. 9) A × (B ∩ C) = (A × B) ∩ (A × C)

(produkt. 10) (B ∩ C) × A = (B × A) ∩ (C × A)
(produkt. 11) (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D)
(produkt. 12) A × (B\C) = (A × B)\(A × C)
(produkt. 13) (B\C) × A = (B × A)\(C × A)

Dopełnienie relacji można również deﬁniować względem pola relacji.

Ze względu na łączność alternatywy pomijamy nawiasy.

Zakaz rozpowszechniania bez zgody autora

Dowód. Ad. (produkt. 1). Oczywiste, gdyż gdyby ha, ci ∈ ∅ × A, to a ∈ ∅.

Ad. (produkt. 2). Załóżmy, że A ⊆ B, C ⊆ D. Weźmy dowolne x i załóżmy, że

x ∈ A × C, czyli istnieją a ∈ A i c ∈ C, takie że x = ha, ci, ale A ⊆ B i C ⊆ D, zatem
a ∈ B i c ∈ D, innymi słowy x = ha, ci ∈ B × D.

Ad. (produkt. 3) — wynikają z bardziej ogólnego (produkt. 2).
Ad. (produkt. 4). Weźmy dowolne x. Zachodzą następujące równoważności: x ∈ A ×

(B ∪ C) wtw x = ha, bi, dla a ∈ A oraz b ∈ B ∪ C wtw x = ha, bi, a ∈ A ∧ (b ∈ B ∨ b ∈ C)
wtw [ze względu na ogólnie prawdziwe wyrażenie p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)] x = ha, bi,
(a ∈ A∧b ∈ B)∨(a ∈ A∧b ∈ C) wtw x ∈ (A×B)∨x ∈ (A×C) wtw x ∈ (A×B)∪(A×C).

Ad. (produkt. 5) — analogicznie do dowodu (produkt. 4).
Ad. (produkt. 6). Weźmy dowolne x i załóżmy, że x ∈ (A × B) ∪ (C × D), czyli że

x ∈ (A × B) ∨ x ∈ (C × D).

◦

. Jeśli x ∈ (A × B), to x = ha, bi dla pewnych a ∈ A i b ∈ B. Ponieważ A ⊆ A ∪ C

i B ⊆ B ∪ D, zatem a ∈ A ∪ C i b ∈ B ∪ D. Stąd x = ha, bi ∈ (A ∪ C) × (B ∪ D).

◦

. Jeśli teraz x ∈ (C × D), to x = hc, di dla pewnych c ∈ C i d ∈ D. Ponieważ

C ⊆ A∪C i D ⊆ B ∪D, zatem c ∈ A∪C i d ∈ B ∪D. Stąd x = hc, di ∈ (A∪C)×(B ∪D).

Ad. (produkt. 7). Wobec (produkt. 6) wystarczy przyjąwszy założenie, udowodnić

inkluzję z prawej do lewej.

Weźmy więc dowolne x i załóżmy, że x ∈ (A ∪ C) × (B ∪ D), czyli x = ha, bi, gdzie

a ∈ A ∪ C oraz b ∈ B ∪ D. Zatem (a ∈ A ∨ a ∈ C) oraz (b ∈ B ∨ b ∈ D).

◦

. a ∈ A. Ze względu na drugą alternatywę mamy dwie możliwości:

a) b ∈ B, czyli x = ha, bi ∈ A × B ⊆ (A × B) ∪ (C × D).

b) b ∈ D. Ze względu na założenie, że D ⊆ B lub A ⊆ C mamy że, albo D ⊆ B i

wtedy b ∈ B i powtarzamy rozumowanie z p. a), albo A ⊆ C, czyli, że a ∈ C i
wtedy otrzymujemy, że x = ha, bi ∈ (C × D) ⊆ (A × B) ∪ (C × D).

◦

. a ∈ C. Znów rozpatrując drugą alternatywę mamy dwa przypadki:

a) b ∈ B. Ze względu na założenie, że C ⊆ A lub B ⊆ D mamy że, albo C ⊆ A i

wtedy a ∈ A i otrzymujemy, że x = ha, bi ∈ A×B ⊆ (A×B)∪(C ×D) albo B ⊆ D,
czyli, że b ∈ D i wtedy otrzymujemy, że x = ha, bi ∈ C × D ⊆ (A × B) ∪ (C × D).

b) b ∈ D, czyli x = ha, bi ∈ (C × D) ⊆ (A × B) ∪ (C × D).

Ad. (produkt. 8). Wobec 6 mamy, że

(A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D)

(A × D) ∪ (C × B) ⊆ (A ∪ C) × (D ∪ B),

ale ponieważ (B ∪ D) = (D ∪ B), zatem (A × D) ∪ (C × B) ⊆ (A ∪ C) × (B ∪ D), stąd
przez monotoniczność (sum. 8) mamy, iż (A × B) ∪ (C × D) ∪ (A × D) ∪ (C × B) ⊆
(A ∪ C) × (B ∪ D). Pozostaje do wykazania inkluzja z lewej do prawej. Jednak łatwo
widać, że jeśli ha, bi ∈ (A ∪ C) × (B ∪ D), to (a ∈ A ∨ a ∈ C) oraz (a ∈ B ∨ a ∈ D), czyli
zachodzi jedna z czterech poniższych możliwości:

a) a ∈ A ∧ b ∈ B, czyli ha, bi ∈ (A × B)

b) a ∈ A ∧ b ∈ D, czyli ha, bi ∈ (A × D)

c) a ∈ C ∧ b ∈ B, czyli ha, bi ∈ (C × B)

d) a ∈ C ∧ b ∈ D, czyli ha, bi ∈ (C × D).

Zakaz rozpowszechniania bez zgody autora

Ale każdy z ww. zbiorów zawiera się w (A × B) ∪ (A × D) ∪ (C × B) ∪ (C × D).

Ad. (produkt. 9). Weźmy dowolne x. Zachodzą następujące równoważności: x ∈ A ×

(B ∩ C) wtw x = ha, bi, dla a ∈ A oraz b ∈ B ∩ C wtw x = ha, bi, a ∈ A ∧ (b ∈ B ∧ b ∈ C)
wtw [ze względu na ogólnie prawdziwe wyrażenie p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ (p ∧ r)] x = ha, bi,
(a ∈ A∧b ∈ B)∧(a ∈ A∧b ∈ C) wtw x ∈ (A×B)∧x ∈ (A×C) wtw x ∈ (A×B)∩(A×C).

Ad. (produkt. 10) — analogicznie do uzasadnienia (produkt. 9).
Ad. (produkt. 11). Weźmy dowolne x. Zachodzą następujące równoważności: x ∈

(A ∩ B) × (C ∩ D) wtw x = ha, bi, dla a ∈ (A ∩ B) oraz b ∈ C ∩ D wtw x = ha, bi,
(a ∈ A ∧ a ∈ B) ∧ (b ∈ C ∧ b ∈ D) wtw [ze względu na ogólnie prawdziwe wyrażenie
(p ∧ q) ∧ (r ∧ s) ⇔ (p ∧ r) ∧ (q ∧ s)] x = ha, bi, (a ∈ A ∧ b ∈ C) ∧ (a ∈ B ∧ b ∈ D) wtw
x ∈ (A × C) ∧ x ∈ (B × D) wtw x ∈ (A × C) ∩ (B × D).

Ad. (produkt. 12). Weźmy dowolne x. Zachodzą następujące równoważności: x ∈

A × (B\C) wtw x = ha, bi, dla a ∈ A oraz b ∈ B\C wtw x = ha, bi, gdzie a ∈ A ∧ (b ∈
B ∧ b 6∈ C) wtw [ze względu na ogólnie prawdziwe wyrażenie p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ (p ∧ r)]
x = ha, bi, (a ∈ A ∧ b ∈ B) ∧ (a ∈ A ∧ b 6∈ C). Z ostatniego stwierdzenia wynika, że
x ∈ (A × B) ∧ x 6∈ (A × C), istotnie gdyby x ∈ (A × C), to skoro x = ha, bi, mielibyśmy
b ∈ C — sprzeczność. W drugą stronę jeśli x ∈ (A × B) ∧ x 6∈ (A × C), to x = ha, bi, dla
pewnych (a ∈ A ∧ b ∈ B), takich że ∼(a ∈ A ∧ b ∈ C). Skoro jednak a ∈ A, zatem b 6∈ C
(gdyby b ∈ C, to mielibyśmy, że a ∈ A ∧ b ∈ C wbrew ustaleniu). Reasumując a ∈ A
oraz b ∈ B\C, czyli x ∈ A × (B\C).

Ad. (produkt. 13) — analogicznie do (produkt. 12).

Wykład 2 kwietnia 2014

Dla R ⊆ (A × B) mamy, że R

−

⊆ (B × A), zatem w kontekście (zł-odw. 10) —

poniżej, przyjmujemy, że (R

−

)

′

= (B × A)\R

−

Twierdzenie 3.18. Niech dane będą relacje: Q, R ⊆ A×B, S, V ⊆ B×C i T, U ⊆ C×D,
wówczas

(zł-odw. 1) ∅ ◦ R = ∅ = R ◦ ∅
(zł-odw. 2) ∆

◦ R = R

(zł-odw. 3) R ◦ ∆

= R

(zł-odw. 4) ((R ◦ S) ◦ T ) = (R ◦ (S ◦ T ))
(zł-odw. 5) (R ◦ S)

−

= S

−

◦ R

−

(zł-odw. 6) (R ∪ T )

−

= R

−

∪ T

−

(zł-odw. 7) (R ∩ T )

−

= R

−

∩ T

−

(zł-odw. 8) (R\T )

−

= R

−

(zł-odw. 9) (R

′

)

−

= (R

−

)

′

(zł-odw. 10) (R

−

)

−

= R

(zł-odw. 11)

R ⊆ T

−

⊆ T

−

monotoniczność

(zł-odw. 12)

R ⊆ Q

R ◦ S ⊆ Q ◦ S

S ⊆ V

R ◦ S ⊆ R ◦ V

monotoniczność

(zł-odw. 13) R ⊆ Q, S ⊆ V

R ◦ S ⊆ Q ◦ V

monotoniczność

(zł-odw. 14) (R ∪ Q) ◦ S = (R ◦ S) ∪ (Q ◦ S)

rozdzielność

(zł-odw. 15) S ◦ (T ∪ U ) = (S ◦ T ) ∪ (S ◦ U )

rozdzielność

(zł-odw. 16) (R ∩ Q) ◦ T ⊆ (R ◦ T ) ∩ (Q ◦ T )
(zł-odw. 17) S ◦ (T ∩ U ) ⊆ (S ◦ T ) ∩ (S ◦ U )
(zł-odw. 18) (R ◦ S)\(Q ◦ S) ⊆ (R\Q) ◦ S
(zł-odw. 19) (S ◦ T )\(S ◦ U ) ⊆ S ◦ (T \U )

Zakaz rozpowszechniania bez zgody autora

Dowód.

Ad. (zł-odw. 1). Gdyby ha, ci ∈ ∅ ◦ R, to istniałoby b, takie że ha, bi ∈ ∅.
Ad. (zł-odw. 2). Weźmy dowolną parę ha, bi ∈ ∆

◦ R, gdzie a ∈ A oraz b ∈ B. Na mocy deﬁnicji

złożenia relacji istnieje c ∈ A, takie że ha, ci ∈ ∆

oraz hc, bi ∈ R, ale ha, ci ∈ ∆

wtw a = c, zatem ha, bi ∈ R.
Na odwrót załóżmy, że ha, bi ∈ R. Ponieważ na mocy deﬁnicji relacji identyczności
mamy, że ha, ai ∈ ∆

, zatem istnieje c (jest nim a), takie że ha, ci ∈ ∆

oraz

hc, bi ∈ R; reasumując ha, bi ∈ ∆

◦ R.

Ad. (zł-odw. 3). — analogicznie do 2.
Ad. (zł-odw. 4). Weźmy dowolną parę ha, di ∈ (R ◦S)◦T , gdzie a ∈ A oraz d ∈ D. Na mocy deﬁnicji

złożenia istnieje c

, takie że ha, c

i ∈ (R ◦ S) i hc

, di ∈ T . Zatem istnieje b

, dla

którego zachodzi ha, b

i ∈ R i hb

, c

i ∈ S. Reasumując istnieje c (jest nim c

takie że hb

, ci ∈ S i hc, di ∈ T , czyli hb

, di ∈ S ◦ T . Istnieje też b (jest nim b

takie że ha, bi ∈ R i hb, di ∈ S ◦ T , innymi słowy ha, di ∈ R ◦ (S ◦ T ).
Inkluzja odwrotna wykazywana jest analogicznie.

Ad. (zł-odw. 5). Skoro R ⊆ A × B oraz S ⊆ B × C, zatem R ◦ S ⊆ A × C a (R ◦ S)

−

⊆ C × A.

Niech c ∈ C i a ∈ A. Mamy:
c(R◦S)

−

a ⇔ aR◦Sc ⇔ ∃

b∈B

(aRb ∧ bSc) ⇔ ∃

b∈B

(bR

−

a ∧ cS

−

b) ⇔ ∃

b∈B

(cS

−

∧ bR

−

a) ⇔ cS

−

◦ R

−

Ad (zł-odw. 6). Skoro R ⊆ A×B oraz T ⊆ C×D, zatem (patrz produkt. 6) R∪T ⊆ (A∪C)×(B∪D)

a (R ∪ T )

−

⊆ (B ∪ D) × (A ∪ C).

Niech b ∈ B ∪ D i a ∈ A ∪ C.
Zachodzą następujące równoważności:
b(R ∪ T )

−

a ⇔ a(R ∪ T )b ⇔ aRb ∨ aT b ⇔ bR

−

a ∨ bT

−

a ⇔ bR

−

∪ T

−

Ad (zł-odw. 7). Skoro R ⊆ A × B oraz T ⊆ C × D, zatem (patrz produkt. 11) R ∩ T ⊆ (A ∩ C) ×

(B ∩ D).
Niech a ∈ A ∩ C i b ∈ B ∩ D.
Mamy b(R ∩ T )

−

a ⇔ a(R ∩ T )b ⇔ aRb ∧ aT b ⇔ bR

−

a ∧ bT

−

a ⇔ bR

−

∩ T

−

Ad (zł-odw. 8). Niech a ∈ A i b ∈ B.

Mamy: b(R\T )

−

a ⇔ a(R\T )b ⇔ aRb ∧ ∼ aT b ⇔ bR

−

a ∧ ∼ bT

−

a ⇔ bR

−

Ad (zł-odw. 9). Niech a ∈ A i b ∈ B.

Mamy: b(R

′

)

−

a ⇔ aR

′

b ⇔ ha, bi ∈ (A × B)\R ⇔ hb, ai ∈ ((A × B)\R)

−

⇔ [na

mocy własności (zł-odw. 8)] hb, ai ∈ ((A × B)

−

) ⇔ hb, ai ∈ ((B × A)\R

−

) ⇔

hb, ai ∈ (R

−

)

′

Ad (zł-odw. 10). Niech a ∈ A i b ∈ B. a(R

−

)

−

b ⇔ b(R

−

)a ⇔ aRb.

Ad (zł-odw. 11). Załóżmy, że R ⊆ T oraz b(R

−

)a. Zachodzą następujące implikacje: b(R

−

)a ⇒

aRb, aRb ⇒ aT b oraz aT b ⇒ b(T

−

)a.

Ad (zł-odw. 12). Załóżmy, że R ⊆ Q oraz aR ◦ Sc, zatem istnieje b

, takie że aRb

i b

Sc. Na mocy

założenia mamy, że aQb

i b

Sc, czyli aQ ◦ Sc.

Drugą wersję dowodzimy analogicznie.

Ad (zł-odw. 13). Załóżmy, że R ⊆ T , Q ⊆ U oraz aR ◦ Qc, zatem istnieje b

, takie że aRb

i b

Qc.

Na mocy założenia mamy, że aT b

i b

U c, czyli aT ◦ U c.

W powyższym uzasadnieniu odszukanie zbiorów, do których należały c i a, miało charakter porząd-

kowy, ale nie jest konieczne, gdyż same określenia relacji “wymusi” należenie do odpowiednich zbiorów.

Zakaz rozpowszechniania bez zgody autora

Ad (zł-odw. 14). Weźmy dowolną parę ha, ci ∈ (R ∪ Q) ◦ S. Na mocy deﬁnicji złożenia istnieje

b, takie że ha, bi ∈ (R ∪ Q) i hb, ci ∈ S. Zatem równoważnie istnieje b, takie że
(ha, bi ∈ R ∨ ha, bi ∈ Q) i hb, ci ∈ S.
Niech b

będzie owym istniejącym b.

Mamy więc dwa przypadki
1

◦

(ha, b

i ∈ R.

◦

ha, b

i ∈ Q).

W każdym z nich prawdą jest że (ha, b

i ∈ R∧hb

, ci ∈ S) lub (ha, b

i ∈ Q∧hb

, ci ∈

S). Czyli ha, ci ∈ R ◦ S lub ha, ci ∈ Q ◦ S innymi słowy ha, ci ∈ (R ◦ S) ∪ (Q ◦ S).

W drugą stronę: Niech x ∈ (R ◦ S) ∪ (Q ◦ S), czyli x ∈ R ◦ S lub x ∈ Q ◦ S. W
pierwszym przypadku x = ha, ci oraz istnieje b, takie że (ha, bi ∈ R ∧ hb, ci ∈ S).
Ale to w szczególności znaczy, że istnieje b, takie że (ha, bi ∈ (R ∪ Q) ∧ hb, ci ∈ S).
Również w drugim przypadku tj. gdy x ∈ Q ◦ S, mamy, że x = ha, ci oraz istnieje
b, takie że (ha, bi ∈ Q ∧ hb, ci ∈ S) i znów stąd mamy, że istnieje b, takie że
(ha, bi ∈ (R ∪ Q) ∧ hb, ci ∈ S). W obu przypadkach x = ha, ci ∈ (R ∪ Q) ◦ S.

Ad (zł-odw. 15). Jw.
Ad (zł-odw. 16). Weźmy dowolną parę ha, ci ∈ (R∩Q)◦S. Na mocy deﬁnicji złożenia istnieje b, takie

że ha, bi ∈ (R ∩ Q) i hb, ci ∈ S. Niech b

będzie rzeczonym b. Zatem mamy (ha, b

i ∈

R ∧ ha, b

i ∈ Q) i hb

, ci ∈ S wtw [[ze względu na ogólnie prawdziwe wyrażenie

(q ∧ r) ∧ p ⇔ (q ∧ p) ∧ (r ∧ p)]] (ha, b

i ∈ R ∧ hb

, ci ∈ S) ∧ (ha, b

i ∈ Q ∧ hb

, ci ∈ S),

czyli ha, ci ∈ R ◦ S i ha, ci ∈ Q ◦ S innymi słowy ha, ci ∈ (R ◦ S) ∩ (Q ◦ S).

Ad (zł-odw. 17). Jw.
Ad (zł-odw. 18). Załóżmy, że ha, ci ∈ (R ◦ S)\(Q ◦ S), czyli ha, ci ∈ (R ◦ S) oraz ha, ci 6∈ (Q ◦ S).

Zatem istnieje b, takie że ha, bi ∈ R oraz hb, ci ∈ S. Niech b

będzie owym b, czyli

ha, b

i ∈ R oraz hb

, ci ∈ S. Ale ha, b

i 6∈ Q — w przeciwnym razie mielibyśmy,

że ha, ci ∈ (Q ◦ S). Zatem ha, b

i ∈ R\Q, czyli istnieje takie b (jest nim b

), że

ha, bi ∈ R\Q oraz hb, ci ∈ S innymi słowy ha, ci ∈ (R\Q) ◦ S.

Ad (zł-odw. 19). Analogicznie do (zł-odw. 18): załóżmy, że ha, ci ∈ (S ◦ T )\(S ◦ U ), czyli ha, ci ∈

(S ◦ T ) oraz ha, ci 6∈ (S ◦ U ). Zatem istnieje b, takie że ha, bi ∈ S oraz hb, ci ∈ T .
Niech b

będzie owym b; tak więc ha, b

i ∈ S oraz hb

, ci ∈ T . Ale hb

, ci 6∈ U —

w przeciwnym razie mielibyśmy, że ha, ci ∈ (S ◦ U ). Zatem hb

, ci ∈ T \U , czyli

istnieje takie b (jest nim b

), że ha, bi ∈ S oraz hb, ci ∈ T \U innymi słowy ha, ci ∈

S ◦ (T \U ).

Rozważmy jeszcze raz równość:

(A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D)

Zakaz rozpowszechniania bez zgody autora

Najpierw na osi X zaznaczamy zbiór A.

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Podobnie czynimy ze zbiorem B.

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na osi Y , czyli na osi pionowej, na czerwono zaznaczamy zbiór C.

{

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na osi Y czyli na osi pionowej, na żółto zaznaczamy zbiór D.

{

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na osi Y na pomarańczowo zaznaczamy C ∩ D.

| {z }

A∩B

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na osi Y na pomarańczowo zaznaczamy C ∩ D.

{

}

C ∩ D

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

I oto przedstawiamy lewą stronę równości:

(A ∩ B) × (C ∩ D)

Rysunek 3. Lewa strona równości.

Zakaz rozpowszechniania bez zgody autora

Na ﬁoletowo przedstawiamy iloczyn kartezjański A × C:

A × C

}

{

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na żółto przedstawiamy iloczyn kartezjański B × D:

B × D

}

{

}

Rysunek 3.

Zakaz rozpowszechniania bez zgody autora

Na biało przedstawiamy część wspólną zbiorów A × C i B × D:

(A × C) ∩ (B × D)

Rysunek 3. Prawa strona równości.

Zakaz rozpowszechniania bez zgody autora

Relacja równoważności

Deﬁnicja 4.1.

• Relację dwuczłonową R ⊆ A × A nazywamy relacją zwrotną wtw

każdy element a ∈ A jest w relacji R do samego siebie, skrótowo:
R ⊆ A × A jest zwrotna ⇔ ∀

a∈A

ha, ai ∈ R.

• Relację dwuczłonową R ⊆ A×A nazywamy relacją symetryczną wtw dla dowolnych

elementów a, b ∈ A jeśli ha, bi ∈ R, to również hb, ai ∈ R, skrótowo:
R ⊆ A × A jest symetryczna ⇔ ∀

a,b

ha, bi ∈ R ⇒ hb, ai ∈ R

• Relację dwuczłonową R ⊆ A× A nazywamy relacją przechodnią wtw dla dowolnych

elementów a, b, c jeśli ha, bi ∈ R oraz hb, ci ∈ R, to ha, ci ∈ R, skrótowo:
R ⊆ A × A jest przechodnia ⇔ ∀

a,b,c∈A

(ha, bi ∈ R ∧ hb, ci ∈ R) ⇒ ha, ci ∈ R

• Relację dwuczłonową R ⊆ A × A nazywamy relacją równoważności wtw R jest

zarazem zwrotna, symetryczna i przechodnia.

Deﬁnicja 4.2. Jeśli R ⊆ A × A jest relacją równoważności, to dla każdego a ∈ A zbiór
wszystkich elementów zbioru A pozostających do a w relacji R zwany jest klasą abstrakcji
elementu a (względem) relacji R (w zbiorze A) i oznaczany jest przez „[a]

”.

Zatem

[a]

:= {b ∈ A : aRb}. Zbiór A/

:= {[a]

; a ∈ A} wszystkich klas abstrakcji względem

ustalonej relacji R na zbiorze A zwany jest zbiorem ilorazowym (zbioru A względem)
relacji R.

Uwaga 4.3. Jeśli A = ∅, to jedyną relacją R w A jest zbiór pusty oraz A/

= ∅.

Twierdzenie 4.4. Niech R ⊆ A × A będzie relacją równoważności, wówczas

1. ∀

∈

a ∈ [a]

2. ∀

∈

∀

∈

]

∩ [a

]

6= ∅ ⇔ a

3. ∀

∈

∀

∈

]

∩ [a

]

6= ∅ ⇔ [a

]

= [a

]

4. A =

a∈A

[a]

Dowód. Ad 1. Ponieważ R jest zwrotna, zatem dla dowolnego a ∈ A zachodzi aRa, zatem
z deﬁnicji klasy abstrakcji a ∈ [a]

Ad 2. Załóżmy, że [a

]

∩ [a

]

6= ∅ ⇔ istnieje c takie, że c ∈ [a

]

∩ [a

]

⇔ istnieje

c, dla którego mamy: c, c ∈ [a

]

oraz c ∈ [a

]

. Z deﬁnicji klasy abstrakcji wnosimy,

iż c ∈ A, a

Rc oraz a

Rc. Z symetryczności wnioskujemy, że również cRa

a stąd i z

przechodniości relacji R mamy, że a

. Dla pokazania implikacji odwrotnej załóżmy,

że a

, wówczas a

należy zarówno do [a

]

(z deﬁnicji klasy abstrakcji) jak i do [a

]

(ze zwrotności R). Z samego założenia o R wiemy, że a

∈ A.

Ad 3. Implikacja z prawej ku lewej jest oczywista i wynika z punktu 1. Załóżmy

teraz, że [a

]

∩ [a

]

6= ∅. Z 2. mamy: a

zaś z symetryczności R: a

. Ale dla

dowolnego b ∈ A zachodzi: b ∈ [a

]

⇔ a

Rb ⇔ bRa

⇔ [ze względu na przechodniość

R oraz nasze wcześniejsze obserwacje, że a

i a

] bRa

⇔ a

Rb ⇔ b ∈ [a

]

Reasumując, przytoczony ciąg równoważności dowodzi, że dla dowolnego b ∈ A:

b ∈

]

⇔ b ∈ [a

]

, co znaczy, że [a

]

= [a

]

Można opuścić informację przy kwantyﬁkatorze, że a, b ∈ A.

Inne możliwe oznaczenia klasy abstrakcji: a/

, kak

— często przy ustalonej relacji R opuszcza się

indeks dolny w „[a]

”.

Zakaz rozpowszechniania bez zgody autora

Ad 4. Niech x ∈ A. Z punktu 1. x ∈ [x]

, zaś z deﬁnicji sumy uogólnionej [x]

⊆

a∈A

[a]

, zatem x ∈

a∈A

[a]

. Z drugiej strony, jeśli x ∈

a∈A

[a]

, to z deﬁnicji sumy

uogólnionej x ∈ [a]

, dla pewnego a ∈ A, z kolei z deﬁnicji klasy abstrakcji relacji

R ⊆ A

mamy, że [a]

⊆ A, czyli element x ∈ A

Deﬁnicja 4.5. Podziałem zbioru A nazywamy dowolną rodzinę {A

}

i∈I

niepustych zbio-

rów parami rozłącznych (czyli ∀

i∈I

6= ∅ oraz ∀

i,j∈I

6= A

⇒ A

∩ A

= ∅), taką że

i∈I

= A.

Document Outline

Podstawowe poj¦cia teorii mnogo±ci —postulaty.
- Wprowadzenie
- Aksjomaty teorii mnogo±ci.
Podstawowe dziaªania na zbiorach
Wykªad 12 marca 2014
- Uzasadnienia wybranych wªasno±ci dziaªa« na zbiorach
Relacje i funkcje
Wykªad 26 marca 2014
- Wybrane wªasno±ci wprowadzonych dziaªa«
Wykªad 2 kwietnia 2014
Relacja równowa»no±ci
Wykªad 16 kwietnia 2014
Relacje porz¡dkuj¡ce
- Diagramy Hassego
Wybrane wªasno±ci funkcji
Klasy funkcji zmiennej rzeczywistej
- Funkcje wielomianowe (caªkowita wymierna)
  - Funkcje liniowe
  - Funkcje kwadratowe
- Funkcje wymierne uªamkowe
- Funkcje pot¦gowe
  - Funkcje, których wykresem jest parabola stopnia n
  - Funkcje, których wykresem jest krzywa typu hiperbolicznego
- Funkcje wykªadnicze
- Funkcja logarytmiczna
- Funkcje trygonometryczne
  - Funkcja sinus
  - Funkcja cosinus
  - Funkcja tangens
  - Funkcja cotangens
Moc zbioru—liczby kardynalne
- Nierówno±ci na liczbach kardynalnych
Arytmetyka liczb kardynalnych
- Twierdzenie Cantora
Ukªady równa« liniowych—wybrane zagadnienia
Algebry Boole'a
- Kraty
- Algebry Boole'a
Literatura

Wyszukiwarka

Podobne podstrony:
Mpk ver 24 03 2014 id 309156 Nieznany
Młoda Polska WYKŁAD (09 04 2014)
3 Projekt Załącznik 1 ZPB GTM 09 04 2014
Mpk ver 24 03 2014
odwadnianie ver.1 - 29.04.09, Polibuda, II semestr, Techologia oczyszczania wód i ścieków, laborator
DGP 2014 09 04 ubezpieczenia i swiadczenia
Wyklad 04 2014 2015
Psychiatria W4 28 04 2014 Zaburzenia spowodowane substancjami psychoaktywnymi
2014 Matura 05 04 2014 odpid 28 Nieznany (2)
28 04 2014 Lechowski
Rozwój form kancelaryjnych 09.11.2014 Sroka, Zarządzanie dokumentacją, archiwistyka i infobrokerstwo
Ekonomika log 09.04.2011 sob, Ekonomika logistyki
3 04 2014 Pesymizm romantyczny
08,04,2014
Młoda Polska WYKŁAD (02 04 2014)
Makroekonomia 9 04 2014
gospodarka odpadami od 04 2014

więcej podobnych podstron

Mpk ver 09 04 2014

Document Outline