# Cardinality, $|x|=|y|$ implies $|A^x|=|A^y|$

I am trying to prove, without using the Schroder-Bernstein theorem, (where a modulus defines cardinality) that

i.) $|x|=|y|$ implies $|A^x|=|A^y|$

and

ii.) $|x|=|y|$ implies $|x^A|=|y^A|$.

Thank you!

-

To say that $|x|=|y|$ is to say that the difference between $x$ and $y$ is just in the labels of the names. An element of $A^x$ is a function whose domain is $x$ and its co-domain is $A$.

If we agreed that simply by changing the name of every element in $x$ we can get $y$, fix a renaming method (that is, pick a particular way to rename from $x$ to $y$) and take some $f\in A^y$, define $\hat f\in A^x$ to be the function which sends $x\in X$ to $f(y)$ such that $y$ is the element we get by renaming $x$ in the renaming method.

Rigorously a renaming method is simply a bijection $\varphi\colon y\to x$, and we simply define $\hat f = \{\langle\varphi(y),f(y)\rangle\mid \langle y,f(y)\rangle\in f\}$. We can show that this is a function from $x$ into $A$ and if $f\neq g$ then $\hat f\neq\hat g$.

Therefore $\hat\bullet\colon A^y\to A^x$ is a bijection and $|A^x|=|A^y|$.

The second question is essentially the same, this time we have a function from $A$ to $x$, so we simply compose it with $\varphi$, our bijection.

The Cantor-Bernstein theorem simply tells us that if we have two injections then we have a bijection. To prove something like $|x|=|y|\implies |A^x|=|A^y|$ without the use of Cantor-Bernstein would depend on how many laws you have already proved using bijections and injections.

For example, if you prove that $|x|\leq |y|\implies |A^x|\leq|A^y|$ then you can simply write:

Since $|x|=|y|$ we have that $|x|\leq |y|$ and therefore $|A^x|\leq|A^y|$; similarly $|y|\leq|x|$ and therefore $|A^y|\leq|A^x|$.

By Cantor-Bernstein we have that $|A^x|=|A^y|$.

However, after quite some time you realize that proving that aforementioned property is not easier than constructing explicit bijections.

-
The theorem I am mentioning is one that states that two sets have the same cardinality if there exists a bijection between them. – user5262 Jun 13 '12 at 6:19
@JoshuaBunce: That is the definition of cardinality. Cantor-Bernstein says that if $|a|\leq|b|$ and $|b|\leq|a|$ then $|a|=|b|$. That is to say if there is an injection from $a$ into $b$ and another injection from $b$ into $a$ then there is a bijection from $a$ onto $b$. – Asaf Karagila Jun 13 '12 at 6:21
Right. What was I thinking... – user5262 Jun 13 '12 at 6:34
@JoshuaBunce: I don't know about that, but I do plan on taking a mind reading course during my Ph.D. studies... so maybe in a few years I could answer your second question too! :-) – Asaf Karagila Jun 13 '12 at 6:37

I don't think you even need Cantor-Bernstein-Schroeder:

Let $f\colon x\to y$ be a bijection.

1. Define $f_A\colon A^y\to A^x$ by $f_A(g) = g\circ f$. Prove that $f_A$ is a bijection.

2. Try a similar idea: use $f$ to construct a map $x^A$ to $y^A$ and prove it is a bijection.

-

If $|x|=|y|$, you have a bijection $f:x\to y$. You want to use $f$ to construct bijections $g:A^x\to A^y$ and $h:x^A\to y^A$. The first is slightly easier; I’ll do the second and let you see if you can adapt the ideas to do the first yourself.

An element of $x^A$ is a function $\varphi:A\to x$, and you want $h$ to match it up with some function from $A$ to $y$. You already have a function $f$ that matches elements of $x$ with elements of $y$, so use it to ‘translate’ the output of $\varphi$: $f(\varphi)$ should be the function that takes $a\in A$ to $\varphi(a)$ and then takes that to $f(\varphi(a))$ over in $y$:

$$A\stackrel{\varphi}\longrightarrow x\stackrel{f}\longrightarrow y:a\mapsto \varphi(a)\mapsto f(\varphi(a))\;.$$

The function that does this is clearly the composition $f\circ\varphi$, so we should set $h(\varphi)=f\circ\varphi$:

$$h:x^A\to y^A:\varphi\mapsto f\circ\varphi\;.$$

-
Thank you! I wasn't sure which to vote - I appreciate your time in answering this. This is the first way that I constructed the proof. – user5262 Jun 15 '12 at 2:31

Two sets $x$ and $y$ have the same cardinality precisely when there is a bijection $f:x\to y$.

Thus, for both parts, there is a bijection $f:x\to y$. How can you use $f$ to create a bijection between $A^x$ and $A^y$? Think about how you might turn an element of $A^x$ into an element of $A^y$ using $f$.

You can use the same idea for the second problem.

-