5
$\begingroup$

While I was reading Enderton's "A mathematical introduction to Logic", I came across the proof of the following sentence: "The set of all finite sequences of members of the countable set A is also countable".

Proof: The set S of all such finite sequences can be characterized by the equation $$S=\bigcup_{n \in N} A^{n+1}$$ Since A is countable, we have a function f mapping A one-to-one into N. The basic idea is to map S one-to-one into N by assigning to $(a_0,a_1,...,a_m)$ the number $2^{f(a_0)+1}3^{f(a_1)+1}\cdot ... \cdot p_m^{f(a_m)+1}$, where $p_m$ is the $(m+1)$st prime. This suffers from the defect that this assignment might not be well-defined. For conceivably there could be $(a_0,a_1,...,a_m)=(b_0,b_1,...,b_n)$, with $a_i$ and $b_j$ in A but with $m\neq n$. But this is not serious; just assign to each member of S the smallest number obtainable in the above fashion. This gives us a well-defined map; it is easy to see that it is one-to-one.

Note: P is a finite sequence of members of A iff for some positive integer $n$, we have $P=(x_1,...,x_n)$, where each $x_i \in A$.

First of all, I cannot understand why the former assignment might not be well-defined and the latter assignment is well-defined. Secondly, I cannot understand what Enderton means by "just assign to each member of S the smallest number obtainable in the above fashion". By the way, is $(a,b,c,d) = ((a,b),(c,d))$ true? Also, in which cases can I omit/add parentheses in a tuple so as to have an equal tuple?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't see how two sequences with different length can be identical. How are $(x_1,\ldots,x_n)$ defined? $\endgroup$ – Apostolos Jun 24 '12 at 16:01
  • $\begingroup$ Some $a_i$ might be itself a finite sequence of $b_j$'s, or the other way around. For example, if $n>m$, then $(a_1,...,a_m) = (b_1,...,b_m,...,b_n)$, where $n=m+k$. That is, $a_1 = (b_1,...,b_{k+1})$. $\endgroup$ – user21530 Jun 24 '12 at 16:26
  • $\begingroup$ The elements of $S$ are of the form $(x_1,\ldots,x_n)$ where $x_i\in A$. Then, I don't see the point of considering sequences of sequences, it is irrelevant to the definition. Am I wrong? $\endgroup$ – Apostolos Jun 24 '12 at 16:35
  • $\begingroup$ Honestly! I don't know. Both definition and proof are somewhat ambiguous. $A$ might be the set whose members are 1/2/.../n-tuples. $\endgroup$ – user21530 Jun 24 '12 at 16:43
  • $\begingroup$ Apostolos, do you know in which cases I can omit/add parentheses in a tuple so as to have an equal tuple? $\endgroup$ – user21530 Jun 24 '12 at 17:15
3
$\begingroup$

So maybe it is a good idea to move part of the comments here, since they are relevant to answering the question:

First of all, there is no unique definition of $(a,b,c,d)$, but the standard one is $(a,(b,(c,d)))$. My guess is that depending on the definition it may be impossible that a problem can arise, but using the definition I provided it is possible to have a conflict.

The problem arises in the case some tuple of elements of $A$ is also in $A$. Let for example let's assume that $a,b\in A$ but at the same time $(a,b)\in A$. Furthermore let's assume that $f(a)=1,f(b)=2,f((a,b))=3$. Then the triple $(a,a,b)$ by the standard definition is $(a,(a,b))$. Then it is not clear whether to send $(a,(a,b))$ to $2^2\cdot3^4$ or to $2^2\cdot 3^2\cdot 5^3$.

What Enderton suggests is to pick the least $n$ such that the sequence $P$ lies in $A^n$. Hence in our previous example we should choose to denote $(a,(a,b))$ with $2^2\cdot 3^4$ since this element is in $A^2$ and in $A^3$ but $2<3$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! Your explanation was quite straightforward and detailed. Ι think that Ross Millikan's assignment is not well-defined due to the fact that $A$ might be equal to $\mathbb{Q}$. Then it could be $\prod_{k=0}^m p_k^{a_k} \notin \mathbb{N}$ for some $(a_0,a_1,...,a_m)$. $\endgroup$ – user21530 Jun 24 '12 at 20:33
2
$\begingroup$

