2
$\begingroup$

There seem to be many questions along the same line but none of them seem to be quite what I am asking, so here goes:

If a set is countable, then we know that a bijection exists between it and the natural numbers. Can we then not choose the canonical bijection to be the first one we became aware of? I realize this is not a completely mathematical definition but I have a hard time arguing against it too. Of course this bijection might be different from person to person and from time to time but that shouldn't matter.

$\endgroup$
4
  • 1
    $\begingroup$ Given finitely many non-empty sets, it is provable without any choice-like assumptions that there is a function assigning to each of the sets one of its elements. In particular, if a set is countable, there is a function that selects an enumeration among all possible ones. This is not the issue. Countable choice is needed when countably (infinite) many selections are needed. (The objects being selected could themselves be functions, numbers, or other sets.That's not relevant here either.) $\endgroup$ Commented Mar 21, 2014 at 20:28
  • $\begingroup$ This is somewhat related to the following: what is the least number not uniquely definable in less than fifteen English words? The basic point being that as it is "not a completely mathematical definition" we have a hard time justifying its use. $\endgroup$
    – user642796
    Commented Mar 21, 2014 at 20:28
  • $\begingroup$ How are you using the word "canonical" here? It doesn't appear to be any standard usage of the term. $\endgroup$ Commented Mar 21, 2014 at 20:35
  • $\begingroup$ @Andres: You're correct, but it seems to me that the question and its title are not truly related. It seems as if the OP saw that we need to use countable choice to prove that the countable union of countable sets is countable, and we do that by choosing an enumeration. Therefore, the OP suggests, maybe we can choose "the first enumeration that appears in our universe" and thus eliminate the use of the axiom of choice. But as we know, that's not how it works. $\endgroup$
    – Asaf Karagila
    Commented Mar 21, 2014 at 20:57

2 Answers 2

2
$\begingroup$

There is no good canonical choice. The reason is that for something canonical we need to first have some canonical hierarchy of constructing the universe, and then we need to be able to say within a certain level what is "first" and what is "second".

For example, if $V=L$ is true, then we have such way. Because we can consider the $L$-hierarchy and the definable global well-ordering of $L$ (which is based on that hierarchy). In that case, indeed we can choose the least such bijection.

However, we don't always have that. What we do have is the von Neumann hierarchy, but that doesn't come with a definable well-ordering. And so, for example, when there are countable sets added to the universe, we often "discover" many bijections at once. Not just one. So which one are we going to take? There's no definable choice which "always works out".

The fact is that this is even worse. Even if the set is well-orderable, nay a countable ordinal, there is still no canonical way of choosing a bijection with $\omega$. For example in models where $\omega_1$ is a countable union of countable sets are models where this is true -- there is no way of choosing a canonical enumeration for every countable ordinal. And of course, such models exist (if any models of $\sf ZFC$ exist, that is).

So your suggestion, while reasonable, can only be true in models which have a particular construction, and usually it is such a construction from which we can prove that the axiom of choice is true in that model to begin with.


I should also add that your informal suggestion, and your admittance to this informality "Of course this bijection might be different from person to person and from time to time but that shouldn't matter." is exactly why we try our very best to be as formal as possible in mathematics.

I want that whenever I say $V_{\omega+\omega}$, it doesn't matter who is reading, as long as they understand the definition, they will think about a single concrete object. Otherwise, if everyone is allowed to interpret things according to their own will we have chaos. And you can look back at the historical definition of "function" to see what can happen then.

$\endgroup$
1
$\begingroup$

The point of the axiom of countable choice is that if $X$ is countable, i.e. $X = \{x_1,\ldots\}$ and all $x_i$ are non-empty then there exists a function $f$ such that $f(n) \in x_n$ for all $n = \{0,1,\ldots\} = \omega$.

That's not the same as a function which enumerates the elements of $X$, i.e. a function with $g$ with $g(n) = x_n$. In fact, such a function of course always exists if $X$ is countable - that's what $X$ being countable says. (And my sloppy $X = \{x_1,\ldots\}$ notation actually already assumes the existance a such a function - the indexing function $n \to x_n$)

To get from an enumeration of the elements of $X$ (i.e. $g$) to a choice function (i.e. $f$), you have to pick one element from each of the $x_i$, and make it's $f$'s image of $i$. It's exactly this picking that you cannot do without the axiom of (countable) choice. For countable choice, you're only assured that you can pick countably many times, where as full choice assumes that you can pick $\alpha$-many times for every cardinal $\alpha$.

$\endgroup$

You must log in to answer this question.

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