# One to one correspondence Why?

How does the definition of one to one correspondence imply all elements in the two sets can be paired with no remaining?

• What is your question exactly? Oct 31, 2014 at 21:03
• That's the definition of 1 to 1 correspondence! Oct 31, 2014 at 21:04
• But how does this imply that all elements are paired?
– Kun
Oct 31, 2014 at 21:04
• I'm guessing you want to know how a function is bijective iff it is both surjective and injective? Oct 31, 2014 at 21:11
• No, let's just not mention the function please. I am trying to gain a intuitive poof.
– Kun
Oct 31, 2014 at 21:12

If I understand you correctly, you want to prove that there exists a perfect pairing of elements from $A$ to $B$. The pairing you want is given by $$\{(a,b)\in A\times B\mid b\text{ corresponds to }a\}$$ The properties of 1 to 1 correspondence say exactly what you want. In fact, this is the usual definition of a function in the set theory which corresponds to the bijection you have between $A$ and $B$.

If you have a correspondence like that, consider the set $$\{\langle a,b\rangle\mid a\in A\text{ and }b\text{ is the element corresponding to }a\}.$$

Every element of $A$ appears in exactly one pair in the left coordinate; and every element of $B$ appears in exactly one pair in the right coordinate. So this is exactly what you have there.

A one-to-one correspondence is given by an injective function. An injective function does not necessarily map elements of its domain to every of element of its codomain. See Bijection, injection and surjection

Perhaps you are thinking of a bijection.

EDIT:

To prove that there exists a bijection between sets $A$ and $B$, you have at least two options:

1. Prove there exists $f:A\to B$ that is both injective and surjective.
2. Prove there exists $f:A\to B$ and $g:B\to A$ were both are injective. (See Cantor–Bernstein-Schröder theorem)
• In the second option, I think it suffices to prove there exists $f:A\rightarrow B$ and $g:B\rightarrow A$
– Kun
Nov 2, 2014 at 16:27
• And then we can think this way, let an element $a$ in $A$ be given. It must then corresponds to an element in $B$ since $f:A\rightarrow B.$ Now, the element in $B$ must correspond to one and only one element in $A$ as $f:B\rightarrow A$. And more specifically, it must correspond to $a$ since correspondence it a two way relationship. Now these two elements are paired and will not appear again. In this way, all element in $A$ is paired with a distinct element in $B$. To see all element in $B$ are used up(all paired off), we can again let an element $b$ in $B$ be given and then proceed as before.
– Kun
Nov 2, 2014 at 16:31
• See edit above. Nov 3, 2014 at 6:40

one to one correspondence is of course Bijective, after you have grasp the definition of Surjection, Injection and Bijection, then you will get the answer to your question.