Matroids Matheplanet Forum Index
Forumbereich moderiert von: Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Sprachen und Konstanten
Druckversion
Druckversion
Universität/Hochschule J Sprachen und Konstanten
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-10-18

Hallo,

(Ich weiß leider nicht ob das hier wirklich zu Logik gehört, aber wir behandeln diese Themen in unserer Logikvorlesung)

Ich versuche gerade Sprachen und Strukturen zu verstehen, stehe aber vor einer ziemlichen Wand. Die Konzepte sind so fremd für mich und ich finde auch kaum Resourcen dazu. Vielleicht ein kleines Beispiel:

In folgender Aufgabe wird gefragt ob zwei Strukturen isomorph zueinander sind. Zuerst möchte ich aber erst einmal die Begriffe selber verstehen bevor ich überhaupt daran denke mich an der Aufgabe zu versuchen. Die erste hälfte:

"In der Sprache $\mathcal{L} = \{c, <\}$ seien c ein Konstantenzeichen und < ein zweistelliges Relationszeichen. Betrachte die $\mathcal{L}$-Struktur $\mathcal{R}_{1}$ mit Universum $\mathbb{R}$ und den Interpretationen $c^{\mathcal{R}_{1}} = \pi$ sowie $<^{\mathcal{R}_{1}}$ als die übliche lineare Ordnung[...]"

Wir haben eine Sprache als eine Menge an Konstanten- Funktions- und Relationszeichen definiert und eine Struktur, als eine nicht-leere Menge die wiederum eine Menge, genannt das Universum, enthält sowie die Interpretationen der Konstanten/Funktions/Relationszeichen der Sprache.

Ich versteh jetzt z.B. gar nicht WAS genau hier betrachtet wird. Die Relation < wird also als die kleiner Relation definiert wie ich sie kenne oder? Also auf den reellen Zahlen. Aber was hat dann z.B. die Konstante für einen Sinn? Das Universum ist $\mathbb{R}$ und es ist ja aber $\pi \in \mathbb{R}$ also welche Bedeutung hat es so eine Konstante festzulegen? Was "macht man" mit dieser Konstante beziehungsweise so einer Struktur überhaupt?

Die zweite Struktur sei wie die erste, bloß das die Konstante nicht $\pi$ sondern $-\sqrt{2}$ ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, vom Themenstarter, eingetragen 2020-10-18

Ich habe mir jetzt einmal folgendes überlegt und würde mich freuen wenn mir jemand sagen kann ob ich dies alles richtig oder total falsch interpretiere:

Wir haben die Sprache $\mathcal{L} = \{c, <\}$ welche mir zusammen mit Mengen eine Struktur definiert mit denen ich dann bestimmte Eigenschaften anwenden kann, die durch die explizite Sprache beschränkt sind. (Das heißt, weil z.B. ein Funktionszeichen + fehlt betrachte ich hier nicht die Addition auf den Reellen Zahlen sondern lediglich die kleiner Relation.) Nun habe ich Strukturen:

$\mathcal{R}_{1} = (\mathbb{R}, \{\pi\}, \{<^{\mathcal{R}_{1}}\})$
$\mathcal{R}_{2} = (\mathbb{R}, \{-\sqrt{2}\}, \{<^{\mathcal{R}_{2}}\})$ wobei das kleiner Zeichen in beiden Strukturen für die bekannte binäre Relation steht. Nun möchte ich zeigen, dass diese Strukturen Isomorph sind. Ich muss also eine bijektive Einbettung $F: \mathbb{R} \rightarrow \mathbb{R}$ die bestimmte Eigenschaften erfüllt finden. Nämlich:

1. Konstante werden auf Konstanten abgebildet
2. Wenn $r' < r$ bezüglich der ersten Struktur, dann $F(r') < F(r)$ bezüglich der zweiten Struktur.

Man kann sich nun eine Abbildung definieren, nämlich: $F: \mathbb{R} \rightarrow \mathbb{R}, r \mapsto r - (\pi + \sqrt{2})$

Mit dieser Abbildung gilt:

1. $F(\pi) = -\sqrt{2}$
2. $(r', r) \in <^{\mathcal{R}_{1}} \Leftrightarrow (F(r'), F(r)) \in <^{\mathcal{R}_{2}}$ denn es gilt definitiv $r' < r \Leftrightarrow r' - (\pi + \sqrt{2}) < r - (\pi + \sqrt{2})$

