𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A short proof of a partition theorem for the ordinal ωω

✍ Scribed by Jean A. Larson

Publisher
Elsevier Science
Year
1973
Weight
716 KB
Volume
6
Category
Article
ISSN
0003-4843

No coin nor oath required. For personal study only.

✦ Synopsis

An ordinal a is equal to the set of its predecessors and is ordered by the membership relation. For any ordinal a, one writes a -~ (a, m) 2 if and only if for any set A order-isomorphic to a, and any function f from the pairs of elements of A into {0, 1}, either there is a subset X c_ A order-isomorphic to a, so that f of any pair of elements of X is zero, or there is an m element set Y c_ A, so that f of any pair of elements of Y is one.

Erd~Ss and Rado [4] first asked for which ~ and m does this relation hold. Specker [ 10] first noticed the special difficulty in proving it for eoo, where 60 o is that ordinal which is the result of raising w to the power 6o by ordinal exponentiation. With the usual ordering, 6o`o is order-isomorphic to the set of finite sequences of natural numbers ordered first by.length and then lexicographically.

Chang [ 1 ] proved that wo -~ (wo, 3) 2, and E.C. Milner (unpublished) generalized his result to prove the following theorem:

For all natural numbers m, wo -\* (coo , m) 2 .

📜 SIMILAR VOLUMES

A short proof of the preservation of the
A short proof of the preservation of the ωω-bounding property
✍ Chaz Schlindwein 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

## Abstract There are two versions of the Proper Iteration Lemma. The stronger (but less well‐known) version can be used to give simpler proofs of iteration theorems (e.g., [7, Lemma 24] versus [9, Theorem IX.4.7]). In this paper we give another demonstration of the fecundity of the stronger versio

A Proof of Halpern–Läuchli Partition The
A Proof of Halpern–Läuchli Partition Theorem
✍ S.A. Argyros; V. Felouzis; V. Kanellopoulos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 116 KB

A proof of the Halpern-Läuchli partition theorem and its version for strong subtrees is given. We prove a general statement which has, as an immediate consequence, the above-mentioned results. The proof of this is direct and avoids metamathematical arguments. Some consequences for partitions of fini

A short proof for a generalization of Vi
A short proof for a generalization of Vizing's theorem
✍ Claude Berge; Jean Claude Fournier 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 1 views

## Abstract For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these re

A new short proof for the Kruskal-Katona
A new short proof for the Kruskal-Katona theorem
✍ P Frankl 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 96 KB

We give a very short proof for the Kruskal-Katona theorem and Lovhsz's version of it: given (~) k-element sets there are at least (k~\_l) (k -1)-element sets which are contained in at least one of the k-sets.

A short proof of the Chen-Manalastas the
A short proof of the Chen-Manalastas theorem
✍ J.A. Bondy 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 232 KB

Gallai and Milgram (1960) proved that a digraph with stability number ct is spanned by ct disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of