Title: Osajoukkotodistukset

Q: Seuraavissa tehtävissä syvennetään edelleen todistusten laatimisen taitoja. Kertaa kurssimateriaalin luvuista 1.5–1.6, miten joukkojen sisältyvyys ja yhtäsuuruus todistetaan, sekä luvusta 3.2 "jos...niin" -tyyppisen väitteen todistamista. Kiinnitä erityistä huomiota todistuksen kokonaisrakenteeseen sekä todistuksissa esiintyviin matemaattisiin sanontatapoihin.

Oletetaan, että \(X\) on jokin joukko. Osoita, että sen kaikille osajoukoille \(A\) ja \(B\) on voimassa \(\complement(A \cap B) = \complement A \cup \complement B\). (Tämä on toinen ns. de Morganin laeista.)

Todistus.

Osoitetaan ensin, että \(\complement(A \cap B) \subset \complement A \cup \complement B\). Olkoon [...]. Komplementin määritelmän nojalla \(x \in X\) ja [...]. Koska \(x \notin A \cap B\), niin leikkauksen määritelmän nojalla \(x \notin A\) tai \(x \notin B\). Tiedetään, että \(x \in X\), joten \(x \in \complement A\) tai [...]. Yhdisteen määritelmän nojalla [...]. On osoitettu, että \(\complement (A \cap B) \subset \complement A \cup \complement B\).

Osoitetaan sitten, että \(\complement A \cup \complement B \subset \complement(A \cap B)\). Olkoon [...]. Yhdisteen määritelmän nojalla \(x \in \complement A\) tai \(x \in \complement B\). Tarkastellaan tapaukset.

1. Oletetaan, että [...]. Tällöin \(x \in X\) ja \(x \notin A\). Koska \(x \notin A\), niin leikkauksen määritelmän nojalla [...]. Siis \(x \in \complement (A \cap B)\).
2. Oletetaan, että [...]. Tällöin \(x \in X\) ja \(x \notin B\). Koska \(x \notin B\), niin leikkauksen määritelmän nojalla [...]. Siis \(x \in \complement (A \cap B)\).

Molemmissa tapauksissa [...]. On osoitettu, että \(\complement A \cup \complement B \subset \complement (A \cap B)\).

Siis \(\complement (A \cap B) = \complement A \cup \complement B\).
A: x ∈ ∁ (A ∩ B); x ∉ A ∩ B; x ∈ ∁ B; x ∈ ∁ A ∪ ∁ B; x ∈ ∁ A ∪ ∁ B; x ∈ ∁ A; x ∉ A ∩ B; x ∈ ∁ B; x ∉ A ∩ B; x ∈ ∁ (A ∩ B)
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistus. Osoitetaan ensin, että \(\complement(A \cap B) \subset \complement A \cup \complement B\). Olkoon \(x \in \complement (A \cap B)\). Komplementin määritelmän nojalla \(x \in X\) ja \(x \notin A \cap B\). Koska \(x \notin A \cap B\), niin leikkauksen määritelmän nojalla \(x \notin A\) tai \(x \notin B\). Tiedetään, että \(x \in X\), joten \(x \in \complement A\) tai \(x \in \complement B\). Yhdisteen määritelmän nojalla \(x \in \complement A \cup \complement B\). On osoitettu, että \(\complement (A \cap B) \subset \complement A \cup \complement B\). Osoitetaan sitten, että \(\complement A \cup \complement B \subset \complement(A \cap B)\). Olkoon \(x \in \complement A \cup \complement B\). Yhdisteen määritelmän nojalla \(x \in \complement A\) tai \(x \in \complement B\). Tarkastellaan tapaukset. 1. Oletetaan, että \(x \in \complement A\). Tällöin \(x \in X\) ja \(x \notin A\). Koska \(x \notin A\), niin leikkauksen määritelmän nojalla \(x \notin A \cap B\). Siis \(x \in \complement (A \cap B)\). 2. Oletetaan, että \(x \in \complement B\). Tällöin \(x \in X\) ja \(x \notin B\). Koska \(x \notin B\), niin leikkauksen määritelmän nojalla \(x \notin A \cap B\). Siis \(x \in \complement (A \cap B)\). Molemmissa tapauksissa \(x \in \complement (A \cap B)\). On osoitettu, että \(\complement A \cup \complement B \subset \complement (A \cap B)\). Siis \(\complement (A \cap B) = \complement A \cup \complement B\).

