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

Question

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

Logik
Mathematik
Gitterordnungen
abstrakte Algebra
universelle Algebra
Nichtklassische Logik

Daniil Kozhemiachenko

Betrachten Sie die Klasse der beschränkten nicht-distributiven Verbände $\mathbf{Mn}$ ( $n\geqslant 3$ ). Von links nach rechts: M3 , M4 , Mn

Betrachten Sie nun eine Aussagesprache als beendet $\{\wedge,\vee,\neg\}$ mit folgender Semantik: $\wedge$ Und $\vee$ entsprechen dem Treffen und Verbinden eines Gitters während $\neg$ funktioniert wie folgt: $\neg\top=\bot$ , $\neg\bot=\top$ , $\neg\mathbf{k}=\mathbf{k}$ ( $\mathbf{k}\leqslant\mathbf{n}$ ). Eine Wertung $v$ ordnet Aussagenvariablen der zugrunde liegenden Menge eines festen Verbandes zu.

Für Formeln $\phi$ Und $\chi$ in unserer Sprache sagen $\phi\vDash_{\mathbf{Mn}}\chi$ iff

\forall v : v (ϕ) ⩽_{M N} v (ϕ)

$\forall v:v(\phi)\leqslant_{\mathbf{Mn}}v(\phi)$

Jetzt nennen wir zwei Gitter $\mathfrak{L}$ Und $\mathfrak{L}'$ Satzmäßig ununterscheidbar, wenn zwei beliebige Formeln vorbei sind $\{\wedge,\vee,\neg\}$ $\phi$ Und $\chi$

