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
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 MSC03-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)