11.3.2021

Gottlob Frege Begriffsschrift 1879 (erste Formulierung der Prädikatenlogik).

Darin kann man alle Aussagen formulieren und beweisen, die wir heute
in der Mathematik und klassischen Logik formulieren bzw. beweisen
können.

David Hilbert hat eine Reihe von Kalkülen aufgestellt und untersucht,
die auf der Begriffsschrift basieren.

Bertrand Russel: Begriffsschrift ist widersprüchlich.
Sie ist zu stark. Man darin widersprüchliche Aussagen formulieren.

Lügner-Paradoxon:
Der Satz, den ich gerade spreche, ist falsch.
Ist dieser Satz wahr oder falsch?
Wenn er wahr ist, dann ist er falsch und umgekehrt.
Dies ist ein Widerspruch.

Definition:
Ein Wort heiße selbstzutreffend, wenn es auf sich selbst zutrifft. Es
heiße selbstunzutreffend, wenn es auf sich selbst nicht zutrifft.

Beispiele:
Das Wort "dreisilbig" ist dreisilbig. Also ist "dreisilbig"
selbzutreffend.
Das Wort "zweisilbig" ist dreisilbig, also nicht zweisilbig. Es ist
also selbstunzutreffend.
Ist das Wort "selbstunzutreffend" selbstzutreffend oder
selbstunzutreffend?
Wenn es selbstzutreffend ist, dann ist es selbstunzutreffend, also
nicht selbstzutreffend und umgekehrt.
Widerspruch.

In der Begriffsschrift kann man Prädikate (Eigenschaften oder
Relationen) definieren. In heutiger Schreibweise würden wir ein
Definition einer Eigenschaft (eines Prädikats) P etwa so schreiben:
P(x) :<=> ...
In der Begriffsschrift kann man dann definieren
P(x) :<=> nicht x(x)            für alle x.
P(x) sagt aus "x ist selbstunzutreffend".
Wir bekommen einen Widerspruch durch Anwendung von P auf P:
P(P) <=> nicht P(P).

Bertrand Russel, Whitehead: Principia Mathematica:
Kalkül, der die Begriffsschrift einschränkt, indem jedes
Prädikat/Funktion eine Stufe zugewiesen bekommt und immer nur auf
Objekte (Stufe 0) oder Prädikate/Funktionen niedrigerer Stufe
angewendet werden darf.
In diesem Kalkül treten diese Widersprüche nicht auf.

Heute verwenden wir ähnliche Kalküle wie den von Principia Mathematica
oder noch eingeschränkter (z.B. nur bis zur ersten Stufe:
Prädikatenlogik erster Stufe, englisch: first order predicate logic).

Alles, was formalisierbar ist als Algorithmus oder Computerprogramm,
lässt sich in der Prädikatenlogik erser Stufe ausdrücken.

Kurt Gödel: Aufgestellte Kalküle für die reine Prädikatenlogik erster
Stufe sind korrekt (man kann damit nur allgemeingültige Formeln
herleiten) und vollständig (man kann damit alle allgemeingültigen
Formeln herleiten). Korrekheitssatz, Vollständigkeitssatz.
Nicht-Allgemeingültigkeit ist nicht formalisierbar.

Die meisten mathematischen Theorien (z.B. Zahlentheorie, also Theorie
der natürlichen Zahlen) sind aber nicht formalisierbar. (Kurt Gödel)
Unvollständigkeitssatz der Zahlentheorie.

Die Zahlentheorie ist formalisierbar in der Prädikatenlogik zweiter
Stufe, aber die Prädikatenlogik zweiter Stufe ist nicht
formalisierbar.

Individuenbereich (englisch domain)


18.3.2021

x₀=5, ε=0,1
δ:=0,005
Sei x eine reelle Zahl mit  |x-x₀| < δ.
Dann ist 4,995 < x < 5,005
24,9 < 24,950025 < x² < 25,050025 < 25,1
|x²-x₀²| < ε.

x=x  ist Infixschreibweise für  =(x,x).

x=y => (Fx => Fy)     nur wenn x und y in Fx bzw. Fy
                      nicht durch ∀ oder ∃ gebunden.
x=y => (∃y x<y => ∃y y<y)       gilt nicht.

Axiom der vollständigen Induktion:
∀P (P(0) ∧ ∀x (P(x)=>P(f(x))) =>  ∀x P(x))