Q: Täydennä todistus väitteelle \((A \setminus B) \cap C \subset A \setminus (B \cap C)\).

Todistus. Oletetaan, että [...].
Leikkauksen määritelmän nojalla [...].
Koska [...], niin erotuksen määritelmän nojalla [...].
Koska [...], niin leikkauksen määritelmän nojalla [...].
Koska [...], niin erotuksen määritelmän nojalla [...].
Siis [...] \(\subset\) [...].
A: x ∈ (A \ B) ∩ C; x ∈ A \ B ja x ∈ C; x ∈ A \ B; x ∈ A ja x ∉ B; x ∉ B; x ∉ B ∩ C; x ∈ A ja x ∉ B ∩ C; x ∈ A \ (B ∩ C); (A \ B) ∩ C; A \ (B ∩ C)
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistus. Oletetaan, että \(x \in (A \setminus B) \cap C\). Leikkauksen määritelmän nojalla \(x \in A \setminus B\) ja \(x \in C\). Koska \(x \in A \setminus B\), niin erotuksen määritelmän nojalla \(x \in A\) ja \(x \notin B\). Koska \(x \notin B\), niin leikkauksen määritelmän nojalla \(x \notin B \cap C\). Koska \(x \in A\) ja \(x \notin B \cap C\), niin erotuksen määritelmän nojalla \(x \in A \setminus (B \cap C)\). Siis \((A \setminus B) \cap C \subset A \setminus (B \cap C)\).

Q: Tutustu kurssimateriaalin lukuun 1.6, jossa selitetään, miten kaksi joukkoa osoitetaan samaksi silloin, kun niiden alkioita ei välttämättä tunneta.

Osoitetaan, että \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\) kaikilla joukoilla \(A, B\) ja \(C\).

Todistus. Osoitetaan ensin, että  \((A \cup B) \setminus C \subset (A \setminus C) \cup (B \setminus C)\). [...] Erotuksen määritelmän nojalla \(x \in A \cup B\) ja \(x \notin C\). Koska \(x \in A \cup B\), on tutkittava molemmat tapaukset erikseen.

1. [...] Koska lisäksi \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in A \setminus C\). Tällöin yhdisteen määritelmän nojalla \(x \in (A \setminus C) \cup (B \setminus C)\).
2. [...] Koska lisäksi \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in B \setminus C\). Tällöin yhdisteen määritelmän nojalla \(x \in (A \setminus C) \cup (B \setminus C)\).

Molemmissa tapauksissa [...] Siis \((A \cup B) \setminus C \subset (A \setminus C) \cup (B \setminus C)\).

Osoitetaan sitten, että  \((A \setminus C) \cup (B \setminus C) \subset (A \cup B) \setminus C \). [...] Nyt yhdisteen määritelmän nojalla \(x \in A \setminus C\) tai \(x \in B \setminus C\). Tarkastellaan tapaukset.

1. [...] Erotuksen määritelmän nojalla \(x \in A\) ja \(x \notin C\). Koska \(x \in A\), yhdisteen määritelmän nojalla \(x \in A \cup B\). Koska \(x \in A \cup B\) ja \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in (A \cup B) \setminus C\).
2. [...] Erotuksen määritelmän nojalla \(x \in B\) ja \(x \notin C\). Koska \(x \in B\), yhdisteen määritelmän nojalla \(x \in A \cup B\). Koska \(x \in A \cup B\) ja \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in (A \cup B) \setminus C\).

Molemmissa tapauksissa [...] Siis \((A \setminus C) \cup (B \setminus C) \subset (A \cup B) \setminus C\).

