Mathematisches Kolloquium

Zusammenfassung: In 1928, F.P. Ramsey, trying to solve a special case of Hilbert's "Entscheidungsproblem", formulated and proved the following statement:
Given positive integers $n, k, m,$ there exists an integer $N$ such that, given any function $c$ from the collection of the $n$-element-subsets of $N=\{0, 1, \ldots, N-1\}$ to $k=\{0, 1, \ldots, k-1\}$, ($c$ is called a \textit{colouring function}), there exists a subset $A$ of $N$ such that $A$ has $m$ elements and the function $c$ assumes the same value on every $n$-element-subset of $A$.
Ramsey found it useful, for heuristic reasons, to prove also the following statement:
Given positive integers $n, k$, given any function $c$ from the collection of the $n$-element-subsets of the set $\mathbb{N}$ of the natural numbers to the set $k=\{0, 1, \ldots, k-1\}$, there exists a infinite subset $A$ of $\mathbb{N}$ such that the function $c$ assumes the same value on every $n$-element-subset of $A$.
In the early fifties, de Bruijn and Erdös saw that the second statement actually implies the first one. They introduced the so-called "compactness argument".
The nice thing is that such a compactness argument also enables one to prove the famous Paris-Harrington-Ramsey theorem (1976) from the second statement. The Paris-Harrington theorem is a strengthening of the first statement and it is unprovable in Peano Arithmetic.
The second statement itself admits of several proofs, and one of these proofs might also be called a "compactness argument".
We give some comments on these compactness arguments from an intuitionistic point of view.

Alle Interessierten sind hiermit herzlich eingeladen. Eine halbe Stunde vor dem Vortrag gibt es Kaffee und Tee im Sozialraum (Raum B448) im 4. Stock.

Treffpunkt zum Abendessen wird noch bekannt gegeben.