Endlichkeitssatz Logik

23.07.2008, 16:54

ambitiousboy

Endlichkeitssatz Logik

Kann mir jemand sagen, was ich am Endlichkeitssatz falsch verstanden habe.
"Eine Menge X von Aussageformen ist genau dann erfüllbar, wenn jede endliche Teilmenge davon erfüllbar ist"

Aber die unendliche Menge X = {x>0, x<1/2, x<1/3, ..., x<1/n (n aus N)} ist für kein x aus R (oder auch x aus Q) erfüllt, aber jede endliche Teilmenge schon.
Oder irre ich bei diesem Gegenbeispiel?

Oder die Fassung:
"Eine Menge X von Aussageformen erfüllt Aussage µ genau dann, wenn schon jede endliche Teilmenge µ erfüllt."

(Def.: Eine Menge X von Aussageformen erfüllt die Aussageform µ, wenn für alle Modelle von X auch µ erfüllt ist.)

Aber dann nehme µ als x=0 und X wie oben, nur mit x>=0 statt x>0.

Vielen Dank,
ambitiousboy

23.07.2008, 16:58

kiste

Auf diesen Beitrag antworten »

für ein festes x existiert ein n so dass $\begin{eqnarray*} x > \frac{1}{n} \end{eqnarray*}$ , also ist es für eine endliche teilmenge nicht erfüllt.

Zur zweiten Fassung kann ich leider nichts sagen, dazu habe ich mich zu lange nicht mehr mit Logik beschäftigt

23.07.2008, 18:03

papahuhn

Auf diesen Beitrag antworten »

RE: Endlichkeitssatz Logik

Zitat:

Original von ambitiousboy
Kann mir jemand sagen, was ich am Endlichkeitssatz falsch verstanden habe.
"Eine Menge X von Aussageformen ist genau dann erfüllbar, wenn jede endliche Teilmenge davon erfüllbar ist"

Aber die unendliche Menge X = {x>0, x<1/2, x<1/3, ..., x<1/n (n aus N)} ist für kein x aus R (oder auch x aus Q) erfüllt, aber jede endliche Teilmenge schon.
Oder irre ich bei diesem Gegenbeispiel?

Du hast in deinem Beispiel bereits die Grundmenge und die Relation "<" festgenagelt. In deiner Menge X sind leider nichtmal syntaktisch korrekte Formeln drin - Zahlen gibt es in der Prädikatenlogik nicht.

24.07.2008, 00:05

ambitiousboy

Auf diesen Beitrag antworten »

wieso
Es muss ja nicht für alle x gehen, sondern nur erfüllbar sein, also für ein x. Und für jedes endliche n gibt es solche x.

24.07.2008, 00:17

ambitiousboy

Auf diesen Beitrag antworten »

@papahuhn
@papahuhn: Wo ist das Problem mit "Struktur und <-Relation" festgenagelt?
Erst dadurch bekommen Formeln ja einen Wahrheitswert.

Und wieso soll es keine Zahlen geben? Entweder definiere ich sie als Konstanten in der nicht-logischen Signatur oder z.B. schreibe Formeln x*n<1, wobei ich statt 1 auch y mit der Zusatzforderung y*y=y and not y=z-z schreiben könnte und statt n (y+y+y...).

Bitte erklär nochmal.

24.07.2008, 01:09

papahuhn

Auf diesen Beitrag antworten »

RE: @papahuhn

Zitat:

Original von ambitiousboy
@papahuhn: Wo ist das Problem mit "Struktur und <-Relation" festgenagelt?
Erst dadurch bekommen Formeln ja einen Wahrheitswert.

Und wieso soll es keine Zahlen geben? Entweder definiere ich sie als Konstanten in der nicht-logischen Signatur oder z.B. schreibe Formeln x*n<1, wobei ich statt 1 auch y mit der Zusatzforderung y*y=y and not y=z-z schreiben könnte und statt n (y+y+y...).

Ok, definieren wir das mal genauer.
$\begin{eqnarray*} X = \{\neg(x < 0), \neg(x = 0), (x < 1), (x+x < 1), (x+x+x < 1), ... \} \end{eqnarray*}$
mit $\begin{eqnarray*} 0, 1 \end{eqnarray*}$ Konstanten, $\begin{eqnarray*} < \end{eqnarray*}$ zweistelliges Prädikat, $\begin{eqnarray*} + \end{eqnarray*}$ dreistelliges Prädikat, geschrieben in Infix- bzw. Funktionsnotation.
Diese Menge ist erfüllbar z.B. mit Grundmenge $\begin{eqnarray*} U = \{\alpha, \Omega\} \end{eqnarray*}$ , $\begin{eqnarray*} I(0) = \alpha, I(1) = \Omega, I(x) = \Omega \end{eqnarray*}$ sowie ein $\begin{eqnarray*} I(+) \end{eqnarray*}$ das immer $\begin{eqnarray*} \alpha \end{eqnarray*}$ ergibt, und $\begin{eqnarray*} I(<) = \{(\alpha, \Omega), (\Omega, \Omega)\} \end{eqnarray*}$ .

24.07.2008, 15:27

ambitiousboy

Auf diesen Beitrag antworten »

RE: @papahuhn
"Infix- bzw. Funktionsnotation" sagt mir jetzt nichts, sorry.
+ meinst Du sicher als Operation statt Prädikat, zweistellig genügt ja sogar, wenn man klammert und sie mehrmals anwendet.
Aber ok, Hauptschwierigkeit habe ich mit I. Ist das eine Funktion I(x) oder eine Symbolzuweisung I(+)?

