Rekonstruktion der FOL-Sprache

Wenn wir eine FOL-Sprache haben S und wir verloren plötzlich seine logische Struktur ( → , ∧ , ∨ , ⊥ , ⊤ , ∀ X , ∃ X ) , können wir es (modulo eine logische Äquivalenz) wiederherstellen, indem wir nur die logische Folgerelation verwenden: ⊨ ?

Lassen Sie uns überlegen S die Menge der Formeln einer Logik erster Ordnung und S ¯ sein Quotient, der durch die logische Äquivalenzrelation ( ≡ ).

Alle logischen Verknüpfungen vorbei S ¯ kann offensichtlich nur mit ausgedrückt werden ⊨ , Zum Beispiel:

P ¯ → Q ¯ = { R ∈ S   |   ∀ S ∈ S , S ⊨ R ⇔ S , P ⊨ Q }

Nun, und um Quantoren zu rekonstruieren, betrachten wir die folgende Menge:

Π = { π ∈ ( S ¯ S ¯ ) ∗   |   ∀ P ∈ S ¯ , ( π   P ⊨ P ) ∧ ( π   π   P = π   P ) ∀ P , Q ∈ S ¯ , π   ( π   P → π   Q ) = π   P → π   Q ∀ P ∈ S ¯ , Γ ⊆ S ¯ , Γ ⊨ P ⇒ π   Γ ⊨ π   P }
Ich denke, dass Elemente von Π e = { π ∈ Π , ∃ ! ( π 1 , π 2 ) ∈ Π 2 , π = π 1 ∘ π 2 } sind universelle Quantoren (z P ↦ ∀ X , P [ A ← X ] Wo X kommt nicht vor P Und A ist eine Variable oder eine Konstante) plus zirkuläre Substitutionen Konjunktionen:
P ↦ ⋀ ich < N P [ X 0 ← X ich , . . . , X k ← X ( k + ich Mod N ) , . . . , X N − 1 ← X ( N − 1 + ich Mod N ) ]
Wo ( X ich ) ich können Variablen, Funktionen oder Relationen derselben Stelligkeit sein.

Ist diese Behauptung im intuitionistischen FOL und im klassischen FOL wahr?

Wenn das ganze Thema bereits diskutiert wird, könnte mich bitte jemand auf entsprechende Artikel verweisen, und vielen Dank.

BEARBEITEN: Um klarer zu sein, frage ich nach der Wiederherstellung der logischen Signatur bis zu einer logischen Äquivalenz. So können wir eine Beziehung zwischen Äquivalenzklassen von Formeln wie folgt feststellen: ∀ X , P ( X ) ¯ ist ein Ergebnis einer Anwendung des universellen Quantifizierers auf P ( X ) ¯ während P ( X ) ∧ Q ( X ) ¯ ist nicht.

EDIT: Und da dies im Allgemeinen nicht möglich ist, ist es zumindest möglich, wenn die nicht logische Signatur endlich ist und mindestens eine Relation ungleich Null und eine Funktion ungleich Null enthält?

Beachten Sie, dass Sie hier ein wenig zwischen Sätzen und Formeln zu jonglieren scheinen ; es macht letztendlich keinen Unterschied, aber die Arbeit mit Sätzen macht die Dinge nur unordentlicher (da im Allgemeinen ∀ X φ ( X ) kann ein Satz ohne sein φ ( X ) ein Satz sein).
Ja, Sie haben Grund, es tut mir leid für diesen Fehler.

Antworten (1)

EDIT: Formeln machen die Situation noch einfacher: Jede Permutation der Variablen induziert einen Automorphismus von B . Aus diesem Grund habe ich meine Antwort größtenteils unverändert gelassen, da die interessante Situation darin besteht, dass wir uns auf Sätze beschränken.

(Das Obige setzt voraus, dass wir eine Formel nicht mit ihrem universellen Abschluss identifizieren; wenn wir dies tun, dann ist die Situation die gleiche wie bei Sätzen, da jede Formel einem Satz entspricht, nämlich seinem universellen Abschluss.)

Nein, das geht nicht generell: wenn wir uns die Boolesche Algebra anschauen B von semantischen Äquivalenzklassen von S -Sätze (was übrig bleibt, wenn man alles vergisst außer " ⊨ " - übrigens ist dies die Lindenbaum-Algebra der leeren Theorie gegenüber S ), hat diese Algebra viele nichttriviale Automorphismen - diese werden Sätze an nicht-äquivalente Sätze senden, während sie erhalten bleiben ⊨ -Struktur.

