a problem on composition of functions
$begingroup$
Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.
I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.
functions
New contributor
$endgroup$
add a comment |
$begingroup$
Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.
I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.
functions
New contributor
$endgroup$
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago
add a comment |
$begingroup$
Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.
I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.
functions
New contributor
$endgroup$
Let $f colon A to A$ be a function such that $f circ f=f$. If $f$ is one-to-one then prove that $f$ is also onto.
I know in my head that the func. $f$ is $f(x)=x$, but I can't develop a proof for the above statement.
functions
functions
New contributor
New contributor
edited 15 mins ago
user649511
New contributor
asked 4 hours ago
user649511user649511
234
234
New contributor
New contributor
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago
add a comment |
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.
Suppose $f$ is not surjective, and let
$B = f(A) tag 1$
be the image of $A$ under $f$; since
$f circ f = f, tag 2$
it is clear that every element of $B$ is fixed under $f$, for
$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$
furthermore, for $c in A$,
$f(c) = c Longrightarrow c in B; tag 4$
thus $B$ is precisely the set of fixed points of $f$.
We have assumed $f$ not surjective; then by the above we have
$B subsetneq A, tag 5$
which implies
$exists a in A setminus B; tag 6$
if
$b = f(a) in B, tag 7$
then
$f(b) = f(f(a)) = f(a) = b; tag 8$
we note
$B ni b ne a in A setminus B, tag 9$
which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.
$endgroup$
add a comment |
$begingroup$
We know
$fcirc f=f$ so $f([f(x)]) =f (x)$.
Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...
i see someone downvoted the question
if you feel its a dumb question please know I'm still in school learning relations and functions ! :)
New contributor
$endgroup$
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
add a comment |
$begingroup$
Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.
QED
$endgroup$
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
});
}
});
user649511 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2f3130960%2fa-problem-on-composition-of-functions%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$
What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.
Suppose $f$ is not surjective, and let
$B = f(A) tag 1$
be the image of $A$ under $f$; since
$f circ f = f, tag 2$
it is clear that every element of $B$ is fixed under $f$, for
$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$
furthermore, for $c in A$,
$f(c) = c Longrightarrow c in B; tag 4$
thus $B$ is precisely the set of fixed points of $f$.
We have assumed $f$ not surjective; then by the above we have
$B subsetneq A, tag 5$
which implies
$exists a in A setminus B; tag 6$
if
$b = f(a) in B, tag 7$
then
$f(b) = f(f(a)) = f(a) = b; tag 8$
we note
$B ni b ne a in A setminus B, tag 9$
which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.
$endgroup$
add a comment |
$begingroup$
What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.
Suppose $f$ is not surjective, and let
$B = f(A) tag 1$
be the image of $A$ under $f$; since
$f circ f = f, tag 2$
it is clear that every element of $B$ is fixed under $f$, for
$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$
furthermore, for $c in A$,
$f(c) = c Longrightarrow c in B; tag 4$
thus $B$ is precisely the set of fixed points of $f$.
We have assumed $f$ not surjective; then by the above we have
$B subsetneq A, tag 5$
which implies
$exists a in A setminus B; tag 6$
if
$b = f(a) in B, tag 7$
then
$f(b) = f(f(a)) = f(a) = b; tag 8$
we note
$B ni b ne a in A setminus B, tag 9$
which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.
$endgroup$
add a comment |
$begingroup$
What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.
Suppose $f$ is not surjective, and let
$B = f(A) tag 1$
be the image of $A$ under $f$; since
$f circ f = f, tag 2$
it is clear that every element of $B$ is fixed under $f$, for
$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$
furthermore, for $c in A$,
$f(c) = c Longrightarrow c in B; tag 4$
thus $B$ is precisely the set of fixed points of $f$.
We have assumed $f$ not surjective; then by the above we have
$B subsetneq A, tag 5$
which implies
$exists a in A setminus B; tag 6$
if
$b = f(a) in B, tag 7$
then
$f(b) = f(f(a)) = f(a) = b; tag 8$
we note
$B ni b ne a in A setminus B, tag 9$
which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.
$endgroup$
What I like about this problem is that it places no restriction on the carinality $A$; its conclusion binds for some very large sets indeed.
Suppose $f$ is not surjective, and let
$B = f(A) tag 1$
be the image of $A$ under $f$; since
$f circ f = f, tag 2$
it is clear that every element of $B$ is fixed under $f$, for
$b in B Longrightarrow exists c in A, ; b = f(c) Longrightarrow f(b) = f(f(c)) = f(c) = b; tag 3$
furthermore, for $c in A$,
$f(c) = c Longrightarrow c in B; tag 4$
thus $B$ is precisely the set of fixed points of $f$.
We have assumed $f$ not surjective; then by the above we have
$B subsetneq A, tag 5$
which implies
$exists a in A setminus B; tag 6$
if
$b = f(a) in B, tag 7$
then
$f(b) = f(f(a)) = f(a) = b; tag 8$
we note
$B ni b ne a in A setminus B, tag 9$
which contradicts the given hypothesis that $f$ is an injective map. Thus $f$ is in fact surjective.
edited 1 hour ago
answered 1 hour ago
Robert LewisRobert Lewis
47.4k23067
47.4k23067
add a comment |
add a comment |
$begingroup$
We know
$fcirc f=f$ so $f([f(x)]) =f (x)$.
Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...
i see someone downvoted the question
if you feel its a dumb question please know I'm still in school learning relations and functions ! :)
New contributor
$endgroup$
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
add a comment |
$begingroup$
We know
$fcirc f=f$ so $f([f(x)]) =f (x)$.
Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...
i see someone downvoted the question
if you feel its a dumb question please know I'm still in school learning relations and functions ! :)
New contributor
$endgroup$
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
add a comment |
$begingroup$
We know
$fcirc f=f$ so $f([f(x)]) =f (x)$.
Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...
i see someone downvoted the question
if you feel its a dumb question please know I'm still in school learning relations and functions ! :)
New contributor
$endgroup$
We know
$fcirc f=f$ so $f([f(x)]) =f (x)$.
Comparing both sides, which shows $[f (x)] = x$ (since $f$ is one-to-one)
so for all $x$ in codomain of $f$ there is an $x$ in domain such that $f(x) = x$ .. so it is onto.. yay...
i see someone downvoted the question
if you feel its a dumb question please know I'm still in school learning relations and functions ! :)
New contributor
edited 3 hours ago
Graham Kemp
86.2k43478
86.2k43478
New contributor
answered 4 hours ago
user649511user649511
234
234
New contributor
New contributor
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
add a comment |
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
$begingroup$
Questions get marked down or voted to close when they don't show enough initiative. To do that, this attempt should be included as part of the question.
$endgroup$
– Graham Kemp
3 hours ago
add a comment |
$begingroup$
Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.
QED
$endgroup$
add a comment |
$begingroup$
Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.
QED
$endgroup$
add a comment |
$begingroup$
Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.
QED
$endgroup$
Let $x in A$. Let $y=f(x).$ Then $f(y) = f(f(x)) = (f circ f) (x) = f(x)$ $implies y=x,$ if f was assumed to be injective. So if $f$ was injective then $f(x)=x,$ for all $x in A.$ So $f$ is the identity map on $A.$ But then $f$ is clearly surjective, as claimed.
QED
answered 1 hour ago
Dbchatto67Dbchatto67
1,301219
1,301219
add a comment |
add a comment |
user649511 is a new contributor. Be nice, and check out our Code of Conduct.
user649511 is a new contributor. Be nice, and check out our Code of Conduct.
user649511 is a new contributor. Be nice, and check out our Code of Conduct.
user649511 is a new contributor. Be nice, and check out our Code of Conduct.
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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%2f3130960%2fa-problem-on-composition-of-functions%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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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');
var $window = $(window),
onScroll = function(e) {
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom)) {
StackExchange.using('gps', function() { StackExchange.gps.track('embedded_signup_form.view', { location: 'question_page' }); });
$window.unbind('scroll', onScroll);
}
};
$window.on('scroll', onScroll);
});
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
$begingroup$
Welcome! What have you tried?
$endgroup$
– user458276
4 hours ago
$begingroup$
Don't try to prove what is the f function. I think that would be much harder than going through the definitions of one-to-one and onto. You can assume you have the one-to-one property and you use the "fof=f" equality somehow (possibly with another thoerem?) to result to the definition of onto.
$endgroup$
– frabala
4 hours ago
$begingroup$
thank you.. got it..
$endgroup$
– user649511
4 hours ago
$begingroup$
What are the definitions? What does it mean to be onto?
$endgroup$
– JavaMan
4 hours ago
$begingroup$
onto means that for a function from set A to set B every element in set B has a pre image in A . i.e. f(x) = y for every y in B
$endgroup$
– user649511
4 hours ago