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
    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