Predicaten vraag

[sip5080]

Ik heb enkele stellingen waar ik maar niet uit kom, dit betreft het laatste onderdeel van de predicatenlogica.

Voorkennis: het domein (::) bestaat uit gehele getallen = Z = {...,-2,-1,0,1,2,...}

( ∀x ∃y :: x+y=0) de stelling zou true zijn want y=-x
Hier kan ik in mee komen, want de combinatie van x en y kan 0 worden, bijvoorbeeld x+y = -1+1=0

(∃y ∀x :: x+y=0) de stelling zou false zijn want er is geen y waarvoor geldt dat de som met elk getal 0 oplevert.
In deze laatste kan ik niet mee komen, want x+y kan nog steeds bijv. -1+= 0 zijn. Waarom mag ik dit niet toepassen als de kwantoren omdraaien?

Mijn kennis schrijft ook voor dat ∀ betekend: alle waarden uit het domein, welke voldoen aan....
En ∃ betekend dat het voor tenminste een van de waarden uit het domein geldt.

[Daos]

Volgens mij moet je het zo zien:
Eerste regel is in woorden: Voor alle x is er een y waarvoor geldt x + y = 0. Je kan hier y = -x pakken.
Tweede regel is in woorden: Er is een y waarvoor geldt dat bij alle x geldt x + y = 0. Neem bijvoorbeeld y = 3. Is deze stelling dan waar? Nee, alleen voor x = -3, maar niet voor alle x (x = -2 bv niet). Ik heb geen idee hoe je dit netjes bewijst voor elke mogelijke y.

edit:
Bewijs moet volgens mij zoiets zijn (met x en y uit Z):

Definitie: x is de 'tegengestelde' van y als geldt x + y = 0;

Lemma: Elke waarde in Z heeft exact 1 tegengestelde in Z.

Bewijs: Er bestaat geen y waarvoor elke x een tegengestelde is omdat Z meer dan 1 elementen heeft en er maar 1 tegengestelde bestaat voor y, welke y dan ook. Er zijn dus altijd elementen in Z te vinden die geen tegengestelde zijn. De tweede regel/stelling is dus niet waar (als het lemma wel waar is).

Moet je wel nog even het lemma bewijzen dat er exact 1 tegengestelde bestaat voor elk element uit Z...

edit2:
Bewijs voor het lemma wordt dan zoiets:

Stel x heeft meer dan 1 unieke tegengestelden: y1, y2, y3, ... Dan volgt uit de definitie x + y1 = 0, x + y2 = 0, x + y3 = 0, ... Dit is alleen waar als y1 = y2 = y3 en dat is strijdig met de aanname dat ze uniek zijn. Er is er dus hooguit 1 tegengestelde en dat is genoeg voor in het eerdere bewijs.

(Mijn bewijzen rammelen wel, maar gelukkig is optelling in Z commutatief, oftewel x + y = y + x)

[ Voor 60% gewijzigd door Daos op 27-07-2016 00:15 ]

[Wolfboy]

Als het een vermenigvuldiging zou zijn dan zou het mogelijk zijn. Maar in dit geval kan je zelfs heel eenvoudig een tegenvoorbeeld bedenken.

Neem y=1, en x=1, dan geldt dat x+y=2, niet x+y=0.

De tweede stelling zegt dat er minimaal 1 y is waarvoor bij iedere x in Z geldt dat x+y=0. Dat kan natuurlijk nooit waar zijn

[Daos]

1 tegenvoorbeeld is niet genoeg in deze. Neem bijvoorbeeld vermenigvuldiging. Dan wordt je voorbeeld:

Neem y=1, en x=1, dan geldt dat x*y=1, niet x*y=0.

Dit zegt dus niet zoveel. Er is namelijk wel een andere y waarvoor de stelling wel geldt bij vermenigvuldiging: y = 0.

[Wolfboy]

Daos schreef op woensdag 27 juli 2016 @ 01:06:
1 tegenvoorbeeld is niet genoeg in deze. Neem bijvoorbeeld vermenigvuldiging. Dan wordt je voorbeeld:

Neem y=1, en x=1, dan geldt dat x*y=1, niet x*y=0.

Dit zegt dus niet zoveel. Er is namelijk wel een andere y waarvoor de stelling wel geldt bij vermenigvuldiging: y = 0.

Dat begrijp ik niet helemaal. Als je ook maar 1 tegenvoorbeeld hebt is een stelling toch per definitie niet meer geldig?

Om te bewijzen dat een stelling correct is zal een voorbeeld inderdaad niet voldoende zijn. Maar het weerleggen van een stelling is met 1 tegenbewijs al mogelijk. Of bedoel je een bewijs uit het ongerijmde?

Dan zou je bijvoorbeeld de stelling kunnen bewijzen dat er voor een y geen enkele x te vinden is waarvoor geldt dat x+y=0. Wat volgens mij ook niet het geval is hier

[F.West98]

