PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (17)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] a surjection between finite sets of the same cardinality is bijective (Result)
Theorem 1   Let $ A$ and $ B$ be finite sets of the same cardinality. If $ f\colon A \to B$ is a surjection then $ f$ is a bijection.
Proof. Let $ A$ and $ B$ be finite sets with $ \vert A\vert = \vert B\vert = n$. Let $ C =\{f^{-1}\left(\{b\}\right)\mid b \in B \}$. Then $ \bigcup C \subseteq A$, so $ \vert\bigcup C\vert \le n$. Since $ f$ is a surjection, $ \vert f^{-1}\left(\{b\}\right)\vert \ge 1$ for each $ b \in B$. The sets in $ C$ are pairwise disjoint because $ f$ is a function; therefore, $ n \le \vert\bigcup C\vert$ and
$\displaystyle \\ \left\vert\bigcup C \right\vert=\sum_{b\in B}\vert f^{-1}\left(\{b\}\right)\vert .$    

In the last equation, $ n$ has been expressed as the sum of $ n$ positive integers; thus $ \vert f^{-1}\left(\{b\}\right)\vert = 1$ for each $ b \in B$, so $ f$ is injective. $ \qedsymbol$



"a surjection between finite sets of the same cardinality is bijective" is owned by ratboy.
(view preamble)

View style:

See Also: one-to-one function from onto function


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: injective, integers, positive, equation, function, pairwise disjoint, bijection, surjection, cardinality, finite sets

This is version 2 of a surjection between finite sets of the same cardinality is bijective, born on 2005-07-12, modified 2005-07-13.
Object id is 7222, canonical name is ASurjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective.
Accessed 1224 times total.

Classification:
AMS MSC: 03-00 (Mathematical logic and foundations :: General reference works )
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)