One-to-one & Onto Function: $f$ from $A$ to $B$

  • MHB
  • Thread starter alexmahone
  • Start date
In summary: Hence, $f$ is one-to-one if and only if it is onto.In summary, $f$ is a one-to-one function from $A$ to $B$ if and only if it is onto, given that $|A|=|B|$. This can be proven using the pigeonhole principle and the definitions of one-to-one and onto functions.
  • #1
alexmahone
304
0
Suppose that $f$ is a function from $A$ to $B$, where $A$ and $B$ are finite sets with
$|A|=|B|$. Show that $f$ is one-to-one if and only if it is onto.

(Hints only as this is an assignment problem.)
 
Physics news on Phys.org
  • #2
If $f$ is a function then if $f(a) = x$ and $f(a) = y$ then $x=y$ function definition
If $f$ is one to one then if $f(a) = f(b)$ then $a = b$. And we have $|A| = |B|$ and each are finite

You begin with the right implication suppose $f$ is one to one want to prove it is onto. You can prove by contradiction suppose not so we have ... What does it mean to be onto ?

If $f$ is onto suppose it is not one to one then there exit $a \not = b$ and $f(a) = f(b)$
 
  • #3
Do you know the pigeonhole principle? Imagine $A$ is a set of $n$ balls, and $f$ is a function that tells you where to put them in $m$ holes ($B$ is the set of holes).

Then "onto" tells you every hole is filled, and "1-1" tells you any hole has only one ball (at most).

See what you can do with this idea, when $n = m$.
 
Last edited:
  • #4
I think I have a counterexample:
Let $A=\{a, b, c, d\}$ and $B=\{1, 2, 3, 4\}$. Let $f$ be a function from $A$ to $B$ defined by $f(a)=1$, $f(b)=2$, $f(c)=3$.
$f$ is surely one-to-one but not onto?
 
  • #5
Alexmahone said:
I think I have a counterexample:
Let $A=\{a, b, c, d\}$ and $B=\{1, 2, 3, 4\}$. Let $f$ be a function from $A$ to $B$ defined by $f(a)=1$, $f(b)=2$, $f(c)=3$.
$f$ is surely one-to-one but not onto?

Hi Alexmahone,

Part of the definition of a function is (usually) that every element in its domain gets mapped.
In your example $d$ does not get mapped.
 
  • #6
I think I got it. I'd be glad if someone could go through this proof for me. I used the pigeonhole principle as Deveno suggested.

Assume that $f$ is not onto. Then there is at least one element in $B$ that does not have a preimage in $A$. Let $m$ be the number of elements in $B$ that have preimages. $m<|B|$
Let the elements in $A$ be the pigeons and the elements in $B$ that have preimages be the pigeonholes.
Number of pigeons $=|A|$
Number of pigeonholes $=m<|B|=|A|$
Since we have more pigeons than pigeonholes, by the pigeonhole principle, at least one of the pigeonholes contains more than one pigeon. That is, there is at least one element in $B$ that has more than one preimage in $A$. So, $f$ is not one-to-one.

Assume that $f$ is not one-to-one. Then there is at least one element in $B$ that has more than one preimage in $A$. Let $b_1$ be one such element in $B$ that has $m$ preimages in $A$ where $m>1$. Number of remaining elements in $A=|A|-m$. These elements can have at most $|A|-m$ images in $B$.
So, total images in $B\le 1+|A|-m=1+|B|-m<|B|$ $(\because m>1)$
So, $f$ is not onto.
 
Last edited:

FAQ: One-to-one & Onto Function: $f$ from $A$ to $B$

What is a one-to-one function?

A one-to-one function, also known as an injective function, is a type of function in which each element in the domain is mapped to a unique element in the codomain. This means that no two elements in the domain are mapped to the same element in the codomain.

What is an onto function?

An onto function, also known as a surjective function, is a type of function in which every element in the codomain has at least one pre-image in the domain. In other words, every element in the codomain is mapped to by at least one element in the domain.

What is the difference between a one-to-one and onto function?

The main difference between a one-to-one and onto function is the way they map elements from the domain to the codomain. A one-to-one function ensures that each element in the domain is mapped to a unique element in the codomain, while an onto function ensures that every element in the codomain is mapped to by at least one element in the domain.

How can I determine if a function is one-to-one?

To determine if a function is one-to-one, you can use the horizontal line test. This involves drawing a horizontal line through the graph of the function and seeing if the line intersects the graph at more than one point. If it does, the function is not one-to-one.

How can I determine if a function is onto?

To determine if a function is onto, you can use the vertical line test. This involves drawing a vertical line through the graph of the function and seeing if the line intersects the graph at least once for every point in the codomain. If it does, the function is onto.

Similar threads

Replies
4
Views
2K
Replies
5
Views
1K
Replies
1
Views
951
Replies
3
Views
1K
Replies
1
Views
1K
Replies
19
Views
3K
Replies
1
Views
1K
Back
Top