Hogyan kell megoldani a következő halmazos bizonyítást?

Nézd meg itt az 1.3. feladatot!

[link]

A komplementer halmazt csillaggal jelölöm majd, nem tudok vonalat rakni a betűk fölé.

Nézzük mondjuk a b) részt:

(A∪B)* = A* ∩ B*

Lássuk be, hogy

1) (A∪B)* ⊆ A* ∩ B*

és lássuk be azt is, hogy fordítva is igaz:

2) A* ∩ B* ⊆ (A∪B)*

Ha mindkettő teljesül, akkor (A∪B)* = A* ∩ B* kell legyen.

Odafelé:

Legyen x ∈ (A∪B)*

Ekkor x ∉ A∪B, ami azt jelenti, hogy x ∉ A és x ∉ B sem, mert ha bármelyiknek eleme lenne, akkor az uniónak is eleme lenne.

Vagyis x ∈ A* és x ∈ B* egyszerre kell teljesüljön.

Tehát x ∈ A* ∩ B*

Ez (A∪B)* minden elemére igaz, tehát 1) teljesül.

Visszafelé indirekt bizonyítás:

Tegyük fel, hogy ∃x ∈ A*∩B* úgy, hogy x ∉ (A∪B)*

Ekkor x ∈ A∪B

Vagyis x∈A, vagy x∈B (vagy mindkettő)

Ha x∈A, akkor x∉A*, ezért nem lehet eleme A*∩B*-nak, hisz A*∩B* ⊆ A*

Ha x∈B, akkor x∉B*, ezért nem lehet eleme A*∩B*-nak, hisz A*∩B* ⊆ B*

Ellentmondásra jutottunk, tehát 2) is igaz.

Az a) részt hasonlóképpen lehet bizonyítani, próbáld meg.

A ∪ B az egy C halmaz. C elemei elemei vagy A-nak, vagy B-nek, vagy mindkettőnek. Ez gondolom eddig tiszta.

(A ∪ B)* az pedig C*, vagyis a C komplementere. Vagyis C* elemei az alaphalmaz azon elemei, amik nem elemei C-nek.

Ha x ∈ (A∪B)*, vagyis x ∈ C*, akkor x nem eleme C-nek, hisz a komplementer éppen ezt jelenti.