Ramsey's theorem and König's lemma (Q866890)

From MaRDI portal





scientific article; zbMATH DE number 5126639
Language Label Description Also known as
English
Ramsey's theorem and König's lemma
scientific article; zbMATH DE number 5126639

    Statements

    Ramsey's theorem and König's lemma (English)
    0 references
    0 references
    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

    Identifiers