Außerdem hat diese Einbettung eine Umkehrabbildung indem man einfach das - zu + macht und ist somit eine bijektive Abbildung zwischen zwei gleich-mächtigen Mengen.

War davon jetzt schon etwas richtig oder liege ich hier komplett falsch?

Mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, eingetragen 2020-10-18

Deine Lösung ist vollkommen richtig. 👍

Ich würde mir bei der Aufgabe nicht zu viel Gedanken über den Sinn machen. Es geht eigentlich nur darum, sich mit den Begrifflichkeiten aus der Logik etwas vertraut zu machen, indem man sich konkrete Beispiele anschaut.

Ganz kurz zu den Begriffen (mehr findest du in Lehrbüchern zur mathematischen Logik): Eine Sprache ist eine "Schablone" für Strukturen. Sie legt fest, wieviele Konstanten, wieviele Verknüpfungen (welcher Stelligkeiten) und wieviele Relationen (welcher Stelligkeiten) wir betrachten möchten. Konstanten sind eigentlich nichts anderes als $0$-stellige Verknüpfungen, sodass man diese nicht extra betrachten muss. Eine Struktur einer Sprache ist eine "konkrete Realisierung" der Sprache. Sprich, man sagt, welche Grundmenge mit welchen Konstanten, Verknüpfungen und Relationen konkret man betrachten möchte.

Noch einmal anders ausgedrückt: die Sprache legt fest, welche Zeichen erlaubt sind (Syntax), und eine Struktur legt fest, welche Bedeutung wir den Zeichen geben (Semantik).

Üblicherweise sind diese Srukturen allerdings zu allgemein. Man möchte noch weitere Gesetzmäßigkeiten, also Axiome, fordern. Genauer gesagt definiert man eine Theorie als eine Menge von Sätzen (also Formeln ohne freie Variablen) in der gegebenen Sprache, und ein Modell dieser Theorie als eine Struktur, in der diese Sätze gelten. Zum Beispiel ist eine Gruppe eine Struktur der Sprache $\{e^{[0]},i^{[1]},m^{[2]}\}$ (die Exponenten deuten die Stelligkeiten an), sodass die Gruppenaxiome (quantifiziert über alle $x,y,z$)

$m(x,e) = x, \, m(e,x) = x, \, m(x,m(y,z)) = m(m(x,y),z),\, m(x,i(x)) = x, \, m(i(x),x) = x$

gelten. Eine Gruppe ist nichts anderes als ein Modell der Theorie der Gruppen. Und eine lineare Ordnung ist eine Struktur der Sprache $\{\leq^{[2]}\}$, sodass die Axiome einer linearen Ordnung (quantifiziert über alle $x,y,z$)

$x \leq x, \, x \leq y \wedge y \leq z \implies x \leq z,\, x \leq y \leq x \implies x = y,\, x \leq y \vee y \leq x$

gelten. Dieser Modellbegriff umfasst also viele der dir bereits bekannten mathematischen Strukturen. Auch strukturerhaltende Abbildungen (Homomorphismen) und invertierbare strukturerhaltende Abbildungen (Isomorphismen) kann man nun in einem ganz allgemeinen Rahmen definieren und untersuchen.

Die Sprache $\{c^{[0]},<^{[2]}\}$ ist tatsächlich nicht besonders spannend und etwas willkürlich. Aber man könnte z. B. noch das Axiom $\forall x.\, c = x \vee c < x$ hinzufügen, sprich dass $c$ das kleinste Element sein soll. Ein Modell wäre dann zum Beispiel $([0,1],0,<)$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.3, vom Themenstarter, eingetragen 2020-10-19

2020-10-18 21:47 - Triceratops in Beitrag No. 2 schreibt:
Deine Lösung ist vollkommen richtig. 👍

Ich würde mir bei der Aufgabe nicht zu viel Gedanken über den Sinn machen. Es geht eigentlich nur darum, sich mit den Begrifflichkeiten aus der Logik etwas vertraut zu machen, indem man sich konkrete Beispiele anschaut.

Ganz kurz zu den Begriffen (mehr findest du in Lehrbüchern zur mathematischen Logik): Eine Sprache ist eine "Schablone" für Strukturen. Sie legt fest, wieviele Konstanten, wieviele Verknüpfungen (welcher Stelligkeiten) und wieviele Relationen (welcher Stelligkeiten) wir betrachten möchten. Konstanten sind eigentlich nichts anderes als $0$-stellige Verknüpfungen, sodass man diese nicht extra betrachten muss. Eine Struktur einer Sprache ist eine "konkrete Realisierung" der Sprache. Sprich, man sagt, welche Grundmenge mit welchen Konstanten, Verknüpfungen und Relationen konkret man betrachten möchte.

