Title: Implikaatiotodistukset

Q: Oletetaan, että \(A, B\) ja \(C\) ovat joukkoja ja \(B \neq \emptyset\). Pyrkimyksenä on osoittaa, että jos \(A \times B \subset B \times C\), niin \(A  \subset C\).

Laita todistuksen vaiheet oikeaan järjestykseen.

Todistus

[...]

[...]

[...]

           \( \vdots \)

[...]

Väite on todistettu.
Also offered: Oletetaan, että A ⊂ C.; Oletetaan, että (a, b) ∈ A × B.; Näytetään, että A × B ⊂ B × C.; Siis (a, b) ∈ B × C.
A: Oletetaan, että A × B ⊂ B × C.; Näytetään, että A ⊂ C.; Oletetaan, että a ∈ A.; Siis a ∈ C.
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistus Oletetaan, että \(A \times B \subset B \times C\). Näytetään, että \(A \subset C\). Oletetaan, että \(a \in A\). \( \vdots \) Siis \(a \in C\). Väite on todistettu.

Q: Todistetaan väite "jos \(A \cap B = B\), niin \(A \cup B = A\)". Aseta todistuksen eri vaiheet järjestykseen.

[...]

Osoitetaan ensin, että \(A \cup B \subset A\).

[...]

[...]

[...]

[...]

[...]

[...]

Osoitetaan sitten, että \(A \subset A \cup B\).

[...]

[...]

[...]

[...]
A: Oletetaan, että A ∩ B = B.; Oletetaan, että x ∈ A ∪ B.; Yhdisteen määritelmän nojalla x ∈ A tai x ∈ B.; Tapaus 1: Jos x ∈ A, väite pätee.; Tapaus 2: Jos x ∈ B, niin oletuksen mukaan x ∈ A ∩ B.; Koska x ∈ A ∩ B, niin x ∈ A ja väite pätee.; On osoitettu, että A ∪ B ⊂ A.; Oletetaan, että x ∈ A.; Yhdisteen määritelmän nojalla x ∈ A ∪ B.; On osoitettu, että A ⊂ A ∪ B.; Koska A ∪ B ⊂ A ja A ⊂ A ∪ B, niin A ∪ B = A.
If right: Vastauksesi on oikein.
If partly right: Vastauksesi on osittain oikein.
If wrong: Vastauksesi on väärin.
Feedback: Todistus. Oletetaan, että \(A \cap B = B\). Halutaan osoittaa, että tällöin \(A \cup B = A\). Osoitetaan ensin, että \(A \cup B \subset A\). Oletetaan, että \(x \in A \cup B\). Yhdisteen määritelmän nojalla \(x \in A\) tai \(x \in B\). Tutkitaan tapaukset: 1. Jos \(x \in A\), väite pätee. 2. Jos \(x \in B\), niin oletuksen \(A \cap B = B\) nojalla \(x \in A \cap B\). Siis \(x \in A\). On osoitettu, että \(A \cup B \subset A\). Osoitetaan sitten, että \(A \subset A \cup B\). Oletetaan, että \(x \in A\). Yhdisteen määritelmän nojalla \(x \in A \cup B\). On osoitettu, että \(A \subset A \cup B\). Siis \(A \cup B = A\).

Q: Kerrataan ennestään tuttuja todistustekniikoita.

Olkoot \(A\) ja \(B\) joukkoja. Halutaan osoittaa, että jos \(A \not\subset B\), niin \(A \setminus B \neq \emptyset\).

a) Mikä oletus tehdään todistuksen alussa?

[...]

b) Mihin johtopäätökseen todistuksessa halutaan päätyä?

[...]

c) Oletuksesta seuraa, että

[...]

d) Edellisestä kohdasta seuraa, että

[...]

e) Miksi väite on nyt todistettu?