Bin bisher von einer bestimmten Struktur und für Modell von einer Belegung über dieser Struktur ausgegangen. Wenn ich beliebige Strukturen nehmen dürfte, kann ich natürlich immer eine bauen, die außer den logischen Kontradiktionen alles irgendwie erfüllt.
Unmissverständlicher ist die zweite Fassung.
"Eine Menge X von Aussageformen erfüllt die Aussageform µ genau dann, wenn eine endliche Teilmenge existiert die µ erfüllt."
Da ist also insbesondere behauptet, dass in Struktur (Q,<,+,0,1) mit µ: x=0 und X = {not x<0, x<1, x+x<1,...} , auch eine endliche Teilmenge T_n={not x<0, x<1,...,n*x<1} von X µ erfüllt. (Anm.: n*x steht für x+x+...+x<1)
(Anmerkung: X und µ sind erfüllt mit Belegung w(x)=0, aber kein T_n ist nur für w(x)=0 sondern auch für w(x)=1/(n+1) erfüllt, aber nicht µ.)

24.07.2008, 15:47

papahuhn

Auf diesen Beitrag antworten »

RE: @papahuhn

Zitat:

"Infix- bzw. Funktionsnotation" sagt mir jetzt nichts, sorry.
+ meinst Du sicher als Operation statt Prädikat, zweistellig genügt ja sogar, wenn man klammert und sie mehrmals anwendet.

Ja, das meine ich.

Zitat:

Aber ok, Hauptschwierigkeit habe ich mit I. Ist das eine Funktion I(x) oder eine Symbolzuweisung I(+)?

Bin bisher von einer bestimmten Struktur und für Modell von einer Belegung über dieser Struktur ausgegangen. Wenn ich beliebige Strukturen nehmen dürfte, kann ich natürlich immer eine bauen, die außer den logischen Kontradiktionen alles irgendwie erfüllt.

Mit $\begin{eqnarray*} I \end{eqnarray*}$ meine ich die Interpretationsfunktion der Struktur. Das Relationssymbol $\begin{eqnarray*} < \end{eqnarray*}$ und das Funktionssymbol $\begin{eqnarray*} + \end{eqnarray*}$ bekommen dadurch erst eine Bedeutung. Eingeführt wird sie bei der Definition der Semantik von Formeln.

29.07.2008, 16:52

ambitiousboy

Auf diesen Beitrag antworten »

Antwort
Ok, kenne ich als w (Omega).
Da mit der zweiten Fassung des Endlichkeitssatzes das aber nicht geht, sind entweder die beiden Fassungen nicht äquivalent oder man muss sich bei der ersten Fassung doch auf eine feste Struktur beziehen.

Wie ist das nun mit der Folgerungsversion, also der Zweiten?
Danke schon mal für Deine Bemühungen.

29.07.2008, 17:28

papahuhn

Auf diesen Beitrag antworten »

RE: Antwort
Ich habe mittlerweile die konkrete Frage aus den Augen verloren. Wo ist jetzt genau das Problem?

04.08.2008, 17:15

ambitiousboy

Auf diesen Beitrag antworten »

konkrete Frage
Kann mir jemand sagen, was ich am Endlichkeitssatz falsch verstanden habe?
"Eine Menge X von Aussageformen erfüllt Aussage µ genau dann, wenn eine endliche Teilmenge von X existiert, die µ erfüllt."

Aber die unendliche Menge X = {"not x<0", "x<1/2", "x<1/3", ..., "x<1/n" (n aus N)} erfüllt µ "x=0", aber keine endliche Teilmenge von X tut dies.

Langsam schwant mir, dass auch X nicht µ erfüllt, wenn man das papahuhn-Modell zugrundlegt. Das heißt es geht beim Endlichkeitssatz gar nicht um Belegungen auf einer Struktur, sondern um alle denkbaren Strukturen (und Belegungen darauf). Stimmts?

Eine Folgerungsrelation auf fester Stuktur A (also |= mit A indiziert), ergibt also keinen Endlichkeitssatz, wie meine "festgenagelte" Struktur zeigt.

Vielen Dank für die fruchtbare Diskussion und Hilfe,
ambitiousboy

04.08.2008, 18:27

papahuhn

Auf diesen Beitrag antworten »

RE: konkrete Frage

Zitat:

Original von ambitiousboy
Langsam schwant mir, dass auch X nicht µ erfüllt, wenn man das papahuhn-Modell zugrundlegt. Das heißt es geht beim Endlichkeitssatz gar nicht um Belegungen auf einer Struktur, sondern um alle denkbaren Strukturen (und Belegungen darauf). Stimmts?

Ja, aber das hat gar nichts mit dem Endlichkeitssatz an sich zu tun, sondern liegt am Symbol $\begin{eqnarray*} \models \end{eqnarray*}$ .
Die Bedeutung von $\begin{eqnarray*} \Phi \models \psi \end{eqnarray*}$ ist: Jedes Modell von $\begin{eqnarray*} \Phi \end{eqnarray*}$ ist auch Modell von $\begin{eqnarray*} \psi \end{eqnarray*}$ .

Dein Axiomsystem ist also gar kein Gegenbeispiel für den Endlichkeitssatz, weil $\begin{eqnarray*} X \not \models (x=0) \end{eqnarray*}$ gilt.

Neue Frage »

Antworten »

Endlichkeitssatz Logik

Verwandte Themen