[Math] How to prove a one to one correspondence.

elementary-set-theory

We already know that the definition of one to one correspondence between set $A$ and $B$ is as follow:

  1. Every element in $A$ corresponds to exactly one element to $B$.

  2. Every element in $B$ corresponds to exactly one element to $A$.

Now, the question is that what does corresponds mean, is this a two way relationship?

Example:

Given $A={1,2,3,4,5,\cdots ,50}$ and $B={2,3,4,5,6,\cdots ,51}$

Two prove they are one to one corresponds, we need to show 1. and 2.

  1. For element $n\in A,$ the corresponding element in $B$ is $n+1$,

  2. For element $n\in B,$ the corresponding element in $A$ is $n-1$,

and we are done.

The question is can I have another correspondence in 2. (only in 2, not 1). Say 51 -1, 50-2, 49-3, etc. Then we also have that Every element in $B$ corresponds to exactly one element to $A$. However, the correspondence are different. Is this valid? If not, when you are proving a one to one correspondence, do you need to show the correspondence is consistent in both 1. and 2.? I think this question is very much related to the definition of correspondence, so I asked this question above.

Best Answer

The "corresponds to" language is vivid and suggestive, but not quite precise, and in this case it seems to be confusing you. It is better to go back to complete technical definitions, in the style of:

A one-to-one correspondence from $A$ to $B$ is a function $f:A\to B$ such that

  1. For every $a\in A$ there is exactly one $b\in B$ such that $f(a)=b$ (this is implicit in the concept of a "function", so will often not be stated in so many words), and
  2. For every $b\in B$ there is one and only one $a\in A$ such that $f(a)=b$.

Note that the formula $f(a)=b$ is the same in the two prongs, so if $a=1$ goes with $b=2$ in one of them they also go together in the other.

Alternatively, to make the definition look more symmetric at the expense as not being quite as conventional, you could say:

A one-to-one correspondence between $A$ and $B$ is a subset $R\subseteq A\times B$ such that

  1. For every $a\in A$ there is exactly one $b\in B$ such that $\langle a,b\rangle\in R$, and
  2. For every $b\in B$ there is exactly one $a\in A$ such that $\langle a,b\rangle\in R$.

The important point for the purpose of this question is still that it is the same $R$ both parts of the definition say something about.

(This is actually the same definition as the one before, if you use the standard set-theoretic representation of "function").

Related Question