WisFaq!

Tegenvoorbeeld opstellen

Hallo!

Het is mij onduidelijk hoe ik een tegenvoorbeeld moet opstellen.
Zo hebben we "x$yR(x,y) |= $y"xR(x,y)
Uitwerken als boom is niet zo moeilijk:
1. "x$yR(x,y) (hypothese)
2. Ø$y"xR(x,y) (Ø conclusie)
3. "yØ"xR(x,y) ($-regel,2)
4. $yR(a,y) ("-regel,1)
5. R(a,b) ($-regel,4)
6. Ø"xR(x,b) ("-regel,3)
7. $xØR(x,b) ("-regel,6)
8. ØR(c,b) ($-regel,7)

(ik hoop dat het goed is, beetje onduidelijk met al die opmaak-codes)
en de boom eindigt niet. Dus een tegenvoorbeeld opstellen. Ik snap dat regel 1 en 3 waar moeten zijn.
Dan levert dit het volgende tegenvoorbeeld (volgens boek):
A = D;Q;d1,d2,d3
D = {d1,d2,d3}
Q = {(d1,d2),(d2,d2),(d3,d3)}
Hoe kom je hieraan en hoe werk je het verder uit?

Mirek
18-6-2004

Antwoord

Als ik het goed begrijp probeer je een bewering te bewijzen door er eigenschappen op los te laten, en als dat niet lukt probeer je te zoeken naar een tegenvoorbeeld.

Dat tegenvoorbeeld kan je vinden door wat te redeneren over de stelling: gegeven is dat voor elke x, er een y bestaat zodat een bepaalde relatie geldt. Te bewijzen is dat er dan ook een y bestaat, zodat voor elke x die relatie geldt.

Een tegenvoorbeeld hiervoor is snel gevonden: kies bijvoorbeeld een verzameling met twee getallen, 0 en 1, en R(x,y) geldt als x verschilt van y. Dan bestaat er voor elke x een y zodat R(x,y) geldt (namelijk als x=0 dan y=1 en als x=1 dan y=0). Maar er geldt niet dat er een y bestaat zodat R(x,y) geldt voor elke x. Immers, R(0,0) geldt niet, en R(1,1) ook niet.

Het tegenvoorbeeld dat jij opgeeft is ook zoiets: R(d1,d2) geldt, evenals R(d2,d2) en R(d3,d3). Dus voor elke x (resp. d1,d2,d3) kan je een y vinden (resp d2,d2,d3). Maar er bestaat geen y zodat R(x,y) geldt voor alle x: bijvoorbeeld voor y=d2 geldt R(d3,d2) niet.

Dat moet dan niet meer verder uitgewerkt worden: één tegenvoorbeeld volstaat om te bewijzen dat een stelling niet geldig is.

Groeten,
Christophe.

Christophe
23-6-2004