Olemme osoittaneet, että \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\) kaikilla joukoilla \(A, B\) ja \(C\).
A: Oletetaan, että x ∈ (A∪B)\C.; Oletetaan, että x ∈ A.; Oletetaan, että x ∈ B.; x ∈ (A\C)∪(B\C).; Oletetaan, että x ∈ (A\C)∪(B\C).; Oletetaan, että x ∈ A\C.; Oletetaan, että x ∈ B\C.; x ∈ (A∪B)\C.
Gap 1 offers: Oletetaan, että x ∈ (A∪B)\C.; Oletetaan, että x ∈ (A\C)∪(B\C).
Gap 2 offers: Oletetaan, että x ∈ A.; Oletetaan, että x ∈ B.; Oletetaan, että x ∈ A∪B.
Gap 3 offers: Oletetaan, että x ∈ A.; Oletetaan, että x ∈ B.; Oletetaan, että x ∈ A∪B.
Gap 4 offers: x ∈ A∪B.; x ∈ (A∪B)\C.; x ∈ (A\C)∪(B\C).
Gap 5 offers: Oletetaan, että x ∈ (A∪B)\C.; Oletetaan, että x ∈ (A\C)∪(B\C).
Gap 6 offers: Oletetaan, että x ∈ A\C.; Oletetaan, että x ∈ B\C.; Oletetaan, että x ∈ (A∪B)\C.
Gap 7 offers: Oletetaan, että x ∈ A\C.; Oletetaan, että x ∈ B\C.; Oletetaan, että x ∈ (A∪B)\C.
Gap 8 offers: x ∈ A∪B.; x ∈ (A∪B)\C.; x ∈ (A\C)∪(B\C).
Feedback: Osoitetaan, että \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\) kaikilla joukoilla \(A, B\) ja \(C\). Todistus. Osoitetaan ensin, että \((A \cup B) \setminus C \subset (A \setminus C) \cup (B \setminus C)\). Oletetaan, että \(x \in (A \cup B) \setminus C\). Erotuksen määritelmän nojalla \(x \in A \cup B\) ja \(x \notin C\). Koska \(x \in A \cup B\), on tutkittava molemmat tapaukset erikseen. 1. Oletetaan, että \(x \in A\). Koska lisäksi \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in A \setminus C\). Tällöin yhdisteen määritelmän nojalla \(x \in (A \setminus C) \cup (B \setminus C)\). 2. Oletetaan, että \(x \in B\). Koska lisäksi \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in B \setminus C\). Tällöin yhdisteen määritelmän nojalla \(x \in (A \setminus C) \cup (B \setminus C)\). Molemmissa tapauksissa \(x \in (A \setminus C) \cup (B \setminus C)\). Siis \((A \cup B) \setminus C \subset (A \setminus C) \cup (B \setminus C)\). Osoitetaan sitten, että \((A \setminus C) \cup (B \setminus C) \subset (A \cup B) \setminus C \). Oletetaan, että \(x \in (A \setminus C) \cup (B \setminus C)\). Nyt yhdisteen määritelmän nojalla \(x \in A \setminus C\) tai \(x \in B \setminus C\). Tarkastellaan tapaukset. 1. Oletetaan, että \(x \in A \setminus C\). Erotuksen määritelmän nojalla \(x \in A\) ja \(x \notin C\). Koska \(x \in A\), yhdisteen määritelmän nojalla \(x \in A \cup B\). Koska \(x \in A \cup B\) ja \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in (A \cup B) \setminus C\). 2. Oletetaan, että \(x \in B \setminus C\). Erotuksen määritelmän nojalla \(x \in B\) ja \(x \notin C\). Koska \(x \in B\), yhdisteen määritelmän nojalla \(x \in A \cup B\). Koska \(x \in A \cup B\) ja \(x \notin C\), niin erotuksen määritelmän nojalla \(x \in (A \cup B) \setminus C\). Molemmissa tapauksissa \(x \in (A \cup B) \setminus C\). Siis \((A \setminus C) \cup (B \setminus C) \subset (A \cup B) \setminus C\). Olemme osoittaneet, että \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\) kaikilla joukoilla \(A, B\) ja \(C\). [Image] Yllä on havainnollistettu joukkoa \((A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)\) Vennin kaavion avulla; joukkoon kuuluvat alueet on merkitty symbolilla X.

Q: Jatketaan joukkoihin liittyvien todistusten harjoittelua. Lue kurssimateriaalin luku 1.5, jossa kerrotaan osajoukoksi todistamisesta.

Oletetaan, että \(A, B\) ja \(C\) ovat joukkoja. Pyritään todistamaan väite

\[(A \cup B) \cap (C \setminus A) \subset B.\]

