Montag, 17. Oktober 2016

Metalogik mit mathematischer Induktion. Allgemeines zur Methode der Metalogik.

Metalogik mit mathematischer Induktion.
Allgemeines zur Methode der Metalogik.

Die Methode der Metalogik bedient sich zunächst einmal der Methoden der ableitungssyntaktischen Regeln der Logik, d. h., der Schlussregeln der natürlichen Deduktion.
Damit kann schon viel entschieden werden, jedoch nicht alles, vor allem nicht die Frage nach Vollständigkeit und Widerspruchsfreiheit.
Hier ist ein mathematisches Beweisverfahren hinzuzuziehen: die mathematische Induktion. Mathematische Induktion kann auf eine Menge von Elementen angewendet werden, die durch die Nachfolgerrelation geordnet sind, d. h, es gibt ein erstes Element der Folge und für jedes Element eines und nur eines, das ihm unmittelbar folgt.
Was bewiesen wird ist, dass eine Eigenschaft E allen Elementen der Menge zukommt. Die Schlussform hat zwei Stufen:

1. Basis:                                            Es ist zu beweisen, dass das erste Element der
                                                           Folge die Eigenschaft E hat.
2. Induktion
a. Induktive Hypothese:                 Es wird angenommen, dass E einem Element an
                                                           k-ter Stelle – k ist beliebig – zukommt.
b. Induktionsschritt:                        Es ist zu beweisen, dass E unter der durch die ICH
                                                           eingeführten Bedingung auch dem k+1 Element
                                                           zukommt.

Konklusion:                                      E kommt allen Elementen der Folge zu.

Mathematische Induktion als Beweisform hat ihre Rechtfertigung durch das Axiom von Peano. Dieses Axiom selbst kann in der PL erster Stufe nicht ausgedrückt werden. Es kann nur durch eine Formel der PL zweiter Stufe repräsentiert werden.

Will man dieses Beweisverfahren, wie das in der Metalogik der Fall ist, auf andere Mengen als auf Zahlen anwenden, so muss zunächst sichergestellt werden, dass sich die Elemente von Satzmengen in eine Ordnung bringen lassen, die sie so abzählbar macht, dass jedem k eine und nur eine natürliche ganze Zahl zugeordnet ist.
Im folgenden Beispiel, das der Grammatik der AL entnommen ist, ergibt sich unmittelbar aus den grammatischen Konstruktionsregeln für gwf-Sätze, dass sie so geordnet werden können, dass einer Stufe k grammatischer Komplexion eine und nur eine Stufe k+1 folgen kann, wobei es durchaus zulässig ist, dass hier mehrere Fälle zu unterscheiden sind. Eine solche abzählbare Ordnung der Satzkomponenten ergibt sich, wenn einer gegebenen grammatischen Verzweigung und der Konvention ‚links vor rechts‘ folgende, eine Auflistung der Komponenten vorgenommen wird.

Das triviale Theorem sei: die Anzahl der Klammern in einer gwf Formel ist immer durch 2 ohne Rest teilbar (die Basis schließt den Fall 0 ein).

Basis: Es handelt sich um einen atomaren Satz. Nach den Konstruktionsregeln ist die Anzahl der Klammern 0, also durch 2 teilbar.

Induktive Hypothesis: Auf der Stufe k der grammatischen Zusammensetzung sei die Anzahl der Klammern durch 2 teilbar.

Induktionsschritt: Unter Voraussetzung der ICH gilt, dass die Anzahl der Klammern auch auf der Stufe k+1 durch 2 teilbar ist.

Das ist nun zu beweise; Wir haben zwei Fälle an der Hand, von denen der zweite in vier Unterfälle zu gliedern ist, die aber nicht jeder für sich betrachtet werden müssen, da sie die für den Beweis entscheidende Eigenschaft gemeinsam haben.

Fall I. Die Stufe k+1 grammatischer Komplexität wird durch Hinzutreten von ‚-‘ erreicht. Nach Konstruktionsregeln werden damit keine neuen Klammern eingeführt. Die in k als erfüllt angenommene Bedingung bleibt damit für k+1 erhalten.

Fall II. Unterfällte sind die mit ‚&‘ oder ‚v‘ oder ‚‘ oder ‚Ξ‘ angefügten Sätze. Die Konstruktionsregel schreibt vor, dass 2 neue Klammern hinzuzufügen sind. Eine Zahl aber entsteht, wenn zu einer durch zwei teilbaren Zahl 2 addiert wird, durch 2 teilbar bleibt.

Also: Für alle Formeln der AL gilt: die Anzahl der Klammern ist durch 2 teilbar.

Es ist zu beachten, dass die generelle, auf Fälle bezugnehmende Schlussform die des konstruktiven Dilemmas ist:

A v B
A C
B C             -> C

die der Regel vE IN entspricht.

Weiter ist anzumerken, dass sich im angegebenen Beispiel die Formeln AL bereits durch die grammatischen Regeln selbst in eine abzählbare Folge bringen lassen. Das ist aber z. B. bei der ‚Menge aller gwf Formeln von AL‘ nicht der Fall. Hier wird ein Verfahren angewandt, das ‚Gödelisierung‘ genannt wird.
Es besteht darin, dass man jedem Zeichen einschließlich der Klammern eine Zahl zuordnet, so dass sich einer Formel eine und nur eine für sie charakteristische Zahl zuordnen lässt. Dann sind die Formeln, gemäß der Ordnung nach größer oder kleiner der für sie charakteristischen Zahlen in eine Folge gebracht, die von der Nachfolgerrelation bestimmt ist. Das kann auf verschiede Weise geschehen. Wichtig ist lediglich, dass die Möglichkeit, die Formeln in eine solche Folge zu bringen, gezeigt wird.
Das Verfahren von Gödel ist besonders komplex, weil es für ihn noch weitere Aufgaben zu erfüllen hatte.
Man bezieht sich allgemein mit ‚Gödelisierung‘ nicht auf sein Verfahren, sondern auf alle Möglichkeiten, durch Zuordnung von Zahlen Formeln in die gewünschte für die Anwendung mathematischer Induktion nötige Folge zu bringen.

Veröffentlicht von Lilith Dan 


Sonntag, 16. Oktober 2016

Metalogik: Elementare Metatheorie von PL.

Metalogik: Elementare Metatheorie von PL.

Die WF-Korrektheit der Ableitungsregeln ND.

Die Ableitungsregeln ND können als solche als ‚evidente‘ Voraussetzungen einfach angenommen werden. Es ist aber auch möglich, zu beweisen, dass sie ‚semantisch korrekt‘, d. h. semantisch als gültig zu rechtfertigen sind.
Eine Ableitungsregel ist semantisch gerechtfertigt, wenn gezeigt werden kann, dass das Ableitungsschema eine semantisch 1-wahre Implikation ist. Sind alle Ableitungsregeln korrekt, dann kann bis zu Anwendung stärkerer Beweismittel davon ausgegangen werden, dass auch jede Folge von Regelanwendungen korrekt ist.

Betrachtet man die allgemeine Struktur des Anfangssegmentes eines Beweises ND, nämlich

P

Γ


q

A

r


B


Dann ist die Annahmemenge der übergeordneten Ableitung Γ für alle Ableitungen auf Zeilen i, j, k, k+1, die Annahmemenge für alle Zeilen der ersten untergeordneten Ableitung Γ ∩ {A}, die der zweiten Γ ∩ {A, B}, usw., wofür man kurz Γ; Γ, A; Γ, A, B schreiben kann.
Wird angenommen, dass aus einer solchen Annahmemenge der Satz auf Zeilen i, j, k bereits nach Regeln ND abgeleitet wurde, so kann das als

iΓ I= P                        bzw. jΓ, A I- P

geschrieben werden. Folgt nun aus einer oder mehreren Zeilen dieser Art nach Regeln ND eine weitere Zeile, die immer als Zeile k+1 gezählt wird, dann kann das mit

k+1     Γ I- P bzw.                 k+1 Γ, A I- P

