I'm having a hard time thinking about this problem.

My question: Let A be a set. Define C to be the collection of all functions f: {0,1} --> A. Prove that |A x A| = |C| by constructing a bijection F: A x A --> C.

I'm assuming A x A has the same cardinality as A itself. Also, to create a bijection from A x A --> C, I think I need to prove |A x A|≤|C| and |A x A|≥|C| through Cantor Schroder-Bernstein Theorem.

Can someone please tell me how to solve this?

  • 3
    $\begingroup$ "I'm assuming A x A has the same cardinality as A itself. " -- You shouldn't. This doesn't hold, for example, for finite sets. $\endgroup$ – Eevee Trainer Nov 29 '19 at 5:56
  • $\begingroup$ Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. $\endgroup$ – José Carlos Santos Nov 29 '19 at 5:57
  • $\begingroup$ "I'm assuming A x A has the same cardinality as A itself. " Well, no. if there are $CARDINALITY$ $a_\alpha \in A$ how many $(a_\alpha, a_\beta) \in A\times A$ are there? $\endgroup$ – fleablood Nov 29 '19 at 6:07
  • 1
    $\begingroup$ For infinite sets ... yes and no. It (somewhat) depends on whether you assume the axiom of choice (see an elaboration here). If you don't mind assuming the axiom of choice, though, yes: for an infinite set $S$, $|S \times S|=|S|$. $\endgroup$ – Eevee Trainer Nov 29 '19 at 6:12
  • 2
    $\begingroup$ Countable Infinite? Yes, but that's because $|\mathbb N|^2 = |\mathbb N|$. It's not an easy thing to prove $|\mathbb R \times \mathbb R| = |\mathbb R|$. ... And there is nothing that says $A$ is infinite. $\endgroup$ – fleablood Nov 29 '19 at 6:14

$C$ is a set of functions from $\{0,1\} \to A$. A function $f\in C$ would be defined by simply spelling out what the two values of $f(0) =a$ and $f(1)=b$ are.

$A\times A$ is the set of all ordered pairs $(a,b)$ where $a,b \in A$.

Can you construct a bijection.

Consider $A =\{a,b,c\}$.

Then $A\times B = \{(a,a),(a,b),(a,c), (b,a), (b,b),(b,c), (c,a), (c,b), (c,c)\}$

ANd $C = \{\{f(0)=a; f(1)=a\}, \{g(0)=a; g(1)=b\}, \{h(0)=a; h(1)=c\},etc.\}$.

Can you see the bijection between them?


Intuitively, the statement is true, because there are $|A|^2$ functions from $\{0,1\}$ to $A$-you have $|A|$ choices for $f(0)$ and again for $f(1)$. This is independent of whether $A$ is finite or infinite. The easiest approach is not through C-S-B but to directly construct the isomorphism. If I give you an $f$, what element of $C$ is it natural to pair with it?


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.