How can an infinite set be countable?

Question

The definition for a countable set is: A non-empty set $S$ is countable when its elements can be a arranged in a sequence; that is, when $S$ is of the form: $$S= \{s_1,s_2,s_3,...\}$$ The sequence can be finite or infinite.

But how can an infinite set be countable?

Edited 17/03/19

The definition was from the book 'The Lebesgue Integral for Undergraduates' by William Johnston. The term 'countable' in this book has been used in the following context: 'sets are countable when the elements of that set can be arranged as a sequence'. The definition I believe is for the cardinality of a set.

My question is how can an infinite set be arranged if the elements seemingly go on forever?

Answer 1

The best example:

The set $\mathbb N$

It obviously contains infinitely many elements, whereas they can be arranged in an increasing sequence of the form $$\mathbb N=\{1, 2, 3, ...\}$$

Answer 2

Actually, countability comes from being able to define a bijection between the set in question with some subset of the natural numbers, $\mathbb{N}$. It just so happens that in finite situations this corresponds to being able to laying all the elements out in a line.

Answer 3

The definition for a countable set is: A non-empty set $S$ is countable when its elements can be a arranged in a sequence

Well, no. Or rather: that's a definition in natural language, and those are always slippery. In particular, "sequence" often means "finite sequence," and I suspect that's implicit in how you're thinking about the "definition" you've given.

The precise definition of countability is:

A set $X$ is countable if there is an injection from $X$ to $\mathbb{N}$.

(Some authors also demand that $X$ be infinite.) The connection with the natural-language definition of countability you've given is this: if $f:X\rightarrow\mathbb{N}$ is an injection, we can think of this as arranging $X$ in a (possibly finite) sequence with $n$th term being $f^{-1}$ of the $n$th element of the range of $f$ (in particular, if $f$'s range is all of $\mathbb{N}$, the sequence has $n$th term $f(n)$).

---

With this definition it should be obvious that there are lots of infinite countable sets - e.g. $\mathbb{N}$ itself (the identity function is an injection from $\mathbb{N}$ to $\mathbb{N}$). More interesting examples include:

• The set of even natural numbers: consider the map $x\mapsto {x\over 2}$.

• The set of integers: consider the map sending $x\ge 0$ to $2x$ and $x<0$ to $2\vert x\vert+1$. Note that I consider $0$ to be a natural number.

• The set of rational numbers: this one's a bit more tricky, but combines an injection of $\mathbb{Q}$ into the set of ordered pairs of natural numbers (exercise: think about putting a fraction into lowest terms ...) and a pairing function.

(At this point, one might conjecture that all "naturally-occurring" infinite sets are countable. Of course, this is false.)