Potenzmenge / Wohlfundiert

01.07.2009, 18:44	pi_mal_Daumen	Auf diesen Beitrag antworten »
Potenzmenge / Wohlfundiert Hallo ihr! Eigentlich sitze ich an ner Aufgabe zur Informatik (Theorie der Programmierung), aber ich denke, das Problem kann man auch von hier aus angehen. Ich soll zeigen, ob eine gegebene Halbordnung eine wohlfundierte Menge ist. Eine Halbordnung ist ein Paar $\begin{eqnarray} (M, \sqsubseteq) \end{eqnarray}$ , wobei M eine beliebige Menge ist und $\begin{eqnarray} \sqsubseteq \end{eqnarray}$ eine reflexive, transitive und antisymmetrische Relation ist. $\begin{eqnarray} (M, \sqsubseteq) \end{eqnarray}$ ist nun eine wohlfundierte Menge, wenn jede nichtleere Teilmenge von M ein minimales Element enthält: $\begin{eqnarray} \forall T \subseteq M: T \not= \emptyset \Rightarrow \exists m \in T: \forall n \in T: \neg (n \sqsubset m) \end{eqnarray}$ Als Satz haben wir noch bewiesen, dass *" $\begin{eqnarray} (M, \sqsubseteq) \end{eqnarray}$ ist wohlfundiert"* äquivalent ist zu "Es gibt keine unendliche, echt absteigende Folge von Elementen aus M" Jetzt stell ich mir die Frage, wie es sich mit der Halbordnung $\begin{eqnarray} (\mathcal{P}(\mathbb{N}), \subseteq) \end{eqnarray}$ verhält. Ich meine gehört zu haben, dass es sich hierbei nicht um eine wohlfundierte Menge handelt. Scheinbar gibt es eine echt absteigende, unendliche Folge mit Elementen (Teilmengen) aus $\begin{eqnarray} \mathcal{P}(\mathbb{N}) \end{eqnarray}$ . Hat einer eine Idee, wie diese Aussehen könnte? Ich hatte eigentlich ursprünglich vor, die Definition zu benutzen. Denn die Leere Menge ist doch eigentlich das minimale Element, welches für alle Teilmengen von der Potentzmenge eine Teilmenge ist. Aber irgendwie scheint da noch der Wurm drin zu sein, den ich nicht ganz verstehe. Hoffe jemand hat da eine Idee. Wenn das Thema in einen anderen Bereich besser passt, dann tuts mir leid :/
01.07.2009, 18:49	Leopold	Auf diesen Beitrag antworten »
So vielleicht? $\begin{eqnarray} \{ 1,2,3, \ldots \} \supset \{ 2,3,4, \ldots \} \supset \{ 3,4,5, \ldots \} \supset \ldots \end{eqnarray}$
01.07.2009, 18:58	pi_mal_Daumen	Auf diesen Beitrag antworten »
Hm. So simpel, aber dennoch einleuchtend. Verstehe nur dann nicht genau den Zusammenhang mit der Definition. Wenn doch gelten muss $\begin{eqnarray} \forall T \subseteq M: T \not= \emptyset \Rightarrow \exists m \in T: \forall n \in T: \neg (n \sqsubset m) \end{eqnarray}$ , dann ist doch die leere Menge eigentlich dieses Element, was das erforderte erfüllt. Oder wo liegt mein Denkfehler?! Aber dass die folge unendlich und echt absteigend ist lässt sich ja nicht anzweifeln! Danke! Dann gehe ich mal davon aus, dass z.B. etwas wie $\begin{eqnarray} (\lbrace A \in \mathcal{P}(\mathbb{N}) : A \textbf{ ist endlich} \rbrace, \subseteq) \end{eqnarray}$ eine wohlfundierte Menge im Sinne der Definition ist, richtig?
01.07.2009, 21:20	Leopold	Auf diesen Beitrag antworten »
Für jedes $\begin{eqnarray} k \in \mathbb{N} = \{ 1,2,3,\ldots \} \end{eqnarray}$ definieren wir $\begin{eqnarray} n_k = \{ k,k+1,k+2,\ldots \} \end{eqnarray}$ und fassen diese $\begin{eqnarray} n_k \end{eqnarray}$ zur Menge $\begin{eqnarray} T = \left\{ n_1,n_2,n_3,\ldots \right\} \end{eqnarray}$ zusammen. In der Menge $\begin{eqnarray} T \end{eqnarray}$ gibt es offenbar kein kleinstes Element $\begin{eqnarray} m \end{eqnarray}$ . Entscheidend ist die Forderung $\begin{eqnarray} m \in T \end{eqnarray}$ . Zwar gilt durchaus $\begin{eqnarray} \emptyset \subseteq n \end{eqnarray}$ für alle $\begin{eqnarray} n \in T \end{eqnarray}$ , aber $\begin{eqnarray} \emptyset \not \in T \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »