### Abstract

The theory of partition relations concerns generalisations of Ramsey's theorem. For any ordinal $\alpha$, write $\alpha \to (\alpha, m)^2$ if for each function $f$ from unordered pairs of elements of $\alpha$ into $\{0,1\}$, either there is a subset $X\subseteq \alpha$ order-isomorphic to $\alpha$ such that $f\{x,y\}=0$ for all $\{x,y\}\subseteq X$, or there is an $m$ element set $Y\subseteq \alpha$ such that $f\{x,y\}=1$ for all $\{x,y\}\subseteq Y$. (In both cases, with $\{x,y\}$ we require $x\not=y$.) In particular, the infinite Ramsey theorem can be written in this notation as $\omega \to (\omega, \omega)^2$, or if we restrict $m$ to the positive integers as above, then $\omega \to (\omega, m)^2$ for all $m$. This entry formalises Larson's proof of $\omega^\omega \to (\omega^\omega, m)^2$ along with a similar proof of a result due to Specker: $\omega^2 \to (\omega^2, m)^2$. Also proved is a necessary result by Erdős and Milner: $\omega^{1+\alpha\cdot n} \to (\omega^{1+\alpha}, 2^n)^2$.

### License

BSD License

### Topics

- Mathematics/Combinatorics
- Logic/Set theory

### Session Ordinal_Partitions

- Library_Additions
- Partitions
- Erdos_Milner
- Omega_Omega

### Depends on

- The Nash-Williams Partition Theorem
- Zermelo Fraenkel Set Theory in Higher-Order Logic

## Cite

×

Ordinal_Partitions-AFP

    @article{Ordinal_Partitions-AFP,
      author  = {Lawrence C. Paulson},
      title   = {Ordinal Partitions},
      journal = {Archive of Formal Proofs},
      month   = {August},
      year    = {2020},
      note    = {\url{https://isa-afp.org/entries/Ordinal_Partitions.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Aug 18, 2020 : Isabelle2020