I'm trying to solve the following problem from Schimmerling's "A Course on Set Theory."

(Problem) Prove that there exists a family $\mathcal G\subseteq\mathcal P(\omega)$ such that $|\mathcal G|=2^{\aleph_0}$ and that for all $A,B\in\mathcal G$, if $A\neq B$ then $A\cap B$ is finite.

This problem has previous parts. First, it asks to show that the ordinal $^{<\omega}2=\bigcup_{n<\omega}{^{n}2}$ is countable. For this, I argued that $^{<\omega}2$ is a subset of $\omega$ (indeed, $^{<\omega}2\subseteq\bigcup_{n<\omega}n=:\omega)$). Second, it asks to show that the set

$$\mathcal F=\{\{x\upharpoonright n:n<\omega\}\mid x\in~^\omega2\}$$

has cardinality $2^{\aleph_0}$. For this, I constructed a bijection between the elements of $\mathcal F$ and the elements of $2^{\aleph_0}$. Specifically, for every function from the set of natural numbers to $\{0,1\}$, there is a corresponding function of the form $\{x\upharpoonright n:n<\omega\}$. (The latter set sort of describes the function recursively; so I'm thinking that $\mathcal F$ is in fact the set of all possible functions, recursively defined, from $\omega$ to $\{0,1\}$.)

The issue I'm facing now is to apply the previous results to prove the main problem. While a hint was given to first show that $\mathcal F\subseteq\mathcal P(^{<\omega}2)$, I can't derive it. (My attempts to biject $\mathcal F$ with a subset of $\mathcal P(^{<\omega}2)$ have failed.)

Assuming I could derive it, I also cannot seem to see its usefulness. If $\mathcal F$ is supposed to be the $\mathcal G$ in the problem, then it does not seem apparent that for all $A,B\in\mathcal F$ we yield a finite intersection $A\cap B$. (E.g., let $A$ and $B$ -- two functions from $\omega$ to $\{0,1\}$-- agree ultimately.)

I suspect that there is something mistaken in my interpretation of one (or more) of the sets above. Indeed, I would also like to ask if there are any general methods or tricks I could use to understand/interpret sets that are defined over many "levels" of quantifiers and predicates, such as $\mathcal F$ above. Also, are there useful ways to understand cardinals/ordinals beyond their definitions that lead to quicker and less confusing solutions?

  • $\begingroup$ One thing that may be confusing you is that $^{\mathord{<}ω}2$, which is defined as $\bigcup_{n<\omega}{^n2}$, is not an ordinal. It the set of functions from natural numbers to 2. $\endgroup$ – Trevor Wilson Nov 27 '13 at 16:45

HINT: Think of $^{<\omega}2$ as a tree. Branches are exactly those of the form $\{x\upharpoonright n\mid n\in\omega\}$ for some $x\in{}^2\omega$. Show that two different branches must have a finite intersection. Then by the countablility of the tree the result transfers to $\omega$ itself.

  • $\begingroup$ Do you mean "finite intersection"? $\endgroup$ – Trevor Wilson Nov 27 '13 at 16:43
  • $\begingroup$ @Trevor: Yes. Yes I do. Thank you. $\endgroup$ – Asaf Karagila Nov 27 '13 at 16:52
  • $\begingroup$ Trevor, besides that, looking down from a proper class of Woodin cardinals, can you even make the difference between finite and countable? :-) $\endgroup$ – Asaf Karagila Nov 27 '13 at 17:02
  • $\begingroup$ It is important because I want to tell the difference between finitely many Woodin cardinals and $\omega$ many Woodin cardinals :-) $\endgroup$ – Trevor Wilson Nov 27 '13 at 17:07
  • $\begingroup$ Trevor: Touche; but still having a proper class of them, it doesn't make any difference! :-) $\endgroup$ – Asaf Karagila Nov 27 '13 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.