notiert werden.
Zeilen k sind dann für den jeweils letzten Schritt einer untergeordneten Ableitung reserviert. Man hat so die Möglichkeit, Schritte in Ableitungen auf der Metaebene in einer für die vorliegenden Zwecke praktischen Schreibweise, die Schreibweise für Gentzensequenzen, dazustellen. Die Wahl der Zeilenzählung ist durch Gesichtspunkte bestimmt, die später erläutert werden. Man kann zunächst Ableitungsregeln ND in dieser Schreibweise wie folgt darstellen:

Reiteration:
K+1     Γ I- Pk+1                                  Rj        (Pk+1 = Pj, Pj Є Γ)

& Einführung:
1          Γ I- P
M         Γ I- Q
K+1     Γ I- (P & Q) k+1                      oder: (Q & P) k+1                   & E 1, m

Einführung:
k          Γ, P I- Q
k+1     Γ I- (P Q) k+1                              E k


D-Definitionen und D-Theoreme
D-Eigenschaften und D-Relationen werden im System ND durch den Begriff der Ableitbarkeit auf der letzten Zeile eines formalen Beweises definiert. Die Restriktion von ND strikt vorausgesetzt. Den Definitionen und D-Theoremen entsprechen bestimmte WF-Theoreme.

D-Definitionen
1. Γ I- B gdw. B aus Γ
2. I- B gdw. Ø I-B
3. -I B gdw. Ø I- B
4. -I gdw. Γ I- -Aj, Aj Γ Є Γ
5. A I-I B gdw. I- A Ξ B

Die nicht-operationalen Definitionen für ¬ Γ I- B, ¬ I- B, ¬ -I B, ¬ A I-I B ergeben sich aus der Negation der rechten Seite der Definitionen 1-5. Dass die Definitionen wahrheitsfunktional korrekt sind, ergibt sich aus den zuzuordnenden WF-Theoremen.


D-Theoreme
DT für 1-wahr, 1-falsch und 1-inkonsistent
1. I- B gdw. -I – B
2. -I gdw. I- – B
3. Wenn I- B dann für jedes A, Γ: A I-B, Γ I- B
4. Wenn I- B dann B I- alle I- A und nur alle I- A
5. Wenn -I B, dann B I- jedes beliebige A
6. Wenn -I Γ, dann Γ I- jedes beliebige B
7. -I gdw. Γ I- B & – B

DT zur 1-Implikation
8. Wenn Γ I- B, dann Γ U {A} I- B und Γ U Δ I- B
9. Γ I- B gdw. I- Γ B
10. Γ I- B gdw. I- Γ U {– B}
11. Γ I- – B gdw. -I Γ U {B}

DT zur leeren Menge
12. ¬ -I Ø
13. I- B gdw. -I Ø U {– B}
14. -I B gdw. -I Ø U {B}

DT über Satzmengen
15. Wenn Γ‘ Teilmenge von Γ ist und Γ‘ I- B, dann Γ I- B
16. Wenn Γ I- B und Δ I- – B, dann Γ U Δ I- B & – B, somit -I Γ U Δ
17. Wenn -I Γ, dann -I Γ U Δ
18. Wenn Γ‘ Teilmenge von Γ ist und -I Γ‘. Dann -I Γ
19. ¬ -I Γ gdw. für jede Teilmenge Γ‘, ¬ -I Γ‘
20. Wenn -I Γ, dann hat es eine Teilmenge Γ‘, so dass -I Γ‘
21. Wenn ¬ -I Γ und Γ I- B, dann ¬ -I Γ U {B}


Veröffentlicht von Lilith Dan 

Freitag, 14. Oktober 2016

Metalogik: QS-Definitionen und QS-Theoreme von PL.

Metalogik: QS-Definitionen und QS-Theoreme von PL.

Die substitutive Interpretation der Quantoren, die auch zuweilen informell genannt wird, setzt einen nicht selbst definierten Wahrheitsbegriff für nicht quantifizierte Sätze mit Namen, Individuenkonstanten voraus, durch die Wahrheit und Falschheit für quantifizierte Sätze durch Substitution bestimmt werden.
Sie unterscheidet sich damit von einer formalistischen Semantik der Quantoren, die auch auf Grammatiken, die nur Individuenvariable und keine Namen zulassen und vom Begriff der Erfüllbarkeit ausgeht, Man spricht hier auch von der objektualen und objektiven Interpretation der Quantoren.