Osajoukoksi todistaminen etenee aina tietyn mallin mukaan. Rakennetaan tässä tehtävässä todistus pala palalta.

a) Mikä oletus on tehtävä todistuksen alussa? (Ks. kurssimateriaali)

[...]

b) Mihin lopputulokseen on päädyttävä, jotta sisältyvyys tulee osoitetuksi?

[...]

c) Kohdassa a) tekemäsi alkuoletus koskee alkiota \(x\), joka kuuluu eräiden joukkojen leikkaukseen. Mitä leikkaukseen kuuluminen tarkoittaa alkion \(x\) kannalta?

[...]

d) Joudut seuraavaksi tutkimaan kaksi tapausta erikseen. Mistä tämä johtuu?

[...]

e) Seuraavaksi voidaan päätellä, että \(x \notin A\), sillä

[...]

Näin ollen päädytään b)-kohdan johtopäätökseen.
A: Oletetaan, että \(x \in (A \cup B) \cap (C \setminus A)\).; \(x \in B\); Sitä, että \(x \in A \cup B\) ja \(x \in C \setminus A\).; Siitä, että \(x\) kuuluu kahden joukon yhdisteeseen.; \(x\) kuuluu joukkojen \(C\) ja \(A\) erotukseen.
Gap 1 offers: Oletetaan, että \(x \in A\).; Oletetaan, että \(x \in B\).; Oletetaan, että \(x \in (A \cup B) \cap (C \setminus A)\).; Oletetaan, että \(x \in A \cup B\).
Gap 2 offers: \(x \in A\); \(x \in B\); \(x \in (A \cup B) \cap (C \setminus A)\); \(x \in A \cup B\)
Gap 3 offers: Sitä, että \(x \in A\) ja \(x \in B\).; Sitä, että \(x \in A\) tai \(x \in B\).; Sitä, että \(x \in A \cup B\) tai \(x \in C \setminus A\).; Sitä, että \(x \in A \cup B\) ja \(x \in C \setminus A\).
Gap 4 offers: Siitä, että \(x\) kuuluu kahden joukon leikkaukseen.; Siitä, että \(x\) kuuluu kahden joukon yhdisteeseen.; Siitä, että \(x\) kuuluu kahden joukon erotukseen.; Kyseinen tilanne ilmenee aina joukkojen sisältyvyystodistuksessa.
Gap 5 offers: \(x\) kuuluu joukkojen \(C\) ja \(A\) erotukseen.; \(x\) kuuluu joukkojen \(A\) ja \(B\) yhdisteeseen.; \(x\) kuuluu joukkojen \(C\) ja \(A\) leikkaukseen.; \(x\) kuuluu joukkojen \(A\) ja \(B\) leikkaukseen.
Feedback: Halutaan osoittaa, että \((A \cup B) \cap (C \setminus A) \subset B\). On siis oletettava, että meillä on mielivaltainen alkio \(x \in (A \cup B) \cap (C \setminus A)\). Haluamme näyttää, että tällöin \(x \in B\). Koska \(x \in (A \cup B) \cap (C \setminus A)\) alussa tehdyn oletuksen mukaan, \(x\) kuuluu joukkojen \(A \cup B\) ja \(C \setminus A\) leikkaukseen. Toisin sanoen \(x \in A \cup B\) ja \(x \in C \setminus A\). Koska \(x\) kuuluu nyt yhdisteeseen \(A \cup B\), niin \(x \in A\) tai \(x \in B\). Koska emme tiedä kuuluuko \(x\) joukkoon \(A\) vai \(B\) (vai molempiin), joudumme tutkimaan molemmat tapaukset. Toisaalta tiedämme nyt, että \(x \in C \setminus A\), joten erotuksen määritelmän nojalla \(x \in C\) ja \(x \notin A\). Tämä yhdistettynä tietoon \(x \in A\) tai \(x \in B\) auttaa meitä päättelemään, että \(x \in B\). Koska \(x\) oli mielivaltainen alkio, päättely toimii kaikilla joukon \((A \cup B) \cap (C \setminus A)\) alkioilla. Siis \((A \cup B) \cap (C \setminus A) \subset B\). [Image] Kuvassa joukko \((A \cup B) \cap (C \setminus A)\) merkittynä symbolilla X.