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.
  • 1
    $\begingroup$ 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? $\endgroup$ – JMoravitz Jul 27 '16 at 6:40
  • $\begingroup$ 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. $\endgroup$ – JasonM Jul 27 '16 at 6:40
  • 1
    $\begingroup$ 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. $\endgroup$ – JMoravitz Jul 27 '16 at 6:46
  • 1
    $\begingroup$ 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. $\endgroup$ – fleablood Jul 27 '16 at 6:59
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.)

  • 1
    $\begingroup$ ...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. $\endgroup$ – fleablood Jul 27 '16 at 7:05
  • $\begingroup$ @fleablood Right, this answer obviously assumes that $\psi:A \to B$. $\endgroup$ – Alex Provost Jul 27 '16 at 7:07
  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 27 '16 at 7:15
  • $\begingroup$ @fleablood Good points. I agree that the question could use clarification. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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