[...]
A: Oletetaan, että \(A \not\subset B\).; \(A \setminus B \neq \emptyset\); on olemassa \(x \in A\) siten, että \(x \notin B\).; \(x \in A \setminus B\).; Koska löydettiin alkio joukosta \(A \setminus B\).
Gap 1 offers: Oletetaan, että \(A \not\subset B\).; Oletetaan, että \(A \setminus B \neq \emptyset\).; Oletetaan, että \(A \subset B\).; Oletetaan, että \(A \setminus B = \emptyset\).
Gap 2 offers: \(A \not\subset B\); \(A \setminus B \neq \emptyset\); \(A \subset B\); \(A \setminus B = \emptyset\)
Gap 3 offers: \(x \notin B\) millään \(x \in A\).; \(B \subset A\).; \(A \cap B = \emptyset\).; on olemassa \(x \in A\) siten, että \(x \notin B\).
Gap 4 offers: \(x \in A \setminus B\).; \(x \in B\).; \(x \notin A\).; \(x \in A \cap B\).
Gap 5 offers: Koska joukossa \(A \setminus B\) ei ollut yhtään alkiota.; Koska löydettiin alkio joukosta \(A \setminus B\).; Koska \(x \in A\).; Koska löytettiin alkio joukosta \(A \cap B\).
Feedback: a) Oletetaan, että \(A \not\subset B\). b) Halutaan näyttää, että \(A \setminus B \neq \emptyset\). c) On olemassa \(x \in A\) siten, että \(x \notin B\). d) Edellisestä seuraa, että \(x \in A \setminus B\). e) Koska löydettiin alkio joukosta \(A \setminus B\) (kyseinen alkio on tietenkin todistuksessa esiintyvä \(x\)).

Q: Osajoukoksi todistaminen noudattaa niin kutsutun implikaatiotodistuksen, eli ”jos…niin…”-tyyppisen todistuksen kaavaa. Seuraavissa tehtävissä tähän todistustekniikkaan tutustutaan yleisemmässä muodossa. Kurssimateriaalin luku 3.2 on omistettu implikaatiotodistukselle. Tutustu siihen.

Olkoon \(m\) jokin kokonaisluku. Todista, että jos \(m\) on pariton, niin myös \(m^2\) on pariton.

Todistus. Oletetaan, että

[...]

Tällöin

[...]

Huomataan, että

[...]

Siten

[...]
A: \(m\) on pariton.; \(m = 2k + 1\) jollakin kokonaisluvulla \(k\).; \(m^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\).; \(m^2\) on pariton.
Gap 1 offers: \(m\) on pariton.; \(m\) on parillinen.; \(m^2\) on pariton.; \(m^2\) on parillinen.
Gap 2 offers: \(m = 2k\) jollakin kokonaisluvulla \(k\).; \(m = 2k + 1\) jollakin kokonaisluvulla \(k\).; \(m^2 = 2k\) jollakin kokonaisluvulla \(k\).; \(m^2 = 2k + 1\) jollakin kokonaisluvulla \(k\).
Gap 3 offers: \(m = 2k/2 = k\).; \(m = 2k + 1\).; \(m^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\).; \(m^2 = (2k)^2 = 4k^2 = 2 \cdot 2k^2\).
Gap 4 offers: \(m\) on pariton.; \(m\) on parillinen.; \(m^2\) on pariton.; \(m^2\) on parillinen.
Feedback: Oletetaan, että \(m\) on pariton. Tällöin \(m = 2k + 1\) jollakin \(k \in \mathbb{Z}\). Huomataan, että \(m^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\). Siten \(m^2\) on pariton.

Q: Valitse paras ilmaus siten, että todistus on looginen ja noudattaa hyvää matemaattista kirjoitustapaa.

Osoitetaan, että jos \(A \neq \emptyset\), niin \(A \cup B \neq \emptyset\).

Todistus

[...], että \(A \neq \emptyset\). [...] \(x \in A\). Nyt yhdisteen [...] nojalla \(x \in A \cup B\).  [...] \(A \cup B \neq \emptyset\), mikä todistaa väitteen.
A: Oletetaan; Tällöin on olemassa; määritelmän; Näin ollen
Gap 1 offers: Oletetaan; Tiedetään; Päätellään
Gap 2 offers: Tällöin on olemassa; Oletetaan, että; Olkoon
Gap 3 offers: määritelmän; lauseen; lemman
Gap 4 offers: Näin ollen; Olkoon siis; Oletetaan siis, että
Feedback: Todistus Oletetaan, että \(A \neq \emptyset\). Tällöin on olemassa \(x \in A\). Nyt yhdisteen määritelmän nojalla \(x \in A \cup B\). Näin ollen \(A \cup B \neq \emptyset\), mikä todistaa väitteen.

Q: Olkoot \(A, B, C\) ja \(D\) joukkoja. Oletetaan, että \(B \neq \emptyset \). Pyritään todistamaan, että jos \(A \times B \subset C \times D\), niin \(A \subset C\).

a) Mikä oletus tehdään todistuksen alussa ensimmäisenä?

[...]

b) Mitä halutaan näyttää?

[...]

c) Mikä oletus tehdään toisena?

[...]

d) Mihin lopputulokseen c-kohdan alkion kanssa halutaan päätyä?

