Kompaktheitssatz < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Angenommen $L$ ist eine Sprache.
(1) Konstruieren Sie eine Menge $T$ von L-Aussagen so, dass [mm] $\mathcal{M}\models T\Leftrightarrow\quad$ [/mm] Die Trägermenge von von [mm] $\mathcal{M} [/mm] ist unendlich für alle L-Strukturen [mm] $\mathcal{M}$ [/mm] gilt.
(2) Beweisen Sie mithilfe des Kompaktheitssatzes, dass es keine endliche Menge von L-Aussagen gibt, die die Bedingung in (1) erfüllt. |
Hallo,
ich habe eine Frage zu dieser Aufgabe. Speziell würde ich gerne mit euch den zweiten Aufgabenteil besprechen.
Leider ist mir der erste nicht gelungen und ich hoffe, dass die Kenntnis über eine mögliche Konstruktion für die Lösung nicht zwingend erforderlich ist.
Bei Aufgabe (2) soll ich ja zeigen, dass für eine endliche Menge $T$ von L-Aussagen die Äquivalenz
[mm] $\mathcal{M}\models T\Leftrightarrow\quad$ [/mm] Die Trägermenge von [mm] $\mathcal{M}$ [/mm] ist unendlich
nicht gilt.
Dann sollte es doch ausreichen folgendes zu zeigen:
Ist T eine endliche Theorie, dann besitzt T ein endliches Modell.
Als Hinweis ist ja bereits der Kompaktheitssatz gegeben.
Dessen Aussage ist, dass jede endlich erfüllbare Theorie T bereits erfüllbar ist.
Dies wiederum heißt, dass jede endliche Teilmenge von T erfüllbar sein muss.
Am sinnvollsten scheint mir ein Widerspruchsbeweis.
Angenommen T besitzt ein unendliches Modell ...
Und nun irgendwie zeigen, dass dann T nicht endlich sein kann, bzw. irgendwie mit dem Kompaktheitssatz zum Widerspruch führen.
Leider reicht es für mehr bisher nicht... :(
Über Tipps würde ich mich sehr freuen.
mfg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:12 Di 12.05.2015 | | Autor: | hippias |
Es waere nicht schlecht, wenn Du den ersten Teil bereits geloest haettest, denn er hilft mir beim zweiten.
Entscheidend ist sich klarzumachen, dass wenn es eine endliche Menge von $L$-Aussagen gibt, die die $L$-Strukturen mit endlichem Traeger axiomatisiert, dann gibt es sogar eine einelementige Menge von $L$-Aussagen, die dies leistet. Sei dies [mm] $\{\phi\}$.
[/mm]
Aus [mm] $\neg \phi$, [/mm] der Menge aus dem ersten Teil - jedenfalls, wenn Du auf die uebliche Loesung kommst - und dem Kompaktheitssatz kannst Du Dir einen Widerspruch konstruieren.
|
|
|
| |
|
Wie könnte man denn den ersten Teil der Aufgabe lösen?
Mein Hauptproblem ist es, dass ich ja für jede beliebige L-Struktur solche unendlichen Formelmengen konstruieren muss, dass sie genau dann gelten wenn die Trägermenge selbst unendlich ist.
(Ich weiß ja aus dem zweiten Aufgabenteil, dass es für endliche Formelmengen nicht geht.)
Dabei fällt es mir bereits schwer dies zu tun wenn ich ein konkretes Beispiel nehme. Etwa:
[mm] $\mathcal{N}=(\mathbb{N},<)$
[/mm]
Im Grunde gibt es hier ja nur eine Möglichkeit eine Formel hinzuschreiben, welche ich allerdings mit anderen logischen Zeichen beliebig oft verknüpfen könnte, nämlich:
[mm] $\exists [/mm] x,y (x<y)$
Dann könnte ich nun induktiv weiter vorgehen:
[mm] $\exists x,y,z(x
[mm] $\exists x,y,z,z_1 (x
usw.
So könnte ich natürlich unendlich viele solcher Formeln erzeugen.
Die Ungleichheitsbedinung bräuchte ich, damit die Formel auch wirklich nur für unendliche Mengen gilt.
Sonst würde ich ja nur zwei Objekte benötigen die sich irgendwie linear Ordnen lassen.
Bei der Aufgabe muss ich es aber allgemein tun. Ich weiß also nicht ob ich überhaupt in meiner Struktur ein Funktionszeichen, Relationszeichen oder Konstantenzeichen habe.
Naheliegend ist es irgendwie wie wieder induktiv über den Formelaufbau zu machen.
Was würde jedoch passieren, wenn meine L-Struktur nur aus der Trägermenge besteht und ich keine Zeichen in L habe?
Wäre sowas eine sinnvolle Formel?
[mm] $\exists [/mm] x (x=x)$
[mm] $\exists [/mm] x,y [mm] (x=x\wedge y=y\wedge x\neq [/mm] y)$
usw.?
Zur ursprünglichen Frage
> Entscheidend ist sich klarzumachen, dass wenn es eine endliche Menge von $ > L $-Aussagen gibt, die die $ L $-Strukturen mit endlichem Traeger
> axiomatisiert, dann gibt es sogar eine einelementige Menge von $ L $->Aussagen, die dies leistet.
Ja, denn wenn ich endlich viele L-Aussagen habe, die meine L-Struktur axiomatisiere, dann kann ich alle diese L-Aussagen auch als "eine" auffassen.
Also wenn [mm] $\underline{\Psi}:=\{\psi_0,\dotso, \psi_n\}$ [/mm] und die L-Struktur [mm] $\mathcal{M}\models\underline{\Psi}$, [/mm] dann gilt [mm] $\mathcal{M}\models\psi$ [/mm] für alle [mm] $\psi\in\underline{\Psi}$.
[/mm]
Nun könnte ich alle diese L-Aussagen aber auch zusammenfügen, durch die L-Aussage [mm] $\psi_0\wedge \psi_1\wedge\dotso\wedge\psi_n$ [/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:03 Mi 13.05.2015 | | Autor: | hippias |
> Wie könnte man denn den ersten Teil der Aufgabe lösen?
> Mein Hauptproblem ist es, dass ich ja für jede beliebige
> L-Struktur solche unendlichen Formelmengen konstruieren
> muss, dass sie genau dann gelten wenn die Trägermenge
> selbst unendlich ist.
>
> (Ich weiß ja aus dem zweiten Aufgabenteil, dass es für
> endliche Formelmengen nicht geht.)
>
> Dabei fällt es mir bereits schwer dies zu tun wenn ich ein
> konkretes Beispiel nehme. Etwa:
>
> [mm]\mathcal{N}=(\mathbb{N},<)[/mm]
>
> Im Grunde gibt es hier ja nur eine Möglichkeit eine Formel
> hinzuschreiben, welche ich allerdings mit anderen logischen
> Zeichen beliebig oft verknüpfen könnte, nämlich:
>
> [mm]\exists x,y (x
>
> Dann könnte ich nun induktiv weiter vorgehen:
>
> [mm]\exists x,y,z(x
>
> [mm]\exists x,y,z,z_1 (x
>
> usw.
> So könnte ich natürlich unendlich viele solcher Formeln
> erzeugen.
> Die Ungleichheitsbedinung bräuchte ich, damit die Formel
> auch wirklich nur für unendliche Mengen gilt.
> Sonst würde ich ja nur zwei Objekte benötigen die sich
> irgendwie linear Ordnen lassen.
>
> Bei der Aufgabe muss ich es aber allgemein tun. Ich weiß
> also nicht ob ich überhaupt in meiner Struktur ein
> Funktionszeichen, Relationszeichen oder Konstantenzeichen
> habe.
> Naheliegend ist es irgendwie wie wieder induktiv über den
> Formelaufbau zu machen.
>
> Was würde jedoch passieren, wenn meine L-Struktur nur aus
> der Trägermenge besteht und ich keine Zeichen in L habe?
>
> Wäre sowas eine sinnvolle Formel?
>
> [mm]\exists x (x=x)[/mm]
>
> [mm]\exists x,y (x=x\wedge y=y\wedge x\neq y)[/mm]
>
> usw.?
Ja, das ist der richtige Ansatz. Die Teilformeln $x=x$ etc. sind natuerlich ueberfluessig. Eine Gleichheitsrelation ist nach Definition in jeder Sprache vorhanden.
>
> Zur ursprünglichen Frage
>
> > Entscheidend ist sich klarzumachen, dass wenn es eine
> endliche Menge von [mm]> L [/mm]-Aussagen gibt, die die [mm]L [/mm]-Strukturen
> mit endlichem Traeger
> > axiomatisiert, dann gibt es sogar eine einelementige Menge
> von [mm]L [/mm]->Aussagen, die dies leistet.
>
> Ja, denn wenn ich endlich viele L-Aussagen habe, die meine
> L-Struktur axiomatisiere, dann kann ich alle diese
> L-Aussagen auch als "eine" auffassen.
> Also wenn [mm]\underline{\Psi}:=\{\psi_0,\dotso, \psi_n\}[/mm] und
> die L-Struktur [mm]\mathcal{M}\models\underline{\Psi}[/mm], dann
> gilt [mm]\mathcal{M}\models\psi[/mm] für alle
> [mm]\psi\in\underline{\Psi}[/mm].
> Nun könnte ich alle diese L-Aussagen aber auch
> zusammenfügen, durch die L-Aussage [mm]\psi_0\wedge \psi_1\wedge\dotso\wedge\psi_n[/mm]
>
Genau!
|
|
|
|
