www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Logik" - Filter, Theorie
Filter, Theorie < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Filter, Theorie: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:58 So 17.05.2015
Autor: impliziteFunktion

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.

        
Bezug
Filter, Theorie: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Logik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]