\documentclass[german]{slides}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[german]{babel}
\newcommand{\3}{\ss}
\parindent0cm


{\catcode`\"12
\expandafter\gdef\csname german@sh@"3@\endcsname{\ss}
}

\advance\vsize4cm
\swapnumbers

\theoremstyle{definition}
% \theoremstyle{remark}

\def\xx#1 {\newtheorem{#1}[thm]{#1}}
\newtheorem{thm}{Theorem}
\def\itm#1 {\item[{(#1)}]}
\xx Notation
\xx Theorem
\xx Lemma
\xx Definition 
\xx Beispiel
\xx Satz
\xx Korollar
\xx Bemerkung
\xx Frage
\xx Antwort

\newcommand{\section}[1]{\medskip\begin{center}#1\end{center}\par}
\newcommand{\N}{{\mathcal N}}
\newcommand{\M}{{\mathcal M}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\NN}{{\mathbb N}}

\advance\rightskip 0cm plus 3cm
\hyphenpenalty2000
%\showthe\parskip
\parskip=0.4\parskip

% \renewcommand{\thethm}{}



\makeatletter

\renewcommand{\swappedhead}[3]{\thmname {#1}%
\thmnote  { {\the \thm@notefont (#3)}}}


\newcommand{\qqq}[1]{\smallskip\hbox to \hsize{\hfil\em #1}}



\begin{document}

\section{Was ist Logik?}

%\begin{description}
%\item{ -- 18. Jahrhundert -- }
\smallskip

 Zuerst Collegium Logicum.                    \\
   Da wird der Geist Euch wohl dressiert, \\
   In spanische Stiefeln eingeschn"urt, \\
   Da"3 er bed"achtiger so fortan \\
   Hinschleiche die Gedankenbahn, \\
   Und nicht etwa, die Kreuz und Quer, \\
   Irrlichteliere hin und her. \\
   Dann lehret man Euch manchen Tag, \\
   Da"3, was Ihr sonst auf einen Schlag \\
   Getrieben, wie Essen und Trinken frei, \\
   Eins! Zwei! Drei! dazu n"otig sei. \\
   \relax   [\dots]\\
%   Zwar ist's mit der Gedankenfabrik \\
%   Wie mit einem Weber-Meisterst"uck, \\
%   Wo ein Tritt tausend F"aden regt, \\
%   Die Schifflein her"uber hin"uber schie"3en, \\
%   Die F"aden ungesehen flie"3en, \\
%   Ein Schlag tausend Verbindungen schl"agt. \\
   Der   Philosoph,
        %  Logiker, 
                      der tritt herein \\
   Und beweist Euch, es m"u"3t so sein: \\
   Das Erst w"ar so, das Zweite so, \\
   Und drum das Dritt und Vierte so; \\
   Und wenn das Erst und Zweit nicht w"ar, \\
   Das Dritt und Viert w"ar nimmermehr. \\
%   Das preisen die Sch"uler allerorten,
%   Sind aber keine Weber geworden.


\qqq{Goethe, ``Faust''}

\newpage
\section{Was ist Logik?}
%\item{-- 19. Jahrhundert --}
%\begin{quotation}
%    `Contrariwise,' continued Tweedledee, `
\noindent
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.
%\end{quotation}

\qqq{Lewis Caroll}\qqq{``Alice through the Looking Glass''}


\vfill
%\item{ -- 20.Jahrhundert -- }

\def\ite[#1]{\par\noindent\hbox to 0pt{\hss\bf #1.}}
\medskip


{
  
\openup -25pt


\begin{description}\let\ite\item
% \ite[03-xx] Reference/Exposition/Historical/...
% \ite[03A05] Philosophical and critical

%      * 03-00 General reference works (handbooks, dictionaries,
%        bibliographies, etc.)
%      * 03-01 Instructional exposition (textbooks, tutorial papers, etc.)
%      * 03-02 Research exposition (monographs, survey articles)
%      * 03-03 Historical (must be assigned at least one Dclassification
%       number from Section 01)
%      * 03-04 Explicit machine computation and programs (not the theory of
%        computation or programming)
%      * 03-06 Proceedings, conferences, collections, etc.
%      * 03A05 Philosophical and critical, {For philosophy of mathematics,
%        See 00A30 }

\ite[03Bxx]     General logic
\ite[03Cxx]     Model theory
\ite[03Dxx]     Recursion theory
\ite[03Exx]     Set theory
\ite[03Fxx]     Proof theory and constructive math.
\ite[03Gxx]     Algebraic logic
\ite[03Hxx]     Nonstandard models
\end{description}

}



\qqq{AMS Classification 1991}

\eject


{\small  % set theory
\openup -7pt
\section{03E: Set Theory}

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




}
% \end{description}


\newpage


% Wechselwirkungen zwischen Logik und ``naiver'' Mathematik: 


\begin{center}\bf Logik und ``naive'' Mathematik
\end{center}

\begin{itemize}
\item Methoden aus der Logik
\begin{itemize}
\item  S"atze aus der Logik k"onnen in S"atze der naiven Mathematik
``"ubersetzt'' werden \\(Beispiel: Ma\3 und Kategorie)
\end{itemize}
\item Resultate aus der Logik
\begin{itemize}
\item Logik zeigt, da\3 Fragen aus der naiven Mathematik keine Antwort
haben, bzw nicht richtig gestellt sind\\ (Beispiel:  Verb"ande)
\item Logik beantwortet Fragen aus der naiven Mathematik\\ (Beispiel:
                                Gleichverteilung/Ma"3theorie)
\end{itemize}

%\item Fragen aus der Logik werden mit naiver Mathematik beantwortet
\item \dots 
\end{itemize}

%\end{document}
\newpage


\newdimen\aa\newdimen\bb
\aa-5.2pt
\bb5.6pt

\def\led{\leaders\vrule depth \aa height \bb width 5pt\hfil
%\relax\global\advance\aa-0.1pt\global\advance\bb0.1pt
}

\def\ce#1{\vbox to -20pt{\vskip -3cm 
\hrule\vskip4pt\hbox to \hsize{\led\  #1\ \led}\vskip4pt\hrule\vss}}
\ce{ Beispiel 1:  Ma"3 und Kategorie}


\medskip\begin{Definition} 
F"ur jede Halbordnung  $(P,<)$ sei 
$$b(P) := \min\{\#A : A \subseteq P, \mbox{$A$ unbeschr"ankt}\}$$
\end{Definition}




\medskip\begin{Beispiel} 
Sei $\N$ das Ideal der Lebesgue-Null\-mengen in $\RR$
geordnet durch Inklusion.  \\
$b(\N)$ is die Antwort auf die Frage:\\
  Wieviele Nullmengen mu\3 man
vereinigen, um eine Menge von positivem "au\3eren Ma\3 zu bekommen?  
\\
Offensichtlich ist $ {\aleph_0} <  b(\N) \le 2^{{\aleph_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. 
\end{Beispiel}
\bigskip\bigskip
\begin{Frage} Gibt es einen Zusammenhang zwischen $b(\N)$ und $b(\M)$?
\end{Frage}


\vfill
\medskip\begin{Satz}[Bartoszy\'nski]
$ b(\N ) \le b(\M)$
\end{Satz}
{\small ``Additivity of measure implies additivity of category''}
\eject
\ce{  Beispiel 1:  Ma"3 und Kategorie }

\begin{Beispiel}  $b(P) \le b(P \times Q)$. 
\end{Beispiel}

\medskip\begin{Definition}   Seien $(P,< )$ und $(Q,<)$ Halbordnungen.  
$P \prec Q$ bedeutet:   
Es gibt Funktionen $e$, $\pi$: 
\begin{align*}
e: P &\to Q\\
   P & \leftarrow Q: \pi\\
\end{align*}
sodass $e(p ) \le q \Rightarrow p \le \pi(q)$. 
\end{Definition}



\medskip\begin{Beispiel}
Seien $P$ und $R$ Halbordnungen. \\
  Dann ist $P\prec P \times R$.
   $e(p) = (p, \hbox{  beliebig })$, $\pi(p,r)=p$. 
\end{Beispiel}

\medskip\begin{Bemerkung}
Wenn $P \prec Q$, dann $b(P) \le b(Q)$. 
\end{Bemerkung}

\vfill\begin{Satz}[Fremlin]
$$\N \prec \M$$
\end{Satz}
\begin{proof} Wie im Satz von Bartoszy\'nski !
\end{proof}
\eject

{ \advance \rightskip 0pt plus 3cm minus 1cm\openup 5pt

\bf 
Warnung des Vortragenden: \\  Die Anwendung der
Kontinuumshypothese kann das Erkennen von Zusammenh"angen
behindern!

}

 \newpage

\ce{Beispiel 2: Algebra}
\medskip\begin{Definition} Sei $L = (L, \vee, \wedge)$ ein Verband.
$L$ hei"3t ``ordnungspolynomvollst"andig'', wenn jede monotone
Funktion $f: L^n \to L$ durch ein Verbandspolynom (mit Koeffizienten
in $L$)  dargestellt werden kann. 

% {\small (Ein
% Polynom "uber $L$ ist ein wohlgeformter Ausdruck, der aus
% Variablen $x,y,\ldots$ und Elementen von $L$ mit den Symbolen $\vee$,
% $\wedge$ aufgebaut wird, z.B.\ $p(x,y) = ((x \vee a) \wedge b)\vee (x
% \wedge y)$.    Jedes Polynom in $n$ Variablen induziert eine monotone
% Funktion von $L^n $ nach $L$)}

\end{Definition}

\medskip\begin{Beispiel}
$M_n$ ist o.p.c.
\end{Beispiel}


\bigskip\bigskip
\medskip\begin{Frage}[naiv]
Gibt es einen unendlichen ordungspolynomvollst"andigen Verband?
\end{Frage}
\medskip\begin{Antwort}[naiv]
Wei"3 nicht.
\end{Antwort}


\bigskip\bigskip

\medskip\begin{Frage}[Logik]

A. Kann man beweisen, da"3 es einen unendlichen o.p.c.\ Verband
gibt?
\\
B.  Kann man beweisen, da"3 es {\em keinen} unendlichen o.p.c.\
Verband gibt? 


\end{Frage}
\bigskip\bigskip
\medskip\begin{Antwort}[Logik]
\ \\
A.  Nein!    [Goldstern$+$Shelah 1997]
\\
B.  Wei"3 (noch) nicht. 

\end{Antwort}






\newpage
\ce{Beispiel 3: Gleichverteilung/Ma"3theorie}


\medskip\begin{Definition}  Sei $\bar x = (x_1, x_2, \ldots)$ eine
$\{0,\ldots,9\}$-Folge.  $\bar x$ hei"3t gleichverteilt, wenn 
f"ur alle $w\in \{0,\ldots, 9\}$ gilt: 
$$ \lim_{N \to \infty} 
\frac{\#\{i<N: a_{i} = w \} } {N} = \frac{1}{10}$$
Die Diskrepanz oder Abweichung von der Gleichverteilung wird durch 
$$ D(\bar x, N) = 10\cdot \max_{w\in  \{0, \ldots , 9\}}
\bigl|\frac{\#\{i<N: a_{i} = w \} } {N} -  \frac{1}{10}\bigr| $$
definiert. 


Sei $k$ eine nat"urliche Zahl.  F"ur jede natuerliche
Zahl $N$ mi"3t die $k$-Diskrepanz
$ D_k(\bar x, N) =$
{\small\openup3pt     % display
\begin{multline*}
 \max_{w: \{1, \ldots , k\} \to \{0, \ldots,9\}}  \\
\left| 
 \frac{\#\{i<N: (a_{i+1}, \ldots, a_{i+k})=(w(1), \ldots,w(k))\}}{N} -
\frac{1}{10^k} \right| \cdot 10^k 
  \end{multline*}

}
wie gut die $10^k$ vielen $\{0,\ldots,9\}$-Worte der L"ange $k$ in den ersten
$N+k$  Elementen von $\bar x$ gleichverteilt sind. 
\end{Definition}

\newpage
\ce{Beispiel 3: Gleichverteilung/Ma"3theorie}
\vskip-2cm
$$ D_k(\bar x, N) = \  \max_{w: \{1, \ldots , k\} \to \{0,\ldots, 9\}} $$
{\small    % display
$$
\left| 
 \frac{\#\{i<N: (a_{i+1}, \ldots, a_{i+k})=(w(1), \ldots,w(k))\}}{N} -
\frac{1}{10^k} \right| \cdot 10^k 
$$
}
$\bar x$ hei"3t ``$k$-gleichverteilt'', wenn
$$ \lim_{N\to\infty} D_k(\bar x, N) = 0 $$
ist.    
Elemente von 
$ \bigcap\limits_{k\in\NN}
 \{\bar x:  \mbox{$\bar x$ ist $k$-gleichverteilt}\}$
heissen ``vollst"andig gleichverteilt''  
(=normal zur Basis 10). 
\\
Fast alle Folgen sind $k$-gleichverteilt.   (Gesetz der
gro"3en Zahl) Daher: Fast alle Zahlen sind normal.
\bigskip
\medskip\begin{Definition}
Sei $s:\NN \to \NN$. 
$\bar x$ hei"3t $s(N)$-gleichverteilt oder $s$-gleichverteilt, wenn gilt:
$$ \lim_{N\to\infty} D_{s(N)}(\bar x, N) = 0 $$
\end{Definition}



\medskip\begin{Definition} Eine Folge 
 $s:\NN \to \NN$ hei"3t\\
 ``langsam'', wenn
$$ \lim_{N\to \infty}\  \log N - \log\log N -s(N) = \infty $$
\end{Definition}

\eject
\ce{Beispiel 3: Gleichverteilung/Ma"3theorie}

\begin{Satz}[Flajolet,Kirschenhofer,Tichy;Grill]
\ \\
Fast alle Folgen sind 
$s$-gleichverteilt  $\Leftrightarrow$ \\
\qquad \qquad  $\Leftrightarrow$ 
$s:\NN \to \NN$ ist langsam. 
\end{Satz}

\medskip\begin{Frage}
Ist die Menge 
$$ \bigcap _{\mbox{$s$ langsam}} \{\bar x: \mbox{$\bar x$ ist
  $s$-gleichverteilt}\}$$ 
-- leer?\\
-- me"3bar mit Ma"3 0?  \\
-- me"3bar mit vollem  Ma"3?
\end{Frage}
\vfill
\medskip\begin{Satz}
 Sei $(B_t)_{t:\NN \to \NN}$ eine Borel-Familie, $\mu(B_t) = 0$ f"ur
 alle $t$, und
$$ \forall n: t(n) < t'(n) \ \Rightarrow \ B_t \subseteq B_{t'}$$
Dann ist $$\mu\bigl(\bigcup_t B_t \bigr) = 0$$
\end{Satz}

\bigskip
\bigskip
\bigskip
\begin{Korollar} 
Fast alle Folgen liegen in 
$$ \bigcap _{\mbox{$s$ langsam}} \{\bar x: \mbox{$\bar x$ ist $s$-gleichverteilt}\}$$
\end{Korollar}

\eject


% \ce{Beispiel 3: Gleichverteilung/Ma"3theorie}
% { \small    % beweis
% 
% \begin{proof}[Beweis(Skizze)] Wir beweisen nur, da"3 
% $$ (*) \qquad \qquad \exists x\, \forall t \,\, x \notin B_t$$ 
%  Sei $V$ ein abz"ahlbares Universum, in dem alle S"atze
% der wirklichen Welt  gelten (Satz von L"owenheim und Skolem).  Sei $r$
% ein ``random real'' "uber $V$, also eine  reelle Zahl, die in keiner
% Nullmenge von $V$ enthalten ist.  
% 
%    Dann ist $V[r] $ wieder ein
%  Universum (Satz "uber forcing-Erweiterungen, Cohen/Solovay).  
% $$ \forall t \in V \,\, \Rightarrow r\notin B_t$$
% weil $r$ ``random'' ist. 
% 
%    F"ur jedes $t\in V[r]$ gibt es aber ein
% $t'\in V$ mit $t \le t'$.  (Folklore)
% 
%  Wegen  $r\notin B_{t'}$ also auch $r\notin
% B_{t}$. Also gilt $$ \forall t\in V[r]: \ \  r \notin B_t$$ 
% daher: 
% $$ \mbox{In $V[r]$ gilt:} \qquad 
%                  \exists x \ 
% %\mbox{\small (n"amlich $r$) }
%  \forall t : \  x \notin B_t$$ 
% In $V[r]$ gelten nun vielleicht andere S"atze als in $V$, aber S"atze
% wie der in $(**)$ mit nur zwei Quantoren sind ``absolut'' (Satz von
%  Shoenfield), daher gilt $(*)$ auch in $V$, somit auch in
% Wirklichkeit.  
% \end{proof}
% 
%}
%\newpage

\ce{Beispiel 3: Gleichverteilung/Ma"3theorie}
{\small
\def\omega{\NN}
\def\sq{ \omega ^ \omega }
\def\cut{\cap}
\def\bigcut{\bigcap}
The set $ W := \{ t: \exists  x \, t\in
B_x\}$ is a $\bf\Sigma^1_1$ 
set, hence measurable.  Assume that $\mu(W)>0$.   So there exists a
Borel (closed)  set $A$ with $\mu(A)>0 $ such that $A \subseteq
W$.  Note that the statement
$$ (*) \qquad\qquad 
 \forall t:  \left[ t \in A \ \Rightarrow \ \exists x \,\,t\in B_x \right]$$
is a $\bf\Pi^1_2$-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\in A$, 
 and work in $V[r]$.  Random forcing is $\sq$-bounding, i.e., we have 
$$ \forall x\in \sq\, \exists x'\in \sq\cut V : x \le x'$$
This implies $ \forall x\in
\sq\, \exists x'\in \sq\cut V: B_x \supseteq B_{ x'}$, and so 
$$  \bigcup _{x\in \,\sq} B_x = 
\bigcup_{x'\in \,\sq\cut V} B_{x'}$$
Moreover, 
$$ \forall x'\in \sq\cut V : r \notin B_{x'}$$
(since $r$ is a random real and each $B_{x'}$ is of measure 0),
 so   together we get  in $V[r]$:
$$ \forall x\in \sq :  r \notin B_x. $$
Since $(*)$ holds also in $V[r]$, we get $V[r] \models r\notin A$, a
contradiction. 


}



% \newpage
% Das Manuskript f"ur diesen Vortrag, sowie die Folien, k"onnen im
% World-Wide-Web derzeit unter 
% \begin{center}
% \tt
% http://math.fu-berlin.de/\char`\~goldstrn
% \end{center}
% und ab Mitte Oktober  auch unter 
% \begin{center}
% \tt
% http://info.tuwien.ac.at/theoinf/\char`\~goldstrn
% \end{center}
% abgerufen werden. 
% 
% \bigskip 
% \bigskip 
% 
%    Kommentare k"onnen an 
% \begin{center}
% \tt Martin.Goldstern@tuwien.ac.at
% \end{center}
% geschickt werden. 
% \newpage
% \frenchspacing
% { \small   % bibliography
% \openup 5pt
% 
% {\bf Tomek Bartoszy\'nski}, \\{\em Additivity of measure implies    
%    additivity of category}.\\ Trans. Amer. Math. Soc. 281 (1984).
% %   209--213. 
% 
% {\bf  P.~Flajolet, P.~Kirschenhofer and R.F.~Tichy},\\
% {\em  Deviations from
%         uniformity in 
%         random strings.}\\ Probab.\ Th.\ Rel.\ Fields 80 (1988).
% 
% {\bf David Fremlin}, {\em Cicho\'n's diagram}.\\  Presented at the
% S\'eminaire Initiation \`a l'analyse, G.~Choquet, M.Rogalski, J. Saint
% Raymont, Universit\'e Pierre et Marie Curie, Paris. 
% 
% {\bf Martin Goldstern}, \\
% {\em An Application of Shoenfield's Absoluteness Theorem
%                   to the Theory of Uniform Distribution}.\\
% Monatshefte f"ur Mathematik 116 (1993).
% %, 237--243.
% 
% {\bf Martin Goldstern und Saharon Shelah}, \\
% {\em Order polynomially complete lattices must be LARGE}.\\
% Algebra Universalis. 1997?
% 
% {\bf  K.~Grill}, \\
% {\em A note on Randomness.}\\
%  Stat.\ and Probab.\ Letters. 14 (1992). 
% 
% }
\end{document}

