Filter, Theorie < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Angenommen [mm] $\Phi$ [/mm] ist eine endlich erfüllbare L-Theorie, $I$ ist die Menge der endlichen Teilmengen von [mm] $\Phi$ [/mm] und
[mm] $\mathcal{F}=\{X\subseteq I|\exists \sigma\in I\forall\tau\in I [\sigma\subseteq\tau\rightarrow\tau\in X]\}$
[/mm]
Zeigen Sie, dass [mm] $\mathcal{F}$ [/mm] ein Filter auf $I$ ist. |
Hallo,
ich möchte zeigen, dass die Menge [mm] $\mathcal{F}$ [/mm] ein Filter ist.
Ich muss also die drei Eigenschaften:
1) [mm] $I\in\mathcal{F}$ [/mm] und [mm] $\emtyset\notin\mathcal{F}$
[/mm]
2) Wenn [mm] $X\in\mathcal{F}$ [/mm] und [mm] $Y\subseteq [/mm] I$ mit [mm] $X\subseteq [/mm] Y$, dann [mm] $Y\in\mathcal{F}$
[/mm]
3) Wenn [mm] $X,Y\in\mathcal{F}$, [/mm] dann ist [mm] $X\cup Y\in\mathcal{F}$
[/mm]
erfüllt sind.
[mm] $\Phi$ [/mm] ist eine endlich erfüllbare Theorie, daher gibt es für jede endliche Teilmenge $T$ von [mm] $\Phi$ [/mm] ein Modell [mm] $\mathcal{M}$ [/mm] mit [mm] $\mathcal{M}\modells [/mm] T$.
Zu erst hätte ich eine Frage zu der Menge selbst.
Mir ist nicht ganz klar, was die Menge eigentlich beschreibt.
Ich betrachte alle Teilmengen $X$ von $I$, welche die Eigenschaft erfüllen, dass ein [mm] $\sigma\in [/mm] I$ existiert so, dass für alle [mm] $\tau\in [/mm] I$ gilt, wenn [mm] $\sigma$ [/mm] eine Teilmenge von [mm] $\tau$ [/mm] ist, dann ist [mm] $\tau$ [/mm] bereits ein Element von $X$.
Dabei sind [mm] $\sigma$ [/mm] und [mm] $\tau$ [/mm] endliche Mengen von L-Aussagen.
[mm] $\mathcal{F}$ [/mm] beschreibt also jene endlichen Teilmengen von [mm] $\Phi$ [/mm] für die es eine endliche Menge von L-Aussagen [mm] $\sigma$ [/mm] gibt, so dass bereits alle Obermengen von [mm] $\sigma$ [/mm] ein Element der Menge sind.
X soll also eine Menge von Mengen sein, welche L-Aussagen enthalten?
Dann zur ersten Eigenschaft.
1)
Das die leere Menge kein Element von [mm] $\mathcal{F}$ [/mm] ist, ist klar.
Das [mm] $I\in\mathcal{F}$ [/mm] sollte auch trivial sein, weil $I$ ja gerade die Menge aller endlichen Teilmengen von [mm] $\Phi$ [/mm] ist. Das heißt wenn ich eine endliche Menge [mm] $\sigma\in [/mm] I$ habe, dann sind auch alle endlichen Obermengen [mm] $\tau$ [/mm] von [mm] $\sigma$ [/mm] in $I$.
2)
Ich weiß, dass [mm] $X\in\mathcal{F}$ [/mm] und [mm] $X\subseteq Y\subseteq [/mm] I$ gilt und soll nun zeigen, dass [mm] $Y\in\mathcal{F}$.
[/mm]
Weil $Y$ eine Obermenge von $X$ ist, und [mm] $X\in\mathcal{F}$. [/mm] Also ist [mm] $\tau$ [/mm] bereits in $Y$.
Irgendwie erscheint es mir eigenartig, $Y$ unterscheidet sich ja nur so von $X$, dass es irgendwelche endlichen Teilmengen von L-Aussagen enthält, welche in $X$ nicht vorkommen. Nun ist $X$ ein Element von [mm] $\mathcal{F}$ [/mm] und daher sind bereits alle Obermengen, zu einer bestimmten Menge [mm] $\sigma$ [/mm] in $X$ enthalten. Daher sind diese Mengen auch in $Y$.
Ich muss die Menge [mm] $\mathcal{F}$ [/mm] falsch verstehen...
Der Teil [mm] $[\sigma\subseteq\tau\rightarrow \tau\in [/mm] X]$ scheint mir nicht klar zu sein. Das kann ja nicht einfach heißen, dass alle Obermengen zu einer bestimmten Menge in X enthalten sein müssen.
Könnte ich als [mm] \sigma [/mm] nicht einfach dann die Menge wählen, welche keine L-Aussage enthält? Dann wäre doch [mm] $\sigma\subseteq\tau$ [/mm] immer erfüllt und daher bereits alle endlichen Teilmengen in $X$.
Hier stehen jetzt wahrscheinlich viele wirre Gedanken...
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:34 Mo 25.05.2015 | | Autor: | tobit09 |
(Für alle, die sich über meine Antwort auf eine Frage mit längst abgelaufener Fälligkeit wundern: impliziteFunktion hat mir per PN mitgeteilt, weiter an einer Antwort interessiert zu sein.)
Hallo impliziteFunktion!
> Angenommen [mm]\Phi[/mm] ist eine endlich erfüllbare L-Theorie, [mm]I[/mm]
> ist die Menge der endlichen Teilmengen von [mm]\Phi[/mm] und
>
> [mm]\mathcal{F}=\{X\subseteq I|\exists \sigma\in I\forall\tau\in I [\sigma\subseteq\tau\rightarrow\tau\in X]\}[/mm]
>
> Zeigen Sie, dass [mm]\mathcal{F}[/mm] ein Filter auf [mm]I[/mm] ist.
> ich möchte zeigen, dass die Menge [mm]\mathcal{F}[/mm] ein Filter
> ist.
> Ich muss also die drei Eigenschaften:
>
> 1) [mm]I\in\mathcal{F}[/mm] und [mm]\emtyset\notin\mathcal{F}[/mm]
>
> 2) Wenn [mm]X\in\mathcal{F}[/mm] und [mm]Y\subseteq I[/mm] mit [mm]X\subseteq Y[/mm],
> dann [mm]Y\in\mathcal{F}[/mm]
>
> 3) Wenn [mm]X,Y\in\mathcal{F}[/mm], dann ist [mm]X\cup Y\in\mathcal{F}[/mm]
>
> erfüllt sind.
Ja, bis auf den Tippfehler, dass es am Ende [mm] $X\cap [/mm] Y$ statt [mm] $X\cup [/mm] Y$ heißen muss.
> [mm]\Phi[/mm] ist eine endlich erfüllbare Theorie, daher gibt es
> für jede endliche Teilmenge [mm]T[/mm] von [mm]\Phi[/mm] ein Modell
> [mm]\mathcal{M}[/mm] mit [mm]\mathcal{M}\models T[/mm].
Genau.
(Das wirst du im Folgenden gar nicht benötigen. Die Aussage aus der Aufgabenstellung bleibt auch für beliebige Mengen [mm] $\Phi$ [/mm] richtig.)
> Zu erst hätte ich eine Frage zu der Menge selbst.
> Mir ist nicht ganz klar, was die Menge eigentlich
> beschreibt.
>
> Ich betrachte alle Teilmengen [mm]X[/mm] von [mm]I[/mm], welche die
> Eigenschaft erfüllen, dass ein [mm]\sigma\in I[/mm] existiert so,
> dass für alle [mm]\tau\in I[/mm] gilt, wenn [mm]\sigma[/mm] eine Teilmenge
> von [mm]\tau[/mm] ist, dann ist [mm]\tau[/mm] bereits ein Element von [mm]X[/mm].
Genau.
Ein weiterer Formulierungsvorschlag:
[mm] $\mathcal{F}$ [/mm] ist die Menge aller Teilmengen [mm] $X\subseteq [/mm] I$, für die eine ("genügend große") Menge [mm] $\sigma\in [/mm] I$ existiert, so dass alle Obermengen [mm] $\tau\supseteq\sigma$ [/mm] mit [mm] $\tau\in [/mm] I$ Elemente von X sind.
> Dabei sind [mm]\sigma[/mm] und [mm]\tau[/mm] endliche Mengen von L-Aussagen.
Ja.
> [mm]\mathcal{F}[/mm] beschreibt also jene endlichen Teilmengen von
> [mm]\Phi[/mm] für die es eine endliche Menge von L-Aussagen [mm]\sigma[/mm]
> gibt, so dass bereits alle Obermengen von [mm]\sigma[/mm] ein
> Element der Menge sind.
Genau.
> X soll also eine Menge von Mengen sein, welche L-Aussagen
> enthalten?
So ist es.
Ich möchte im Folgenden die folgende Abkürzung verwenden:
Sei [mm] $X\subseteq [/mm] I$ und [mm] $\sigma\in [/mm] I$.
Dann verwenden wir [mm] $F(X,\sigma)$ [/mm] als Abkürzung für die Aussage
[mm] $\forall\tau\in I\colon(\sigma\subseteq\tau\rightarrow\tau\in [/mm] X)$.
Es gilt also
[mm] $\mathcal{F}=\{X\subseteq I\;|\;\exists\sigma\in I\colon F(X,\sigma)\}$.
[/mm]
> Dann zur ersten Eigenschaft.
>
> 1)
>
> Das die leere Menge kein Element von [mm]\mathcal{F}[/mm] ist, ist
> klar.
Warum?
Angenommen es gäbe doch ein Element [mm] $\sigma\in [/mm] I$ mit [mm] $F(\emptyset,\sigma)$.
[/mm]
Finde nun im Widerspruch zu [mm] $F(\emptyset,\sigma)$ [/mm] ein Element [mm] $\tau\in [/mm] I$ mit [mm] $\sigma\subseteq\tau$, [/mm] aber [mm] $\tau\notin\emptyset$.
[/mm]
> Das [mm]I\in\mathcal{F}[/mm] sollte auch trivial sein, weil [mm]I[/mm] ja
> gerade die Menge aller endlichen Teilmengen von [mm]\Phi[/mm] ist.
> Das heißt wenn ich eine endliche Menge [mm]\sigma\in I[/mm] habe,
> dann sind auch alle endlichen Obermengen [mm]\tau[/mm] von [mm]\sigma[/mm]
die [mm] $\tau\subseteq\Phi$ [/mm] erfüllen
> in [mm]I[/mm].
Ja, wenn [mm] $I\not=\emptyset$ [/mm] gilt, kannst du willkürlich ein Element [mm] $\sigma\in [/mm] I$ auswählen und dies genügt automatisch der Bedingung [mm] $F(I,\sigma)$.
[/mm]
Begründe nun, dass tatsächlich [mm] $I\not=\emptyset$ [/mm] gilt, indem du ein Element [mm] $\sigma\in [/mm] I$ angibst.
> 2)
>
> Ich weiß, dass [mm]X\in\mathcal{F}[/mm] und [mm]X\subseteq Y\subseteq I[/mm]
> gilt und soll nun zeigen, dass [mm]Y\in\mathcal{F}[/mm].
Ja.
> Weil [mm]Y[/mm] eine Obermenge von [mm]X[/mm] ist, und [mm]X\in\mathcal{F}[/mm]. Also
> ist [mm]\tau[/mm] bereits in [mm]Y[/mm].
Was meinst du hier mit [mm] $\tau$?
[/mm]
Weil [mm] $X\in\mathcal{F}$ [/mm] gilt, existiert ein [mm] $\sigma\in [/mm] I$ mit [mm] $F(X,\sigma)$.
[/mm]
Gesucht ist nun ein [mm] $\sigma'\in [/mm] I$ mit [mm] $F(Y,\sigma')$.
[/mm]
(Wenn du keine Idee für [mm] $\sigma'$ [/mm] hast, schreibe zunächst die Abkürzungen [mm] $F(X,\sigma)$ [/mm] und [mm] $F(Y,\sigma')$ [/mm] aus.)
> Irgendwie erscheint es mir eigenartig, [mm]Y[/mm] unterscheidet sich
> ja nur so von [mm]X[/mm], dass es irgendwelche endlichen Teilmengen
> von L-Aussagen enthält, welche in [mm]X[/mm] nicht vorkommen.
(Außer wenn $Y=X$ gilt, aber dann ist ohnehin nichts mehr zu zeigen.)
> Nun
> ist [mm]X[/mm] ein Element von [mm]\mathcal{F}[/mm] und daher sind bereits
> alle Obermengen
aus $I$
> , zu einer bestimmten Menge [mm]\sigma[/mm] in [mm]X[/mm]
> enthalten. Daher sind diese Mengen auch in [mm]Y[/mm].
Genau.
Also leistet welche Wahl von [mm] $\sigma'$ [/mm] das Gewünschte?
> Ich muss die Menge [mm]\mathcal{F}[/mm] falsch verstehen...
> Der Teil [mm][\sigma\subseteq\tau\rightarrow \tau\in X][/mm]
> scheint mir nicht klar zu sein. Das kann ja nicht einfach
> heißen, dass alle Obermengen zu einer bestimmten Menge in
> X enthalten sein müssen.
Doch (alle Obermengen aus I zu einer bestimmten Menge aus I).
> Könnte ich als [mm]\sigma[/mm] nicht einfach dann die Menge
> wählen, welche keine L-Aussage enthält? Dann wäre doch
> [mm]\sigma\subseteq\tau[/mm] immer erfüllt und daher bereits alle
> endlichen Teilmengen in [mm]X[/mm].
Sei [mm] $X\subseteq [/mm] I$.
Wenn "man für [mm] $\sigma$ [/mm] die leere Menge wählen kann" (d.h. wenn [mm] $F(X,\emptyset)$ [/mm] gilt), dann folgt schon $X=I$.
Mit anderen Worten: Wenn nicht gerade $X=I$ gilt, kann man für [mm] $\sigma$ [/mm] nicht die leere Menge wählen.
Vielmehr "muss man [mm] $\sigma$ [/mm] genügend groß wählen", damit [mm] $F(X,\sigma)$ [/mm] gilt.
Um dies zu präzisieren:
Seien [mm] $X\subseteq [/mm] I$ und [mm] $\sigma,\sigma'\in [/mm] I$.
Falls [mm] $F(X,\sigma)$ [/mm] und [mm] $\sigma\subseteq\sigma'$ [/mm] gelten, so gilt auch [mm] $F(X,\sigma')$.
[/mm]
Man kann also jedes [mm] $\sigma\in [/mm] I$ in diesem Sinne durch beliebige Obermengen [mm] $\sigma'\in [/mm] I$ ersetzen.
Mit [mm] $\sigma=\emptyset$ [/mm] ist [mm] $F(X,\sigma)$ [/mm] gerade am schwierigsten zu erfüllen.
Präzise: Wenn [mm] $F(X,\emptyset)$ [/mm] für ein [mm] $X\subseteq [/mm] I$ gilt, dann schon [mm] $F(X,\sigma')$ [/mm] für alle [mm] $\sigma'\in [/mm] I$.
> Hier stehen jetzt wahrscheinlich viele wirre Gedanken...
Das finde ich nicht.
Viele Grüße
Tobias
|
|
|
|
