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 was reading A Walk Through Combinatorics: An Introduction to Enumeration And Graph Theory (Miklós Bóna) and came across a definition for bijection:

Let $X$ and $Y$ be two finite sets, and let $f : X \rightarrow Y$ be a function so that

(1) if $f(a) = f(b)$, then $a = b$, and

(2) for all $y \in Y$, there is an $x \in X$ so that $f(x) = y$,

then we say that $f$ is a bijection from $X$ onto $Y$.

I see that (1) prevents the case of mapping multiple elements in $X$ to the same element in $Y$. Though, unless I'm missing something here (2) seems to say to me that each element in $Y$ must be mapped by something in $X$. What I'm not seeing here is what about unmapped (unused) elements in $X$? I saw some sources saying bijections cannot include those scenarios but I'm not sure if this definition is wrong or if my understanding of it is flawed.

E.g., how would this mapping that I drew below violate the definition above where I create an element in $X$ that is not mapped to $Y$?

enter image description here

share|improve this question
2  
The fact that it is a function means that there can be no "unused" elements in $X$ (this is part of the definition of a function). –  Tobias Kildetoft Dec 12 '12 at 16:44

1 Answer 1

up vote 2 down vote accepted

The relation you've drawn is not a function from $X$ to $Y$. By definition, a function with domain $X$ must assign to every $x\in X$ a unique $y\in Y$.

share|improve this answer
1  
OK thanks, looks like I overlooked something simple! –  user17753 Dec 12 '12 at 16:46
    
Dear @user17753, If this has answered your question, you can accept it by clicking the check mark below the number of votes in the upper left of the answer. –  Keenan Kidwell Dec 12 '12 at 16:50
    
Thanks, will do when the timer allows me. –  user17753 Dec 12 '12 at 16:51

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.