Is my proof correct? (function composition, surjectivity) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)How to prove if a function is bijective?Function Surjectivity ProofProving a function is surjective given the composition is surjectiveSurjectivity of compositionShow that if $g circ f$ is injective, then so is $f$.Function composition proof - proof that function is injectiveright-cancellative property and surjectivityProof on surjective functionsComposite function proofsIf $g(x) = g(y)$ implies $f(x) = f(y)$ and $g$ is surjective, there's $h$ such that $f(x) = h(g(x))$
What do you call the main part of a joke?
How come Sam didn't become Lord of Horn Hill?
Do wooden building fires get hotter than 600°C?
How to write the following sign?
Is there any word for a place full of confusion?
What was the first language to use conditional keywords?
How to tell that you are a giant?
Take 2! Is this homebrew Lady of Pain warlock patron balanced?
How much damage would a cupful of neutron star matter do to the Earth?
What are the diatonic extended chords of C major?
What initially awakened the Balrog?
Drawing without replacement: why is the order of draw irrelevant?
How do you solve the twins Paradox?
Why does the remaining Rebel fleet at the end of Rogue One seem dramatically larger than the one in A New Hope?
Is grep documentation about ignoring case wrong, since it doesn't ignore case in filenames?
Time to Settle Down!
Maximum summed subsequences with non-adjacent items
How could we fake a moon landing now?
Find 108 by using 3,4,6
Why weren't discrete x86 CPUs ever used in game hardware?
An adverb for when you're not exaggerating
Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?
Effects on objects due to a brief relocation of massive amounts of mass
What is this clumpy 20-30cm high yellow-flowered plant?
Is my proof correct? (function composition, surjectivity)
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)How to prove if a function is bijective?Function Surjectivity ProofProving a function is surjective given the composition is surjectiveSurjectivity of compositionShow that if $g circ f$ is injective, then so is $f$.Function composition proof - proof that function is injectiveright-cancellative property and surjectivityProof on surjective functionsComposite function proofsIf $g(x) = g(y)$ implies $f(x) = f(y)$ and $g$ is surjective, there's $h$ such that $f(x) = h(g(x))$
$begingroup$
Exercise. Given sets $E$, $F$, $G$ and functions $g : E to F$ surjective, and $f : E to G$. Prove that there's a function $h : F to G$ such that $f = h circ g$ if and only if the equality $g(x) = g(y)$, with $x, y in E$, implies the equality $f(x) = f(y)$.
My strategy was the following.
Right to left. I assume that $h$ exists. Then if $g(x) = g(y)$, $h(g(x)) = h(g(y))$. Therefore $f(x) = f(y)$ by definition.
Left to right. I assume that the equality $g(x) = g(y)$, with $x,y in E$, implies the equality $f(x) = f(y)$. Given that $g$ is surjective, $g^-1(g(E)) = g^-1(F) = E$. Therefore $f(g^-1circ g(x)) = f(x)$ [note: I know that $f$ and $g$'s values at any given point $xin E$ have the same preimages, but I don't know how to state this more formally.]. I can then define $h: F to G$ such that $h(x) = fcirc g^-1(x)$, and it verifies the stated condition.
abstract-algebra functions discrete-mathematics proof-verification
edited Apr 3 at 16:29
egreg
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
$endgroup$
add a comment |
$begingroup$
Exercise. Given sets $E$, $F$, $G$ and functions $g : E to F$ surjective, and $f : E to G$. Prove that there's a function $h : F to G$ such that $f = h circ g$ if and only if the equality $g(x) = g(y)$, with $x, y in E$, implies the equality $f(x) = f(y)$.
My strategy was the following.
Right to left. I assume that $h$ exists. Then if $g(x) = g(y)$, $h(g(x)) = h(g(y))$. Therefore $f(x) = f(y)$ by definition.
Left to right. I assume that the equality $g(x) = g(y)$, with $x,y in E$, implies the equality $f(x) = f(y)$. Given that $g$ is surjective, $g^-1(g(E)) = g^-1(F) = E$. Therefore $f(g^-1circ g(x)) = f(x)$ [note: I know that $f$ and $g$'s values at any given point $xin E$ have the same preimages, but I don't know how to state this more formally.]. I can then define $h: F to G$ such that $h(x) = fcirc g^-1(x)$, and it verifies the stated condition.
abstract-algebra functions discrete-mathematics proof-verification
edited Apr 3 at 16:29
egreg
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
$endgroup$
1
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29
add a comment |
$begingroup$
Exercise. Given sets $E$, $F$, $G$ and functions $g : E to F$ surjective, and $f : E to G$. Prove that there's a function $h : F to G$ such that $f = h circ g$ if and only if the equality $g(x) = g(y)$, with $x, y in E$, implies the equality $f(x) = f(y)$.
My strategy was the following.
Right to left. I assume that $h$ exists. Then if $g(x) = g(y)$, $h(g(x)) = h(g(y))$. Therefore $f(x) = f(y)$ by definition.
Left to right. I assume that the equality $g(x) = g(y)$, with $x,y in E$, implies the equality $f(x) = f(y)$. Given that $g$ is surjective, $g^-1(g(E)) = g^-1(F) = E$. Therefore $f(g^-1circ g(x)) = f(x)$ [note: I know that $f$ and $g$'s values at any given point $xin E$ have the same preimages, but I don't know how to state this more formally.]. I can then define $h: F to G$ such that $h(x) = fcirc g^-1(x)$, and it verifies the stated condition.
abstract-algebra functions discrete-mathematics proof-verification
edited Apr 3 at 16:29
egreg
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
$endgroup$
Exercise. Given sets $E$, $F$, $G$ and functions $g : E to F$ surjective, and $f : E to G$. Prove that there's a function $h : F to G$ such that $f = h circ g$ if and only if the equality $g(x) = g(y)$, with $x, y in E$, implies the equality $f(x) = f(y)$.
My strategy was the following.
Right to left. I assume that $h$ exists. Then if $g(x) = g(y)$, $h(g(x)) = h(g(y))$. Therefore $f(x) = f(y)$ by definition.
Left to right. I assume that the equality $g(x) = g(y)$, with $x,y in E$, implies the equality $f(x) = f(y)$. Given that $g$ is surjective, $g^-1(g(E)) = g^-1(F) = E$. Therefore $f(g^-1circ g(x)) = f(x)$ [note: I know that $f$ and $g$'s values at any given point $xin E$ have the same preimages, but I don't know how to state this more formally.]. I can then define $h: F to G$ such that $h(x) = fcirc g^-1(x)$, and it verifies the stated condition.
abstract-algebra functions discrete-mathematics proof-verification
abstract-algebra functions discrete-mathematics proof-verification
edited Apr 3 at 16:29
egreg
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
edited Apr 3 at 16:29
egreg
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
edited Apr 3 at 16:29
egreg
186k1486209
edited Apr 3 at 16:29
egreg
186k1486209
edited Apr 3 at 16:29
egreg
186k1486209
186k1486209
asked Apr 1 at 19:08
ydnfmewydnfmew
433
asked Apr 1 at 19:08
ydnfmewydnfmew
433
asked Apr 1 at 19:08
ydnfmewydnfmew
433
433
1
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29
add a comment |
1
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29
1
1
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As Arturo has written in the comment $g$ will not necessary have an inverse. Here's a minimal example: $$E=0,1\F=0\G=0$$
In this case, all three functions, $f,g,h$, will be the constant map to $0$ (with different domain/range).
To me, there are two issues in your proof
- You seem to have only used the surjective property of $g$ but you haven't really used your assumption: $$g(x)=g(y)Rightarrow f(x)=f(y)$$
- You even wrote down that you cannot state something more formally (which really is the critical part of the proof)
The idea of your proof is more or less correct, but you will need to define what you are calling $g^-1$ into an actual function. You will need to pick a representative and use the $g(x)=g(y)Rightarrow f(x)=f(y)$ assumption to show that $h$ has the properties needed.
answered Apr 3 at 15:49
DubsDubs
59426
$endgroup$
add a comment |
Your Answer
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%2f3171034%2fis-my-proof-correct-function-composition-surjectivity%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As Arturo has written in the comment $g$ will not necessary have an inverse. Here's a minimal example: $$E=0,1\F=0\G=0$$
In this case, all three functions, $f,g,h$, will be the constant map to $0$ (with different domain/range).
To me, there are two issues in your proof
- You seem to have only used the surjective property of $g$ but you haven't really used your assumption: $$g(x)=g(y)Rightarrow f(x)=f(y)$$
- You even wrote down that you cannot state something more formally (which really is the critical part of the proof)
The idea of your proof is more or less correct, but you will need to define what you are calling $g^-1$ into an actual function. You will need to pick a representative and use the $g(x)=g(y)Rightarrow f(x)=f(y)$ assumption to show that $h$ has the properties needed.
answered Apr 3 at 15:49
DubsDubs
59426
$endgroup$
add a comment |
$begingroup$
As Arturo has written in the comment $g$ will not necessary have an inverse. Here's a minimal example: $$E=0,1\F=0\G=0$$
In this case, all three functions, $f,g,h$, will be the constant map to $0$ (with different domain/range).
To me, there are two issues in your proof
- You seem to have only used the surjective property of $g$ but you haven't really used your assumption: $$g(x)=g(y)Rightarrow f(x)=f(y)$$
- You even wrote down that you cannot state something more formally (which really is the critical part of the proof)
The idea of your proof is more or less correct, but you will need to define what you are calling $g^-1$ into an actual function. You will need to pick a representative and use the $g(x)=g(y)Rightarrow f(x)=f(y)$ assumption to show that $h$ has the properties needed.
answered Apr 3 at 15:49
DubsDubs
59426
$endgroup$
add a comment |
$begingroup$
As Arturo has written in the comment $g$ will not necessary have an inverse. Here's a minimal example: $$E=0,1\F=0\G=0$$
In this case, all three functions, $f,g,h$, will be the constant map to $0$ (with different domain/range).
To me, there are two issues in your proof
- You seem to have only used the surjective property of $g$ but you haven't really used your assumption: $$g(x)=g(y)Rightarrow f(x)=f(y)$$
- You even wrote down that you cannot state something more formally (which really is the critical part of the proof)
The idea of your proof is more or less correct, but you will need to define what you are calling $g^-1$ into an actual function. You will need to pick a representative and use the $g(x)=g(y)Rightarrow f(x)=f(y)$ assumption to show that $h$ has the properties needed.
answered Apr 3 at 15:49
DubsDubs
59426
$endgroup$
As Arturo has written in the comment $g$ will not necessary have an inverse. Here's a minimal example: $$E=0,1\F=0\G=0$$
In this case, all three functions, $f,g,h$, will be the constant map to $0$ (with different domain/range).
To me, there are two issues in your proof
- You seem to have only used the surjective property of $g$ but you haven't really used your assumption: $$g(x)=g(y)Rightarrow f(x)=f(y)$$
- You even wrote down that you cannot state something more formally (which really is the critical part of the proof)
The idea of your proof is more or less correct, but you will need to define what you are calling $g^-1$ into an actual function. You will need to pick a representative and use the $g(x)=g(y)Rightarrow f(x)=f(y)$ assumption to show that $h$ has the properties needed.
answered Apr 3 at 15:49
DubsDubs
59426
answered Apr 3 at 15:49
DubsDubs
59426
answered Apr 3 at 15:49
DubsDubs
59426
answered Apr 3 at 15:49
DubsDubs
59426
59426
add a comment |
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%2f3171034%2fis-my-proof-correct-function-composition-surjectivity%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
1
$begingroup$
You are conflating two different meantings of "$g^-1$". In your assertion "Given that $g$ is surjective", your use of $g^-1$ is for the function associated to sets: for each subset $X$ of $F$, $g^-1(X)$ is the collection of all $ein E$ such that $g(e)in X$. However, when you write $g^-1circ g(x))$, you are using it as a functional inverse that takes elements to elements, and such a function need not exist. There is no "$g^-1(x)$", because you do not know that $g$ has an inverse.
$endgroup$
– Arturo Magidin
Apr 1 at 19:15
$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
Apr 1 at 19:26
$begingroup$
Please, have a look at my edit, in order to improve your MathJax-fu.
$endgroup$
– egreg
Apr 3 at 16:29