I have already given this answer elsewhere. Let me repeat this here.

To prove the countability of $\bigcup _{n=1}^\infty A^n$, it suffices give an injective function $\phi$ from this union to $A$. Without loss of generalty take $A$ to be the set of positive integers and for the sake of this proof regard them as written out in base 10, which makes use of the symbols $0, 1,2$ upto $9$. Now let us bring in 3 more symbols namely the comma, the open and then the closed paraentheses which are to be interpreted as the (additional) symbols for the numbers ten, eleven and twelve respectively in base thriteen.

Now the injection $\phi$ takes a typical element such as $(3,8,17)$ and interprets them as an expression base thirteen: $(3,8,17)_{\rm thirteen}$ which when expressed in base ten is $(11\times 13^7) + (3\times 13^6) + (10\times 13^5) + (8\times 13^4) +(10\times 13^3) + (1\times 13^2) + (7\times 13^1) + (12\times 1).$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ $(+1)$ But with your coding, $(3,8,17)_{\rm thirteen}$ expressed in base-ten would be $(\color{blue}{\mathbf{11}}\times 13^7) + ...$ $\endgroup$ – r.e.s. Nov 1 '17 at 7:15
  • $\begingroup$ Another neat injection for countable $A=\{\mathbb{a_0, a_1,a_2,...}\}$ is the one that maps $[\mathbb{a_{i_1},a_{i_2},...,a_{i_n}}]$ to the number whose hexadecimal (or any base $>10$) representation is $\tt{Ai_1Ai_2...Ai_n}$, where $\tt{i_k}$ is the decimal representation of $i_k$. E.g., $[\mathbb{a_0,a_{12},a_7}]\mapsto\tt{A0A12A7}_{hex}=168432295_{dec}$. $\endgroup$ – r.e.s. Nov 1 '17 at 15:18
  • $\begingroup$ Thanks r.e.s., now I corrected the mistake you pointed out. $\endgroup$ – P Vanchinathan Nov 1 '17 at 15:56
0
$\begingroup$

You don't define what $f$ is, but as long as it is injective and positive I don't see how you get a conflict. In particular, if $n \gt m$, one of the numbers will be divisible by $p_{m+1}$ and one will not. It looks simpler to me to take $(a_0,a_1,\ldots,a_m)$ to $2^{a_0}3^{a_1}\ldots p_m^{a_m}$. Unique factorization shows that each tuple goes to a distinct image.

For your last we haven't defined tuples of tuples, which is what $((a,b),(c,d))$ is. If we map it recursively using my function $(a,b)\to 2^a3^b$, so $(a,b,c,d) \to 2^a3^b5^c7^d$ while $((a,b),(c,d)) \to 2^{2^a3^b}3^{2^c3^d}$, which are not equal.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ First of, thanks for your answer. Enderton only says that f is injective. If A is the set whose members are n-tuples, then your assignment is not well-defined. As for my last question, I think that we have defined recursively tuples of tuples. For example, $(a,b,c,d) = ((a,b,c),d) = (((a,b),c),d)$. However, I don't know if there are any other cases in which I can add/omit the parentheses. $\endgroup$ – user21530 Jun 24 '12 at 16:21
  • $\begingroup$ I was taking A to be a countable set, and in particular $\mathbb N$ which we can using the bijection that witnesses countability. Then I think this shows that the finite sequences from A are countable. If you want to show that the sequences of sequences are countable, we can just apply the theorem twice. $\endgroup$ – Ross Millikan Jun 24 '12 at 16:29
  • $\begingroup$ By the way, if $A=Q$, then your assignment is well-defined? And in which case there could be $(a_0,...,a_m)=(b_0,...,b_m)$? Please enlighten me! Furthermore, I haven't understood what Enderton means by "just assign to each member of S the smallest number obtainable in the above fashion". What is the smallest number? $\endgroup$ – user21530 Jun 24 '12 at 18:22
  • $\begingroup$ @Stavros: for the first, if one tuple is longer than the other, then the primes in the expansion for the short one only go up to $p_m$. For the second, just inject $\mathbb Q$ into $\mathbb N$ and choose the primes according to the injection. $\endgroup$ – Ross Millikan Jun 24 '12 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy