Uncountable union of a chain of countable sets can be uncountable?

[Josh Swanson]

Let X be a non-empty set, and let S contain all countable subsets of X. Partially order S by inclusion. Let C be a totally ordered subset ("chain") of S, and let
$$U = \cup_{E \in C} E$$

It appears that U is not always countable: if it were, U would be an upper bound of the chain C, and U would be in S. From Zorn's lemma [by the way, I'm assuming AC throughout] S would have a maximal countable set M. Letting X be any uncountable set, there would then be some point x in X but not in M. Adding x to M produces a larger but still countable set, contradicting M's maximality.

Now I'm confused, since this is very unintuitive to me. For instance, I can't for the life of me construct an explicit chain C letting X be the real numbers. It's certainly the case that a chain resulting in an uncountable U must then be over uncountably many distinct sets E, which should give some uncountable set "uncountably far up" the chain. Of course, this isn't rigorous while the above is, so it must be wrong. So... could someone un-confuse me, perhaps by providing an explicit example of a set of countable sets totally ordered by inclusion whose union is uncountable? Thanks!


To be extra explicit, C is totally ordered. The analogous result without this condition is trivial: the union of all singleton subsets of the real numbers is uncountable.

 

[micromass]

Hi Josh!

Do you know what ordinal numbers are?

 

[Stephen Tashi]

I'm not sure I completely understand the question.

Let X be a non-empty set, and let S contain all countable subsets of X.

Can S contain anything else? Is S exactly the set of countable subsets of X?

Partially order S by inclusion. Let C be a totally ordered subset ("chain") of S,

I'll assume the total order is also by set inclusion.

and let
$$U = \cup_{E \in C} E$$

What about:
X = the real numbers
For a sequence of real numbers {a}, let s(a) denote the set of real numbers which are elements of {a}.
For a real number r, let c(r) denote set of all s{a} where {a} is a sequence of real numbers such that each term of {a} is equal or less than r
C = the set of all c(r) for r a real number.

Would that work?

 

[Amir Livne]

As micromass hinted, it is hard to give an example without ordinal numbers. What I'll try to do in the mean while, is give some intuition how this sort of chain can happen.

A similar question to the one you asked, is if there can be a union of a chain of finite sets which is infinite. This can happen: take the sets {1}, {1,2}, {1,2,3} and so on. That's a chain of sets, and all of them are finite. Their union is $\mathbb{N}$, the set of natural numbers, which is infinite.

Extending this construction to larger cardinalities, is very similar, if you have ordinal numbers. In general this can be done for any cardinality that can be good-ordered. Finding such an example with X being the set of real numbers can be very hard - and U cannot be all the real numbers unless you assume the continuum hypothesis.

 

[disregardthat]

There are uncountably many countable subsets of an uncountable set, so the union of a chain need not necessarily be countable.

Take the countable ordinals under their natural order by inclusion. This poset is actually a chain, and the union is an ordinal. However it cannot be countable.

 

[Josh Swanson]

Thank you all.

@micromass: Nope, I don't really know what ordinals are. That is, I've read the first paragraph of the Wikipedia article on the topic without unwinding the other definitions.

@Stephen: S contains only the countable subsets of X. The total order is the one inherited from S's partial order, so yes, it's also ordered by inclusion. Sorry for my lack of precision. Your example doesn't work, since the sets aren't totally ordered by inclusion: for r=2, {0} and {1} are both in C [obtained from the constant sequences {0, 0, ...} and {1, 1, ...}], yet they're incomparable.

@Amir: the analogous example over the naturals is helpful, thank you. I should have thought of it myself :). I might read some more about ordinals, though I'm much happier with this situation now. I was afraid that constructing an explicit example over the reals might not be possible, or might be extremely difficult. The connection to the continuum hypothesis is interesting. Thanks for pointing it out.

@disregardthat: "There are uncountably many countable subsets of an uncountable set, so the union of a chain need not necessarily be countable." I don't see how this implication holds (though I'm convinced the bit after "so" is true in any case). That is, there are uncountably many chains of countable sets in an uncountable set [each singleton is in its own; by "countable" I'm including finite sets, though that's almost certainly unimportant here]. Supposing the union of each chain were countable, the union of all of their unions could still be uncountable. Thank you for mentioning an explicit example, though I haven't encountered ordinals more than passingly.

 

[micromass]

Thank you all.

@micromass: Nope, I don't really know what ordinals are. That is, I've read the first paragraph of the Wikipedia article on the topic without unwinding the other definitions.

We have an FAQ on the topic https://www.physicsforums.com/showthread.php?t=510966 maybe you'll find this helpful. Let's just say that your question is very difficult to answer without ordinals, but becomes trivial with them :tongue: The analogy with finite numbers by Amir Livne is a very good one and actually generalizes immediately once you know how ordinals behave.

 

[Stephen Tashi]

I admit I don't know what I'm doing, but I can't resist another try at doing this with the real numbers.

Let C1 = the integers

Let C2 = the set formed by taking each integer n and appending to C1, the points in a strictly monotone increasing sequence (I suppose to be specific, I could say a geometric sequence) whose first term is n - 1/2 and which converges to n.

