Intereting Posts

Why do we look at morphisms?
show that $\int_{0}^{\infty}\frac{x\cos ax}{\sinh x}dx=\frac{\pi^2}{4} \operatorname{sech}^2 \left(\frac{a\pi}{2}\right) $
Prime number between $n$ and $n!+1$
Existence of an injection from $\Bbb N$ without the axiom of choice
Let $f$ be a real uniformly continuous function on the bounded set $E$ in $\mathbb{R^1}$. Prove that $f$ is bounded on $E$
Polynomial function
Area under a point
Number of binary numbers with two consecutive zeros
Conditional expectation on Gaussian random variables
Symmetric Stable Distribution
If $f : A \to B$ is a ring homomorphism, then what can be said about $\text{deg}$?
Finding matrix for given recurrence
how to show $SU(2)/\mathbb{Z}_2\cong SO(3)$
To prove Cayley-Hamilton theorem, why can't we substitute $A$ for $\lambda$ in $p(\lambda) = \det(\lambda I – A)$?
Closed form of a partial sum of the power series of $\exp(x)$

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$.

- Question related with partial order - finite set - minimal element
- Category-theoretic cross product and set-theoretic cross product
- Union of preimages and preimage of union
- How to solve probability when sample space is infinite?
- what is the relationship between ZFC and first-order logic?
- When does it make sense to define a generator of a set system?

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?

- Trying to prove that cardinality of power sets are equal
- The empty function and constants
- Show that $X$ can be represented as a union of disjoint equivalence classes
- Explicit well-ordering of $\mathbb Q$
- Some kind of “bijection” between $\mathbb R$ and $\mathbb N$
- The equivalence of “Every surjection has a right inverse” and the Axiom of Choice
- What are the bounds (upper and lower) for $|A+A|$?
- For every infinite cardinal $\kappa$, $\kappa^2 =\kappa$.
- let $A$ be any inductive set, then $\{C \in P(A)|C \text{ is inductive set} \}$ is a set? … and $\mathbb{N}$…?
- Is there a set of all topological spaces?

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$.

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

$(12\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).$

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.

- Does $\mathcal P ( \mathbb R ) \otimes \mathcal P ( \mathbb R ) = \mathcal P ( \mathbb R \times \mathbb R )$?
- Noetherian domains with finitely many primes
- Why is the category of groups not closed, or enriched over itself?
- Compact form of the series $\sum\limits_{n=-\infty}^{\infty} {1\over (x-n)^2}$
- Gosper's unusual formula connecting $e$ and $\pi$
- Finding maximal chain of cardinality $\aleph$
- Evaluate $\int_0^\infty\frac{1-e^{-x}(1+x )}{x(e^{x}-1)(e^{x}+e^{-x})}dx$
- asymptotic of $x^{x^x} = n$
- Suppose that $f$ is analytic on a close curve γ. Prove or disprove $\int_\gamma \overline{f(z)}f'(z)dz$ is purely imagine.
- Proof of cardinality inequality: $m_1\le m_2$, $k_1\le k_2$ implies $k_1m_1\le k_2m_2$
- Some question of sheaf generated by sections
- An inequality from Littlewood's Miscellany
- Why is the infinite set from the axiom of infinity the natural numbers?
- How does the sum of the series “$1 + 2 + 3 + 4 + 5 + 6\ldots$” to infinity = “$-1/12$”?
- Infimum is a continuous function, compact set