Tipi~cni primjer zadatka sa skupovima
S Na primjeru ovog zadatka ~temo pokazati mnoge stvari, neke od kojih smo ve~t nau~cili (poput negiranja slo~zenih izjav~a), a i neke nove poput kori~stenja "BSOMP" u dokazima. Tako~der mo~ze poslu~ziti kao primjer dokazivanja metodom kontradikcije (da bismo dokazali P, pretpostavimo !P i iz toga poku~sajmo dobiti kontradikciju (Q & !Q, za neki Q). Ako to uspijemo, znamo da !P ne vrijedi (jer vodi do kontradikcije), pa mora vrijediti P.)
3Z Doka~zite: ako dva skupa imaju iste podskupove, tada imaju i iste elemente. P(A)=P(B) => A=B To se jo~s mo~ze izre~ti i kao "P je injektivan", ili kao "o~cito je da su partitivni skupovi jednakih skupova jednaki - no vrijedi i obrat".
Rj Trebamo dokazati implikaciju (ne~sto oblika P => Q). Ona se obi~cno dokazuje tako da se pretpostavi P, i onda se poku~sa iz te pretpostavke zaklju~citi da vrijedi Q. Dakle, pretpostavimo da vrijedi P(A)=P(B).
Trebamo dokazati A=B. To je jednakost dvaju skupova, pa bi se moglo krenuti dokazivati A C= B i obrnuto, ali ovaj put krenut ~temo metodom kontradikcije. Dakle, pretpostavimo A != B, i pogledajmo ~sto mo~zemo dobiti iz toga.

Imamo A != B, negaciju izjave A=B. A=B je skra~teni zapis za konjunkciju dvije inkluzije, pa je negacija toga zapravo negacija konjunkcije, dakle disjunkcija negacij~a pojedinih inkluzij~a: !(A C= B & B C= A) <=> !(A C= B) V !(B C= A).

O Sad nam se dokaz (sjetimo se, trebamo pod danim pretpostavkama dokazati kontradikciju ~ ali sli~cno razmi~sljanje vrijedi i kad bismo trebali dokazati bilo ~sto drugo) ra~cva u dva dijela, jedan u kojem nije A podskup od B, i drugi u kojem nije B podskup od A. No jasno je da
ako ovaj prvi dio dokaza uspijemo dovesti do kontradikcije na neki na~cin, tada je trivijalno isto u~ciniti i s drugim dijelom dokaza, jednostavnom zamjenom slov~a "A" i "B" u dokazu. Naime, "A" i "B" imaju potpuno simetri~cne uloge u ovom zadatku (zamjenom "A" i "B" u tekstu zadatka smisao zadatka ostaje isti),
i zbog toga je takav manevar mogu~t.

U redu, dakle dovoljno je dokazati samo jedan slu~caj (ie, samo jednu granu dovesti do kontradikcije) ~ drugi se lakom zamjenom svodi na prvi. To zapisujemo tako da zapi~semo slu~caj u koji idemo kao pretpostavku, ali pred nju stavimo "BSOMP" (akronim od "bez smanjenja op~tenitosti mo~zemo pretpostaviti"), da se zna da tom pretpostavkom nismo umanjili op~tenitost dokaza, ve~t jednostavno jeftino smanjili njegovu duljinu skoro na pola.

Rj Nastavljamo dokaz, dakle pi~semo "BSOMP !(A C= B)" i idemo dalje. A C= B je skra~tenica za univerzalno kvantificiranu izjavu (A_x@A)(x@B), pa je njena negacija (E_x@A)!(x@B). Dakle, dobili smo neki x, element od A, koji nije element od B.

Toliko o raspisivanju. Sad treba to ~sto znamo o xu dovesti do ne~ceg ~sto ~te biti u kontradikciji s P(A)=P(B). Dakle, o~cito treba na~ti neki podskup od A koji nije podskup od B (ili obrnuto), i pri tome bi bilo dobro iskoristiti element x. Sad mislim da je jasno da se radi o skupu {x}. Zaista, {x} C= A, jer je svaki njegov element (~sto se svodi na x) ujedno i element od A, a isto tako {x} !C= B, jer postoji njegov element (x) koji nije element od B.

Dakle, postoji element ({x}) od P(A) koji nije element od P(B), dakle P(A) !C= P(B), pa ne mogu biti jednaki. Kontradikcija.
Pretpostavka A != B nas je dovela do kontradikcije, dakle A=B. To smo dokazali pod pretpostavkom P(A)=P(B), pa smo time dokazali implikaciju koja se tra~zila u zadatku. QED.