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?
Best Answer
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$.