1.4.2: Enumerations and Countable Sets
- Page ID
- 121644
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)
We’ve already given examples of sets by listing their elements. Let’s discuss in more general terms how and when we can list the elements of a set, even if that set is infinite.
Informally, an enumeration of a set \(A\) is a list (possibly infinite) of elements of \(A\) such that every element of \(A\) appears on the list at some finite position. If \(A\) has an enumeration, then \(A\) is said to be countable.
A couple of points about enumerations:
- We count as enumerations only lists which have a beginning and in which every element other than the first has a single element immediately preceding it. In other words, there are only finitely many elements between the first element of the list and any other element. In particular, this means that every element of an enumeration has a finite position: the first element has position \(1\), the second position \(2\), etc.
- We can have different enumerations of the same set \(A\) which differ by the order in which the elements appear: \(4\), \(1\), \(25\), \(16\), \(9\) enumerates the (set of the) first five square numbers just as well as \(1\), \(4\), \(9\), \(16\), \(25\) does.
- Redundant enumerations are still enumerations: \(1\), \(1\), \(2\), \(2\), \(3\), \(3\), … enumerates the same set as \(1\), \(2\), \(3\), … does.
- Order and redundancy do matter when we specify an enumeration: we can enumerate the positive integers beginning with \(1\), \(2\), \(3\), \(1\), …, but the pattern is easier to see when enumerated in the standard way as \(1\), \(2\), \(3\), \(4\), …
- Enumerations must have a beginning: …, \(3\), \(2\), \(1\) is not an enumeration of the positive integers because it has no first element. To see how this follows from the informal definition, ask yourself, “at what position in the list does the number 76 appear?”
- The following is not an enumeration of the positive integers: \(1\), \(3\), \(5\), …, \(2\), \(4\), \(6\), …The problem is that the even numbers occur at places \(\infty + 1\), \(\infty + 2\), \(\infty + 3\), rather than at finite positions.
- The empty set is enumerable: it is enumerated by the empty list!
If \(A\) has an enumeration, it has an enumeration without repetitions.
Proof. Suppose \(A\) has an enumeration \(x_1\), \(x_2\), … in which each \(x_i\) is an element of \(A\). We can remove repetitions from an enumeration by removing repeated elements. For instance, we can turn the enumeration into a new one in which we list \(x_i\) if it is an element of \(A\) that is not among \(x_1\), …, \(x_{i-1}\) or remove \(x_i\) from the list if it already appears among \(x_1\), …, \(x_{i-1}\). ◻
The last argument shows that in order to get a good handle on enumerations and countable sets and to prove things about them, we need a more precise definition. The following provides it.
An enumeration of a set \(A \neq \emptyset\) is any surjective function \(f \colon \PosInt \to A\).
Let’s convince ourselves that the formal definition and the informal definition using a possibly infinite list are equivalent. First, any surjective function from \(\PosInt\) to a set \(A\) enumerates \(A\). Such a function determines an enumeration as defined informally above: the list \(f(1)\), \(f(2)\), \(f(3)\), …. Since \(f\) is surjective, every element of \(A\) is guaranteed to be the value of \(f(n)\) for some \(n \in \PosInt\). Hence, every element of \(A\) appears at some finite position in the list. Since the function may not be injective, the list may be redundant, but that is acceptable (as noted above).
On the other hand, given a list that enumerates all elements of \(A\), we can define a surjective function \(f\colon \PosInt \to A\) by letting \(f(n)\) be the \(n\)th element of the list, or the final element of the list if there is no \(n\)th element. The only case where this does not produce a surjective function is when \(A\) is empty, and hence the list is empty. So, every non-empty list determines a surjective function \(f\colon \PosInt \to A\).
A set \(A\) is countable iff it is empty or has an enumeration.
A function enumerating the positive integers (\(\PosInt\)) is simply the identity function given by \(f(n) = n\). A function enumerating the natural numbers \(\Nat\) is the function \(g(n) = n - 1\).
The functions \(f\colon \PosInt \to \PosInt\) and \(g \colon \PosInt \to \PosInt\) given by \[\begin{aligned} f(n) & = 2n \text{ and}\\ g(n) & = 2n+1\end{aligned}\] enumerate the even positive integers and the odd positive integers, respectively. However, neither function is an enumeration of \(\PosInt\), since neither is surjective.
Define an enumeration of the positive squares \(1\), \(4\), \(9\), \(16\), …
The function \(f(n) = (-1)^{n} \lceil \frac{(n-1)}{2}\rceil\) (where \(\lceil x \rceil\) denotes the ceiling function, which rounds \(x\) up to the nearest integer) enumerates the set of integers \(\Int\). Notice how \(f\) generates the values of \(\Int\) by “hopping” back and forth between positive and negative integers: \[\begin{array}{c c c c c c c c} f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & \dots \\ \\ - \lceil \tfrac{0}{2} \rceil & \lceil \tfrac{1}{2}\rceil & - \lceil \tfrac{2}{2} \rceil & \lceil \tfrac{3}{2} \rceil & - \lceil \tfrac{4}{2} \rceil & \lceil \tfrac{5}{2} \rceil & - \lceil \tfrac{6}{2} \rceil & \dots \\ \\ 0 & 1 & -1 & 2 & -2 & 3 & \dots \end{array}\nonumber\] You can also think of \(f\) as defined by cases as follows: \[f(n) = \begin{cases} 0 & \text{if $n = 1$}\\ n/2 & \text{if $n$ is even}\\ -(n-1)/2 & \text{if $n$ is odd and $>1$} \end{cases}\nonumber\]
Show that if \(A\) and \(B\) are countable, so is \(A \cup B\). To do this, suppose there are surjective functions \(f\colon \PosInt \to A\) and \(g\colon \PosInt \to B\), and define a surjective function \(h\colon \PosInt \to A \cup B\) and prove that it is surjective. Also consider the cases where \(A\) or \(B = \emptyset\).
Show that if \(B \subseteq A\) and \(A\) is countable, so is \(B\). To do this, suppose there is a surjective function \(f\colon \PosInt \to A\). Define a surjective function \(g\colon \PosInt \to B\) and prove that it is surjective. What happens if \(B = \emptyset\)?
Show by induction on \(n\) that if \(A_1\), \(A_2\), …, \(A_n\) are all countable, so is \(A_1 \cup \dots \cup A_n\). You may assume the fact that if two sets \(A\) and \(B\) are countable, so is \(A \cup B\).
Although it is perhaps more natural when listing the elements of a set to start counting from the \(1\)st element, mathematicians like to use the natural numbers \(\Nat\) for counting things. They talk about the \(0\)th, \(1\)st, \(2\)nd, and so on, elements of a list. Correspondingly, we can define an enumeration as a surjective function from \(\Nat\) to \(A\). Of course, the two definitions are equivalent.
There is a surjection \(f\colon \PosInt \to A\) iff there is a surjection \(g\colon \Nat \to A\).
Proof. Given a surjection \(f\colon \PosInt \to A\), we can define \(g(n) = f(n+1)\) for all \(n \in \Nat\). It is easy to see that \(g\colon \Nat \to A\) is surjective. Conversely, given a surjection \(g\colon \Nat \to A\), define \(f(n) = g(n+1)\). ◻
This gives us the following result:
A set \(A\) is countable iff it is empty or there is a surjective function \(f\colon \Nat \to A\).
We discussed above that an list of elements of a set \(A\) can be turned into a list without repetitions. This is also true for enumerations, but a bit harder to formulate and prove rigorously. Any function \(f\colon \PosInt \to A\) must be defined for all \(n \in \PosInt\). If there are only finitely many elements in \(A\) then we clearly cannot have a function defined on the infinitely many elements of \(\PosInt\) that takes as values all the elements of \(A\) but never takes the same value twice. In that case, i.e., in the case where the list without repetitions is finite, we must choose a different domain for \(f\), one with only finitely many elements. Not having repetitions means that \(f\) must be injective. Since it is also surjective, we are looking for a bijection between some finite set \(\{1, \dots, n\}\) or \(\PosInt\) and \(A\).
If \(f\colon \PosInt \to A\) is surjective (i.e., an enumeration of \(A\)), there is a bijection \(g\colon Z \to A\) where \(Z\) is either \(\PosInt\) or \(\{1, \dots, n\}\) for some \(n \in \PosInt\).
Proof. We define the function \(g\) recursively: Let \(g(1) = f(1)\). If \(g(i)\) has already been defined, let \(g(i+1)\) be the first value of \(f(1)\), \(f(2)\), … not already among \(g(1)\), …, \(g(i)\), if there is one. If \(A\) has just \(n\) elements, then \(g(1)\), …, \(g(n)\) are all defined, and so we have defined a function \(g\colon \{1, \dots, n\} \to A\). If \(A\) has infinitely many elements, then for any \(i\) there must be an element of \(A\) in the enumeration \(f(1)\), \(f(2)\), …, which is not already among \(g(1)\), …, \(g(i)\). In this case we have defined a funtion \(g\colon \PosInt \to A\).
The function \(g\) is surjective, since any element of \(A\) is among \(f(1)\), \(f(2)\), … (since \(f\) is surjective) and so will eventually be a value of \(g(i)\) for some \(i\). It is also injective, since if there were \(j < i\) such that \(g(j) = g(i)\), then \(g(i)\) would already be among \(g(1)\), …, \(g(i-1)\), contrary to how we defined \(g\). ◻
A set \(A\) is countable iff it is empty or there is a bijection \(f\colon N \to A\) where either \(N = \Nat\) or \(N = \{0, \dots, n\}\) for some \(n \in \Nat\).
Proof. \(A\) is countable iff \(A\) is empty or there is a surjective \(f\colon \PosInt \to A\). By Proposition \(\PageIndex{3}\), the latter holds iff there is a bijective function \(f\colon Z \to A\) where \(Z = \PosInt\) or \(Z = \{1, \dots, n\}\) for some \(n \in \PosInt\). By the same argument as in the proof of Proposition \(\PageIndex{2}\), that in turn is the case iff there is a bijection \(g\colon N \to A\) where either \(N = \Nat\) or \(N = \{0, \dots, n-1\}\). ◻
According to Definition \(\PageIndex{3}\), a set \(A\) is enumerable iff \(A = \emptyset\) or there is a surjective \(f\colon \PosInt \to A\). It is also possible to define “countable set” precisely by: a set is enumerable iff there is an injective function \(g\colon A \to \PosInt\). Show that the definitions are equivalent, i.e., show that there is an injective function \(g\colon A \to \PosInt\) iff either \(A = \emptyset\) or there is a surjective \(f\colon \PosInt \to A\).