Let C3 = the set formed as follows. Taking each point in p in (C2 - C1). Let the point which immediately preceeds it be q. (I think there always is such an immediate predecessor since we aren't using the points in C1). Append to C2 the points in a strictly monotone increasing sequence whose first term is (q+p)/2 and which converges to p.

Form C4 using the same idea, i.e. for each of its non-limit points p, append to C3 a strictly monotone sequence that coverges to it and begins between it and its predecessor non-limit point.

... etc.

The union of any finite number of the Ci should be countable since it has the cardinality of a finite cartesian product of countable sets. The union of all the Ci has the same cardinality as a countable cartesian product of countable sets. I think this is uncountable.

 

[Josh Swanson]

@micromass: Thank you for the FAQ, it was informative. I have a few questions:

1. Is the set of all ordinals well-ordered by inclusion? I suppose it must be, since you defined the cardinal corresponding to a set X as the "smallest" ordinal that corresponds to a well-ordering of X. The set of ordinals then itself corresponds to an ordinal--is this ordinal important? I have difficulty getting a handle on it.
2. Can the cardinal numbers be taken as the equivalence classes of sets where $A \sim B \Leftrightarrow \exists f:A \rightarrow B$ where f is a bijection?
3. Can the ordinal numbers be taken as the equivalence classes of well-ordered sets where $(A, \leq_A) \sim (B, \leq_B) \Leftrightarrow \exists f:A \rightarrow B$ where f is an order-preserving bijection, i.e. $x \leq_A y \Leftrightarrow f(x) \leq_B f(y)$?
4. How is $\aleph_\alpha$ defined, where $\alpha$ is an ordinal?

@Stephen: Certainly each Ci is countable. It's not clear to me that Ci is or can be well-defined except if the indexing set is the naturals. In that case, their union is just a countable union of countable sets, so is countable. [Brief proof outline: let $\{E_i\}_{i \in \mathbb{N}}$ be a countable collection of disjoint, countable sets, and let $E_i = \{E_{i,1}, E_{i,2}, ...\}$. The function $f(E_{i,j}) = 2^i 3^j$ is an injection from $\cup_i E_i \rightarrow \mathbb{N}$, so this union is countable. The disjoint requirement can be dropped, but tediously so.] The cartesian product of countably many countable sets is uncountable. In fact, the cartesian product of countably many copies of $\{0, 1\}$ is bijectively equivalent to the set of subsets of the natural numbers, so from Cantor's diagonalization argument is uncountable.

I agree, it's very tempting to try to come up with explicit examples. Since my contradiction uses the axiom of choice, it might not be possible to do so explicitly--it's unclear to me.

 

[Amir Livne]

@stephen: In addition to Josh's comments, there is another and more direct problem with your construction. If you build your sets with geometric series like you suggested, and the factor is rational, all the numbers in all the sets are rational, so the union must be countable.

@josh: Your questions are excellent, and touch the heart of set theory.

The usual answer to http://en.wikipedia.org/wiki/Burali-Forti_paradox" is to avoid it. Every axiomatic system I'm aware of for the formalization of set theory disallows some predication - the definition of a set by a predicate. That is, the FAQ defines an ordinal as "a well ordered set where every element is its segment". There is a formula in the logic language to say that a set is an ordinal, but that doesn't mean a set of all sets with this property exists.

In ZF you can only choose elements as a subset on a given set, in NF you have limitations on the form of the predicate, and so on. It is in fact not trivial to prove that all these ordinals actually exist. The finite ones you can build directly, but for $\omega$ you need an axiom which says it exists. Further on, you can build all the countable ordinals (that is, ordinals which are countable as a set) by looking at $\mathbf{P}(\mathbf{P}(\omega))$, but this can't actually be done for every cardinality, you need the Axioms of Replacement for some of them.

There are similar issues with the definitions you propose for cardinal and ordinal numbers. These will work in some axiomatizations but not in others - for example, the cardinal 1 would be {x | x is a set}, so the union of all its elements is the set of all sets. This usually causes paradoxes (although not in every axiom system).

$\aleph_{\alpha}$ is defined simply as the first cardinal that is larger than all $\{ \aleph_{\beta} \mid \beta < \alpha \}$. Proving that such a cardinal exists is not very hard.

 

[disregardthat]

@disregardthat: "There are uncountably many countable subsets of an uncountable set, so the union of a chain need not necessarily be countable." I don't see how this implication holds (though I'm convinced the bit after "so" is true in any case). That is, there are uncountably many chains of countable sets in an uncountable set [each singleton is in its own; by "countable" I'm including finite sets, though that's almost certainly unimportant here]. Supposing the union of each chain were countable, the union of all of their unions could still be uncountable. Thank you for mentioning an explicit example, though I haven't encountered ordinals more than passingly.

My point was that in his argument he implicitly assumed that a chain was countable, but this needs an argument, and in this sense not neccessarily true. I didn't mean that there must be an uncountable chain in any uncountable poset, but I can see how it could be understood as such.

Answers to 1. 2. and 3. are all yes.

Amir Livne: how exactly do you prove that such a cardinal N_a exists?

 

[Josh Swanson]

Thank you all for your input. Sorry for the delay in getting back to this thread. Some day I'll have to start a study of set theory, since it's clear to me that there are far more technicalities in the ideas discussed in this thread than can reasonably be included in it. But, my original question has been answered satisfactorily: my intuition in this case is just plain wrong, and it's at least difficult to come up with an explicit counterexample in the reals, though ordinals provide a counterexample immediately.

Thank you again!