Do we need Axiom of choice(or weaker version axiom of countable choice) to say countable Cartesian product of countable sets is nonempty? I think yes. I read somewhere answer no giving argument: each countable set can be well ordered and after well ordering each countable set we choose least element in each to prove their Cartesian product is non empty. But I see gap in this argument because there are many ways a countable set can be well ordered. So which way we will well order sets?
$\begingroup$
$\endgroup$
12
-
$\begingroup$ It is false in general that the countable product of countable sets is countable. Take for example $\prod_{\alpha\in \aleph_0}{2}=2^{\aleph_0}=|\mathbb{R}|$. $\endgroup$– HaydenCommented Nov 26, 2014 at 15:08
-
$\begingroup$ @Hayden Sorry there was mistake in typing which completely changed the meaning of question. Now see it makes sense or not $\endgroup$– SushilCommented Nov 26, 2014 at 15:12
-
$\begingroup$ Ah, that makes much more sense. The argument you give does require the axiom of choice (you have to choose for each set a well-ordering, i.e. a bijection with $\mathbb{N}$). $\endgroup$– HaydenCommented Nov 26, 2014 at 15:16
-
$\begingroup$ But bijection with N also we can define in many ways and I doubt in uncountable no. of ways $\endgroup$– SushilCommented Nov 26, 2014 at 15:18
-
$\begingroup$ Choosing a single bijection isn't an issue, even though there are many ways to do so. Finite choice only refers to the indexing set, not the sets being indexed, and this is provable without AC. It's only when you move to the infinite indexing set that AC (or one of its weaker versions) is needed. $\endgroup$– HaydenCommented Nov 26, 2014 at 15:20
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
3
Even when free the sets have a natural well order to them, the countable union of countable sets is not necessarily countable.
For example, in some models of $\sf ZF$ the first uncountable ordinal, $\omega_1$ is the countable union of countable ordinals.
And no, the countable product of finite sets doesn't have to be non-empty without choice, let alone that of countable sets. Not only that, it is true that the statement "every countable product of countable sets is non-empty" is strictly weaker than the axiom of countable choice.
In fact! It can Bethe case that the countable product of countable sets are non-empty, but there is a countable family of countable sets whose union is not countable. Because in the proof of the latter we choose from sets of size continuum, not just countable sets.
answered Nov 26, 2014 at 15:49
-
$\begingroup$ And 'Every countable product of finite set is nonempty' must be strictly weaker. Am I right? $\endgroup$– SushilCommented Nov 26, 2014 at 15:57
-
$\begingroup$ and just for reference axiom: 'every countable product of countable sets is non-empty' would it imply dedekind finite and finite sets are same? $\endgroup$– SushilCommented Nov 26, 2014 at 16:05
-
1$\begingroup$ Yes to the first, no to the second (In Cohen's first model every countable family of countable sets has a non-empty product; but there is an infinite Dedekind-finite set of real numbers). $\endgroup$– Asaf Karagila ♦Commented Nov 26, 2014 at 16:31
$\begingroup$
$\endgroup$
2
If you have a product $\prod_{i\in I}x_i$ of sets $x_i$ indexed by some set $I$, then an element in that product is exactly a choice of an element $y_i \in x_i$ for each $i \in I$. The axiom of choice (and its weaker counterparts) will therefore tell you exactly that such an element always exists.
Note that there are products that can be proven to be non-empty even without the axiom of choice. For instance, if all the $x_i$ are ordinals or subsets of ordinals.
And yes, choosing a well-ordering for each $x_i$ is (at least) as difficult as choosing a single element, logically speaking. So unless there's a distinguished well-ordering you can choose (for instance, if the $x_i$ are ordinals, then $\in$ defines a well ordering for all of them, or if the union $\bigcup_{i \in I}x_i$ admits a well-ordering, or $I$ is finite), then you're back where you started, and in need of choice.
-
1$\begingroup$ I think the OP is asking if, when $x_i$ is countable for each $i$ and $I$ is also countable, the result continues to hold even if we don't assume choice, or if it requires some weaker variant like countable choice. $\endgroup$– HaydenCommented Nov 26, 2014 at 15:18
-