Eine Interpretation I wählt (a) ein Universum U aus, ordnet (b) den Termen t-Elemente aus U und (c) jedem n-stelligen Prädikat eine gegebenenfalls leere Menge von n-Tupeln von Elementen zu. Atomare Sätze der Form:

φ t1, t2 …tn                                                                     ti = tj oder tj ≠ tj  

Atomare Sätze sind = 1 gdw. < I (t1), I (t2), …I (tn) > Elemente der von φ aus U ausgewählten Menge von n-Tuplen ist. Die Wahrheitsbedingungen für Sätze, die durch Satzkonnektive gebildet werden, werden wie in AL festgelegt. Die Definition der Wahrheitsbedingungen für quantifizierte Sätze werden quantensemantische Definitionen (QS-D) genannt. Es sind:

QS-D 1                      (Ɐx) φx = 1    gdw    φt = 1 für jedes t
QS-D 2                      (Ɐx) φx = 0    gdw    φt = 0 für mindestens ein t
QS-D 3                      (Ǝx) φx = 1    gdw    φt = 1 für mindestens ein t
QS-D 4                      (Ǝx) φx = 0    gdw    φt = 0 für alle t

Aus diesem QS-D lassen sich, zuweilen auch unter Rückgriff auf die WFT, die quantensemantischen Theoreme beweisen. Sie werden kurz als QS-Th bezeichnet.

QS-Th 1                    – (Ɐx) φx I-I (Ǝx) – φx
QS-Th 2                    – (Ǝx) φx I-I (Ɐx) – φx
QS-Th 3                    – (Ɐx) – φx I-I (Ǝx)φx
QS-Th 4                    – (Ǝx) – φx I-I (Ɐx)φx
QS-Th 5                    I sei eine Interpretation, unter der jedem Element von U ein Term                          t zugeordnet ist: Wenn jede Einsetzung von (Ɐx) φx = 1 unter I
                                    Ist, dann ist I ((Ɐx) φx) = 1.
QS-Th 6                    I sei eine Interpretation, unter der jedem Element aus U ein Term
                                    t zugeordnet ist: Wenn jede Einsetzungsinstanz von (Ǝx)φx
                                    unter dieser I = 0, dann I ((Ǝ x) φx) = 0.
QS-Th 7                    Wenn ¬ =I Γ U {(Ǝx) φx} und t kommt in Γ U {(Ǝx) φx} nicht vor,
                                    dann ¬ =I Γ U {(Ǝx) φx, φt}.
QS-Th 8                    I sei eine Interpretation, unter der für jedes Element von U gilt
a.    Es gibt einen Term t, dem das Element zugeordnet ist.
b.     φt = 1 unter I.
Gelten a und b, dann gilt für die Generalisierung (Ɐx)φx = 1.
QS-Th 9                    {(Ɐx)φx} I= alle Einsetzungen φt von (Ɐx)φx.
QS-Th 10                  Ist φt eine Einsetzung von (Ǝx) φx, dann {φt} I= (Ǝx) φx
QS-Th 11                  Wenn Γ I= φt, dann Γ I= (Ɐx)φx, vorausgesetzt t kommt nicht in
                                    irgendeinem anderen Element von Γ und auch nicht in (Ɐx)φx
                                    vor.
