Was ist Logik?

Zuerst Collegium Logicum. Da wird der Geist Euch wohl dressiert, In spanische Stiefeln eingeschnürt, Daß er bedächtiger so fortan Hinschleiche die Gedankenbahn, Und nicht etwa, die Kreuz und Quer, Irrlichteliere hin und her. Dann lehret man Euch manchen Tag, Daß, was Ihr sonst auf einen Schlag Getrieben, wie Essen und Trinken frei, Eins! Zwei! Drei! dazu nötig sei. [ …] Der Philosoph, der tritt herein Und beweist Euch, es müßt so sein: Das Erst wär so, das Zweite so, Und drum das Dritt und Vierte so; Und wenn das Erst und Zweit nicht wär, Das Dritt und Viert wär nimmermehr.

Goethe, “Faust”

Was ist Logik?

If it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.

Lewis Caroll

“Alice through the Looking Glass”

03Bxx General logic 03Cxx Model theory 03Dxx Recursion theory 03Exx Set theory 03Fxx Proof theory and constructive math. 03Gxx Algebraic logic 03Hxx Nonstandard models

AMS Classification 1991

03E: Set Theory

03E05 Combinatorial set theory 03E10 Ordinal and cardinal numbers 03E15 Descriptive set theory 03E20 Other classical set theory 03E25 Axiom of choice and related propositions 03E30 Axiomatics of classical set theory 03E35 Consistency and independence results 03E40 Other aspects of forcing 03E45 Constructibility, ordinal definability, … 03E47 Other notions of set-theoretic definability 03E50 Continuum hypothesis and Martin’s axiom 03E55 Large cardinals 03E60 Determinacy and related principles 03E65 Other hypotheses and axioms 03E70 Nonclassical and second-order set theories 03E75 Applications 03E99 None of the above but in this section

Logik und “naive” Mathematik

• Methoden aus der Logik

– Sätze aus der Logik können in Sätze der naiven Mathematik “übersetzt” werden (Beispiel: Maß und Kategorie)

• Resultate aus der Logik

– Logik zeigt, daß Fragen aus der naiven Mathematik keine Antwort haben, bzw nicht richtig gestellt sind (Beispiel: Verbände)

– Logik beantwortet Fragen aus der naiven Mathematik (Beispiel: Gleichverteilung/Maßtheorie)

• …

Beispiel 1: Maß und Kategorie

Definition. Für jede Halbordnung (P, <) sei

