Logikk / Diskret Matematikk: Bevis med relasjoner

[kjetulf]

Hei!

Sliter med en oppgave som går som følger:

La R være en transitiv og symmetrisk relasjon på mengden S. Anta at for alle x ∈ S, så fins det en y ∈ S slik at xRy. Bevis at R er en ekvivalensrelasjon.

Til nå er jeg vant til bevis(direkte, kontrapositive og motsigelse) med logiske formler og relasjoner hver for seg, men jeg klarer ikke helt å se for meg hvordan jeg kan kombinere de to på en like ryddig og formell måte som jeg tidligere kunne hver for seg. Jeg vet rett og slett ikke helt hvor jeg skal begynne for å se at påstanden stemmer, og heller ikke hvordan jeg skal føre det.

Så langt tenker jeg at det er når man tilføyer setningen

Anta at for alle x ∈ S, så fins det en y ∈ S slik at xRy

som gjør at R blir en ekvivalensrelasjon, da transitivitet og symmetri kan være tilstede uten at relasjonen nødvendigvis er refleksiv av den grunn. Jeg ser dog ikke helt hvorfor det er sånn at dersom jeg har en x i S, vil jeg alltid ha en y i S som gjør at relasjonen R gjelder og at dette gjør at jeg får en ekvivalensrelasjon.

Tips(om nødvendig deler av svaret, men helst ikke hele ) er veldig velkomne!

tl;dr: Sliter med oppgaven i quotes over, og trenger tips!

[Fibonacci92]

Ting du får oppgitt:
- For alle x så finnes det en y slik at xRy.
- R er symmetrisk
- R er transitiv

Tanke: Hva vil det si at R er symmetrisk?

[kjetulf]

OK, ser nå at selve påstanden stemmer. Men;

Vi har at S = {x,y}. Det følger fra at R er symmetrisk at R = { <x,y>,<y,x>}. R er transitiv. Da følger det at R = { <x,y>, <y,x>, <x,x>, <y,y> }. R er nå også refleksiv, og er en ekvivalensrelasjon.

Er dette korrekt? Hvis ja; Er det godkjent føring?

[Fibonacci92]

Nå er jeg usikker på notasjonen din, men du sier at S={x,y} ?
Eksempelet ditt er korrekt, men det er bare et godkjent bevis dersom S bare har to elementer.

S skal kunne være en hvilken som helst mengde som er slik at R er en transitiv og symmetrisk relasjon på denne mengden.

Dersom jeg skulle ført dette beviset ville jeg gjort det slik:

(1) R er symmetrisk relasjon på S (aRb -> bRa)
(2) R er en transitiv relasjon på S (aRb og bRc -> aRc)
(3) For alle x finnes det en y slik at xRy.

La x være et element i S. Da har vi at det finnes en y slik at xRy (3). R er symmetrisk på S slik at fordi xRy så er også yRx (1). R er transitiv på S slik at xRy og yRx -> xRx (2).

Vi ser dermed at dersom x er et element i S, så er xRx og dermed er R refleksiv på S.

Fordi R er symmetrisk, refleksiv og transitiv på S er R en ekvivalensrelasjon på S. QED

[kjetulf]

Dang, klart. Tusen takk!