Noch einmal anders ausgedrückt: die Sprache legt fest, welche Zeichen erlaubt sind (Syntax), und eine Struktur legt fest, welche Bedeutung wir den Zeichen geben (Semantik).

Üblicherweise sind diese Srukturen allerdings zu allgemein. Man möchte noch weitere Gesetzmäßigkeiten, also Axiome, fordern. Genauer gesagt definiert man eine Theorie als eine Menge von Sätzen (also Formeln ohne freie Variablen) in der gegebenen Sprache, und ein Modell dieser Theorie als eine Struktur, in der diese Sätze gelten. Zum Beispiel ist eine Gruppe eine Struktur der Sprache $\{e^{[0]},i^{[1]},m^{[2]}\}$ (die Exponenten deuten die Stelligkeiten an), sodass die Gruppenaxiome (quantifiziert über alle $x,y,z$)

$m(x,e) = x, \, m(e,x) = x, \, m(x,m(y,z)) = m(m(x,y),z),\, m(x,i(x)) = x, \, m(i(x),x) = x$

gelten. Eine Gruppe ist nichts anderes als ein Modell der Theorie der Gruppen. Und eine lineare Ordnung ist eine Struktur der Sprache $\{\leq^{[2]}\}$, sodass die Axiome einer linearen Ordnung (quantifiziert über alle $x,y,z$)

$x \leq x, \, x \leq y \wedge y \leq z \implies x \leq z,\, x \leq y \leq x \implies x = y,\, x \leq y \vee y \leq x$

gelten. Dieser Modellbegriff umfasst also viele der dir bereits bekannten mathematischen Strukturen. Auch strukturerhaltende Abbildungen (Homomorphismen) und invertierbare strukturerhaltende Abbildungen (Isomorphismen) kann man nun in einem ganz allgemeinen Rahmen definieren und untersuchen.

Die Sprache $\{c^{[0]},<^{[2]}\}$ ist tatsächlich nicht besonders spannend und etwas willkürlich. Aber man könnte z. B. noch das Axiom $\forall x.\, c = x \vee c < x$ hinzufügen, sprich dass $c$ das kleinste Element sein soll. Ein Modell wäre dann zum Beispiel $([0,1],0,<)$.

Danke, das war eine wirklich tolle Erklärung. Vielen dank für die Mühe. Ich bin auch froh, dass nicht nur ich das Gefühl habe das dies alles ein wenig willkürlich gewirkt hat :D Aber es geht ja eben darum die Begriffe zu lernen.

Ich hab noch eine Zusatzfrage. Nehmen wir an wir erweitern beide Strukturen um eine weitere Konstante d. Und nehmen wir erst einmal an wir betrachten zwei allgemeine Strukturen, sagen wir $\mathcal{A}$ und $\mathcal{B}$. Diese sehen folgendermaßen aus:

$\mathcal{A} = (A, c^{\mathcal{A}}, d^{\mathcal{A}}, <_{\mathcal{A}}^{[2]})$
$\mathcal{B} = (B, c^{\mathcal{B}}, d^{\mathcal{B}}, <_{\mathcal{B}}^{[2]})$

Wenn ich jetzt Isomorphie zwischen den beiden $\mathcal{L}$-Strukturen untersuchen will (mit $\mathcal{L} = \{c^{[0]}, d^{[0]}, <^{[2]}\}$ ) wie sieht das dann mit der Regel über Konstanten aus? Mein Skript besagt "Für jedes Konstantenzeichen c aus $\mathcal{L}$ ist $F(c^{\mathcal{A}}) = c^{\mathcal{B}}$".

Bei einer Konstante habe ich diese Aussage noch nicht hinterfragt, da es dort ja offensichtlich nur eine Abbildungsart zwischen den beiden Konstanten, nämlich eben die eine auf die andere, gab. Wie sieht es nun aber mit mehreren Konstanten aus? Muss c von A auf c von B abgebildet werden, analog mit d? Oder kann c von a auf d von B und d von a auf c von B abgebildet werden? Wie ist diese Aussage aus dem Skript zu verstehen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.4, eingetragen 2020-10-19

2020-10-19 12:01 - MePep in Beitrag No. 3 schreibt:
Muss c von A auf c von B abgebildet werden, analog mit d?

