This question comes from chapter six of Enderton's Elements of Set Theory. It immediately follows a discussion of the axiom of choice, including Zorn's lemma, if that's relevant. Omega represents the set of natural numbers.

Assume that $S$ is a function with domain $\omega$ such that $S(n) \subseteq S(n^+)$ for each $n \in \omega$. (Thus $S$ is an increasing sequence of sets.) Assume that B is a subset of the union $\cup _{n \in \omega} S(n)$ such that for every infinite subset $B'$ of $B$ there is some $n$ for which $B' \cap S(n)$ is infinite. Show that $B$ is a subset of some $S(n)$.

My idea for the proof goes something like this, after days of thinking about it:

  1. Suppose $B$ isn't a subset of any $S(n)$.
  2. (Using the axiom of choice) Let $B'$ be the set which contains a member of each successive $S(n)$ minus all of the previous $S(n)$'s. Of course this will be a subset of $B$. Furthermore, $B'$ should be infinite because if it weren't, $B$ would be a subset of whichever is the last $S(n)$ to have unique elements in it.
  3. There must be some $S(m)$ such that $S(m) \cap B'$ is infinite and therefor equinumerous with $\omega$. But then $S(m)$ must contain an infinite number of members from sets further in the sequence $(S(m^+)$, $S(m^{++})$, etc.) which are explicitly defined as not being members of $S(m)$. This is a contradiction.

This proof concept feels like it works, but there's no answer in the book for me to check it with. Is everything I've done here legal? Is there an easier or more obvious proof that I'm missing?

  • 1
    $\begingroup$ My edits were only for a typo, the 2nd word of the 3rd line of the 2nd paragraph "subest", and to move a left bracket from outside the dollars to inside so it would appear on the same line as what followed it $\endgroup$ – DanielWainfleet Apr 26 '18 at 3:45

Your basic idea is right, but the presentation becomes somewhat murky around step 3.

Since you're starting by assuming the negation that you want to show in step 1, your goal is then to reach a contradiction. But it looks like you're losing sight of that goal when you reach step 3.

The clear way to obtain a contradiction there would be to observe that $B'\cap S(n)$ is finite for every $n$ (because by construction this intersection has exactly $n$ elements, one for each increase). But this directly contradicts your assumption about all $B'\subseteq B$, and then you're done.

In step 2 you need to do something explicit about the risk that $S(n)=S(n-1)$ in one of the steps, such that there are no elements in the delta you can choose one from.

The slickest way to dealt with that (see bof's comment for a slicker one) may be to conduct your entire proof as a lemma with the additional assumption that $S(n)\subsetneq S(n+1)$ for every $n$, and then afterwards showing that your real goal follows from that: If there are infinitely many $n$ where $S(n)$ increases, then there is a subsequence you can apply the lemma to, and if there are only finitely many, then $B=S(n)$ for some $n$, and then your desired conclusion is trivial.

In general mathematical writing you could probably get away with just saying

Without loss of generality, assume that $S(n)\ne S(n+1)$ for all $n$.

before your argument begins, but for classwork purposes you'll probably be expected to give an explicit argument why you can afford making that additional assumption.

Small nitpick: When you write

Let $B'$ be the set which contains a member of each ...

"the set" should be "a set", because there will be many sets that satisfy your description, even though you need only one of them.

  • $\begingroup$ Or just choose for each $n$ an element $b_n\in B\setminus S(n)$ and let $B'=\{b_1,b_2,b_3,\dots\}.$ $\endgroup$ – bof Apr 26 '18 at 3:42
  • $\begingroup$ @bof: You're right, that is simpler. (Though arguing that $B'$ is infinite becomes slightly more involved). $\endgroup$ – Henning Makholm Apr 26 '18 at 10:29

I am sorry I have not checked your work. The following proof came to me:

For $b\in B$ let $f(b)$ be the least $n\in \omega$ such that $b\in S(n).$

By contradiction, suppose $C(n)=B\setminus S(n) \ne \emptyset$ for every $n\in \omega.$ By the Axiom of Choice there exists $B'=\{g(n):n\in\omega\}\subset B$ where $g(n)\in C(n)$ for each $n\in \omega.$

Now $B'$ is infinite. Otherwise, with $m=\sup \{f(x):x\in B'\},$ we have $B'\subset \bigcup_{j\leq m}S(j)=S(m),$ which implies that $g(m)\in S(m),$ contrary to $g(m)\in C(m)=B\setminus S(m).$

So since $B'$ is an infinite subset of $B,$ take the least (or any) $n\in \omega$ such that $B'\cap S(n)$ is infinite. Then $\{m\in \omega:g(m)\in S(n)\}$ is infinite, so there exists $m\in \omega$ with $m>n,$ such that $g(m)\in S(n).$ But $g(m)\not\in S(m)\supset S(n),$ so $g(m)\not \in S(n).$ This is the desired contradiction.

  • 1
    $\begingroup$ We use a special case (CC, for Countable Choice) of AC (the Axiom of Choice). CC is: If $ \emptyset \not\in F=\{T(n):n\in\omega \},$ there exists $g:\omega\to \cup F$ such that $\forall n\in \omega\;(g(n)\in T_n).$ $\endgroup$ – DanielWainfleet Apr 26 '18 at 3:28
  • 1
    $\begingroup$ At first I thought I would need 2 cases:(1). $B$ finite (Easy case) (2), $B$ infinite, I thought I would need to use the non-finiteness of $B$ in case (2), but when writing it out I saw that I hadn't .. $\endgroup$ – DanielWainfleet Apr 26 '18 at 3:55

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.