[...]
A: Oletetaan, että \(A \times B \subset C \times D\).; Halutaan näyttää, että \(A \subset C\).; Oletetaan, että \(a \in A\).; \(a \in C\)
Gap 1 offers: Oletetaan, että \(A \times B \subset C \times D\).; Oletetaan, että \(A \subset C\).; Oletetaan, että \((a,b) \in A \times B\).
Gap 2 offers: Halutaan näyttää, että \(A \subset C\).; Halutaan näyttää, että \(A \times B \subset C \times D\).; Halutaan näyttää, että \(B \neq \emptyset\).
Gap 3 offers: Oletetaan, että \(a \in A\).; Oletetaan, että \(b \in B\).; Oletetaan, että \((a,b) \in A \times B\).
Gap 4 offers: \(a \in C\); \(b \in C\); \((a,b) \in C \times D\)
Feedback: a) Mikä oletus tehdään todistuksen alussa ensimmäisenä? Oletetaan, että \(A \times B \subset C \times D\). b) Mitä halutaan näyttää? Halutaan näyttää, että \(A \subset C\). c) Mikä oletus tehdään toisena? Oletetaan, että \(a \in A\). d) Mihin lopputulokseen c-kohdan alkion kanssa halutaan päätyä? \(a \in C\)

Q: Tässä tehtävässä tutkitaan todistamista ja yhtälönratkaisun logiikkaa.

Todistetaan väite "jos \(- \sqrt{2x^2 - 4} = 4 + x\), niin \(x \in \{-2,10\}\)".

Kyseessä on

[...]

Todistuksessa oletetaan, että

[...]

Todistuksessa halutaan päästä siihen lopputulokseen, että

[...]

Päteekö väite myös toiseen suuntaan? [...]

Yhtälöllä on

[...]
A: implikaatiotodistus.; yhtälö pätee.; \(x=-2\) tai \(x = 10\).; Ei; nolla ratkaisua.
Gap 1 offers: induktiotodistus.; implikaatiotodistus.; ekvivalenssitodistus.; Ei mikään näistä.
Gap 2 offers: \(x = -2\).; \(x = 10\).; \(x=-2\) tai \(x = 10\).; yhtälö pätee.
Gap 3 offers: \(x = -2\).; \(x = 10\).; \(x=-2\) tai \(x = 10\).; yhtälö pätee.
Gap 4 offers: Kyllä; Ei
Gap 5 offers: nolla ratkaisua.; yksi ratkaisu, \(x = -2\).; yksi ratkaisu, \(x = 10\).; kaksi ratkaisua, \(x = -2\) tai \(x = 10\).
Feedback: Implikaatiotodistuksessa oletetaan väitteen "jos"-osa ja päädytään väitteen "niin"-osaan. Oletetaan siis, että \(- \sqrt{2x^2 - 4} = 4 + x\) ja päätellään tästä, että \(x \in \{-2,10\}\). Korottamalla yhtälön molemmat puolet potenssiin \(2\), saadaan yhtälö \(2x^2 - 4 = (4 + x)^2\). Avaamalla oikean puolen sulut saadaan \(2x^2 - 4 = x^2 + 8x + 16\). Tästä yhtälöstä saadaan yhtälö \(x^2 - 8x - 20 = 0\), mistä seuraa, että \(x = -2\) tai \(x = 10\). Väite ei päde toiseen suuntaan, sillä jos \(x \in \{-2,10\}\), niin yhtälön vasen ja oikea puoli eivät ole samat. Yhtälöllä ei siis ole ratkaisua. [Image] Kuvassa funktioiden \(f(x) = - \sqrt{2x^2-4}\) (sininen) ja \(g(x) = x + 4\) (punainen) kuvaajat.

Olkoot \(a, b \in \mathbb{R}\). Osoita, että jos \(a < b\), niin \(\frac{a+b}{2} < b\).

Väitteelle tulee laatia .

Todistus. Oletetaan, että . Tästä seuraa, että
\(a + b < \) .
Jakamalla epäyhtälön molemmat puolet luvulla , saadaan epäyhtälö sievennettyä muotoon . Väite on todistettu.
Feedback: Todistus. Oletetaan, että \(a < b\). Tästä seuraa, että \(a + b < b + b\), mikä voidaan kirjoittaa myös muodossa \(a + b < 2b\). Jakamalla epäyhtälö puolittain luvulla \(2\), saadaan epäyhtälö muotoon \(\frac{a+b}{2} < b\). Väite on todistettu.