8.2

[manül]

Ich hab das folgendermaßen (hoffentlich) gelöst:

Angenommen wir haben ein endliches Universum: B = \lbrace x_1, x_2, ..., x_n \rbrace.
Dann: x_i (\exists x_j \in B): P(x_i, x_j) (für xi gibt es ein xj in B, sodass P(xi, xj))
und x_j (\exists x_k \in B): P(x_j, x_k)

da: P(x_i, x_j) \wedge P(x_j, x_k) \supset P(x_i, x_k) folgt x_i \neq x_k, denn sonst P(x_i, x_i)
daraus folgt wiederum: x_i \neq x_j \neq x_k

für x_k (\exists x_l \in B): P(x_k, x_l)
aus P(x_j, x_k) \wedge P(x_k, x_l) \supset P(x_j, x_l) folgt wieder x_j \neq x_l
etc...

d.h. es kann kein endliches Modell geben

[-vigrid-]

Das sieht alles ganz logisch aus, nur wie beweißt du das die Formel erfüllbar ist? Ich habs mit einem Tableau Kalkül probiert und komm zu keinem Ergebnis
Oder bin ich da komplett am falschen Weg?? :confused:

[david.mihola]

Ich denke, das müsste gehen, indem man ein Modell dafür findet; und ein solches wäre z. B.:

D = ℕ
Φ(P) = <

(Das Zeichen für die Signaturinterpretation ist doch ein großes Phi, oder?)

Im Bereich der natürlichen Zahlen gilt:
1. keine Zahl ist kleiner als sie selbst
2. wenn x < y und y < z, dann ist x < z
3. für jedes x gibt es eine größere Zahl

Analog zu Seite 143 im Skriptum müsste das doch als Beweis für die Erfüllbarkeit ausreichen, oder?

Meine Frage dazu wäre: Gilt das dann auch als Beweis dafür, dass es kein endliches Modell gibt? Dieses Modell ist ganz offensichtlich nicht endlich (für jedes x gibt es eine noch größere Zahl), aber kann man daraus, dass ein Modell unendlich ist, schließen, dass es gar keine endlichen gibt?

LG, David

[jak]

Bin auch auf den Ansatz P = < gekommen, das reicht auf jeden Fall für die Erfüllbarkeit. Ich denke nicht, daß man daraus schließen kann das kein endliches Modell existiert.

Ich glaube aber, daß man den folgenden Ansatz o.B.d.A. machen kann:
Als Informatiker denke ich ans sortieren: Teil 1 & 2 implizieren das ich nach P sortieren kann: Wenn P(x,y) = t stelle ich x links von y hin. Damit führt der 3. Teil nur dann nicht zu einem Widerspruch wenn das Modell unendlich ist:
Der 3.Teil ist nur t wenn es ein Element rechts vom aktuellen Element gibt, d.h. es gibt kein letztes (rechtestes) Element --> unendliches Modell.

[-vigrid-]

Danke, jetzt ist mir einiges klarer geworden..:o

Das es überhaupt kein endl. Modell geben kann, kann man aus manüls Lösung sehen. [...]

Ich glaub im Grunde stimmts schon so, nur mein Problem ist noch immer wie ich es formal aufschreiben kann. Dein BSP mit den nat. Zahlen ist eigentl. ganz gut.

@ jak
auch nicht schlecht ;)

[jak]

Ich könnte mir zwei Wege vorstellen das formal zu beweisen:
1.) Man nimmt an das der Satz für alle Mengen mit mehr als n Elementen gilt und zeigt das dies für kein n wahr ist. Könnte man mit vollst. Induktion versuchen, weiß aber nicht ob das im negativfall auch erlaubt ist.
Die Vorgehensweise wäre dann: Induktionsanfang: n=3 (für n=1 und n=2 ist es sowieso falsch und man kann den zweiten Teil nicht wirklich verwenden). --> Widerspruch
Induktionsschluß: Wenn es für n-1 ein widerspruch ist, ist es auch für n ein Widerspruch.
2.) Man nimmt an das es ein minimales n gibt für das diese Formel gilt und führt dies Annahme auf einen Widerspruch.

Btw: Die Eigenschaften der Formel entsprechen der einer strengen Ordnung, ich glaube aus Teil 2 & 3 kann man sogar ableiten das es eine Totalordnung ist (siehe WP: Ordnungsrelation).