(ik gebruik hier E voor there exists en V voor de omgekeerde A en de ! voor de negation (omkering in NL?))
Je hebt dus de stelling:
Ey Vx : x + y = 0

En je wilt deze ontkrachten, aangezien deze intuïtief gezien niet waar is (zie post van Daos). In dit geval moet je bewijzen:
!Ey Vx : x + y = 0
Dus, het is NIET zo dat er een y bestaat waarvoor alle x geldt dat x+y = 0
Dan maak je gebruik van Ex P <=> !Vx !P (die zijn gelijk aan elkaar. in dit geval is P dus een statement met x die waar/onwaar is. Als er één x is waarvoor P geldt, dan is het dus niet zo dat het voor alle x niet geldt (lees dat 3x door)) dus dan krijg je:
Vy !(Vx : x + y = 0)
Dus in woorden: voor alle y is het niet zo dat voor alle x geldt dat x + y = 0. Om dit te bewijzen moet je dus bewijzen dat inderdaad voor niet voor alle x x+y=0 geldt, met een willekeurige y. Neem x = y + 1. Dan krijg je dus dat y + y + 1 = 0 en dat kan nooit waar zijn (want y kan enkel een geheel getal zijn).
Nu heb je dus de laatste stelling bewezen (niet heel formeel maargoed) en die is gelijkwaardig aan de tweede stelling. Die is dus waar, dus kan het omgekeerde ervan (de eerste) nooit waar zijn. Dus heb je bewezen dat waar je mee begon niet waar is.

edit:
Om op je vraag terug te komen: in het algemeen mag je niet E en V omdraaien. Voorbeeld:
Voor elk kind bestaat er een volwassene, een volwassene die de ouder van het kind is.
Er bestaat een volwassene waarvoor geldt die de ouder is van alle kinderen. (moeilijker te verwoorden)
Ofwel:
Vkind Evolw : volw = ouder(kind)
Evolw Vkind: volw = ouder(kind)

edit2:
Of een heel formeel bewijs (met de hulpstelling !(x+1+x = 0) voor alle x):
| ∃y(∀x(x+y=0))
| ∀z(¬((z+1)+z=0))
--------------------------
|| |a| ∀x(x+a)=0
|| -----------------------
|| (a + 1) + a = 0 ∀ Elim 4
|| ¬((a + 1) + a=0) ∀ Elim 2
|| ⊥ ⊥ Intro 6,7
|
| ⊥ ∃ Elim 4-8
| ¬(∃y(∀x(x+y=0))) ⊥ Elim 9

[ Voor 25% gewijzigd door F.West98 op 27-07-2016 02:27 ]

[MSalters]

Het probleem hier is dat je een relatie van x en y hebt, die volgt uit je predicaten.

Dat heb je zelf al enigzins door, als je schrijft "( ∀x ∃y :: x+y=0) de stelling zou true zijn want y=-x". Hier geldt dat y afhankelijk is van x. Voor elke keuze van y is er een verschillende waarde van y.

Voor (∃y ∀x :: x+y=0) geldt niet dat y afhankelijk is van x. Sterker nog, de claim hier is dat er een tenminste één y waarde is (noem deze Y) zodat Y+x=0 voor alle x.

PS. ∃y ∀x :: x*y=0 is natuurlijk wel waar: x*0 = 0 voor alle x.

[narotic]

Als je kwantoren omdraait krijg je gewoonweg een geheel andere stelling. Een heel simpel voorbeeld:

∀p ∃d :: past(p, d)=1 Voor elk potje is er een dekseltje dat erop past
∃d ∀p :: past(p, d)=1 Er is een dekseltje wat op alle potjes past

[sip5080]

Dank allen voor een uitleg in normaal Nederlands, daar schort het nog wel eens aan in de studieboeken!

[Daos]

Wolfboy schreef op woensdag 27 juli 2016 @ 01:45:
[...]
Dat begrijp ik niet helemaal. Als je ook maar 1 tegenvoorbeeld hebt is een stelling toch per definitie niet meer geldig?

Om te bewijzen dat een stelling correct is zal een voorbeeld inderdaad niet voldoende zijn. Maar het weerleggen van een stelling is met 1 tegenbewijs al mogelijk.

Alleen als een stelling begint met "voor alle" heb je aan 1 tegenvoorbeeld genoeg om aan te tonen dat de stelling onjuist is. De tweede stelling hier begint met "er is een" en dan heb je niet genoeg aan 1 tegenvoorbeeld. Wat wel weer kan is met 1 voorbeeld aantonen dat de stelling juist is.

[Wolfboy]

Daos schreef op woensdag 27 juli 2016 @ 14:08:
[...]


Alleen als een stelling begint met "voor alle" heb je aan 1 tegenvoorbeeld genoeg om aan te tonen dat de stelling onjuist is. De tweede stelling hier begint met "er is een" en dan heb je niet genoeg aan 1 tegenvoorbeeld. Wat wel weer kan is met 1 voorbeeld aantonen dat de stelling juist is.

Ah, right. Nu begrijp ik m'n denkfout