Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: philosophy

Topic: Countability

Julius Hamilton (Jan 21 2025 at 20:08):

One can look up a definition of “countably infinite” on Wikipedia or a textbook:

A set is countably infinite if it can be made in one-to-one correspondence with the natural numbers.

This sounds like the existence and properties of natural numbers are already given. Counting things appears to be an innate mental capability that humans have. To say that there is a one-to-one correspondence between natural numbers and a set $S$ sounds like a fancy, technical way of saying that the elements of $S$ can be counted: $1, 2, 3, \ldots$.

To say that $S$ can be counted tells us about its size. The process of counting something finite is comparable to tallying: for each next thing, add one to the tally. The number of things is the number at the end of the tally process. When someone counts on their own - and is not counting any particular thing - counting does not appear as a correspondence between a tally and some things. There is only the tallying process, on its own.

If we say that there are 6 of something because they can be put in correspondence with a tallying process that terminated at 6, it is implied that 6 is something external to those 6 things. It’s as if we could not say that there are 6 of those things, unless we already knew what 6 was. It makes natural numbers seem fundamental: anything can be counted, so long as we have natural numbers.

Natural numbers can be defined inductively. Start with some arbitrary thing. Call it 0. Introduce a concept of nextness: if there is 0, then there is some next thing to 0. If there is some next thing to 0, then there is some next thing to the next thing to 0. Keep going like that.

Now to say that there are 6 of something means we have a next function $n: \mathbb{N} \to \mathbb{N}$, and a correspondence function $F : \mathbb{N} \to S$, and we have that $F(0) = a$, $F(s(0)) = b$, $\ldots$, $F(s(s(s(s(s(0)))))) = f$.

In order to ground the notion of size, we used the notion of correspondence as a conduit. We said that the size of a set is the size of the natural number that the set’s elements can be put in correspondence with. But then the notion of the size of a natural number proved illusory, because it turned out to be a result of applying a successor function repeatedly.

One way for there to be a correspondence between the set inductively defined by $0$ and $\text{succ}$ (which I’ll refer to as $(0, \text{succ})$) and some other set $S$ is by listing the elements of the correspondence. One might say $f(0) = a, f(1) = b, f(2) = c, \ldots$. If $S$ is finite, we will eventually write every term of the correspondence. But if $S$ is not finite, we cannot show there is a one-to-one correspondence by listing every term of the correspondence.

In this scenario, we might ask, when we said “$S$ is not finite”, how did we know that, and what does that mean?; given that we did away with some of our previous concepts about size. You could say, “I tried counting its elements one by one, and so far, I haven’t come to the end yet”; and this would leave open the question of if $S$ has an end we haven’t reached, or if $S$ never ends.

If you can look at some of the elements of $S$, you can freely choose which one you want to choose next, in your counting. One can imagine selecting a marble from a bowl of marbles, and putting them in a line on a table.

If we assume there is something called “infinite”, and it means “bigger than any finite number” or “never ending”, we can demonstrate that $S$ is countably infinite if we can put the elements of $(0, \text{succ})$ in correspondence with $S$; but because we cannot list every term in the correspondence, there has to be a general rule that tells us how to go from $x \in (0, \text{succ})$ to $y \in S$.

We can imagine that $S$ has infinite elements, but we don’t know what they are. In this case, there is no way to make a rule associating $i \in (0, \text{succ})$ with $y \in S$, except “pick one at random”.

Or, we can say that it isn’t possible to say that $S$ is countably infinite without showing that it has an unending list of elements, and since we can’t list them all, we have to provide a function which will keep giving us new elements of $S$. We can say $S$ has an element $s$, and give a function $g : S \to S$. A correspondence can be established between $(0, \text{succ})$ and $(s, g)$. Let it be a function $h : (0, \text{succ}) \to (s, g)$, such that $h(0) = s$, $\forall x (h(\text{succ}(x)) = g(h(x))$.

We have a correspondence from natural numbers to $S$, but it’s trivial, since $(s, g)$ has the same structure as $(0, \text{succ})$. Through a renaming of symbols, we could say $(s, g)$ is the natural numbers.

One point I would like to make more precise, if I can, is that one may want to make a distinction between a correspondence between $\mathbb{N}$ and a set $S$, versus a rule which turns $n \in \mathbb{N}$ into an $s \in S$ via a computation, but actually the latter is required for the former.

Ryan Wisnesky (Jan 21 2025 at 20:43):

if you just want to characterize an infinite set (not necessarily countable), that's easy to do without numbers: a set is infinite iff it can be put in a bijective correspondence with a subset of itself. but it's difficult for me to imagine a situation where one can define countably infinite sets in general but not the set of natural numbers specifically. At a technical level, the natural numbers are a particularly nice countably infinite set, and such sets are all isomorphic anyway. Conceptually though I'm not sure I believe that either of "counting" or "natural numbers" is prior to the other, they strike me as "the same". Finally, note that many definitions of infinite set / countable are only equivalent in non-constructive settings and many bijections between infinite sets are not necessarily computable (try exhibiting a well order of the reals)

Morgan Rogers (he/him) (Jan 21 2025 at 21:12):

If you look closely at what it means to define something inductively, you'll find the natural numbers hiding in there too ;)

John Baez (Jan 21 2025 at 21:20):

Maybe Julius would be interested to learn about the concept of [[natural numbers object]].