Substrukturen, (N, +) < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie:
1) [mm] $(\mathbb{N},+)$ [/mm] hat unendlich viele verschiedene Substrukturen, die isomorph zu [mm] $(\mathbb{N},+)$ [/mm] sind.
2) Jede elementare Substruktur von [mm] $(\mathbb{N}, [/mm] +)$ ist gleich [mm] $(\mathbb{N}, [/mm] +)$ |
Hallo,
ich habe eine Frage zu dieser Aufgabe.
Erstmal zu 1):
Ich soll zeigen, dass [mm] $(\mathbb{N},+)$ [/mm] unendlich viele verschiedene Substrukturen hat, die isomorph zu [mm] $(\mathbb{N},+)$ [/mm] sind.
Ich muss also Mengen angeben, für die die Identität ein injektiver Homomorphismus ist. Damit ich die Isomorphie bekomme, muss ich noch zeigen, dass die Abbildung surjektiv ist.
Die erste Frage ist dann natürlich wie die Substrukturen von [mm] $\mathbb{N}$ [/mm] aussehen.
Mein erster Gedanke ist, dass sie die Substrukturen von [mm] $\mathbb{N}$ [/mm] die Mengen der Form [mm] $k\mathbb{N}$ [/mm] sind, also jeweils alle durch k-teilbaren natürlichen Zahlen enthalten. Wobei [mm] $k\neq [/mm] 0, [mm] k\in\mathbb{N}$. [/mm] Jedenfalls ist es mein Gedanke, dass diese Trägermengen isomorphe Substrukturen sind.
Eine Substruktur von [mm] $(\mathbb{N}, [/mm] +)$ wären ja auch alle Mengen natürlicher Zahlen wo ich endlich viele Elemente herausnehme, oder?
Etwa wäre [mm] $(\mathbb{N}\setminus\{1,2,3\},+)$ [/mm] eine Substruktur von [mm] $(\mathbb{N},+)$. [/mm] Sehe ich das richtig?
Nun ja, wie gesagt vermute ich, dass die isomorphen Substrukturen von [mm] $(\mathbb{N},+)$ [/mm] von der Form [mm] $(k\mathbb{N},+)$ [/mm] sind.
Offensichtlich gilt [mm] $k\mathbb{N}\subseteq\mathbb{N}$ [/mm] und
[mm] $\operatorname{id}:k\mathbb{N}\to\mathbb{N}$ [/mm] ist injektiv.
Jetzt brauch ich noch die Eigenschaft des Homomorphismus.
Dabei ist mir vielleicht die Definition zu abstrakt...
So haben wir es definiert:
Angenommen [mm] \mathcal{M}=(M,(z^{\mathcal{M}})_{z\in L}), \mathcal{N}=(M,(z^{\mathcal{N}})_{z\in L}) [/mm] sind L-Strukturen und $h: [mm] M\to [/mm] N$
$h$ ist ein Homomorphismus wenn für alle $n$ und alle [mm] $a_0,\dotso, a_{n-1}\in [/mm] M$
a) [mm] $h(c^{\mathcal{M}})=c^{\mathcal{N}}$
[/mm]
b) [mm] $h(f^{\mathcal{M}}(a_0,\dotso,a_{n-1})=f^{\mathcal{N}}(h(a_0),\dotso,h(a_{n-1}))$
[/mm]
c) [mm] $R^{\mathcal{M}}(a_0,\dotso, a_{n-1})\Rightarrow R^{\mathcal{N}}(h(a_0),\dotso, h(a_{n-1}))$
[/mm]
Ich denke schon, dass ich weiß was es bedeutet, nur kann ich es wohl nicht umsetzen.
a) Bedeutet einfach, dass ich Konstantenzeichen auf Konstantenzeichen abbilde.
b) Bedeutet, dass wenn ich die Funktion h auf ein Funktionszeichen in [mm] $\mathcal{M}$ [/mm] anwende ich ein Funktionszeichen in [mm] $\mathcal{N}$ [/mm] erhalte, was ich eben auf die [mm] $h(a_i)\quad$ ($0\leq i\leq [/mm] n$) anwende. Also ich wende die Abbildung $h$ vorher an.
c) Wie in b) nur für Relationszeichen und das ich keine Gleichheit habe, also Relationszeichen "bleiben" Relationszeichen.
Was nun mein Problem ist, ist das ich nicht so recht weiß, wie ich es umzusetzen habe.
Ich muss ja eigentlich "nur" zeigen, dass die Identität hier ein injektiver Homomorphismus ist.
Die injektivität ist klar, aber wie zeige ich den Homomorphismus, wenn ich
[mm] $\operatorname{id}:k\mathbb{N}\to\mathbb{N}$ [/mm] mit
[mm] $n\mapsto k\cdot [/mm] n$
habe...
Über Anregungen und Korrekturen jeglicher Art würde ich mich sehr freuen.
Vielen Dank im voraus.
mfg
|
|
| |
|
Weiß jemand zu dieser Aufgabe Rat?
Es fällt mir schwer einen geeigneten Lösungsansatz zu finden. :(
Insbesondere weil der Homomorphismus mir Schwierigkeiten bereitet, bzw. ich dies nicht umsetzen kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:26 Di 28.04.2015 | | Autor: | hippias |
Ein paar grundsaetzliche Bemerkungen zuerst.
Da Deine Struktur nur eine $2$-stelliges Funktion hat, beschraenke ich mich auch nur auf diese Situation und ignoriere Konstanten und Relationen.
Eine Struktur $(A,+_{A})$, mit $2$-stelliger Funktion $+_{A}$, ist eine Substruktur von [mm] $(\IN,+)$, [/mm] wenn die Identitaet $id: [mm] (A,+_{A})\to (\IN,+)$ [/mm] ein Homomorphismus ist.
Dies bedeutet, dass $A$ Teilmenge von [mm] $\IN$ [/mm] ist. Ferner gilt fuer alle [mm] $a,b\in [/mm] A$, dass $id(a+_{A}b)= id(a)+id(b)$ ist: dies folgt aus der Definition eines Homomorphismus. Da $id$ die Identitaet ist, heisst dies, dass $a+_{A}b= a+b$ gilt. Also ist die Verknuepfung in $A$ einfach die Einschraenkung der Verknuepfung von [mm] $\IN$.
[/mm]
Ferner ist $+_{A}$ nach Definition eine Abbildung in $A$.
Es gilt dazu auch die Umkehrung:
Sei [mm] $\emptyset\neq A\subseteq \IN$ [/mm] und es gelte fuer alle [mm] $a,b\in [/mm] A$, dass [mm] $a+b\in [/mm] A$ ist (also $A$ ist unter Addition abgeschlossen). Dann ist $(A,+_{A})$ eine Substruktur von [mm] $(\IN,+)$, [/mm] wobei $+_{A}:= [mm] (A\times A)\cap [/mm] +$ die Einschraenkung von $+$ auf [mm] $A\times [/mm] A$ ist.
Versuche ruhig, dies einmal zu beweisen.
Mit diesem Kriterium laesst sich Deine Aufgabe gut bearbeiten. Insbesondere ergibt sich damit, dass Deine vermuteten Substrukturen tatsaechlich welche sind, denn alle Deine Vorschlaege sind nichtleere Teilmengen von [mm] $\IN$, [/mm] die additiv abgeschlossen sind.
Wenn $(A,+_{A})$ eine isomorphe Substruktur von [mm] $(\IN,+)$ [/mm] ist, dann bedeutet das nicht, dass die identische Abbildung ein Isomorphismus sein muss, sondern, dass es einen moeglicherweise anderen Isomorphismus zwischen den Strukturen gibt. Tatsaechlich ist die Identitaet genau ein Isomorphismus, wenn [mm] $(A,+_{A})=(\IN,+)$ [/mm] ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:51 Mi 29.04.2015 | | Autor: | tobit09 |
Hallo impliziteFunktion!
Das Wesentliche hat hippias schon erklärt, daher nur noch ein paar kleine Ergänzungen:
> Ich soll zeigen, dass [mm](\mathbb{N},+)[/mm] unendlich viele
> verschiedene Substrukturen hat, die isomorph zu
> [mm](\mathbb{N},+)[/mm] sind.
Ja.
> Die erste Frage ist dann natürlich wie die Substrukturen
> von [mm]\mathbb{N}[/mm] aussehen.
> Mein erster Gedanke ist, dass sie die Substrukturen von
> [mm]\mathbb{N}[/mm] die Mengen der Form [mm]k\mathbb{N}[/mm] sind, also
> jeweils alle durch k-teilbaren natürlichen Zahlen
> enthalten. Wobei [mm]k\neq 0, k\in\mathbb{N}[/mm]. Jedenfalls ist es
> mein Gedanke, dass diese Trägermengen isomorphe
> Substrukturen sind.
Ja, diese Mengen sind genau die Träger der zu [mm] $(\IN,+)$ [/mm] isomorphen Substrukturen von [mm] $(\IN,+)$.
[/mm]
> Eine Substruktur von [mm](\mathbb{N}, +)[/mm] wären ja auch alle
> Mengen natürlicher Zahlen wo ich endlich viele Elemente
> herausnehme, oder?
Wenn du die endlich vielen Elemente passend wählst: Ja.
> Etwa wäre [mm](\mathbb{N}\setminus\{1,2,3\},+)[/mm] eine
> Substruktur von [mm](\mathbb{N},+)[/mm]. Sehe ich das richtig?
Ja.
> Nun ja, wie gesagt vermute ich, dass die isomorphen
> Substrukturen von [mm](\mathbb{N},+)[/mm] von der Form
> [mm](k\mathbb{N},+)[/mm] sind.
Ja.
> Offensichtlich gilt [mm]k\mathbb{N}\subseteq\mathbb{N}[/mm]
Ja.
> und
>
> [mm]\operatorname{id}:k\mathbb{N}\to\mathbb{N}[/mm] ist injektiv.
Die Inklusionsabbildung [mm] $i\colon M\to\IN$ [/mm] ist für jedes [mm] $M\subseteq\IN$ [/mm] injektiv.
> Jetzt brauch ich noch die Eigenschaft des Homomorphismus.
> Dabei ist mir vielleicht die Definition zu abstrakt...
> So haben wir es definiert:
>
> Angenommen [mm]\mathcal{M}=(M,(z^{\mathcal{M}})_{z\in L}), \mathcal{N}=(M,(z^{\mathcal{N}})_{z\in L})[/mm]
> sind L-Strukturen und [mm]h: M\to N[/mm]
>
> [mm]h[/mm] ist ein Homomorphismus wenn für alle [mm]n[/mm] und alle
> [mm]a_0,\dotso, a_{n-1}\in M[/mm]
>
> a) [mm]h(c^{\mathcal{M}})=c^{\mathcal{N}}[/mm]
>
> b)
> [mm]h(f^{\mathcal{M}}(a_0,\dotso,a_{n-1})=f^{\mathcal{N}}(h(a_0),\dotso,h(a_{n-1}))[/mm]
>
> c) [mm]R^{\mathcal{M}}(a_0,\dotso, a_{n-1})\Rightarrow R^{\mathcal{N}}(h(a_0),\dotso, h(a_{n-1}))[/mm]
>
> Ich denke schon, dass ich weiß was es bedeutet, nur kann
> ich es wohl nicht umsetzen.
>
> a) Bedeutet einfach, dass ich Konstantenzeichen auf
> Konstantenzeichen abbilde.
Konstantenzeichen sind fester Bestandteil der Sprache $L$ und nicht Gegenstand einer Abbildung.
Vielmehr bildet h die Interpretation jedes einzelnen Konstantenzeichens in [mm] $\mathcal{M}$ [/mm] auf die Interpretation dieses Konstantenzeichens in [mm] $\mathcal{N}$ [/mm] ab.
> b) Bedeutet, dass wenn ich die Funktion h auf ein
> Funktionszeichen in [mm]\mathcal{M}[/mm] anwende ich ein
> Funktionszeichen in [mm]\mathcal{N}[/mm] erhalte, was ich eben auf
> die [mm]h(a_i)\quad[/mm] ([mm]0\leq i\leq n[/mm]) anwende. Also ich wende die
> Abbildung [mm]h[/mm] vorher an.
>
> c) Wie in b) nur für Relationszeichen und das ich keine
> Gleichheit habe, also Relationszeichen "bleiben"
> Relationszeichen.
Auch bei b) und c) geht es jeweils um die Verträglichkeit von $h$ mit der Interpretation der Zeichen in [mm] $\mathcal{M}$ [/mm] bzw. [mm] $\mathcal{N}$, [/mm] weniger um die Zeichen selbst.
> Was nun mein Problem ist, ist das ich nicht so recht weiß,
> wie ich es umzusetzen habe.
In unserer Aufgabe besteht die Sprache L nur aus einem zweistelligen Funktionszeichen $+$.
Eine Abbildung [mm] $h\colon M\to [/mm] N$ für $L$-Strukturen [mm] $\mathcal{M}=(M,+^{\mathcal{M}})$ [/mm] und [mm] $\mathcal{N}=(N,+^{\mathcal{N}})$ [/mm] ist genau dann ein Homomorphismus, wenn
[mm] $h(m_1+^{\mathcal{M}}m_2)=h(m_1)+^{\mathcal{N}}h(m_2)$
[/mm]
für alle [mm] $m_1,m_2\in [/mm] M$ gilt.
> Ich muss ja eigentlich "nur" zeigen, dass die Identität
> hier ein injektiver Homomorphismus ist.
> Die injektivität ist klar, aber wie zeige ich den
> Homomorphismus, wenn ich
>
> [mm]\operatorname{id}:k\mathbb{N}\to\mathbb{N}[/mm] mit
>
> [mm]n\mapsto k\cdot n[/mm]
>
> habe...
Die Inklusionsabbildung [mm] $i\colon k\IN\to\IN$ [/mm] bildet jedes [mm] $n\in k\IN$ [/mm] auf $n$ selbst und nicht auf $k*n$ ab.
Viele Grüße
Tobias
|
|
|
| |
|
> Wenn du die endlich vielen Elemente passend wählst: Ja.
Passend wählen sollte man die Elemente, wenn man sie "Lückenlos" wählt, also etwa wie in meinem Beispiel die Menge [mm] $\{1,2,3\}$ [/mm] aus den natürlichen Zahlen rausnimmt. Wenn ich etwa
[mm] $(\mathbb{N}\setminus\{1,5\},+)$ [/mm] betrachte, dann wäre dies keine Substruktur mehr. Ist dies richtig?
Denn dies wäre nicht mehr additiv abgeschlossen, da etwa 2+3=5 ist und 5 nicht mehr in der Menge enthalten ist.
Es spielt aber keine Rolle, wenn ich [mm] $(k\mathbb{N},+)$ [/mm] als Substruktur betrachte, dann hätte ich ja bereits unendlich viele gefunden.
Ich hätte nun also nichts weiter zu tun als einen Homomorphismus
$f: [mm] (k\mathbb{N},+)\to(\mathbb{N},+)$
[/mm]
anzugeben, welcher bijektiv ist?
> Konstantenzeichen sind fester Bestandteil der Sprache $ L $ und nicht
> Gegenstand einer Abbildung.
Das was ich hier glaube ich immer durcheinander bringe ist, dass ich denke die Konstantenzeichen wären die Zeichen aus der Trägermenge, hier also etwa die natürlichen Zahlen.
Wenn ich eine L-Struktur [mm] $(\mathbb{N},0,+)$ [/mm] hätte, dann wäre 0 ein Konstantenzeichen? Oder ist dieses Beispiel schlecht weil die Null in den natürlichen Zahlen vorkommt?
Sind die Elemente der Trägermenge dann stets Variablen?
> $ [mm] \operatorname{id}:k\mathbb{N}\to\mathbb{N} [/mm] $ mit
>
> $ [mm] n\mapsto k\cdot [/mm] n $
>
> habe...
> Die Inklusionsabbildung $ [mm] i\colon k\IN\to\IN [/mm] $ bildet jedes $ [mm] n\in k\IN [/mm] $ auf $ > n $ selbst und nicht auf $ [mm] k\cdot{}n [/mm] $ ab.
Stimmt...
Aber dann wäre diese Abbildung doch ein geeigneter Isomorphismus?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:55 Do 30.04.2015 | | Autor: | hippias |
> > Wenn du die endlich vielen Elemente passend wählst: Ja.
>
> Passend wählen sollte man die Elemente, wenn man sie
> "Lückenlos" wählt, also etwa wie in meinem Beispiel die
> Menge [mm]\{1,2,3\}[/mm] aus den natürlichen Zahlen rausnimmt. Wenn
> ich etwa
>
> [mm](\mathbb{N}\setminus\{1,5\},+)[/mm] betrachte, dann wäre dies
> keine Substruktur mehr. Ist dies richtig?
> Denn dies wäre nicht mehr additiv abgeschlossen, da etwa
> 2+3=5 ist und 5 nicht mehr in der Menge enthalten ist.
Richtig.
>
> Es spielt aber keine Rolle, wenn ich [mm](k\mathbb{N},+)[/mm] als
> Substruktur betrachte, dann hätte ich ja bereits unendlich
> viele gefunden.
>
> Ich hätte nun also nichts weiter zu tun als einen
> Homomorphismus
>
> [mm]f: (k\mathbb{N},+)\to(\mathbb{N},+)[/mm]
>
> anzugeben, welcher bijektiv ist?
Ja.
>
> > Konstantenzeichen sind fester Bestandteil der Sprache [mm]L[/mm] und
> nicht
> > Gegenstand einer Abbildung.
>
> Das was ich hier glaube ich immer durcheinander bringe ist,
> dass ich denke die Konstantenzeichen wären die Zeichen aus
> der Trägermenge, hier also etwa die natürlichen Zahlen.
>
> Wenn ich eine L-Struktur [mm](\mathbb{N},0,+)[/mm] hätte, dann
> wäre 0 ein Konstantenzeichen? Oder ist dieses Beispiel
> schlecht weil die Null in den natürlichen Zahlen
> vorkommt?
> Sind die Elemente der Trägermenge dann stets Variablen?
Es gibt Konstantenzeichen/symbole und die Belegung/Interpretation der Konstantenzeichen/symbole: die $0$ der natuerlichen Zahlen waere eine Interpretation eines Konstantensymbols. Dies ergibt sich aus der Symbolmange $L$. Wenn beispielsweise $L= [mm] \{f,c\}$ [/mm] ist, wobei $f$ ein $2$-stelliges Funktionssymbol und $c$ ein Kosntantensymbol ist, dann kann man $f$ als Addition $+$ und $c$ als $0$ interpretieren, sodass in diesem Sinne [mm] $(\IN,+,0)$ [/mm] eine $L$-Struktur ist.
>
> > [mm]\operatorname{id}:k\mathbb{N}\to\mathbb{N}[/mm] mit
> >
> > [mm]n\mapsto k\cdot n[/mm]
> >
> > habe...
>
> > Die Inklusionsabbildung [mm]i\colon k\IN\to\IN[/mm] bildet jedes
> [mm]n\in k\IN[/mm] auf [mm]> n[/mm] selbst und nicht auf [mm]k\cdot{}n[/mm] ab.
>
> Stimmt...
> Aber dann wäre diese Abbildung doch ein geeigneter
> Isomorphismus?
Schreib das mal genauer auf.
|
|
|
|
