Injektivität einer Struktur < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei L = L(f) die Sprache, die nur das 1-stellige Funktionszeichen f enthält.
(a) Geben Sie einen Satz σ an, so dass für jede L-Struktur A gilt:
A |= σ ⇔ [mm] f^A [/mm] ist injektiv.
(b) Wir nennen eine Funktion g : A → A quasi-injektiv, wenn jedes Element von A höchstens endlich viele Urbilder unter g besitzt.
Zeigen Sie, dass die Klasse D = {A : A ist L − Struktur und [mm] f^{A} [/mm] ist quasi-injektiv} nicht ∆-elementar ist. |
Hallo zusammen,
das ist eine Aufgabe vom letzten (Bonus) Aufgabenblatt und ich brauche dringend noch ein paar Punkte sonst werde ich nicht zur Klausur zugelassen :/
Leider habe ich hier keinen Ansatz wie man heir ran gehen muss und würde mich super mega über eure Hilfe freuen.
Danke und liebe Grüße,
An
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:17 So 01.02.2015 | | Autor: | hippias |
Fange damit an, dass Du ersteinmal die Definitionen von injektiv und [mm] $\Delta$-elementar [/mm] nennst. Dann versuche die Definition der Injektivitaet zu formalisieren.
|
|
|
| |
|
Hi hippias,
injektiv bei einer Struktur M=(d,δ) bedeutet das δ auf der Menge der Grundterme injektiv ist. Es gibt also auf der Menge der Grundterme keine Synonyme.
Leider ist mir nicht so klar wie man da anfängt sowas zu zeigen :/
Eine Klasse D heißt ja ∆-elementar, wenn sie die Modellklasse einer Theorie ist.
Bei ∆-elementar muss man ja meistens eine Theorie aufstellen, diese um ein Konstantensymbol erweitern, so dass sie nicht mehr ∆-elementar ist und dann bei einer Teilmenge davon zeigen das sie es doch ist und man einen widerspruch hat... :)
Du siehst schon das ich hier große Probleme habe, vieleicht hast du noch ein paar gute Tips, dass ich doch noch irgendwie die letzten paar Punkte zur Zulassung schaffe?
Grüße,
Daniel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:05 Mo 02.02.2015 | | Autor: | hippias |
> Hi hippias,
>
> injektiv bei einer Struktur M=(d,δ) bedeutet das δ auf
> der Menge der Grundterme injektiv ist. Es gibt also auf der
> Menge der Grundterme keine Synonyme.
> Leider ist mir nicht so klar wie man da anfängt sowas zu
> zeigen :/
Tja, das hat doch gar nichts mit der Aufgabenstellung zu tun: darin geht es um die Injektivitaet der Funktion [mm] $f^{A}:A\to [/mm] A$. Also auf ein neues...
>
> Eine Klasse D heißt ja ∆-elementar, wenn sie die
> Modellklasse einer Theorie ist.
>
> Bei ∆-elementar muss man ja meistens eine Theorie
> aufstellen, diese um ein Konstantensymbol erweitern, so
> dass sie nicht mehr ∆-elementar ist und dann bei einer
> Teilmenge davon zeigen das sie es doch ist und man einen
> widerspruch hat... :)
> Du siehst schon das ich hier große Probleme habe,
> vieleicht hast du noch ein paar gute Tips, dass ich doch
> noch irgendwie die letzten paar Punkte zur Zulassung
> schaffe?
Es geht ja um endliche Urbilder. Angenommen es gibt eine Satzmenge $T$, deren Modellklase $D$ ist.
Nun kannst Du Dir sicher Beispiele ueberlegen, in denen die Urbilder beliebig grosse, endliche Mengen sind. Sei [mm] $\phi_{n}$ [/mm] ein Satz, der ausdrueckt, dass alle Urbilder mindestens $n$ Elemente haben. Locker gesprochen sind [mm] $T\cup\{\phi_{1},\ldots, \phi_{n}\}$ [/mm] fuer alle $n$ erfuellbar. Aus dem Kompaktheitssatz kann man schlussfolgern, dass auch [mm] $T\cup\{\phi_{n}|n\in \IN\}$ [/mm] ein Modell $A$ hat. Dann folgt zwar [mm] $A\in [/mm] D$, aber [mm] $f^{A}$ [/mm] kann keine endlichen Urbildmengen haben.
So aehnlich stelle ich es mir vor.
>
> Grüße,
> Daniel
|
|
|
| |
|
Der Ausdruck [mm] \beta [/mm] = [mm] \forall [/mm] x ( [mm] \forall [/mm] y ( (Fx = F y) [mm] \rightarrow [/mm] (x =y )))
besagt die Injektivität von f.
Kommt mir von den Paeno Axiom bekannt vor, dort hatte ich ja ein ähnliches problem und konnte es auch nicht zeigen :/
zu deinem delta-elementar Kommentar, genau das meinte ich mit dem Kompaktheitssatz, aber inwiefern hat man damit meine Frage beantwort. Somit kann man ja nur zeigen das man es zu einem widerspruch führen kann oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:10 Di 03.02.2015 | | Autor: | hippias |
> Der Ausdruck [mm]\beta[/mm] = [mm]\forall[/mm] x ( [mm]\forall[/mm] y ( (Fx = F y)
> [mm]\rightarrow[/mm] (x =y )))
> besagt die Injektivität von f.
Richtig.
> Kommt mir von den Paeno Axiom bekannt vor, dort hatte ich
> ja ein ähnliches problem und konnte es auch nicht zeigen
> :/
Verstehe ich nicht: was willst Du noch zeigen?
>
> zu deinem delta-elementar Kommentar, genau das meinte ich
> mit dem Kompaktheitssatz,
Wie bitte? Wo hast Du denn bisher den Kompaktheitssatz erwaehnt?
> aber inwiefern hat man damit
> meine Frage beantwort. Somit kann man ja nur zeigen das man
> es zu einem widerspruch führen kann oder?
Koenntest Du bitte vernueftig zu mir sprechen und nicht in diesem Rumpel-Deutsch? Ich verstehe naemlich beim besten Willen nicht, was Du mir damit sagen moechtest. Mein "delta-elementar Kommentar" liefert Dir ein Beweisgeruest, mit dem Du Deine Aussage beweisen kannst. Versuche es umzusetzten oder stelle eine konkrete Frage. Ich werde Deine Hausaufgaben naemlich nicht erledigen.
|
|
|
| |
|
hi hippias,
tut mir leid wenn du mein deutsch nicht so gut verstehst, leider ist es für mich schwierig mich auszudrücken wenn man die Aufgabe nicht versteht und keinen Ansatz hat wie es funktioniert.
Ein Beispiel für beliebig große endliche Mengen wäre eine Menge von 1,..,n mit n [mm] \in \IN [/mm] welche auf ihre quadrat Zahlen abgeildet werden.
Nun verstehe ich deine Idee bis zu dem Punkt in dem du schreibst "dass auch $ [mm] T\cup\{\phi_{n}|n\in \IN\} [/mm] $ ein Modell $ A $ hat. Dann folgt zwar $ [mm] A\in [/mm] D $, aber $ [mm] f^{A} [/mm] $ kann keine endlichen Urbildmengen haben. "
was genau ist denn D und wieso kann [mm] f^{A} [/mm] hier keine endlichen Urbildermengen haben, ist $ [mm] T\cup\{\phi_{1},\ldots, \phi_{n}\} [/mm] $ unendlich?
Zur a) habe ich nach wie vor keinen Ansatz. Fragen wie geben sie einen Satz an, so dass... finde ich immer schwierig. Wie kommt man denn nun darauf einen Satz anzugeben welcher $ [mm] \beta [/mm] $ = $ [mm] \forall [/mm] $ x ( $ [mm] \forall [/mm] $ y ( (Fx = F y) $ [mm] \rightarrow [/mm] $ (x =y ))) erfüllt? Aus dem Stehgreif kann ich das leider nicht und weiss auch einfach nicht wie man das zeigt.
Wiegesagt geht es hier auch nicht mehr um Hausaufgaben, sondern um eine freiwillige Aufgabe welche es mir möglich gemacht hätte doch noch eine Zulassung zur Klausur zu bekommen, wäre natürlich sehr wichtig für mich :/
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:54 Do 05.02.2015 | | Autor: | AnnaK1990 |
ah sorry D ist die Modellklasse, hatte ich überlesen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:17 Fr 06.02.2015 | | Autor: | hippias |
> hi hippias,
>
> tut mir leid wenn du mein deutsch nicht so gut verstehst,
> leider ist es für mich schwierig mich auszudrücken wenn
> man die Aufgabe nicht versteht und keinen Ansatz hat wie es
> funktioniert.
Manchmal hilft es schon, wenn man wenigstens die Grundlregeln der Orthographie und Interpunktion beruecksichtigt.
> Ein Beispiel für beliebig große endliche Mengen wäre
> eine Menge von 1,..,n mit n [mm]\in \IN[/mm] welche auf ihre quadrat
> Zahlen abgeildet werden.
Ich sagte: [mm] $\phi_{k}$ [/mm] soll ausdruecken, dass alle Urbilder von $f$ mindestens $k$ Elemente haben. Dein Vorschlag hat damit nichts zu tun. Im uebrigen muss die Interpretation von $f$ nach Definition stets die Grundmenge der Interpretation in die die Grundmenge abbilden; dies waere bei Deinem Vorschlag nicht gegeben. Darueber hinaus ist die Abbildung [mm] $\IN\ni [/mm] n [mm] \mapsto n^{2}\in \IN$ [/mm] injektiv, hat also hoechstens $1$ Urbild.
>
> Nun verstehe ich deine Idee bis zu dem Punkt in dem du
> schreibst "dass auch [mm]T\cup\{\phi_{n}|n\in \IN\}[/mm] ein Modell
> [mm]A[/mm] hat. Dann folgt zwar [mm]A\in D [/mm], aber [mm]f^{A}[/mm] kann keine
> endlichen Urbildmengen haben. "
>
> was genau ist denn D
Diese Bezeichnung wurde doch von Dir selbst gewaehlt.
> und wieso kann [mm]f^{A}[/mm] hier keine
> endlichen Urbildermengen haben,
Wie gesagt: wenn [mm] $\phi_{n}$ [/mm] bedeutet, dass die Urbilder [mm] $f^{A}$ [/mm] mindestens $n$ Elemente haben. Wenn [mm] $f^{A}$ [/mm] dies fuer alle $n$ erfuellt, dann ist jedes Urbild unendlich.
> ist [mm]T\cup\{\phi_{1},\ldots, \phi_{n}\}[/mm]
> unendlich?
Was soll das bedeuten?
>
> Zur a) habe ich nach wie vor keinen Ansatz. Fragen wie
> geben sie einen Satz an, so dass... finde ich immer
> schwierig. Wie kommt man denn nun darauf einen Satz
> anzugeben welcher [mm]\beta[/mm] = [mm]\forall[/mm] x ( [mm]\forall[/mm] y ( (Fx = F
> y) [mm]\rightarrow[/mm] (x =y ))) erfüllt? Aus dem Stehgreif kann
> ich das leider nicht und weiss auch einfach nicht wie man
> das zeigt.
Man kommt darauf mittels Intuition. Unverzichtbare Grundlage ist, dass man das Vokabular lernt und die Aufgabenstellung aufmerksam liest. Du sollst laut Aufgabenstellung einen Satz angeben. Das hast Du getan. Jetzt aber schreibst Du
> ... einen Satz
> anzugeben welcher [mm]\beta[/mm] = [mm]\forall[/mm] x ( [mm]\forall[/mm] y ( (Fx = F
> y) [mm]\rightarrow[/mm] (x =y ))) erfüllt?
Das ist erstens nicht die Aufgabenstellung und zweitens ergibt es komplett keinen Sinn zu sagen "einen Satz anzugeben, der einen anderen Satz erfuellt". Der obige Satz ist also bereits die Loesung der Aufgabe! Eventuell wird noch erwartet, dass Du nachrechnest, dass er Injektivitaet formalisiert.
> Wiegesagt geht es hier auch nicht mehr um Hausaufgaben,
> sondern um eine freiwillige Aufgabe welche es mir möglich
> gemacht hätte doch noch eine Zulassung zur Klausur zu
> bekommen, wäre natürlich sehr wichtig für mich :/
Dann streng Dich an: schnapp Dir ein paar Buecher aus der Bib und los gehts. Viele vor Dir haben es geschafft und Du kannst es auch.
|
|
|
|
