Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
The theorem I am mentioning is one that states that two sets have the same cardinality if there exists a bijection between them. –  Joshua Jun 13 '12 at 6:19
1  
@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... –  Joshua Jun 13 '12 at 6:34
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! :-) –  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.

share|improve this answer

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

share|improve this answer
    
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. –  Joshua 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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