Ramsey's theorem and König's lemma (Q866890)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey's theorem and König's lemma |
scientific article |
Statements
Ramsey's theorem and König's lemma (English)
0 references
14 February 2007
0 references
Let \([X]^n\) denote the set of \(n\)-element subsets of \(X\). For natural numbers \(n\), \(k\), Ramsey's theorem \(\text{RT}^n_k\) states: For any infinite set \(X\) and map \(F: [X]^n\to k\), there is an infinite subset \(Y\subseteq X\) such that the restriction of \(F\) to \([Y]^n\) is constant. König's infinity lemma states: An infinite tree having finite levels has an infinite branch. Then the authors prove: König's lemma follows from \(\text{RT}^2_2\). Further: For each fixed \(n\), the statements \(\text{RT}^n_k\) are equivalent for all integers \(k\geq 2\). If \(n_1\geq n_2\geq 1\) and \(k_1,k_2> 1\), then \(\text{RT}^{n_1}_{k_1}\to\text{RT}^{n_2}_{k_2}\). Corollary: For each \(n\geq 2\), König's lemma follows from \(\text{RT}^n_2\). For any sequence \(\sigma= (\sigma_k: k\in\omega)\) of positive integers, let DC\(_\sigma\) be the statement that any tree in which all elements on the \(k\)th level have exactly \(\sigma_k\) immediate successors, has an infinite branch. The last theorem considers implications \(\text{DC}_\sigma\to \text{DC}_\tau\), for infinite sequences \(\sigma\), \(\tau\) of positive integers.
0 references
Ramsey's theorem
0 references
König's lemma
0 references
Axiom of choice
0 references