Matematické Fórum

↑ Frantik88:
To zadanie nie je celkom spravne, asi si mal na mysli, ze ak mame dve antisymetricke relacie, tak ci ich zjednotenie je antisymetricka relacia. Toto tvrdenie neplati, takze sa ho nesnaz dokazat, ale hladaj nejaky kontrapriklad :)

↑ Frantik88:
Aha, ono je to takto... Relacia je vlastne mnozina usporiadanych dvojic. Cize napriklad {[5,3], [7,5], [1,2]}. Antisymetricka relacia je taka, ze ak usporiadana dvojica [a,b] je v tejto relacii, tak [b,a] v nej nie je (pokial 'a' sa nerovna 'b'). Formalne povedane: ak [a,b] je v relacii a zaroven [b,a] je v tejto relacii, tak potom a=b.
Teda napriklad relacie {[2,5], [3,4]} a {[7,1]} su antisymetricke; relacie {[1,2], [5,6], [2,1]} a {[7,7], [8,2], [2,8]} nie su antisymetricke.
Zjednotenie dvoch relacii je vlastne zjednotenie mnozin, cize vsetky ich prvky dame dokopy.
Hladame teda take dve relacie (mnoziny usporiadanych dvojic), ktore obe splnaju podmienku pre antisymetrickost, ale ich zjednotenie ju nesplna. Skus najst nejaky kontrapriklad, nie je to vobec tazke :)

↑ Frantik88:
Ano, je to spravne :)

↑ Frantik88:
No toto nie je strohy dokaz, pretoze to vobec nie je ani dokaz :) Iba si ukazal, ze v jednom pripade to tvrdenie plati, ale to este neznamena, ze musi aj v ostatnych :)
Zjednotenie symetrickych relacii je ale naozaj vzdy symetricka relacia. Dokaz tu ale musime robit cez definiciu. Takze aka je definicia symetrickej relacie?

↑ Frantik88:
Nie, ani to predtym nebol dokaz. To bolo najdenie kontraprikladu, cize sme vlastne ukazali, ze to tvrdenie neplati.
Ta definicia je spravna. Majme teda relacie R,S, pricom vieme, ze platia dve veci:
1. ak [a,b] patri do R, tak aj [b,a] patri do R
2. ak [a,b] patri do S, tak aj [b,a] patri do S
Chceme dokazat, ze ak [a,b] patri do zjednotenia R a S, tak potom aj [b,a] patri do zjednotenia R a S. Pri dokaze mozeme (resp. musime) vyuzit tie 2 veci, ktore platia. Vies ako dalej?

↑ Frantik88:
No vidis a pritom je to uplne jednoduche :)
Takze dokaz: nech [a,b] patri do zjednotenia R a S. Z toho vyplyva (z definicie zjednotenia) ze bud [a,b] patri do R alebo [a,b] patri do S (alebo aj do oboch naraz, ale na tom nezalezi). No a teraz pouzijeme tie 2 veci ktore sme si predtym napisali (predpoklady) a dostavame ze potom aj [b,a] patri do R alebo do S. A teraz posledny krok: ak [b,a] patri do R alebo do S, tak urcite patri do zjednotenia R a S, cim je dokaz skonceny.
Je Ti to jasne alebo treba podrobnejsie? :)

↑ Frantik88:
Aby sme to mohli pekne napisat, tak si musime uvedomit, ze co to vlastne ten kontrapriklad je :)
To tvrdenie, ze "ak mame dve antisymetricke relacie, tak aj ich zjednotenie je antisymetricka relacia" v skutocnosti presnejsie znamena "pre KAZDE dve antisymetricke relacie plati, ze ich zjednotenie je antisymetricka relacia". To slovo "kazde" sa nepise v kazdom tvrdeni, ale ak je to matematicke tvrdenie, tak sa naozaj predpoklada, ze to plati pre akekolvek dve relacie.
No a kontrapriklad je v tomto pripade taka dvojica relacii, pre ktore to tvrdenie neplati. Cize ak napiseme kontrapriklad, tak minimalne sme ukazali ze to tvrdenie plati pre vsetky dvojice relacii okrem jednej. Treba si ale uvedomit tiez, ze kontraprikladom sme neukazali, ze by tvrdenie neplatilo pre ziadnu dvojicu. Cize v podstate tolko, ze pre niektore mozno plati, ale nie pre vsetky. Povieme ale, ze "tvrdenie neplati", cim teda myslime, ze neplati pre vsetky dvojice. Toto je uz taky hlbsi pohlad do vyznamu matematickych tvrdeni, tak dufam ze som Ta s tym nedoplietol :)
Teraz ale spat k tej formulacii. Stacilo by jednoducho napisat ze "kontrapriklad ukazuje, ze tvrdenie neplati", pripadne "kontrapriklad ukazuje, ze tvrdenie vo vseobecnosti neplati".

↑ Frantik88:
Co tak skusit nejaky priklad z konecnych mnozin namiesto nekonecnej? :)

↑ Frantik88:
No a chceme vytvorit relaciu, ktora nebude tranzitivna. Napriklad povedzme ze nasa relacia bude obsahovat prvky [1,2] a [2,3], ale nebude obsahovat prvok [1,3]. Tym urcite nebude tranzitivna.
Aj tato dvojprvkova mnozina je uz samozrejme relaciou, uz ju len treba doplnit o nejake usporiadane dvojice aby bola zaroven este aj reflexivna a antisymetricka. Skus to :)
Inak ulohy typu "najdite relaciu, ktora je..." sa v podstate takmer vzdy riesia priamo takoutou konstrukciou, teda pridavanim (pripadne odoberanim) prvkov.

↑ Frantik88:
Presne tak a je pomerne jednoduche sa presvedcit, ze tato 5-prvkova relacia uz splna vsetky tri pozadovane vlastnosti :)
Mohli sme samozrejme vymysliet aj iny priklad, ale tento je najjednoduchsi.