Unter schwachen Hypothesen auf S (angenommen S ist vorerst zählbar) können wir das schnell beweisen. Wenn S enthält zwei unterschiedliche Symbole desselben Typs (z. B. zwei konstante Symbole oder zwei 17 -äre Beziehungssymbole oder etc.), dann führt deren Austausch zu einem nichttrivialen Automorphismus von B . Komplizierter, wenn S ist dann unendlich B ist eine zählbare atomlose Boolesche Algebra, und diese sind homogen (bei gegebenen zwei Elementen, von denen keines ist 0 oder 1 , es gibt einen Automorphismus, der sie vertauscht); Dies wird durch ein Hin- und Her-Argument bewiesen, ähnlich dem in diesem Beweis, dass zwei beliebige zählbare atomlose Boolesche Algebren isomorph sind . Ebenso, wenn S = ∅ dann jede Permutation der Sätze der Form "es gibt genau N Elemente" induziert einen Automorphismus von B .

Ich glaube zwar, dass wir die von Ihnen gewünschte Rekonstruktion niemals durchführen können, aber dafür habe ich noch keinen Beweis. Beachten Sie insbesondere, dass wir Beispiele produzieren können S wo einige Elemente von B sind Atome, aber andere Elemente liegen nicht über Atomen, also ist es weder atomlos noch "atomvoll"; das verkompliziert das bild etwas.

Das Bild für die intuitionistische Logik wird ähnlich sein, außer dass Heyting-Algebren die Rolle der Booleschen Algebren übernehmen. Im Allgemeinen müsste jede Logik, die eine erhebliche Menge an Rekonstruktionen entlang der von Ihnen vorgeschlagenen Linien zulässt, sehr "algebraisch restriktiv" (im Sinne der algebraischen Logik ) sein , und mir ist keine natürliche solche Logik bekannt.

Vielen Dank für Ihre Antwort. Tatsächlich habe ich einen Fehler gemacht, ich habe Sätze statt Formeln geschrieben. Kannst du es bitte nochmal sehen :)
@AhmedLazhar: Das ändert nicht wirklich etwas, denn normalerweise betrachten wir eine Nicht-Satz-Formel und ihre universelle Schließung als miteinander verbunden. Jede der Äquivalenzklassen wird also sowieso einige Sätze enthalten.
@HenningMakholm Ich bin mir nicht sicher, wie üblich das ist. Ich denke, ohne sie sind die Dinge fast immer interessanter. Es macht die Quantifizierung sicherlich schöner, da ∀ X P ( X ) Und ∀ X P ( j ) sind ungleich, obwohl die universellen Schließungen von P ( X ) Und P ( j ) sind gleichwertig.
@NoahSchweber, und was ist, wenn die Signatur endlich ist? Betrachten wir zum Beispiel unsere Signatur mit zwei Relationen P ( X ) Und R ( X , j ) Dann ∀ X ∀ j ( P ( X ) ∧ Q ( X , j ) ∧ X = j ) ist ein Atom. Wenn die Logik nicht mit Gleichheit übereinstimmt oder wir die Existenz von unendlich vielen Elementen benötigen, dann ∀ X ∀ j ( P ( X ) ∧ Q ( X , j ) ) wäre ein Atom. Ist das wahr ? Was können in diesem Fall die Elemente meiner sein Π ? Ich muss erwähnen, dass ich nach der Rekonstruktion der logischen Signatur suche. Es gibt kein Problem, wenn ich zwei Symbole vertausche, solange die gesamte Satzstruktur wiederhergestellt wird.
Auch wenn wir hinzufügen ¬ ∀ X ∀ j ( P ( X ) ∧ R ( X , j ) ) als Axiom, können wir nicht als Atom nehmen ∀ X ∀ j ≠ A ( P ( X ) ∧ R ( X , j ) ) wenn die Logik mit Gleichheit und ist ∀ X ∀ j ( P ( X ) ∧ R ( X , F ( j ) ) ) ansonsten ?
Wir können nicht nehmen ∀ X ∀ j ( P ( X ) ∧ R ( X , F ( j ) ) ) als Atom, weil es aus folgt ∀ X ∀ j ( P ( X ) ∧ R ( X , F ( j ) ) ∧ R ( X , A ) ) . Vergessen wir also Logik ohne Gleichheit und konzentrieren uns nur auf FOL mit Gleichheit.
Rekonstruktion der FOL-Sprache
AntwortenHierDatenschutz-Bestimmungen1y, 0v