Sei P ein 1-stelliges Prädikat auf der Menge der
natürlichen Zahlen und es gelte
P(0) ∧ ∀x (P(x)=>P(f(x))).
Dann gilt
P(0).
Wegen ∀x (P(x)=>P(f(x))) gilt also P(f(0)), also P(1).
Wegen ∀x (P(x)=>P(f(x))) gilt also P(2).
Wegen ∀x (P(x)=>P(f(x))) gilt also P(3).
Und so weiter.


25.3.2021
Beispiel für mögliche Axiome:

A∨¬A
∀x F[x] -> F[t]

Beispiel für eine Schlussregel "modus ponens"

A     A -> B
------------
     B

Beispiel für eine Schlussregel:

 F[a]
———–———     wobei a nicht in F[x] vorkommt
∀x F[x]

F[x] steht für eine Formel, in der die Variable x frei vorkommen darf.
F[a] steht für die Formel, die sich daraus ergibt, indem man alle
freien Vorkommen von x durch a ersetzt.

F[x] ≡ x=a  ist nicht erlaubt, also

 a=a
—————–     verletzt die Bedingung, dass a nicht in F[x] vorkommt.
∀x x=a

P(∅)={∅}
P({1,2,3}) =
{∅, {1}, {2}, {1,2},
 {3}, {1,3}, {2,3}, {1,2,3}}

f:R->R
f(x)=x³    f ist injektiv und surjektiv
g(x)=x²    g ist nicht injektiv, weil g(3)=9 ∧ g(-3)=9, aber 3 ≠ -3.
           g ist nicht surjektiv, weil es kein x gibt mit g(x) = -1.

Wenn f:A->B, dann f(A):={f(x)|x∈A}.

Wenn A abzählbar, dann A höchstens gleichmächtig zu N, also existiert
eine injektive Abbildung f von A nach N. Definiere θ(n) als dasjenige
x∈A mit f(x) ist die (n+1)-te Zahl von f(A).

A =    {x₀,x₂,x₃,x₅,...}  f(xᵢ)=i
f(A) = { 0, 2, 3, 5,...}
n:       0  1  2  3 ...
θ(n):   x₀ x₂ x₃ x₅ ...

θ(N)={θ(n)|n∈N}


15.4.2021
n'=n∪{n}
n'=n+1 für jede natürliche Zahl n.

0 = ∅
0' = 0∪{0} = {0}
0'' = 0'∪{0'} = {0,0'}
0''' = 0''∪{0''} = {0,0',0''}

0 = {}
1 = {0}
2 = {0,1}
3 = {0,1,2}
...


21.4.2021

B3A2(a) Sei x:=f(1). Dann ist x∈A, weil f:{1,...,n+1}->A.
Da f bijektiv ist, ist f surjektiv. Wegen x∈A gibt es
also ein k∈{1,...,n+1} mit f(k)=x.

Definiere g:{1,...,n}->A\{x} durch
g(j):=f(j)    für j<k
g(j):=f(j+1)  für j≥k.


22.4.2021

x₁, x₂, x₃, ...
x'  x'' x''' ...
In Programmiersprachen: Wörter werden strings genannt. ι(a) = "a"

29.4.2021
Seien L,L' über Σ akzeptiert von DEA A,A'.
A=(Q,Σ,δ,q₀,F), A'=(Q',Σ,δ',q₀',F').
DEA für Σ^*\L: (Q,Σ,δ,q₀,Q\F)
Für L∩L' und L∪L' stellen wir uns vor, dass wir
die Automaten A und A' synchron laufen lassen:
Automaten für L∩L' und L∪L':
(Q×Q',Σ,θ,(q₀,q₀'),E)
θ((q,q'),a):=(δ(q,a),δ'(q',a))
(q,q')∈E <=> q∈F ∧ q'∈F'    bzw. q∈F ∨ q'∈F'.


2.6.2021

Blatt 5 Aufgabe 2:
x+0  = x
x+y' = (x+y)'

4+2 = 4+1' = (4+1)' = (4+0')' = (4+0)'' = 4'' = 6.

add(x,0)  = x
add(x,y') = add(x,y)'

Ansatz: add=(Rfg). Dann muss gelten:
add(x,0)  = f(x)
add(x,y') = g(add(x,y),x,y)
Wir wählen  f(x) := x  und  g(u,x,y) := u'.
Dann ist add=(Rfg), also unser Ansatz führt dann zum Ziel.

Es gilt dann  f = P_1^1  und
g(u,x,y) = N(P_1^3(u,x,y)) = (NP_1^3)(u,x,y), also  g = (NP_1^3).
Nach unserem Ansatz ist   add = (RP_1^1(NP_1^3)).