This is part II of this question I asked yesterday. In the link you can find a proof of the $\Delta$-system lemma. In case 1 it uses the axiom of choice (correct me if I'm wrong). Now one can also prove the $\Delta$-system lemma differently, for example as follows:

enter image description here

I have two questions about it:

1) It seems to me that by using the ordinals to index the family of sets we have eliminated the axiom of choice from the proof. Have we or did we just use it a bit earlier in the proof where we index the family $B$?

2) But, more importantly, why is it ok to assume that $b \in B$ are subsets of $\omega_1$? In the theorem there is no such restriction. Can one just "wlog" this? The answer is probably yes since otherwise the proof would be wrong but I don't see how.

Thanks for your help!


2 Answers 2


Some Choice is used in justifying the assumptions on $B$ -- effectively, in proving Exercise 16.1. I will sketch this below.

It is clear that passing to an uncountable subset of our given family does not influence solving the problem (a $\Delta$-system on this subset is one for the entire family as well).

Now we invoke a bit of Choice to ensure that there is a subset of our family of size $\omega_1$; this establishes $B = \{b_\xi: \xi < \omega_1\}$ is allowed.

A further bit of Choice establishes that $\bigcup B$ also has cardinality $\omega_1$; we conveniently identify it with $\omega_1$; now we have $B \subseteq [\omega_1]^{<\aleph_0}$.

The "$\omega_1$-pigeonhole principle" (which also uses a bit of choice) ensures there is some $n$ such that $B \cap [\omega_1]^n$ is uncountable; WLOG we restrict from $B$ to $B \cap [\omega_1]^n$.

Thus we have reduced Theorem 16.1 to Claim 16.2.

  • $\begingroup$ Thank you. I must have had a stupid moment when I asked the question. Duh. $\endgroup$ Commented Apr 30, 2013 at 13:42

You need some AC to prove the statement just for a family of pairs of $\omega_1$.

If $\omega_1$ is the union of a countable family $\{B_n:n \in \omega \}$ of countable sets (which is consistent with ZF!), then the family $\{\{n, \beta\}: n<\omega, \beta \in B_n-\omega \}$ does not contain an uncountable $\Delta$-system.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .