The Gateway to Computer Science Excellence
0 votes
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.
in Set Theory & Algebra by Boss (10.9k points) | 37 views

1 Answer

0 votes
$\because$ this is a Biconditional proof , we'd have to proof both ways.
1.First, let us prove f is one-to-one $\Rightarrow$ f is onto.
Assume f is not an onto function,$\Rightarrow \exists$ a value in the range which does not have an incoming edge from the domain, but $\because$ |A|=|B|, this cannot happen. $\Rightarrow$ f is onto.

2.1.Now, let us prove f is onto $\Rightarrow$ f is one-to-one .
Assume f is not one-to-one, then |B|<|A|, but we know |A|=|B|, Hence our assumption is false. Therefore f is one-one.

$\therefore$ f is one-to-one $\Leftrightarrow$ f is onto.

Hence proved.
by Active (2.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
102,213 users