# Is this example being bijective?

There is a related nice problem discussing this (deeper discussion):
Difference between bijection and isomorphism?
But I do not want to ask it that further.

This simple problem confuses me for a long time.

Consider two examples:

1. Two sets: $A = \{a_1,a_2,a_3\}$, $B = \{b_1,b_2,b_3\}$. Suppose there is a map $\phi$ such that $\phi(a_1) = b_1, \phi(a_2) = b_2, \phi(a_3) = b_3$. Undoubtedly, this map is bijective.
2. However, Two sets: $A = \{a_1,a_2,a_3\}$, $B = \{b_1,b_2\}$. Suppose there is a map $\psi$ such that $\psi(a_1) = b_1, \psi(a_2) = b_2$. Is $\psi$ still bijective? It looks like one to one and onto to me.
• For #2, what is $\psi(a_3)$? If $\psi(a_3)$ doesn't exist, is $\psi$ actually a function in the first place? Remember that a function must be well defined and everywhere defined. If $\psi(a_3)$ happens to be $b_1$ what fails? If $\psi(a_3)$ happens to be $b_2$ what fails? – JMoravitz Jul 27 '16 at 6:40
• Yes, it is a bijection, so long as its domain is not $A$. Its domain needs to be $\{a_1,a_2\}$. A function must map everything in its domain. – JasonM Jul 27 '16 at 6:40
• If $\psi(a_3)$ doesn't exist, then it makes no sense as a map, however it doesn't need to explicitly tell us what $\psi(a_3)$ is so long as we know it exists. Regardless what $\psi(a_3)$ is, we run into a problem as $\psi(a_3)$ is guaranteed to be either $b_1$ or $b_2$ and whichever that was, will overlap with either $\psi(a_1)$ or $\psi(a_2)$ respectively. This can be seen via an application of the pigeon-hole principle. – JMoravitz Jul 27 '16 at 6:46
• I'm going to repeat Jason vs comment. There is no bijective mapping $\mu:A \rightarrow B$, in 2. But no - where in 2 is it claimed that $\psi:A\rightarrow B$. IF $\psi:\{a_1,a_2\}\rightarrow B$ then $\psi$ is a bijection. But if $\psi:A\rightarrow B$ and we simply haven't been told what $\psi (a_3)$ is, then it isn't a bijection. – fleablood Jul 27 '16 at 6:59
• Okay. In neither 1 nor 2 do you indicate that A and B are the domains or range of the function. That must be specified before we reach a conclusion. – fleablood Jul 27 '16 at 7:07

By definition, a function $\psi:A \to B$ must assign a value to every element of the domain. In your case, this means that either $\psi(a_3) = b_1$ or $\psi(a_3) = b_2$ must hold. In both cases, the resulting map $\psi$ isn't injective. (And, more generally, you cannot have an injection from a finite set to a smaller finite set.)

• ...or it could be that although A and B were sets, we were not told what those sets have to do with this mapping. It could be for all we were told that $A \subset X$ and $B \subset Y$ $\psi:X \rightarrow Y$ which .... could be anything.For all we were told. – fleablood Jul 27 '16 at 7:05
• @fleablood Right, this answer obviously assumes that $\psi:A \to B$. – Alex Provost Jul 27 '16 at 7:07
• It does. But ... I don't think we can actually legitimately make such an assumption. Either 1) $\psi (a_3)$ isn't defined and it isn't a proper function from A to B. 2) $\psi (a_3)$ is defined but we weren't given enough information to fully know this function. 3)the function maps {a1,a2} to B and A was just a red herring or 4) the function maps X to Y and A and B were red herrings. In any case, we (the students) were mislead and forced to make invalid assumptions. – fleablood Jul 27 '16 at 7:15
• @fleablood Good points. I agree that the question could use clarification. – Alex Provost Jul 27 '16 at 13:45

A function must map a domain (input) set to a range set. Often the domain is not explicit stated but even so it must exist.

In these examples you are stating that sets $A$ and $B$ exist but you are assuming, without explicitly stating the $\psi:A \rightarrow B$. This is fine but exploited ambiguities makes the second example unclear. Here are the ambiguities of 2:

a) I can assume the function can be defined in set/ordered pair terms as $\psi = \{(a_1, b_1), (a_2,b_2)\} \subset A \times B$. This is the entirety of and complete description of the function.

If so then $\psi$ is simply NOT a function from $A \rightarrow B$. It is a function $\psi:\{a_1,a_2\} \rightarrow B$. And, yes, as such it is a bijection.

The ambiguity is that its domain is not A as was implied.

b) If I assume that $\psi$ IS a function from $A \rightarrow B$, then $\psi = \{(a_1, b_1), (a_2,b_2)\}$ can not be a complete description of the function. It doesn't tell us what $\psi(a_3)$-- a required value for an meaningful function-- is. We must assume we have $\psi = \{(a_1, b_1), (a_2, b_2), (a_3,????)\} \subset A \times B$. If $\psi$ is a injective, then the second terms must be distinct. This is impossible as it would require three distinct elements of $B$ but $B$ has only two elements.

This ambiguity is that $\psi: A \rightarrow B$ but $\psi \ne \{(a_1, b_1), (a_2,b_2)\}$; that was an incomplete definition.

Indeed it is always impossible to have a bijection between finite sets of different number of elements.