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!
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.
I don't think you even need Cantor-Bernstein-Schroeder:
Let $f\colon x\to y$ be a bijection.
Define $f_A\colon A^y\to A^x$ by $f_A(g) = g\circ f$. Prove that $f_A$ is a bijection.
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\;.$
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.