Mixing
Show that a function $f: A to B$ is surjective if and only if it has a right inverse.
$begingroup$
The textbook I'm reading from defines a right-inverse as follows:
Let $f: A to B$ be a function. A right inverse of $f$ is a function $g: B to A$ with the property that $f circ g = id_B$ where $id_B$ is the identity function on $B$.
Now, I'm asked to show that $f: A to B$ has a right inverse iff it is surjective. The author notes that I may use the axiom of choice in this proof. In other words, they say to assume that given a family of disjoint nonempty subsets of a set, there is a way to choose one element in each member of the family.
Proof Attempt: Suppose $f$ has a right inverse. So, there is a function $g: B to A$ such that $f circ g = id_B$. Now, choose an element $b in B$. We observe that $g(b) in A$ and that, by hypothesis, $f(g(b)) = id_B(b) = b$. So, we have found an element of $A$ (namely $g(b)$) whose image under $f$ is $b$. Since the choice of $b$ was arbitrary, we conclude that $f$ is surjective.
For the converse, suppose that $f$ is surjective. We need to construct a function $g: B to A$ such that $f circ g = id_B$ for all $x in B$. In order to do this, fix $b in B$. Since $f$ is surjective, there exists an element $g(b) in A$ such that $f(g(b)) = b$. However, we note that there may be more than one element of $A$ whose image is $b$ under $f$ (i.e. there may be more than one possible candidate for $g(b)$). In order to isolate a single candidate for $g(b)$, we proceed by cases.
Case 1: The function $f$ sends all elements of $A$ to $b in B$.
In this case, we may conclude by the surjectivity of $f$ that $b$ is the only element of $B$. Therefore if we pick an element $s in A$, we may define a function $g: B to A$ where $g(b) = s$. Then, we simply observe that $f(g(b)) = f(s) = b = id_B(b)$. Since $b$ is the only element of $B$, we may immediately conclude that $g$ is a right inverse of $f$.
Case 2: Only the elements in a proper subset of $A$ are mapped to $b$ by the function $f$.
In this case, we can divide the set $A$ into two disjoint subsets $R$ and $S$ where $R$ is the set of all elements in $A$ that get mapped to $b$ by $f$ and $S$ is the set of all elements of $A$ that are not mapped to $b$ by $f$. By the axiom of choice, I can select a single element $p in R$ and simply let $g(b) = p$. This shows that for any element $x$ of $B$, I can always find a single candidate for $g(x) in A$ such that $f(g(x)) =x$. Then, we can properly define a function $g: B to A$ that sends any $x in B$ to the single candidate $g(x)$ that we have chosen, and, by construction, $g$ will be a right inverse of $f$. This completes the proof.
Is my proof correct? This is the first time I've done a proof requiring the axiom of choice, so I'm wondering if I've invoked it correctly. Are there any ways that I could improve the proof or details that perhaps I'm missing?
functions proof-verification elementary-set-theory proof-writing
edited Dec 21 '18 at 16:23
SvanN
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
$endgroup$
add a comment |
$begingroup$
The textbook I'm reading from defines a right-inverse as follows:
Let $f: A to B$ be a function. A right inverse of $f$ is a function $g: B to A$ with the property that $f circ g = id_B$ where $id_B$ is the identity function on $B$.
Now, I'm asked to show that $f: A to B$ has a right inverse iff it is surjective. The author notes that I may use the axiom of choice in this proof. In other words, they say to assume that given a family of disjoint nonempty subsets of a set, there is a way to choose one element in each member of the family.
Proof Attempt: Suppose $f$ has a right inverse. So, there is a function $g: B to A$ such that $f circ g = id_B$. Now, choose an element $b in B$. We observe that $g(b) in A$ and that, by hypothesis, $f(g(b)) = id_B(b) = b$. So, we have found an element of $A$ (namely $g(b)$) whose image under $f$ is $b$. Since the choice of $b$ was arbitrary, we conclude that $f$ is surjective.
For the converse, suppose that $f$ is surjective. We need to construct a function $g: B to A$ such that $f circ g = id_B$ for all $x in B$. In order to do this, fix $b in B$. Since $f$ is surjective, there exists an element $g(b) in A$ such that $f(g(b)) = b$. However, we note that there may be more than one element of $A$ whose image is $b$ under $f$ (i.e. there may be more than one possible candidate for $g(b)$). In order to isolate a single candidate for $g(b)$, we proceed by cases.
Case 1: The function $f$ sends all elements of $A$ to $b in B$.
In this case, we may conclude by the surjectivity of $f$ that $b$ is the only element of $B$. Therefore if we pick an element $s in A$, we may define a function $g: B to A$ where $g(b) = s$. Then, we simply observe that $f(g(b)) = f(s) = b = id_B(b)$. Since $b$ is the only element of $B$, we may immediately conclude that $g$ is a right inverse of $f$.
Case 2: Only the elements in a proper subset of $A$ are mapped to $b$ by the function $f$.
In this case, we can divide the set $A$ into two disjoint subsets $R$ and $S$ where $R$ is the set of all elements in $A$ that get mapped to $b$ by $f$ and $S$ is the set of all elements of $A$ that are not mapped to $b$ by $f$. By the axiom of choice, I can select a single element $p in R$ and simply let $g(b) = p$. This shows that for any element $x$ of $B$, I can always find a single candidate for $g(x) in A$ such that $f(g(x)) =x$. Then, we can properly define a function $g: B to A$ that sends any $x in B$ to the single candidate $g(x)$ that we have chosen, and, by construction, $g$ will be a right inverse of $f$. This completes the proof.
Is my proof correct? This is the first time I've done a proof requiring the axiom of choice, so I'm wondering if I've invoked it correctly. Are there any ways that I could improve the proof or details that perhaps I'm missing?
functions proof-verification elementary-set-theory proof-writing
edited Dec 21 '18 at 16:23
SvanN
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
$endgroup$
add a comment |
$begingroup$
The textbook I'm reading from defines a right-inverse as follows:
Let $f: A to B$ be a function. A right inverse of $f$ is a function $g: B to A$ with the property that $f circ g = id_B$ where $id_B$ is the identity function on $B$.
Now, I'm asked to show that $f: A to B$ has a right inverse iff it is surjective. The author notes that I may use the axiom of choice in this proof. In other words, they say to assume that given a family of disjoint nonempty subsets of a set, there is a way to choose one element in each member of the family.
Proof Attempt: Suppose $f$ has a right inverse. So, there is a function $g: B to A$ such that $f circ g = id_B$. Now, choose an element $b in B$. We observe that $g(b) in A$ and that, by hypothesis, $f(g(b)) = id_B(b) = b$. So, we have found an element of $A$ (namely $g(b)$) whose image under $f$ is $b$. Since the choice of $b$ was arbitrary, we conclude that $f$ is surjective.
For the converse, suppose that $f$ is surjective. We need to construct a function $g: B to A$ such that $f circ g = id_B$ for all $x in B$. In order to do this, fix $b in B$. Since $f$ is surjective, there exists an element $g(b) in A$ such that $f(g(b)) = b$. However, we note that there may be more than one element of $A$ whose image is $b$ under $f$ (i.e. there may be more than one possible candidate for $g(b)$). In order to isolate a single candidate for $g(b)$, we proceed by cases.
Case 1: The function $f$ sends all elements of $A$ to $b in B$.
In this case, we may conclude by the surjectivity of $f$ that $b$ is the only element of $B$. Therefore if we pick an element $s in A$, we may define a function $g: B to A$ where $g(b) = s$. Then, we simply observe that $f(g(b)) = f(s) = b = id_B(b)$. Since $b$ is the only element of $B$, we may immediately conclude that $g$ is a right inverse of $f$.
Case 2: Only the elements in a proper subset of $A$ are mapped to $b$ by the function $f$.
In this case, we can divide the set $A$ into two disjoint subsets $R$ and $S$ where $R$ is the set of all elements in $A$ that get mapped to $b$ by $f$ and $S$ is the set of all elements of $A$ that are not mapped to $b$ by $f$. By the axiom of choice, I can select a single element $p in R$ and simply let $g(b) = p$. This shows that for any element $x$ of $B$, I can always find a single candidate for $g(x) in A$ such that $f(g(x)) =x$. Then, we can properly define a function $g: B to A$ that sends any $x in B$ to the single candidate $g(x)$ that we have chosen, and, by construction, $g$ will be a right inverse of $f$. This completes the proof.
Is my proof correct? This is the first time I've done a proof requiring the axiom of choice, so I'm wondering if I've invoked it correctly. Are there any ways that I could improve the proof or details that perhaps I'm missing?
functions proof-verification elementary-set-theory proof-writing
edited Dec 21 '18 at 16:23
SvanN
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
$endgroup$
The textbook I'm reading from defines a right-inverse as follows:
Let $f: A to B$ be a function. A right inverse of $f$ is a function $g: B to A$ with the property that $f circ g = id_B$ where $id_B$ is the identity function on $B$.
Now, I'm asked to show that $f: A to B$ has a right inverse iff it is surjective. The author notes that I may use the axiom of choice in this proof. In other words, they say to assume that given a family of disjoint nonempty subsets of a set, there is a way to choose one element in each member of the family.
Proof Attempt: Suppose $f$ has a right inverse. So, there is a function $g: B to A$ such that $f circ g = id_B$. Now, choose an element $b in B$. We observe that $g(b) in A$ and that, by hypothesis, $f(g(b)) = id_B(b) = b$. So, we have found an element of $A$ (namely $g(b)$) whose image under $f$ is $b$. Since the choice of $b$ was arbitrary, we conclude that $f$ is surjective.
For the converse, suppose that $f$ is surjective. We need to construct a function $g: B to A$ such that $f circ g = id_B$ for all $x in B$. In order to do this, fix $b in B$. Since $f$ is surjective, there exists an element $g(b) in A$ such that $f(g(b)) = b$. However, we note that there may be more than one element of $A$ whose image is $b$ under $f$ (i.e. there may be more than one possible candidate for $g(b)$). In order to isolate a single candidate for $g(b)$, we proceed by cases.
Case 1: The function $f$ sends all elements of $A$ to $b in B$.
In this case, we may conclude by the surjectivity of $f$ that $b$ is the only element of $B$. Therefore if we pick an element $s in A$, we may define a function $g: B to A$ where $g(b) = s$. Then, we simply observe that $f(g(b)) = f(s) = b = id_B(b)$. Since $b$ is the only element of $B$, we may immediately conclude that $g$ is a right inverse of $f$.
Case 2: Only the elements in a proper subset of $A$ are mapped to $b$ by the function $f$.
In this case, we can divide the set $A$ into two disjoint subsets $R$ and $S$ where $R$ is the set of all elements in $A$ that get mapped to $b$ by $f$ and $S$ is the set of all elements of $A$ that are not mapped to $b$ by $f$. By the axiom of choice, I can select a single element $p in R$ and simply let $g(b) = p$. This shows that for any element $x$ of $B$, I can always find a single candidate for $g(x) in A$ such that $f(g(x)) =x$. Then, we can properly define a function $g: B to A$ that sends any $x in B$ to the single candidate $g(x)$ that we have chosen, and, by construction, $g$ will be a right inverse of $f$. This completes the proof.
Is my proof correct? This is the first time I've done a proof requiring the axiom of choice, so I'm wondering if I've invoked it correctly. Are there any ways that I could improve the proof or details that perhaps I'm missing?
functions proof-verification elementary-set-theory proof-writing
functions proof-verification elementary-set-theory proof-writing
edited Dec 21 '18 at 16:23
SvanN
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
edited Dec 21 '18 at 16:23
SvanN
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
edited Dec 21 '18 at 16:23
SvanN
2,0661422
edited Dec 21 '18 at 16:23
SvanN
2,0661422
edited Dec 21 '18 at 16:23
SvanN
2,0661422
2,0661422
asked Dec 21 '18 at 15:37
user516079user516079
328210
asked Dec 21 '18 at 15:37
user516079user516079
328210
asked Dec 21 '18 at 15:37
user516079user516079
328210
328210
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
I think you start having difficulty right around this statement:
By the axiom of choice, I can select a single element $pin mathbb{R}$ and simply let $g(b) = p$.
That is not the point of the axiom of choice. The axiom of choice means, intuitively, that we can make infinitely many choices all at once.
As such, your proof doesn't really highlight how to use the AC fully formally.
I'd phrase it as follows. Recall that AC has one of its formulations as follows.
If your textbook gave a different definition, it may be a good exercise to prove it is equivalent to mine.
Axiom of Choice. Let $mathscr{C}$ be a nonempty set, not containing the empty set. Then there exists a function $F : mathscr{C} to bigcup mathscr{C}$ such that $F(S) in S$ for all $S in mathscr{C}$.
(Recall that $bigcup mathscr{C}$ is the union of all sets in $mathscr{C}$, i.e., $bigcup mathscr{C} = bigcup_{S in mathscr{C}} S$.)
In other words, AC guarantees the existence of a function that, for a collection of sets, 'picks' an element from each set in that collection.
Now suppose that a function $f : A to B$ is surjective. Then define the collection
$$ mathscr{C} := { f^{-1}({b}) subseteq A mid bin B }.$$
(Recall that $f^{-1}({b})$ is the set of all $a in A$ such that $f(a) = b$.)
Since $f$ is surjective, none of the sets in $mathscr{C}$ is empty. Thus we may apply AC to it to obtain a map
$$ F : mathscr{C} to A$$
which picks one element from each set in $mathscr{C}$ (note that $bigcup mathscr{C} = A$). Now define
$$ g : B to A : b mapsto F( f^{-1}({b})).$$
That is, when given a $b in B$, we consider the set $f^{-1}({b})$ (which is nonempty) and 'pick' an element from it. This makes $g$ a right-inverse for $f$. As an exercise, try to write out fully formally why this is so.
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
$endgroup$
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
add a comment |
$begingroup$
The use of the axiom of choice actually comes in after the following sentence in your question:
"...This shows that for any element $x$ of $B$, I can find a single candidate for $g(x)in A$ such that $f(g(x))=x$...."
You can do that observation for any fixed $xin A$ but that on its own does not assure yet the existence of a function $g:Bto A$ that sends every $yin B$ to a suitable candidate.
For that last step the axiom of choice comes in.
One of its forms is:
If $mathcal P$ is a partition of $A$ then a function $nu:mathcal Pto A$ exists such that $nu(P)in P$ for every $Pinmathcal P$.
This can be applied here on the partition $mathcal P:={f^{-1}({b})mid bin B}$.
Note that this $mathcal P$ is indeed a partition of $A$ because $f$ is surjective ensuring that $f^{-1}({b})neqvarnothing$ for every $bin B$.
If $h:Btomathcal P$ is prescribed by $bmapsto f^{-1}({b})$ then for $g$ we can take the composition $nucirc h:Bto A$.
Also this way of working makes a split up in two cases redundant.
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
$endgroup$
add a comment |
$begingroup$
The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$Lambda:={(h,C): Csubseteq B, h: Cto A , fcirc h=Id_C}$
This set is non-empty because if you consider $ain A$ then
$(h, {f(a)})in Lambda neq emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $Lambda$ :
$(h,C)< (r,S)$ if and only if $ Csubseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $Lambda$.
Now we consider a chain $Xsubset Lambda$
Then $(cup_{(h,C)in X} h, cup_{(h,C)in X} C)in Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$ for $(Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $bin B/C$ by surjectivity of $f$ there exists an element $ain A$ such that $f(a)=b$.
Then you can define $r: Ccup {b} to A$ such that $r(x)=h(x)$ if $xin C$ and $r(x)=a$ if $x=f(a)$.
So $(r,Ccup {b})in Lambda$ and $(r,Ccup {b})<(h,C)$ and it is not possible by maximality of $(h,C)$
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
$endgroup$
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048616%2fshow-that-a-function-f-a-to-b-is-surjective-if-and-only-if-it-has-a-right-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I think you start having difficulty right around this statement:
By the axiom of choice, I can select a single element $pin mathbb{R}$ and simply let $g(b) = p$.
That is not the point of the axiom of choice. The axiom of choice means, intuitively, that we can make infinitely many choices all at once.
As such, your proof doesn't really highlight how to use the AC fully formally.
I'd phrase it as follows. Recall that AC has one of its formulations as follows.
If your textbook gave a different definition, it may be a good exercise to prove it is equivalent to mine.
Axiom of Choice. Let $mathscr{C}$ be a nonempty set, not containing the empty set. Then there exists a function $F : mathscr{C} to bigcup mathscr{C}$ such that $F(S) in S$ for all $S in mathscr{C}$.
(Recall that $bigcup mathscr{C}$ is the union of all sets in $mathscr{C}$, i.e., $bigcup mathscr{C} = bigcup_{S in mathscr{C}} S$.)
In other words, AC guarantees the existence of a function that, for a collection of sets, 'picks' an element from each set in that collection.
Now suppose that a function $f : A to B$ is surjective. Then define the collection
$$ mathscr{C} := { f^{-1}({b}) subseteq A mid bin B }.$$
(Recall that $f^{-1}({b})$ is the set of all $a in A$ such that $f(a) = b$.)
Since $f$ is surjective, none of the sets in $mathscr{C}$ is empty. Thus we may apply AC to it to obtain a map
$$ F : mathscr{C} to A$$
which picks one element from each set in $mathscr{C}$ (note that $bigcup mathscr{C} = A$). Now define
$$ g : B to A : b mapsto F( f^{-1}({b})).$$
That is, when given a $b in B$, we consider the set $f^{-1}({b})$ (which is nonempty) and 'pick' an element from it. This makes $g$ a right-inverse for $f$. As an exercise, try to write out fully formally why this is so.
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
$endgroup$
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
add a comment |
$begingroup$
I think you start having difficulty right around this statement:
By the axiom of choice, I can select a single element $pin mathbb{R}$ and simply let $g(b) = p$.
That is not the point of the axiom of choice. The axiom of choice means, intuitively, that we can make infinitely many choices all at once.
As such, your proof doesn't really highlight how to use the AC fully formally.
I'd phrase it as follows. Recall that AC has one of its formulations as follows.
If your textbook gave a different definition, it may be a good exercise to prove it is equivalent to mine.
Axiom of Choice. Let $mathscr{C}$ be a nonempty set, not containing the empty set. Then there exists a function $F : mathscr{C} to bigcup mathscr{C}$ such that $F(S) in S$ for all $S in mathscr{C}$.
(Recall that $bigcup mathscr{C}$ is the union of all sets in $mathscr{C}$, i.e., $bigcup mathscr{C} = bigcup_{S in mathscr{C}} S$.)
In other words, AC guarantees the existence of a function that, for a collection of sets, 'picks' an element from each set in that collection.
Now suppose that a function $f : A to B$ is surjective. Then define the collection
$$ mathscr{C} := { f^{-1}({b}) subseteq A mid bin B }.$$
(Recall that $f^{-1}({b})$ is the set of all $a in A$ such that $f(a) = b$.)
Since $f$ is surjective, none of the sets in $mathscr{C}$ is empty. Thus we may apply AC to it to obtain a map
$$ F : mathscr{C} to A$$
which picks one element from each set in $mathscr{C}$ (note that $bigcup mathscr{C} = A$). Now define
$$ g : B to A : b mapsto F( f^{-1}({b})).$$
That is, when given a $b in B$, we consider the set $f^{-1}({b})$ (which is nonempty) and 'pick' an element from it. This makes $g$ a right-inverse for $f$. As an exercise, try to write out fully formally why this is so.
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
$endgroup$
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
add a comment |
$begingroup$
I think you start having difficulty right around this statement:
By the axiom of choice, I can select a single element $pin mathbb{R}$ and simply let $g(b) = p$.
That is not the point of the axiom of choice. The axiom of choice means, intuitively, that we can make infinitely many choices all at once.
As such, your proof doesn't really highlight how to use the AC fully formally.
I'd phrase it as follows. Recall that AC has one of its formulations as follows.
If your textbook gave a different definition, it may be a good exercise to prove it is equivalent to mine.
Axiom of Choice. Let $mathscr{C}$ be a nonempty set, not containing the empty set. Then there exists a function $F : mathscr{C} to bigcup mathscr{C}$ such that $F(S) in S$ for all $S in mathscr{C}$.
(Recall that $bigcup mathscr{C}$ is the union of all sets in $mathscr{C}$, i.e., $bigcup mathscr{C} = bigcup_{S in mathscr{C}} S$.)
In other words, AC guarantees the existence of a function that, for a collection of sets, 'picks' an element from each set in that collection.
Now suppose that a function $f : A to B$ is surjective. Then define the collection
$$ mathscr{C} := { f^{-1}({b}) subseteq A mid bin B }.$$
(Recall that $f^{-1}({b})$ is the set of all $a in A$ such that $f(a) = b$.)
Since $f$ is surjective, none of the sets in $mathscr{C}$ is empty. Thus we may apply AC to it to obtain a map
$$ F : mathscr{C} to A$$
which picks one element from each set in $mathscr{C}$ (note that $bigcup mathscr{C} = A$). Now define
$$ g : B to A : b mapsto F( f^{-1}({b})).$$
That is, when given a $b in B$, we consider the set $f^{-1}({b})$ (which is nonempty) and 'pick' an element from it. This makes $g$ a right-inverse for $f$. As an exercise, try to write out fully formally why this is so.
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
$endgroup$
I think you start having difficulty right around this statement:
By the axiom of choice, I can select a single element $pin mathbb{R}$ and simply let $g(b) = p$.
That is not the point of the axiom of choice. The axiom of choice means, intuitively, that we can make infinitely many choices all at once.
As such, your proof doesn't really highlight how to use the AC fully formally.
I'd phrase it as follows. Recall that AC has one of its formulations as follows.
If your textbook gave a different definition, it may be a good exercise to prove it is equivalent to mine.
Axiom of Choice. Let $mathscr{C}$ be a nonempty set, not containing the empty set. Then there exists a function $F : mathscr{C} to bigcup mathscr{C}$ such that $F(S) in S$ for all $S in mathscr{C}$.
(Recall that $bigcup mathscr{C}$ is the union of all sets in $mathscr{C}$, i.e., $bigcup mathscr{C} = bigcup_{S in mathscr{C}} S$.)
In other words, AC guarantees the existence of a function that, for a collection of sets, 'picks' an element from each set in that collection.
Now suppose that a function $f : A to B$ is surjective. Then define the collection
$$ mathscr{C} := { f^{-1}({b}) subseteq A mid bin B }.$$
(Recall that $f^{-1}({b})$ is the set of all $a in A$ such that $f(a) = b$.)
Since $f$ is surjective, none of the sets in $mathscr{C}$ is empty. Thus we may apply AC to it to obtain a map
$$ F : mathscr{C} to A$$
which picks one element from each set in $mathscr{C}$ (note that $bigcup mathscr{C} = A$). Now define
$$ g : B to A : b mapsto F( f^{-1}({b})).$$
That is, when given a $b in B$, we consider the set $f^{-1}({b})$ (which is nonempty) and 'pick' an element from it. This makes $g$ a right-inverse for $f$. As an exercise, try to write out fully formally why this is so.
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
edited Jan 17 at 19:08
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
answered Dec 21 '18 at 16:07
SvanNSvanN
2,0661422
2,0661422
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
add a comment |
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
$begingroup$
Your prove is the simplest and interesting
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:28
add a comment |
$begingroup$
The use of the axiom of choice actually comes in after the following sentence in your question:
"...This shows that for any element $x$ of $B$, I can find a single candidate for $g(x)in A$ such that $f(g(x))=x$...."
You can do that observation for any fixed $xin A$ but that on its own does not assure yet the existence of a function $g:Bto A$ that sends every $yin B$ to a suitable candidate.
For that last step the axiom of choice comes in.
One of its forms is:
If $mathcal P$ is a partition of $A$ then a function $nu:mathcal Pto A$ exists such that $nu(P)in P$ for every $Pinmathcal P$.
This can be applied here on the partition $mathcal P:={f^{-1}({b})mid bin B}$.
Note that this $mathcal P$ is indeed a partition of $A$ because $f$ is surjective ensuring that $f^{-1}({b})neqvarnothing$ for every $bin B$.
If $h:Btomathcal P$ is prescribed by $bmapsto f^{-1}({b})$ then for $g$ we can take the composition $nucirc h:Bto A$.
Also this way of working makes a split up in two cases redundant.
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
$endgroup$
add a comment |
$begingroup$
The use of the axiom of choice actually comes in after the following sentence in your question:
"...This shows that for any element $x$ of $B$, I can find a single candidate for $g(x)in A$ such that $f(g(x))=x$...."
You can do that observation for any fixed $xin A$ but that on its own does not assure yet the existence of a function $g:Bto A$ that sends every $yin B$ to a suitable candidate.
For that last step the axiom of choice comes in.
One of its forms is:
If $mathcal P$ is a partition of $A$ then a function $nu:mathcal Pto A$ exists such that $nu(P)in P$ for every $Pinmathcal P$.
This can be applied here on the partition $mathcal P:={f^{-1}({b})mid bin B}$.
Note that this $mathcal P$ is indeed a partition of $A$ because $f$ is surjective ensuring that $f^{-1}({b})neqvarnothing$ for every $bin B$.
If $h:Btomathcal P$ is prescribed by $bmapsto f^{-1}({b})$ then for $g$ we can take the composition $nucirc h:Bto A$.
Also this way of working makes a split up in two cases redundant.
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
$endgroup$
add a comment |
$begingroup$
The use of the axiom of choice actually comes in after the following sentence in your question:
"...This shows that for any element $x$ of $B$, I can find a single candidate for $g(x)in A$ such that $f(g(x))=x$...."
You can do that observation for any fixed $xin A$ but that on its own does not assure yet the existence of a function $g:Bto A$ that sends every $yin B$ to a suitable candidate.
For that last step the axiom of choice comes in.
One of its forms is:
If $mathcal P$ is a partition of $A$ then a function $nu:mathcal Pto A$ exists such that $nu(P)in P$ for every $Pinmathcal P$.
This can be applied here on the partition $mathcal P:={f^{-1}({b})mid bin B}$.
Note that this $mathcal P$ is indeed a partition of $A$ because $f$ is surjective ensuring that $f^{-1}({b})neqvarnothing$ for every $bin B$.
If $h:Btomathcal P$ is prescribed by $bmapsto f^{-1}({b})$ then for $g$ we can take the composition $nucirc h:Bto A$.
Also this way of working makes a split up in two cases redundant.
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
$endgroup$
The use of the axiom of choice actually comes in after the following sentence in your question:
"...This shows that for any element $x$ of $B$, I can find a single candidate for $g(x)in A$ such that $f(g(x))=x$...."
You can do that observation for any fixed $xin A$ but that on its own does not assure yet the existence of a function $g:Bto A$ that sends every $yin B$ to a suitable candidate.
For that last step the axiom of choice comes in.
One of its forms is:
If $mathcal P$ is a partition of $A$ then a function $nu:mathcal Pto A$ exists such that $nu(P)in P$ for every $Pinmathcal P$.
This can be applied here on the partition $mathcal P:={f^{-1}({b})mid bin B}$.
Note that this $mathcal P$ is indeed a partition of $A$ because $f$ is surjective ensuring that $f^{-1}({b})neqvarnothing$ for every $bin B$.
If $h:Btomathcal P$ is prescribed by $bmapsto f^{-1}({b})$ then for $g$ we can take the composition $nucirc h:Bto A$.
Also this way of working makes a split up in two cases redundant.
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
edited Dec 21 '18 at 16:20
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
answered Dec 21 '18 at 16:07
drhabdrhab
102k545136
102k545136
add a comment |
add a comment |
$begingroup$
The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$Lambda:={(h,C): Csubseteq B, h: Cto A , fcirc h=Id_C}$
This set is non-empty because if you consider $ain A$ then
$(h, {f(a)})in Lambda neq emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $Lambda$ :
$(h,C)< (r,S)$ if and only if $ Csubseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $Lambda$.
Now we consider a chain $Xsubset Lambda$
Then $(cup_{(h,C)in X} h, cup_{(h,C)in X} C)in Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$ for $(Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $bin B/C$ by surjectivity of $f$ there exists an element $ain A$ such that $f(a)=b$.
Then you can define $r: Ccup {b} to A$ such that $r(x)=h(x)$ if $xin C$ and $r(x)=a$ if $x=f(a)$.
So $(r,Ccup {b})in Lambda$ and $(r,Ccup {b})<(h,C)$ and it is not possible by maximality of $(h,C)$
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
$endgroup$
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
add a comment |
$begingroup$
The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$Lambda:={(h,C): Csubseteq B, h: Cto A , fcirc h=Id_C}$
This set is non-empty because if you consider $ain A$ then
$(h, {f(a)})in Lambda neq emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $Lambda$ :
$(h,C)< (r,S)$ if and only if $ Csubseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $Lambda$.
Now we consider a chain $Xsubset Lambda$
Then $(cup_{(h,C)in X} h, cup_{(h,C)in X} C)in Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$ for $(Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $bin B/C$ by surjectivity of $f$ there exists an element $ain A$ such that $f(a)=b$.
Then you can define $r: Ccup {b} to A$ such that $r(x)=h(x)$ if $xin C$ and $r(x)=a$ if $x=f(a)$.
So $(r,Ccup {b})in Lambda$ and $(r,Ccup {b})<(h,C)$ and it is not possible by maximality of $(h,C)$
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
$endgroup$
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
add a comment |
$begingroup$
The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$Lambda:={(h,C): Csubseteq B, h: Cto A , fcirc h=Id_C}$
This set is non-empty because if you consider $ain A$ then
$(h, {f(a)})in Lambda neq emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $Lambda$ :
$(h,C)< (r,S)$ if and only if $ Csubseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $Lambda$.
Now we consider a chain $Xsubset Lambda$
Then $(cup_{(h,C)in X} h, cup_{(h,C)in X} C)in Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$ for $(Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $bin B/C$ by surjectivity of $f$ there exists an element $ain A$ such that $f(a)=b$.
Then you can define $r: Ccup {b} to A$ such that $r(x)=h(x)$ if $xin C$ and $r(x)=a$ if $x=f(a)$.
So $(r,Ccup {b})in Lambda$ and $(r,Ccup {b})<(h,C)$ and it is not possible by maximality of $(h,C)$
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
$endgroup$
The axiom of choice is equivalent to Zorn’s Lemma that is more useful to prove a lot of results.
You can consider this set
$Lambda:={(h,C): Csubseteq B, h: Cto A , fcirc h=Id_C}$
This set is non-empty because if you consider $ain A$ then
$(h, {f(a)})in Lambda neq emptyset$ where $h(f(a))=a$
You can fix a particular order $<$ on $Lambda$ :
$(h,C)< (r,S)$ if and only if $ Csubseteq S$ and $r_{|C}=h$
You can verify that $<$ a partial order on $Lambda$.
Now we consider a chain $Xsubset Lambda$
Then $(cup_{(h,C)in X} h, cup_{(h,C)in X} C)in Lambda $ and it is a maggiorante for the chain $X$.
So by Zorn’s lemma there exists a maximal element $(h,C)$ for $(Lambda,<)$.
You can prove that $C=B$ in the hypothesis that $f$ is surjective.
If there exists an element $bin B/C$ by surjectivity of $f$ there exists an element $ain A$ such that $f(a)=b$.
Then you can define $r: Ccup {b} to A$ such that $r(x)=h(x)$ if $xin C$ and $r(x)=a$ if $x=f(a)$.
So $(r,Ccup {b})in Lambda$ and $(r,Ccup {b})<(h,C)$ and it is not possible by maximality of $(h,C)$
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
edited Dec 21 '18 at 16:23
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
answered Dec 21 '18 at 16:16
Federico FalluccaFederico Fallucca
2,175210
2,175210
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
add a comment |
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
I'm not sure if Zorn's lemma is the easiest introduction to the axiom of choice...
$endgroup$
– SvanN
Dec 21 '18 at 16:20
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
$begingroup$
You’re right, but I wanted propose another way to prove the statement.
$endgroup$
– Federico Fallucca
Dec 21 '18 at 16:26
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3048616%2fshow-that-a-function-f-a-to-b-is-surjective-if-and-only-if-it-has-a-right-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