ϕ ⊨_{L} χ \Leftrightarrow ϕ ⊨_{L^{'}} χ

$\phi\vDash_{\mathfrak{L}}\chi\Leftrightarrow\phi\vDash_{\mathfrak{L}'}\chi$

Das sagen wir $\mathfrak{L}$ ist das stärker $\mathfrak{L}'$ iff für alle $\phi$ Und $\chi$

ϕ ⊭_{L^{'}} χ \Rightarrow ϕ ⊭_{L} χ

$\phi\nvDash_{\mathfrak{L}'}\chi\Rightarrow\phi\nvDash_{\mathfrak{L}}\chi$

Die Frage lautet also wie folgt.

Stimmt das alles $\mathbf{Mn}$ Gitter sind nicht zu unterscheiden? Wenn ja, wie können wir es beweisen (oder wo es bewiesen wurde)?

Noah Schweber

Auch bei mathoverflow: mathoverflow.net/questions/331073/… .

Antworten (2)

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

Auch bei mathoverflow: mathoverflow.net/questions/331073/… .

Eran · Answer 1

Es ist nicht wahr.

Betrachten Sie die Gitter $\mathbf{M}_3,\mathbf{M}_4, \dots$ nur mit der Sprache $\{\vee,\wedge\}$ anstatt $\{\vee,\wedge,\neg\}$ . Das kann man erst einmal zeigen $\mathbf{M}_n$ ist einfach für $n\geq 3$ . Zweitens können wir, da die Klasse aller Verbände eine kongruenzdistibutive Varietät ist, Jonssons Lemma verwenden, um zu sagen, dass die subdirekt irreduziblen in $\mathsf{V}(\mathbf{M}_n)$ gehören $\mathsf{HS}(\mathbf{M}_n)$ . Da die einzigen Untergitter von $\mathbf{M}_n$ sind die Gitter $\mathbf{M}_k$ für $k=0,1,2,\dots,n$ , und alle diese (außer $\mathbf{M}_1$ Und $\mathbf{M}_2$ ) einfach sind, erhalten wir, dass die subdirekt irreduziblen in $\mathsf{V}(\mathbf{M}_n)$ sind genau $\mathbf{M}_0,\mathbf{M}_3,\dots,\mathbf{M}_n$ .

So $\mathsf{V}(\mathbf{M}_m)$ ist strikt enthalten $\mathsf{V}(\mathbf{M}_n)$ wann immer $3\leq m<n$ . Nach dem Satz von Birkhoff muss es also eine universell quantifizierte Gleichung geben $\forall v, \phi(v)=\chi(v)$ zufrieden durch $\mathbf{M}_m$ das ist nicht zufrieden $\mathbf{M}_n$ . Also rein $\mathbf{M}_n$ $\exists v,\phi(v)\neq\chi(v)$ (Wenn $\phi(v)<\chi(v)$ , dann wechseln $\phi$ Und $\chi$ ). Dann $\phi\models_{\mathbf{M}_m}\chi$ , Aber $\phi\not\models_{\mathbf{M}_n}\chi$ . Seit $\phi,\chi$ sind Formeln drin $\{\vee,\wedge\}$ , sie sind auch Formeln in $\{\vee,\wedge,\neg\}$ .

Als konkretes Beispiel $\mathbf{M}_3$ erfüllt die Gleichung

$x_1\vee((x_2\vee(x_3\wedge x_4))\wedge(x_3\vee(x_1\wedge x_4)))\approx x_1\vee(((x_1\vee x_2)\vee(x_3\wedge x_4))\wedge(x_3\wedge(x_2\vee x_4)))$

Aber $\mathbf{M}_4$ nicht. Lassen

$\chi(x_1,x_2,x_3,x_4)=x_1\vee((x_2\vee(x_3\wedge x_4))\wedge(x_3\vee(x_1\wedge x_4)))$

Und

$\phi(x_1,x_2,x_3,x_4)=x_1\vee(((x_1\vee x_2)\vee(x_3\wedge x_4))\wedge(x_3\wedge(x_2\vee x_4)))$

Jetzt $\phi\models_{\mathbf{}_3}\chi$ seit $\phi(v)$ gibt immer dasselbe Element zurück wie $\chi(v)$ , Aber $\phi\not\models_{\mathbf{M}_4}\chi$ seit $\chi(1,2,3,4)=1$ Und $\phi(1,2,3,4)=\top$ .

Ein Problem sehe ich darin, dass es in der obigen Semantik keine Tautologien gibt (also Formeln über $\{\neg,\wedge,\vee\}$ die immer als bewertet werden $\top$ ), und es gibt keine 'Widersprüche' (Formeln, die immer als ausgewertet werden $\bot$ ).
@DaniilKozhemiachenko Du hast Recht. Ich habe die Logik falsch interpretiert. Ich glaube, ich habe meine Antwort gerettet.
Ich fürchte, nein. Wir haben Aussagenformeln (ohne Prädikate und individuelle Variablen). Sagen Sie so etwas wie $p\wedge\neg q$ . Und wir können sagen, dass eine Formel die andere zur Folge hat: $\neg p\vDash_{\mathbf{M3}}\neg(p\wedge q)$ . Und das ist es.
@DaniilKozhemiachenko Meine ursprüngliche Antwort verwendete Formeln erster Ordnung, aber meine Bearbeitung verwendete Satzformeln. Ich habe ein Beispiel hinzugefügt, um dies deutlicher zu machen.
Am Anfang Ihres letzten Absatzes $\phi \vDash_{\mathbf M_3} \chi$ , Rechts?
Danke. Scheint richtig. Dies führt jedoch zu einer anderen Frage … Gibt es propositionale Ausdrücke der Form $\phi\vDash\chi$ das wird zwischen diesen Gittern unterscheiden?

Daniil Kozhemiachenko · Answer 2

Nach viel Zeit und Mühe scheint es mir, als hätte ich eine Familie von Formelpaaren konstruiert $\phi$ Und $\chi$ Trennung $\mathbf{Mn}$ aus $\mathbf{Mn+1}$ .

Folgendes berücksichtigen

D_{N} = ⋀_{ich = 2}^{N + 1} (P_{1} \lor P_{ich}) ⊨ P_{1} \lor \underset{\begin{matrix} ich, J \in (\binom{N + 1}{2}) \end{matrix}}{⋁} (P_{ich} \land P_{J})

$\mathscr{D}_{n}=\bigwedge\limits_{i=2}^{n+1}(p_1\!\vee\!p_i)\vDash\!p_1\!\vee\!\bigvee\limits_{\begin{matrix}i,j\in\binom{n+1}{2}\end{matrix}}(p_i\!\wedge\!p_j)\label{MnMn+1separation}$

Es ist klar, dass $\mathscr{D}_n$ hält sich nicht $\mathbf{Mn+1}$ (einfach einstellen $v(p_i)=\mathbf{i}$ ). Andererseits hält es an $\mathbf{Mn}$ für $n>2$ .

Das Argument sollte ziemlich einfach sein.

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

Daniil Kozhemiachenko

Noah Schweber

Antworten (2)

Eran

Daniil Kozhemiachenko

Eran

Daniil Kozhemiachenko

Eran

amrsa

Daniil Kozhemiachenko

Daniil Kozhemiachenko

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

Hat Axiomatisierbarkeit in der Logik nullter Ordnung wichtige Konsequenzen?

Finden eines geeigneten Universums für eine gegebene Struktur

Existenz einer universellen umhüllenden inversen Halbgruppe (ähnlich der "Grothendieck-Gruppe")

Klassifizieren setzt abstrahierte Orte anhand ihrer strukturellen Eigenschaften

Können wir ein Feld axiomatisieren, indem wir mit den binären Operationen und nur „gleichen“ Axiomen beginnen?

Bedeutet das Gesetz der ausgeschlossenen Mitte syntaktische Vollständigkeit?

Symmetriegruppen, die Termen in einer Algebra entsprechen

Ist der Verband der Topologien eine Heyting-Algebra?

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