So ist es.

Zum Beispiel soll ein Ringhomomorphismus die Null auf die Null und die Eins auf die Eins abbilden, nicht die Eins auf die Null oder so.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.5, vom Themenstarter, eingetragen 2020-10-19

2020-10-19 12:11 - Triceratops in Beitrag No. 4 schreibt:
2020-10-19 12:01 - MePep in Beitrag No. 3 schreibt:
Muss c von A auf c von B abgebildet werden, analog mit d?

So ist es.

Zum Beispiel soll ein Ringhomomorphismus die Null auf die Null und die Eins auf die Eins abbilden, nicht die Eins auf die Null oder so.

Also, zum Abschluss dieses threads, wenn die zuvor genannten Strukturen $\mathcal{R}_{1}$ und $\mathcal{R}_{2}$ um ein d erweitert werden, und zwar mit $d^{\mathcal{A}}$ = 0 = $d^{\mathcal{B}}$, dann wären es keine Isomorphen Strukturen mehr, da durch die Abbildung und die kleiner Relation dann gelten müsste: $0 < \pi$ und damit auch $0 < -\sqrt{2}$ was falsch ist ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.6, eingetragen 2020-10-19

Das geht schon in die richtige Richtung. Du schreibst "die Abbildung". Meinst du damit den von dir genannten Isomorphismus? Das würde nicht ausreichen. Du musst die Existenz eines beliebigen Isomorphismus widerlegen. Schreibe es am besten einmal etwas ausführlicher auf.

Kennst du schon Begriff der elementaren Äquivalenz? Damit kann man das Argument noch etwas besser auf den Punkt bringen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 08.05.2020, Mitteilungen: 167
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.7, vom Themenstarter, eingetragen 2020-10-19

2020-10-19 15:11 - Triceratops in Beitrag No. 6 schreibt:
Das geht schon in die richtige Richtung. Du schreibst "die Abbildung". Meinst du damit den von dir genannten Isomorphismus? Das würde nicht ausreichen. Du musst die Existenz eines beliebigen Isomorphismus widerlegen. Schreibe es am besten einmal etwas ausführlicher auf.

Kennst du schon Begriff der elementaren Äquivalenz? Damit kann man das Argument noch etwas besser auf den Punkt bringen.

Ja den Begriff kenne ich, dieser darf aber meines erachtens noch nicht für diese Aufgabe vorrausgesetzt werden. Man muss dann lediglich über Ismorphie argumentieren.

Mit Abbildung meinte ich eine bijektive Abbildung. Es stimmt das ich vermutlich nicht sagen sollte "auf diese Art geht es nicht" sondern das es eben keinen Isomorphismus geben kann (das ist meine Annahme, das es keinen geben kann. Die Frage mit der erweiterten Sprache war ob es sich immer noch um Isomorphe Strukturen handelt). Jedenfalls müsste für eine, wie in meinem Skript beschriebene bijektive Einbettung, ja die Regel mit den Relationen gelten, also

"$(a_{1},...,a_{n})$ liegt genau dann in R$^{\mathcal{A}}$, wenn $(F(a_{1}),...,F(a_{n}))$ in R$^{\mathcal{B}}$ liegt."

Aber die Eigenschaft, dass $F(\pi) = -\sqrt{2}$ und $F(0) = 0$ gelten muss gilt ja für jeden potentiell möglichen Isomorphismus zwischen den Strukturen oder? Weil anhand davon wollte ich irgendwie argumentieren, dass mit diesen Werten dann die Relation verletzt wird. Oder ist das doch nicht der richtige Weg? Weil bei dieser Argumentation geht es ja nichtmal unbedingt um einen Isomorphismus, sondern eben vielleicht auch nur eine Injektive Abbildung... jetzt bin ich mir gerade etwas unsicher. Aber vielleicht ist dadurch eben einfach keine Einbettung mehr möglich weil die Interpretationen dies nicht zulassen? Sorry falls ich noch etwas wirr schreibe 🙄. Ich finde das alles echt abstrakt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 28.04.2016, Mitteilungen: 4989, aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.8, eingetragen 2020-10-19

Du hast das schon ganz richtig verstanden. 👍

Und man kann hier auch sehen, dass es gar keinen Homomorphismus zwischen den beiden Strukturen gibt (egal in welche Richtung).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep hat die Antworten auf ihre/seine Frage gesehen.
MePep hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]