Finden eines geeigneten Universums für eine gegebene Struktur

Question

Finden eines geeigneten Universums für eine gegebene Struktur

Logik
Funktionen
Mathematik
Modelltheorie
Beziehungen
universelle Algebra

Gianna Albertini

Ich bin neu in diesem Forum, also hoffe ich, dass meine mathematische Art, hier zu schreiben, korrekt ist, da ich es vorher nicht oft getan habe. :(

Ich nehme gerade an meinem Logikkurs teil und bin über die folgende Aufgabe gestolpert.

Uns wird eine Struktur gegeben $\mathcal{G}$ aus der universellen Algebra, die den Bereich (oder das Universum ) beinhaltet $G$ := $\wp(\mathbb{N})$ (die Potenzmenge der natürlichen Zahlen), eine Signatur $\omega:=\{\cup,\cap\ , ^c \}$ Wo $\{\cup,\cap\, ^c \}$ ist die Menge der Funktionssymbole und $^c$ ist lediglich die Ergänzung von $\{G'^c= \mathbb{N} \setminus G'$ | $G'\in\wp(\mathbb{N})\}$ - in Übereinstimmung mit der Definition . (Wir haben eine rein algebraische Struktur ohne Beziehungssymbole).

Außerdem sind uns zwei Teilmengen des Universums gegeben $\wp(\mathbb{N})$ (das sind wiederum Universen für sich) mit

(1) $\{G'' \subseteq \mathbb{N}$ | $G''$ endlich}.

(2) $\{G'' \subseteq \mathbb{N}$ | $G''$ , $G''^c$ unendlich}.

Und so wie ich es verstanden habe, sollen wir beweisen, ob es eine Unterstruktur von gibt $\mathcal{G}$ über das Universum (1). Wenn nicht, geben wir die kleinste Unterstruktur von an $\mathcal{G}$ die enthält (1) . Dasselbe gilt für Universum (2).

Also, was ich weiß, ist, dass eine Unterstruktur $\mathcal{F}$ (mit seinem Universum $F$ ) muss die Eigenschaften erfüllen

ich. Die Domäne von $\mathcal{F}$ ist in der Domäne von enthalten $\mathcal{G}$ , dh $|\mathcal{F}| \subseteq |\mathcal{G}|$ . (oder $F\subseteq G$ )

ii. $\mathcal{F}$ Und $\mathcal{G}$ dieselbe Signatur haben $\omega(\mathcal{F}) = \omega(\mathcal{G})$ .

Nun, ich verstehe, dass (1) trivialerweise nicht das Universum einer Unterstruktur von sein kann $\mathcal{G}$ weil seine Teilmengen nicht unter dem Komplement abgeschlossen sind, und (2) kann es auch nicht sein, da seine Teilmengen nicht unter Vereinigung abgeschlossen sind. Allerdings weiß ich nicht wirklich, wie ich den kleinsten Unterbau finden könnte $\mathcal{G}$ das würde (1), (2) oder beides enthalten. Ich würde mich also sehr über Ihre Hilfe freuen.

Vielen Dank, Gianna

amrsa

In (1) und (2) ist es

G \subseteq N

$G \subseteq \mathbb N$ , wie Sie es haben, oder

G \subseteq ℘ (N)

$G \subseteq \wp(\mathbb N)$ ? Im ersten Fall (so wie es ist) ist es ziemlich trivial und für beide Fragen gleich, es sei denn, ich verstehe etwas falsch ...

Gianna Albertini

Es ist in der Tat

G \subseteq N

$G \subseteq \mathbb{N}$ . Ich sehe jedoch nicht, wie trivial es sein soll ... Ich hoffe, ich habe keine widersprüchlichen / verwirrenden Notationen geschrieben?

amrsa

In diesem Fall wird die Unterstruktur erzeugt durch

G

$G$ hat die zugrunde liegende Menge

{\emptyset, G, N ∖ G, N} .

$\{\varnothing, G, \mathbb N\setminus G, \mathbb N\}.$ Und die Operationen sind die gleichen wie in

℘ (N)

$\wp(\mathbb N)$ . Aber vielleicht ist das nicht das, was Sie wollen?

Gianna Albertini

Meinen Sie, dass Ihr vorgeschlagenes Universum mit seiner Signatur die kleinste Unterstruktur ist, die (1) und (2) beinhaltet? Und wenn Sie denken, dass es so ist, könnten Sie erklären, warum es (1) und (2) beinhaltet? Eigentum i. und ii. sind offensichtlich trivial.

amrsa

Wenn

G \subseteq N

$G\subseteq\mathbb N$ (entweder endlich oder unendlich), dann ist die obige Menge unter den Operationen von abgeschlossen

ω

$\omega$ , und es ist das kleinere derartige Set, das enthält

G

$G$ : in der Tat, wenn

G

$G$ zu einer solchen Menge gehört, dann auch

G^{c} = N ∖ G

$G^c=\mathbb N\setminus G$ , und dann auch

\emptyset = G \cap G^{c}

$\varnothing=G\cap G^c$ Und

N = G \cup G^{c}

$\mathbb N=G\cup G^c$ .

Alex Kruckmann

Ein Kommentar zum Schreiben. Anscheinend hast du den Brief benutzt

G

$G$ für drei völlig verschiedene Dinge hier: (a) Die Domäne von

G

$\mathcal{G}$ ,

G = P (N)

$G = \mathscr{P}(\mathbb{N})$ . (b) Eine Variable im Bereich über

P (N)

$\mathscr{P}(\mathbb{N})$ in der Definition von

^{c}

$^c$ . (c) Eine Teilmenge von

N

$\mathbb{N}$ verwendet bei der Angabe der Teilmengen von

P (N)

$\mathscr{P}(\mathbb{N})$ nach denen Sie in (1) und (2) fragen. Das ist ziemlich verwirrend!

Alex Kruckmann

Hier sind einige andere Dinge, die mich verwirren. Könntest Du das erläutern? (1) Das sagen Sie

^{c}

$^c$ sollte ein Beziehungssymbol sein. Welchen Stellenwert hat dieses Beziehungssymbol? Ist es binär, so dass

(X, Y)

$(X,Y)$ erfüllt die Relation genau dann, wenn

Y = X^{c}

$Y = X^c$ ? (2) Fragen Sie nach einer einzigen festen Endlichkeit?

G \subseteq N

$G\subseteq \mathbb{N}$ , oder über die Menge aller

{G \subseteq N ∣ G is finite}

$\{G\subseteq \mathbb{N}\mid G\text{ is finite}\}$ ? Ich denke, die zweite Option ist das, was Sie meinten, aber es ist nicht ganz klar. (3) Was meinst du mit "beinhaltet"? Meinten Sie vielleicht "die kleinste Unterstruktur, die [die durch] (1) definierte Menge enthält "?

Gianna Albertini

Es tut mir leid, dies ist meine erste Frage zu Stackexchange, daher kannte ich die genauen Konventionen nicht. :( In Bezug auf Ihre Punkte: (1) Die Arität (wenn ich mich nicht irre) ist binär, wenn man sich ansieht, wie

^{c}

$^c$ ist in der Aufgabe definiert. (2) Letzteres meine ich tatsächlich. Jede beliebige Menge, die eine Teilmenge von (1) oder (2) ist. Ich bin mir bereits sicher, dass sie kein Universum für eine potenzielle Unterstruktur sein können, also gibt es das (3), das ich meine, enthält. Es tut mir leid, Englisch ist nicht meine Muttersprache, ich dachte, dass Enthalten und Enthalten dasselbe bedeuten würden. @amrsa: Danke für die Erklärung.

Gianna Albertini

@AlexKruckman Ich habe gerade die Frage bearbeitet und hoffe, ich konnte die Lesbarkeit verbessern.

Alex Kruckmann

Danke für die Klarstellung - jetzt ist es viel klarer. Willkommen bei Math Stackexchange!

Gianna Albertini

Danke :)) gerne hier!

amrsa

Ah! Diese neue Version sieht für mich besser aus. Sie sehen, sagen, der Stromerzeuger ist so etwas wie

G = {F \subseteq N : F is finite}

$G=\{F\subseteq\mathbb N:F\text{ is finite}\}$ ist äquivalent zu

G \subseteq ℘ (N)

$G\subseteq\wp(\mathbb N)$ Und

F

$F$ ist endlich, wann immer

F \in G

$F \in G$ . Nicht mehr trivial!

Antworten (1)

Finden eines geeigneten Universums für eine gegebene Struktur

In (1) und (2) ist es $G \subseteq \mathbb N$ , wie Sie es haben, oder $G \subseteq \wp(\mathbb N)$ ? Im ersten Fall (so wie es ist) ist es ziemlich trivial und für beide Fragen gleich, es sei denn, ich verstehe etwas falsch ...
Es ist in der Tat $G \subseteq \mathbb{N}$ . Ich sehe jedoch nicht, wie trivial es sein soll ... Ich hoffe, ich habe keine widersprüchlichen / verwirrenden Notationen geschrieben?
In diesem Fall wird die Unterstruktur erzeugt durch $G$ hat die zugrunde liegende Menge ${\emptyset, G, N ∖ G, N} .$ $\{\varnothing, G, \mathbb N\setminus G, \mathbb N\}.$ Und die Operationen sind die gleichen wie in $\wp(\mathbb N)$ . Aber vielleicht ist das nicht das, was Sie wollen?
Meinen Sie, dass Ihr vorgeschlagenes Universum mit seiner Signatur die kleinste Unterstruktur ist, die (1) und (2) beinhaltet? Und wenn Sie denken, dass es so ist, könnten Sie erklären, warum es (1) und (2) beinhaltet? Eigentum i. und ii. sind offensichtlich trivial.
Wenn $G\subseteq\mathbb N$ (entweder endlich oder unendlich), dann ist die obige Menge unter den Operationen von abgeschlossen $\omega$ , und es ist das kleinere derartige Set, das enthält $G$ : in der Tat, wenn $G$ zu einer solchen Menge gehört, dann auch $G^c=\mathbb N\setminus G$ , und dann auch $\varnothing=G\cap G^c$ Und $\mathbb N=G\cup G^c$ .
Ein Kommentar zum Schreiben. Anscheinend hast du den Brief benutzt $G$ für drei völlig verschiedene Dinge hier: (a) Die Domäne von $\mathcal{G}$ , $G = \mathscr{P}(\mathbb{N})$ . (b) Eine Variable im Bereich über $\mathscr{P}(\mathbb{N})$ in der Definition von $^c$ . (c) Eine Teilmenge von $\mathbb{N}$ verwendet bei der Angabe der Teilmengen von $\mathscr{P}(\mathbb{N})$ nach denen Sie in (1) und (2) fragen. Das ist ziemlich verwirrend!
Hier sind einige andere Dinge, die mich verwirren. Könntest Du das erläutern? (1) Das sagen Sie $^c$ sollte ein Beziehungssymbol sein. Welchen Stellenwert hat dieses Beziehungssymbol? Ist es binär, so dass $(X,Y)$ erfüllt die Relation genau dann, wenn $Y = X^c$ ? (2) Fragen Sie nach einer einzigen festen Endlichkeit? $G\subseteq \mathbb{N}$ , oder über die Menge aller $\{G\subseteq \mathbb{N}\mid G\text{ is finite}\}$ ? Ich denke, die zweite Option ist das, was Sie meinten, aber es ist nicht ganz klar. (3) Was meinst du mit "beinhaltet"? Meinten Sie vielleicht "die kleinste Unterstruktur, die [die durch] (1) definierte Menge enthält "?
Es tut mir leid, dies ist meine erste Frage zu Stackexchange, daher kannte ich die genauen Konventionen nicht. :( In Bezug auf Ihre Punkte: (1) Die Arität (wenn ich mich nicht irre) ist binär, wenn man sich ansieht, wie $^c$ ist in der Aufgabe definiert. (2) Letzteres meine ich tatsächlich. Jede beliebige Menge, die eine Teilmenge von (1) oder (2) ist. Ich bin mir bereits sicher, dass sie kein Universum für eine potenzielle Unterstruktur sein können, also gibt es das (3), das ich meine, enthält. Es tut mir leid, Englisch ist nicht meine Muttersprache, ich dachte, dass Enthalten und Enthalten dasselbe bedeuten würden. @amrsa: Danke für die Erklärung.
@AlexKruckman Ich habe gerade die Frage bearbeitet und hoffe, ich konnte die Lesbarkeit verbessern.
Danke für die Klarstellung - jetzt ist es viel klarer. Willkommen bei Math Stackexchange!
Ah! Diese neue Version sieht für mich besser aus. Sie sehen, sagen, der Stromerzeuger ist so etwas wie $G=\{F\subseteq\mathbb N:F\text{ is finite}\}$ ist äquivalent zu $G\subseteq\wp(\mathbb N)$ Und $F$ ist endlich, wann immer $F \in G$ . Nicht mehr trivial!

Alex Kruckmann · Answer 1

Im Allgemeinen, wenn $\mathcal{A}$ ist eine Struktur und $B\subseteq A$ ist eine Teilmenge der Domäne $A$ von $\mathcal{A}$ , Dann $B$ ist die Domäne einer Unterstruktur von $A$ dann und nur dann, wenn $B$ enthält alle Interpretationen von konstanten Symbolen in der Sprache und ist unter allen Interpretationen von Funktionssymbolen in der Sprache abgeschlossen. Das heißt, wenn $c$ ein konstantes Symbol ist, benötigen wir das $c^{\mathcal{A}}\in B$ , und wenn $f$ ist ein $n$ -äres Funktionssymbol und $b_1,\dots,b_n\in B$ , das verlangen wir $f^\mathcal{A}(b_1,\dots,b_n)\in B$ .

Für eine beliebige Teilmenge $B\subseteq A$ , gibt es eine kleinste Teilmenge $\langle B\rangle$ enthält $B$ das ist die Domäne einer Unterstruktur. Dies wird als Unterstruktur bezeichnet, die von erzeugt wird $B$ . Intuitiv, $\langle B\rangle$ besteht aus allen Elementen von $A$ die aus den Konstanten und den Elementen von "konstruiert" werden kann $B$ durch Anwendung der Funktionen. Formaler kann dies beschrieben werden durch

⟨ B ⟩ = {T^{A} (B_{1}, \dots, B_{k}) ∣ T (X_{1}, \dots, X_{k}) ist ein Begriff und B_{1}, \dots, B_{k} \in B} .

$\langle B\rangle = \{t^\mathcal{A}(b_1,\dots,b_k)\mid t(x_1,\dots,x_k) \text{ is a term, and }b_1,\dots,b_k\in B\}.$

Ok, also in der Situation Ihrer Frage haben wir die Struktur $\mathcal{G} = (\wp(\mathbb{N}),\cup,\cap,^c)$ , Wo $\cup$ , $\cap$ , Und $^c$ sind Funktionssymbole (es gibt keine konstanten Symbole). Wie Sie darauf hingewiesen haben, ist keine der gegebenen Mengen die Domäne einer Unterstruktur, da (1) nicht unter Komplementen abgeschlossen ist und (2) nicht unter Schnittmengen oder Vereinigung abgeschlossen ist. Was sind also die Unterstrukturen, die sie erzeugen?

Hinweise:

(1) Die endlichen Teilmengen von $\mathbb{N}$ sind unter Schnittmengen und Vereinigungen geschlossen, aber nicht unter Komplementen. Als ersten Schritt können wir also ihre Ergänzungen einwerfen, um sie zu erhalten $\{X\subseteq \mathbb{N}\mid X\text{ is finite}\}\cup \{X\subseteq \mathbb{N}\mid X^c\text{ is finite}\}$ . Ist diese Menge unter Schnittmengen, Vereinigungen und Komplementen abgeschlossen?

(2) Der Satz $F = \{X\subseteq \mathbb{N}\mid X\text{ and }X^c\text{ infinite}\}$ ist unter Komplementen abgeschlossen, aber nicht unter Schnittpunkten und Vereinigungen. Welche Teilmengen von $\mathbb{N}$ können Sie machen, indem Sie zwei Sätze in schneiden $F$ ? Wie wäre es mit der Vereinigung zweier Mengen? $F$ ?

Vielen Dank für diese umfangreiche Antwort!! Ich denke, was selbst mich hier ein wenig verwirrt, ist, dass in der Aufgabe nicht ausdrücklich angegeben ist, ob $^c$ ist eigentlich ein Funktionssymbol oder ein Beziehungssymbol. Einer unserer Tutoren hier sagte, dass es unter allen Operationen geschlossen werden muss. Vielleicht sind alle Operationen lediglich Funktionssymbole. Aber andererseits - wäre es eine gültige Struktur mit nur Funktionssymbolen und überhaupt keinen Beziehungssymbolen?
Ich verstehe. In deiner Frage hast du das geschrieben $^c$ ist ein Beziehungssymbol, also habe ich mich dafür entschieden. Wenn sich das Problem nicht konkretisiert, solltest du wahrscheinlich deinen Professor um eine Klärung bitten - aber ich halte das für sehr wahrscheinlich $\cap$ , $\cup$ , Und $^c$ sind alle als Funktionssymbole gedacht. Es ist nicht erforderlich, dass eine Struktur Beziehungssymbole hat – die Menge der Beziehungssymbole kann leer sein (und dasselbe gilt für Funktionssymbole und Konstantensymbole).
Was für ein Timing, ich habe gerade eine Mail von unserem Professor bekommen!! :) sagte er, dass sie alle als Funktionssymbole gedacht sind. Das hat er anscheinend in der Aufgabe vergessen zu sagen. Also habe ich recht, sowohl (1) als auch (2) können nicht stimmen! was mich auch mit meiner anfänglichen Frage zurücklässt, obwohl ... :( if $^c$ ein Beziehungssymbol wäre, trivialerweise wäre es (1) als Unterstruktur gewesen!
@GiannaAlbertini Ich habe meine Antwort bearbeitet, um die neue Version der Frage anzusprechen.
@GiannaAlbertini Nehmen Sie sich etwas Zeit, um Folgendes zu überprüfen: Was soll ich tun, wenn jemand meine Frage beantwortet? . Wenn Sie mit dieser Antwort zufrieden sind, möchten Sie sie vielleicht akzeptieren und vielleicht sogar positiv bewerten, da Sie bereits über die erforderliche Reputationsbewertung verfügen.
Vielen Dank Professor, den Rest des Beweises konnte ich dank Ihrer Hinweise herausfinden :D @amrsa hat genau das getan ;)

Finden eines geeigneten Universums für eine gegebene Struktur

Gianna Albertini

amrsa

Gianna Albertini

amrsa

Gianna Albertini

amrsa

Alex Kruckmann

Alex Kruckmann

Gianna Albertini

Gianna Albertini

Alex Kruckmann

Gianna Albertini

amrsa

Antworten (1)

Alex Kruckmann

Gianna Albertini

Alex Kruckmann

Gianna Albertini

Alex Kruckmann

amrsa

Gianna Albertini

Klären Sie den Satz von Birkhoff (in der universellen Algebra)

Symmetriegruppen, die Termen in einer Algebra entsprechen

Wann können wir unterschiedliche Axiomatisierungen für Theorien mit denselben Modellen finden?

Welche Theorien werden unter dem Produkt bewahrt?

Versuchen, Fragen in der Übung über Beziehungen zu verstehen

Ist die Theorie regulärer formaler Sprachen endlich axiomatisierbar?

Prinicpal 1-Typen scheinbares Paradoxon

Wie wird die vollständige Semantik von SOL und HOL spezifiziert?

Relative Stärke und propositionale Ununterscheidbarkeit von nicht-distributiven Verbänden

Endlich viele abzählbare Modelle implizieren Entscheidbarkeit