# Assuming $A$ is infinite, show that the set of sequences of $A$ is equinumerous to $A$

The question: Assume that $A$ is an infinite set. Prove that $A$ is equinumerous to Sq($A$).

Clarification:

We're using Enderton's "Elements of Set Theory", which defines natural numbers recursively as $0 = \emptyset$ and $n+1 = n \cup \{n\}$.

Sq(A) is the set of finite sequences with members in $A$, i.e. define Sq($A$) as $\{f\text{ | }(\exists n \in \mathbb{N})\space f:n\to A \text{ is injective} \}$.

My attempt:

I tried to use the Schröder-Bernstein theorem by finding two injective functions...

Let $f:A\to \text{Sq }A$ be an injective function defined as follows: For each $a \in A$, let $f(a) = \{\langle \emptyset, a \rangle\}$. This maps each element to the sequence of length 1 starting with $a$. Of course $f$ is injective, because $$f(a) = f(b) \implies a = b \text{ and thus } a\neq b \implies f(a) \neq f(b).$$

However I am having trouble finding an injective $g: \text{Sq }A \to A$. Can someone help me out? Am I overcomplicating the problem by using the Schröder-Bernstein theorem?

Show that for every $n$, the set of sequences of length $n$ is equinumerous with $A$ itself (recall that $|A\times A|=|A|$ for an infinite set $A$); then conclude the wanted statement.
• Thanks for the hint, but I still haven't been able to find a way to solve it. Which form of the Axiom of Choice would I use to show that for every $n$, the set of sequences of length $n$ is equinumerous to $A$? – Bobby Lee May 4 '15 at 23:18
• Well, $|A\times A|=|A|$ is equivalent to the axiom of choice. So let me suggest that form again. – Asaf Karagila May 5 '15 at 4:08
• I did answer the question. Use the fact that $A\times A$ and $A$ have the same cardinality. If you don't know that fact, then I really don't know how would one solve this question without invariably proving this fact in the process. If you haven't proved this fact before, there have been a good deal of questions about it where you can find elaborated answers with the proof, or sketches of that proof. I'd find you one, but I have to go in a few minutes. – Asaf Karagila May 5 '15 at 5:13
• Of course I have seen this fact, but no, you didn't answer the question. What you wrote is exactly what you labeled it, a hint. What does $A \times A$ have to do with the question? – Bobby Lee May 5 '15 at 5:20