QS-Th 12                  Wenn Γ I= (Ǝx)φx und Γ U {φt I= Q, dann Γ I= Q, vorausgesetzt,
                                    dass t nicht in Γ, Q und (Ǝx)φx vorkommt.



Veröffentlicht von Lilith Dan 

Sonntag, 9. Oktober 2016

Metalogik: Elementare semantische Metatheoreme. Notation.

Metalogik: Elementare semantische Metatheoreme. Notation.


Es wird folgende Notation für die Metalogik vereinbart:

B ist semantisch 1-wahr                                                    I= B
B ist nicht semantisch 1-wahr                                          ¬ I= B
B ist semantisch 1-falsch                                                  =I B
B ist nicht semantisch 1-falsch                                        ¬ =I B
Γ 1-impliziert B semantisch                                               Γ I= B
Γ 1-impliziert B semantisch nicht                                     ¬ (Γ I= B)
Vereinigung von Γ mit B                                                    Γ U {B}
A, B sind semantisch 1-äquivalent                                  A I=I B
A, B sind nicht semantisch 1-äquivalent                        ¬ A I=I B

Anzumerken ist, dass auch mengentheoretische Notation übernommen wird. Mengen sind aber immer als Satzmengen zu verstehen, d. h., sie sind Konjunktionen von Sätzen.
Anzumerken ist weiter, dass das Zeichen ‚I=‘ in Verbindung mit Σ, d. h mit ‚Σ I=‘ eine abweichende Bedeutung erhält. ‚Σ ‘ soll ein semantisches Modell bezeichnen. Der Ausdruck ‚Σ I= B‘ besagt dann, dass der Satz B in Σ ein Modell hat, d. h. in ihm erfüllbar ist.


WF-Definitionen AL

WF-Definitionen der AL für logische Eigenschaften und Relationen sind:

WFD. 1 I= A                                                 gdw. A = 1 für alle I
WFD. 2 =I A                                                 gdw. A = 0 für alle I
WFD. 3 ¬ I= A                                             gdw. A = 0 für mindestens eine I
              und ¬ =I A                                      und A = 1 mindestens eine I
WFD. 4 =I Γ                                                 gdw. Γ = 0 für alle I
WFD. 5 ¬ =I Γ                                              gdw. Γ= 1 für mindestens eine I
WFD. 6 Γ I=B                                               gdw. Γ B = 1 für alle I
WFD. 7 A I=I B                                            gdw. B = 1 für alle I, für die A = 1 und
                                                                       B = 0 für alle I, für die A = 0
WFD. 8 =I Γ                                                 gdw. es gibt kein I, so dass alle Elemente
                                                                       Aus Γ = 1
WFD. 9 ¬ =I Γ                                              gdw. es gibt mindestens ein I, so dass alle
                                                                       Elemente aus Γ = 1
WFD. 10 Γ I= B                                           gdw. Γ = 1 und B = 0 für keine I.

WFD 8 – 10 sind aus den entsprechenden Grunddefinitionen ableitbar.


WF-Theoreme der AL

Das Beweismaterial für die i. F. aufgeführten Theoreme sind (1) die wahrheitswertfunktionale Definition der Konnektive und grammatischen Konventionen und (2) die soeben angegebenen WDF.

Grundlegende Theoreme

Theoreme über 1-wahre, 1-falsche und 1-indeterminierte Sätze

1          I= A                                                    gdw =I – A
2          =I A                                                    gdw I= – A
3          ¬ I= A
            und ¬ =I A                                         gdw ¬ I= – A und ¬ =I – A
4          I= B                                                    gdw für alle Γ, =I Γ, ¬ =I Γ: I= B
                                                                       und für alle A, – A, I= A, =I A: I= B
5          I= B                                                    gdw B I= alle I= A und nur alle I= A
6          =I A                                                    gdw A I= alle Sätze der Form: B, – B, I= B,
                                                                       =I B, d. h. jeden Satz und alle Γ, sei es, dass 
                                                                       =I Γ oder ¬ =I Γ.

Theoreme über inkonsistente Satzmengen

7          =I Γ                                                    gdw Γ I= alle Sätze der Form: B, - B. =I B.,
                                                                       d. h. jeden Satz und jedes Δ, sei es, dass
                                                                       =I Δ oder ¬ =I Δ
8          =I                                                       gdw Γ I= B & - B
9          =I Γ                                                    gdw Ai ϵ Γ, dann Γ I= - Ai  

Theoreme über L-Implikation

10       Γ I= B                                     gdw I= Γ B
11       Γ I= B                                     gdw =I Γ U {-B}
12       Γ I= - B                                   gdw =I Γ U {B}

Theoreme über L-Äquivalenz

13       A I=I B                                               gdw I= A ≡ B
14       A I=I B                                               A I= B und B I= A
15       A I=I B                                               wenn I= A und I= B
16       A I=I B                                               wenn =I A und =I B

Theoreme 1-16 sind nützlich für die Konstruktion verkürzter Wahrheitswerttafeln und für die Verwendung des Verzweigungsverfahrens, weil sie die Definitionen angeben, mit deren Hilfe andere 1-Eigenschaften und 1-Relationen durch Inkonsistenz und Konsistenz definiert werden können. Die Beweise für die Theoreme 1-16 sollten geläufig sein, bevor man sich den folgenden Theoremen zuwendet, die nun in der Metatheorie selbst Verwendung finden werden.

Wichtige Theoreme für die Metalogik
Weitere WFT über 1-Implikationen

17       Wenn Γ I= A und Γ I= B, dann Γ I= A & B                                              (&E)
18       Wenn Γ I= A & B, dann Γ I= A und Γ I= B                                              (&B)
19       Wenn Γ U {A} I= B und Γ U {A} I= - B, dann Γ I= - A                            (– E)
20       Wenn Γ I= – – B, dann Γ I= B                                                                  (– B)
21       Wenn Γ U {A} I= B, dann Γ I= (A B)                                                     (E)
22       Wenn Γ I= A B und Γ I= A, dann Γ I= B                                              (B)
23       Wenn Γ I= A, dann Γ I= A v B                                                                  (v E)  
24       Wenn Γ I= {A v B} und Γ U {A} I= C und Γ U {B} I= C, dann Γ I= C   (v B) 

Da sich mit WFT 14 1-Äquivalenz leicht auf 1-Implikation zurückführen lässt, wird auf die durchaus mögliche Angabe der WFT, mit deren Hilfe die WF-Korrektheit von ≡ E und ≡ B gezeigt werden kann, verzichtet. Beide Regeln werden deshalb auch generell i. F. nicht mehr berücksichtigt.

WFT zur leeren Satzmenge

25       ¬ =I Ø
26       I= B                                                    gdw =I Ø U {– B}
27       =I B                                                    gdw =I Ø U {B}  
28       I= B                                                    gdw Ø I= B  
29       =I B                                                    gdw Ø I= – B

WFT 25 bis 27 sind in dieser Reihenfolge zu beweisen. 25 ist in einer reductio ad absurdum zu beweisen, die letztlich auf die WFD zurückgreifen muss. Aus 25-27 ergeben sich mithilfe der grundlegenden WFT für 1-Implikation die für ND entscheidend wichtigen Theoreme 28 und 29

WFT über Vereinigung von Satzmengen und Teilmengen von Satzmengen

Auch bei den Beweisen dieser Theoreme sollte die Reihenfolge ihrer Auflistung beachtet werden.

30       Wenn Γ I= B, dann für jedes Δ und für jedes A, Γ U Δ I= B
31       Wenn Γ‘ Teilmenge von Γ ist und Γ‘ I= B, dann Γ I= B
32       Wenn Γ I= B und Δ I= B, dann =I {Γ U Δ}
33       Wenn =I Γ, dann für jedes Δ und für jedes A, =I Γ U Δ und =I Γ U {A}
34       Wenn Γ‘ Teilmenge von Γ ist und =I Γ‘, dann =I Γ
35       Wenn =I Γ, dann hat es eine Teilmenge Γ‘, so dass =I Γ‘
36       ¬ =I Γ, gdw. für jede Teilmenge Γ‘ von Γ, ¬ =I Γ‘
37       Wenn ¬ I= Γ U {B} I= A, dann ¬ =I Γ U {A, B}
38       Wenn ¬ =I Γ und es gibt ein Element Ai aus Γ, so dass A oder B = 1 für alle I,
            für die Ai = 1, dann ¬ =I Γ U {A} oder ¬ =I Γ U {B}

Wichtig für die Metalogik des Verzweigungsverfahrens sind 36, 37 und 38. Für die Metalogik von ND wird dann insbesondere auf 30, 31 und 34-36 zu achten sein.


Veröffentlicht von Lilith Dan