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 (197)
Orphanage
Unclass'd
Unproven (498)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] one-to-one function from onto function (Definition)
Theorem 1   Given an onto function from a set $ A$ to a set $ B$, there exists a one-to-one function from $ B$ to $ A$.
Proof. Suppose $ f:A\rightarrow B$ is onto, and define $ \mathcal{F}=\big\{f^{-1}(\{b\}):b\in B\big\}$; that is, $ \mathcal{F}$ is the set containing the pre-image of each singleton subset of $ B$. Since $ f$ is onto, no element of $ \mathcal{F}$ is empty, and since $ f$ is a function, the elements of $ \mathcal{F}$ are mutually disjoint, for if $ a\in f^{-1}(\{b_1\})$ and $ a\in f^{-1}(\{b_2\})$, we have $ f(a)=b_1$ and $ f(a)=b_2$, whence $ b_1=b_2$. Let $ \mathscr{C}:\mathcal{F}\rightarrow\bigcup\mathcal{F}$ be a choice function, noting that $ \bigcup\mathcal{F}=A$, and define $ g:B\rightarrow A$ by $ g(b)=\mathscr{C}\big(f^{-1}(\{b\})\big)$. To see that $ g$ is one-to-one, let $ b_1,b_2\in B$, and suppose that $ g(b_1)=g(b_2)$. This gives $ \mathscr{C}\big(f^{-1}(\{b_1\})\big)=\mathscr{C}\big(f^{-1}(\{b_2\})\big)$, but since the elements of $ \mathcal{F}$ are disjoint, this implies that $ f^{-1}(\{b_1\})=f^{-1}(\{b_2\})$, and thus $ b_1=b_2$. So $ g$ is a one-to-one function from $ B$ to $ A$. $ \qedsymbol$



"one-to-one function from onto function" is owned by mathcam. [ owner history (1) ]
(view preamble)

View style:

See Also: function, choice function, axiom of choice, set, onto, Schröder-Bernstein theorem, an injection between two finite sets of the same cardinality is bijective, a surjection between finite sets of the same cardinality is bijective, set, surjective

Keywords:  one-to-one, onto, choice function, axiom of choice

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

Cross-references: implies, disjoint, choice function, mutually disjoint, subset, singleton, one-to-one, function, onto
There is 1 reference to this entry.

This is version 5 of one-to-one function from onto function, born on 2006-12-08, modified 2006-12-08.
Object id is 8604, canonical name is OneToOneFunctionFromOntoFunction.
Accessed 3586 times total.

Classification:
AMS MSC: 03E25 (Mathematical logic and foundations :: Set theory :: Axiom of choice and related propositions)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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