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


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?


HINT: The axiom of choice is essential in this proof, so constructive arguments are not really an option.

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.

  • $\begingroup$ 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$? $\endgroup$ – Bobby Lee May 4 '15 at 23:18
  • $\begingroup$ Well, $|A\times A|=|A|$ is equivalent to the axiom of choice. So let me suggest that form again. $\endgroup$ – Asaf Karagila May 5 '15 at 4:08
  • $\begingroup$ Do you mind answering the question? I have tried for hours with no progress. I appreciate the hint, but I suppose I am too stubborn to see the answer. $\endgroup$ – Bobby Lee May 5 '15 at 5:11
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila May 5 '15 at 5:13
  • $\begingroup$ 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? $\endgroup$ – Bobby Lee May 5 '15 at 5:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.