Durchschnitt, Differenz, Paare < axiomatisch < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 03:57 Mi 01.05.2013 | | Autor: | Lu- |
| Aufgabe | Formulieren Sie die Existenz von Durchschnitt und Mengendifferenz als first order Satz und beweisen Sie dies Existenz (mithilfe von Aussonderungsaxiom).
Beweisen sie außerdem ZFC [mm] \models \forall [/mm] x ,y,x',y' (x,y)=(x',y') -> x=x' [mm] \wedge [/mm] y=y' |
Skriptum!: http://www.logic.univie.ac.at/~kellner/teaching/2010SS_Grundbegriffe/Ziegler_2008-07.pdf
Seite 38 beginnt das Kapitel (erste 3 seiten nötig)
Existenz von Durchschnitten:
ZZ: [mm] \exists [/mm] z [mm] \forall [/mm] t (t [mm] \in [/mm] z <-> [mm] \phi(t))
[/mm]
Setzte z= x [mm] \cap [/mm] y Dann (t [mm] \in [/mm] x [mm] \cap [/mm] y <-> z [mm] \in [/mm] x [mm] \wedge [/mm] z [mm] \in [/mm] y)
z [mm] \in [/mm] x [mm] \wedge [/mm] z [mm] \in [/mm] y ist eine Formel
First-order:
Als Hilfestellung was ich meine hab ich Obertitel geschrieben.
[mm] \overbrace{\exists z \neg \exists t \neg}^{\exists z \forall t} \wedge \overbrace{\neg \wedge \in t z \neg \wedge \in zx \in z y}^{Richtung ->} \overbrace{\neg \wedge \wedge \in z x \in zy \neg \in t z}^{Richtung <-}
[/mm]
Darf man nun in der first-order [mm] \in [/mm] verwenden?
Existenz von Mengendifferenz:
ZZ: [mm] \exists [/mm] z [mm] \forall [/mm] t (t [mm] \in [/mm] z <-> [mm] \phi(t))
[/mm]
Setzte z= x [mm] \setminus [/mm] y Dann (t [mm] \in [/mm] x [mm] \setminus [/mm] y <-> z [mm] \in [/mm] x [mm] \wedge \neg [/mm] (z [mm] \in [/mm] y))
First-Order
[mm] \overbrace{\exists z \neg \exists t \neg}^{\exists z \forall t} \wedge \overbrace{\neg \wedge \in t z \neg \wedge \in zx \neg \in zy}^{Richtung ->} \overbrace{\neg \wedge \wedge \in zx \neg \in zy \neg \in t z}^{Richtung <-}
[/mm]
Natürlich kann man die t,z,y auch durch [mm] x^0, x^1, x^2 [/mm] ersetzten wie es sonst in der first order sprache ist (war mir hier zu langwierig)
Lemma : ZFC [mm] \models \forall [/mm] x ,y,x',y' (x,y)=(x',y') -> x=x' [mm] \wedge [/mm] y=y'
(x,y)= [mm] \{\{x\},\{x,y\}\}= \{\{x'\},\{x',y'\}\} [/mm] =(x',y')
Extensionalität: [mm] \forall [/mm] x,y [mm] (\forall z(z\in [/mm] x <-> z [mm] \in [/mm] y ) -> x=y )
[mm] \forall [/mm] a [mm] \in \{\{x\},\{x,y\}\} [/mm] -> a [mm] \in \{\{x'\},\{x',y'\}\}
[/mm]
-) [mm] \{ x\} \in {\{x'\},\{x',y'\}\}
[/mm]
[mm] \{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases}
[/mm]
Aus ersten Fall folgt x=x'.
Aber kann aus zweiten fall nicht auch folgen x=y' ?. Aus zweiten Fall folgt x=x' [mm] \vee [/mm] x=y'
[mm] -)\{ x,y \} \in \{\{x'\},\{x',y'\}\}
[/mm]
[mm] \{x', y'\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases}
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:23 Mi 01.05.2013 | | Autor: | tobit09 |
Hallo Lu-,
> Existenz von Durchschnitten:
> ZZ: [mm]\exists[/mm] z [mm]\forall[/mm] t (t [mm]\in[/mm] z <-> [mm]\phi(t))[/mm]
Mit [mm] $\phi(t):=t\in x\wedge t\in [/mm] y$.
Gemeint ist der sogenannte "All-Abschluss" der von dir angegebenen Formel, d.h. deine Formel mit vorangestelltem [mm] "$\forall x\forall [/mm] y$".
> Setzte z= x [mm]\cap[/mm] y
Was bedeutet das? Noch hast du ja gar nicht bewiesen, dass es so eine Menge $z$ gibt, die genau die Elemente enthält, die sowohl in x als auch in y enthalten sind.
> Dann (t [mm]\in[/mm] x [mm]\cap[/mm] y <-> z [mm]\in[/mm] x [mm]\wedge[/mm]
> z [mm]\in[/mm] y)
> z [mm]\in[/mm] x [mm]\wedge[/mm] z [mm]\in[/mm] y ist eine Formel
>
> First-order:
> Als Hilfestellung was ich meine hab ich Obertitel
> geschrieben.
> [mm]\overbrace{\exists z \neg \exists t \neg}^{\exists z \forall t} \wedge \overbrace{\neg \wedge \in t z \neg \wedge \in zx \in z y}^{Richtung ->} \overbrace{\neg \wedge \wedge \in z x \in zy \neg \in t z}^{Richtung <-}[/mm]
Wenn ich mich nicht vertan habe, ist das die ausführliche Schreibweise der obigen Formel. Ich glaube aber nicht, dass irgendjemand Lust hat, solche Formeln ohne abkürzende Schreibweisen zu entziffern. Ich denke, ihr habt nun genügend Übung darin, die abkürzenden Schreibweisen zu verstehen und könnt nun mit ihnen arbeiten, ohne Übersetzungen in die nicht abgekürzte Form vorzunehmen. Im Skript wird ja auch mit abkürzenden Schreibweisen gearbeitet.
> Darf man nun in der first-order [mm]\in[/mm] verwenden?
Ja. Schließlich enthält die Sprache [mm] $L_{\operatorname{Me}}=\{\in\}$ [/mm] der Mengenlehre ja das zweistellige Prädikatszeichen [mm] $\in$. [/mm] (Ich sehe gerade, dass ihr im Skript [mm] $\epsilon$ [/mm] statt [mm] $\in$ [/mm] schreibt. Vielleicht solltest du das dann so übernehmen.)
> Existenz von Mengendifferenz:
> ZZ: [mm]\exists[/mm] z [mm]\forall[/mm] t (t [mm]\in[/mm] z <-> [mm]\phi(t))[/mm]
> Setzte z= x [mm]\setminus[/mm] y Dann (t [mm]\in[/mm] x [mm]\setminus[/mm] y <-> z
> [mm]\in[/mm] x [mm]\wedge \neg[/mm] (z [mm]\in[/mm] y))
Hier gilt Analoges zu oben.
> First-Order
>
> [mm]\overbrace{\exists z \neg \exists t \neg}^{\exists z \forall t} \wedge \overbrace{\neg \wedge \in t z \neg \wedge \in zx \neg \in zy}^{Richtung ->} \overbrace{\neg \wedge \wedge \in zx \neg \in zy \neg \in t z}^{Richtung <-}[/mm]
Passt wieder, wenn ich mich nicht vertan habe.
> Natürlich kann man die t,z,y auch durch [mm]x^0, x^1, x^2[/mm]
> ersetzten wie es sonst in der first order sprache ist (war
> mir hier zu langwierig)
Gut, dass du das nicht getan hast!
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:26 Mi 01.05.2013 | | Autor: | Lu- |
Hallo,
> Existenz von Durchschnitten:
[mm] \forall [/mm] x [mm] \exists [/mm] z [mm] \forall [/mm] t (t [mm] \in [/mm] z <-> (z [mm] \in [/mm] x [mm] \wedge \phi(t)))
[/mm]
mit [mm] \phi(t):=z \in [/mm] y [mm] \forall [/mm] y
Nach Aussonderungsaxiom existiert solch eine Menge . Bezeichnet diese mit x [mm] \cap [/mm] y.
> Wenn ich mich nicht vertan habe, ist das die ausführliche Schreibweise der obigen Formel.
Aber genau dass war doch in der Aufgabenstellung verlangt.. die Existenz von Durchschnitt in first order Satz zu formulieren und das hab ich getan! Hätte ich was anders übersetzten müssen in first order? Oder was habe ich falsch verstanden in der Aufgabenstellung?
Existenz von Mengendifferenz
[mm] \forall [/mm] x [mm] \exists [/mm] z [mm] \forall [/mm] t (t [mm] \in [/mm] z <-> ( z [mm] \inx \wedge \phi(t)))
[/mm]
mit [mm] \phi)t)=\neg [/mm] ( z [mm] \in [/mm] y) [mm] \forall [/mm] y
Nach Aussonderungsaxiom existiert solch eine Menge, bezeichne diese mit x [mm] \setminus [/mm] y.
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:34 Mi 01.05.2013 | | Autor: | tobit09 |
> Lemma : ZFC [mm]\models \forall[/mm] x ,y,x',y' (x,y)=(x',y') ->
> x=x' [mm]\wedge[/mm] y=y'
>
> (x,y)= [mm]\{\{x\},\{x,y\}\}= \{\{x'\},\{x',y'\}\}[/mm] =(x',y')
> Extensionalität: [mm]\forall[/mm] x,y [mm](\forall z(z\in[/mm] x <-> z [mm]\in[/mm]
> y ) -> x=y )
> [mm]\forall[/mm] a [mm]\in \{\{x\},\{x,y\}\}[/mm] -> a [mm]\in \{\{x'\},\{x',y'\}\}[/mm]
Du brauchst dafür nicht einmal Extensionalität. Wenn zwei Mengen gleich sind, enthalten sie auch ohne Extensionalität die gleichen Elemente. Lediglich für die Umkehrung braucht man Extensionalität.
> -) [mm]\{ x\} \in {\{x'\},\{x',y'\}\}[/mm]
Genau.
> [mm]\{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases}[/mm]
Damit meinst du vermutlich, dass [mm] $\{x\}$ [/mm] mit mindestens einer der beiden Mengen auf der rechten Seite übereinstimmt.
> Aus ersten Fall folgt x=x'.
Genau.
> Aber kann aus zweiten fall nicht auch folgen x=y' ?. Aus
> zweiten Fall folgt x=x' [mm]\vee[/mm] x=y'
Genau. Im zweiten Fall folgt auch [mm] $x'\in\{x\}$.
[/mm]
Du weißt also in jedem Fall $x=x'$. Nun gilt es noch, $y=y'$ zu zeigen.
> [mm]-)\{ x,y \} \in \{\{x'\},\{x',y'\}\}[/mm]
> [mm]\{x', y'\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases}[/mm]
Auf der linken Seite meinst du sicherlich [mm] $\{x,y\}$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:37 Mi 01.05.2013 | | Autor: | Lu- |
> Genau.
> $ [mm] \{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases} [/mm] $
> Damit meinst du vermutlich, dass $ [mm] \{x\} [/mm] $ mit mindestens einer der beiden Mengen auf der rechten Seite übereinstimmt.
> Aus ersten Fall folgt x=x'.
> Genau.
> Aber kann aus zweiten fall nicht auch folgen x=y' ?. Aus
> zweiten Fall folgt x=x' $ [mm] \vee [/mm] $ x=y'
> Genau. Im zweiten Fall folgt auch $ [mm] x'\in\{x\} [/mm] $.
Aber:
[mm] \{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} => x =x' \\ \{x',y'\}:=\{z|z=x' \vee z=y'\}=>x=x' \vee x=y' \end{cases}
[/mm]
Die beiden Fälle sind doch durch ein ODER verbunden.
Wieso folgt daraus x=x' ?
> Auf der linken Seite meinst du sicherlich $ [mm] \{x,y\} [/mm] $.
Ja wenn ich dann schon weiß x=x' kann ich das hier nutzen:
$ [mm] \{x' , y\}=\begin{cases} \{x'\}:=\{z|z=x'\} => x'=x' \vee y=x' \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} => x'=x' \vee x'=y' \vee y=x' \vee y=y' \end{cases} [/mm] $
Hier habe ich dasselbe problem wie oben!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:07 Do 02.05.2013 | | Autor: | tobit09 |
> > [mm]\{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} \end{cases}[/mm]
>
> > Damit meinst du vermutlich, dass [mm]\{x\}[/mm] mit mindestens einer
> der beiden Mengen auf der rechten Seite übereinstimmt.
>
> > Aus ersten Fall folgt x=x'.
>
> > Genau.
>
> > Aber kann aus zweiten fall nicht auch folgen x=y' ?. Aus
> > zweiten Fall folgt x=x' [mm]\vee[/mm] x=y'
>
> > Genau. Im zweiten Fall folgt auch [mm]x'\in\{x\} [/mm].
>
> Aber:
> [mm]\{x\}=\begin{cases} \{x'\}:=\{z|z=x'\} => x =x' \\ \{x',y'\}:=\{z|z=x' \vee z=y'\}=>x=x' \vee x=y' \end{cases}[/mm]
>
> Die beiden Fälle sind doch durch ein ODER verbunden.
> Wieso folgt daraus x=x' ?
Im zweiten Fall hast du [mm] $x'\in\{x',y'\}=\{x\}$, [/mm] also $x'=x$.
> > Auf der linken Seite meinst du sicherlich [mm]\{x,y\} [/mm].
> Ja wenn ich dann schon weiß x=x' kann ich das hier
> nutzen:
> [mm]\{x' , y\}=\begin{cases} \{x'\}:=\{z|z=x'\} => x'=x' \vee y=x' \\ \{x',y'\}:=\{z|z=x' \vee z=y'\} => x'=x' \vee x'=y' \vee y=x' \vee y=y' \end{cases}[/mm]
>
> Hier habe ich dasselbe problem wie oben!
Im ersten Fall hast du [mm] $y\in\{x',y\}=\{x'\}$, [/mm] also $x'=y$ und somit schon $x=x'=y$. Wegen [mm] $\{x',y'\}=\{x\}$ [/mm] oder [mm] $\{x',y'\}=\{x,y\}$ [/mm] folgt [mm] $y'\in\ldots$.
[/mm]
Im zweiten Fall hast du [mm] $y\in\{x',y\}=\{x',y'\}$. [/mm] Also $y=x'$ oder $y=y'$. Im ersteren Fall kannst du wie oben weiterargumentieren. Im zweiten Fall bist du fertig.
Die Aufgabe läuft also auf viele Fallunterscheidungen hinaus.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:25 Do 02.05.2013 | | Autor: | Lu- |
Hallo
Woher nimmst du:
> Wegen $ [mm] \{x',y'\}=\{x\} [/mm] $ oder $ [mm] \{x',y'\}=\{x,y\} [/mm] $
im ersten Fall?
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:01 Do 02.05.2013 | | Autor: | tobit09 |
> Woher nimmst du:
> > Wegen [mm]\{x',y'\}=\{x\}[/mm] oder [mm]\{x',y'\}=\{x,y\}[/mm]
> im ersten Fall?
[mm] $\{x',y'\}\in\{\{x'\},\{x',y'\}\}=\{\{x\},\{x,y\}\}$.
[/mm]
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
Wenn du das [mm] $\forall [/mm] y$ in der drittletzten Zeile streichst, passt es! (Stattdessen wäre ein [mm] $\forall [/mm] y$ zu Beginn der langen Formel oben sinnvoll, um sie zu einem Satz zu machen. Es sei denn, ihr habt vereinbart, dass mit Formeln nun stets deren "All-Abschluss" gemeint ist.)