b(P) := min {#A : A ⊆ P, A unbeschränkt }

Beispiel. Sei N das Ideal der Lebesgue-Null-mengen in ℝ geordnet durch Inklusion. b(N) is die Antwort auf die Frage: Wieviele Nullmengen muß man vereinigen, um eine Menge von positivem äußeren Maß zu bekommen? Offensichtlich ist ℵ_{0} < b(N) ≤ 2^{ℵ_{0}}.

Analog sei M das Ideal der mageren Mengen ( = Mengen von 1. Kategorie). b(M) ist die kleinste Anzahl von mageren (oder: nirgends dichten) Mengen, deren Vereinigung von 2. Kategorie ist.

Frage. Gibt es einen Zusammenhang zwischen b(N) und b(M)? Satz (Bartoszyński). b(N) ≤ b(M)

“Additivity of measure implies additivity of category”

Beispiel. b(P) ≤ b(P × Q). Definition. Seien (P, <) und (Q, <) Halbordnungen. P ≺ Q bedeutet: Es gibt Funktionen e, π:

e : P → Q
P ← Q : π

sodass e(p) ≤ q ⇒ p ≤ π(q). Beispiel. Seien P und R Halbordnungen. Dann ist P ≺ P × R. e(p) = (p, beliebig ), π(p, r) = p. Bemerkung. Wenn P ≺ Q, dann b(P) ≤ b(Q).

Satz (Fremlin).

N ≺ M

Beweis. Wie im Satz von Bartoszyński !

Warnung des Vortragenden: Die Anwendung der Kontinuumshypothese kann das Erkennen von Zusammenhängen behindern!

Beispiel 2: Algebra

Definition. Sei L = (L, ∨, ∧) ein Verband. L heißt “ordnungspolynomvollständig”, wenn jede monotone Funktion f : L^{n} → L durch ein Verbandspolynom (mit Koeffizienten in L) dargestellt werden kann. Beispiel. M_{n} ist o.p.c.

Frage (naiv). Gibt es einen unendlichen ordungspolynomvollständigen Verband? Antwort (naiv). Weiß nicht.

Frage (Logik). A. Kann man beweisen, daß es einen unendlichen o.p.c. Verband gibt? B. Kann man beweisen, daß es keinen unendlichen o.p.c. Verband gibt?

Antwort (Logik). A. Nein! [Goldstern+Shelah 1997] B. Weiß (noch) nicht.

Beispiel 3: Gleichverteilung/Maßtheorie

Definition. Sei x̄ = (x_{1}, x_{2}, …) eine {0, …, 9}- Folge. x̄ heißt gleichverteilt, wenn für alle w ∈ {0, …, 9} gilt:

lim_{N→∞} \frac{#\{i < N : a_{i} = w\}}{N} = \frac{1}{10}

Die Diskrepanz oder Abweichung von der Gleichverteilung wird durch

D(x̄, N) = 10· max_{w∈\{0,... ,9\}} |\frac{#\{i < N : a_{i} = w\}}{N} −\frac{1}{10} |

definiert.

Sei k eine natürliche Zahl. Für jede natuerliche Zahl N mißt die k-Diskrepanz D_{k}(x̄, N) =

max_{w:{1,... ,k}→{0,... ,9}}

|\frac{#\{i < N : (a_{i+1} , …, a_{i+k} ) = (w(1), …, w(k))\}}{N} − \frac{1}{10^{k}} |·10^{k}

wie gut die 10^{k} vielen {0, …, 9}-Worte der Länge k in den ersten N + k Elementen von x̄ gleichverteilt sind.

D_{k}(x̄, N) = max_{w:{1,... ,k}→{0,... ,9}}

|\frac{#\{i < N : (a_{i+1} , …, a_{i+k} ) = (w(1), …, w(k))\}}{N} − \frac{1}{10^{k}} |·10^{k}

x̄ heißt “k-gleichverteilt”, wenn

lim_{N→∞} D_{k}(x̄, N) = 0

ist. Elemente von _{k∈ℕ}^{⋂}{x̄ : x̄ ist k-gleichverteilt }

heissen “vollständig gleichverteilt” (=normal zur Basis 10). Fast alle Folgen sind k-gleichverteilt. (Gesetz der großen Zahl) Daher: Fast alle Zahlen sind normal.

Definition. Sei s : ℕ → ℕ. x̄ heißt s(N)- gleichverteilt oder s-gleichverteilt, wenn gilt:

lim_{N→∞} D_{s(N)}(x̄, N) = 0

Definition. Eine Folge s : ℕ → ℕ heißt “langsam”, wenn

lim_{N→∞} log N − log log N − s(N) = ∞

Satz (Flajolet,Kirschenhofer,Tichy;Grill). Fast alle Folgen sind s-gleichverteilt ⇔ ⇔ s : ℕ → ℕ ist langsam. Frage. Ist die Menge

⋂ ; s langsam {x̄ : x̄ ist s-gleichverteilt }

– leer?

– meßbar mit Maß 0?

– meßbar mit vollem Maß? Satz. Sei (B_{t})_{t:ℕ→ℕ} eine Borel-Familie, μ(B_{t}) = 0 für alle t, und

∀n : t(n) < t′(n) ⇒ B_{t} ⊆ B_{t′}

Dann ist

μ(_{t}^{⋃} B_{t}) = 0

Korollar. Fast alle Folgen liegen in

⋂ ; s langsam {x̄ : x̄ ist s-gleichverteilt }

The set W := {t : ∃x t ∈ B_{x}} is a Σ_{1}^{1} set, hence measurable. Assume that μ(W) > 0. So there exists a Borel (closed) set A with μ(A) > 0 such that A ⊆ W. Note that the statement

(∗) ∀t : [t ∈ A ⇒ ∃x t ∈ B_{x}]

is a Π_{2}^{1}-statement, hence absolute between any two transitive universe with the same ordinals [Shoenfield].

Now let r be a random real over the universe V, r ∈ A, and work in V [r]. Random forcing is ℕ^{ℕ}-bounding, i.e., we have

∀x ∈ ℕ^{ℕ} ∃x′ ∈ ℕ^{ℕ} ∩ V : x ≤ x′

This implies ∀x ∈ ℕ^{ℕ} ∃x′ ∈ ℕ^{ℕ} ∩ V : B_{x} ⊇ B_{x′}, and so

⋃_{x∈ ℕ^{ℕ}} B_{x} = ⋃_{x′∈ ℕ^{ℕ}∩V} B_{x′}

Moreover,

∀x′ ∈ ℕ^{ℕ} ∩ V : r ∉ B_{x′}

(since r is a random real and each B_{x′} is of measure 0), so together we get in V [r]:

∀x ∈ ℕ^{ℕ} : r ∉ B_{x}.

Since (∗) holds also in V [r], we get V [r] ⊧ r ∉ A, a contradiction.