2
$\begingroup$

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!

4 Answers 4

2

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.

  • 1
    @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! :-)2012-06-13
5

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.

4

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

  • 0
    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.2012-06-15
3

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.