Fhyujk

Why has the mole been redefined for 2019?

Can I string the D&D Starter Set campaign into another module, keeping the same characters?

Using only 1s, make 29 with the minimum number of digits

Early credit roll before the end of the film

How to prevent cleaner from hanging my lock screen in Ubuntu 16.04

How to prevent users from executing commands through browser URL

Cookies - Should the toggles be on?

A starship is travelling at 0.9c and collides with a small rock. Will it leave a clean hole through, or will more happen?

Could a phylactery of a lich be a mirror or does it have to be a box?

Advice for a new journal editor

Blindfold battle as a gladiatorial spectacle - what are the tactics and communication methods?

What is 6÷2×(1+2) =?

What's a good word to describe a public place that looks like it wouldn't be rough?

Why do no American passenger airlines still operate dedicated cargo flights?

Why is oil called more viscous than water when we slip on oil more than we do on water

How to say "Brexit" in Latin?

How to count the characters of jar files by wc

How would an AI self awareness kill switch work?

Can an insurance company drop you after receiving a bill and refusing to pay?

Roman Numerals equation 1

Why zero tolerance on nudity in space?

Table formatting top left corner caption

Why do stocks necessarily drop during a recession?

Why isn't there a non-conducting core wire for high-frequency coil applications

a problem on composition of functions

Proving a Composition of Functions is BijectivePlease explain how to do this proof (involving functions)Proof involving functions.Proof of onto and one-to-one functions, compositionDefining composition of multiples of functions.Proof about composed functionsBehaviour of composition functions of a composite functionComposition of two functions - Bijectionfunction composition and identity functions proof2 questions regarding basic functions

3

1

$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

share|cite|improve this question

edited 17 mins ago

user649511

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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 | 

3

1

$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

share|cite|improve this question

edited 17 mins ago

user649511

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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

share|cite|improve this question

edited 17 mins ago

user649511

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

edited 17 mins ago

user649511

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

edited 17 mins ago

user649511

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 4 hours ago

user649511user649511

234

3 Answers
3

active

oldest

votes

3

$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.

share|cite|improve this answer

edited 1 hour ago

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

$endgroup$

add a comment | 

0

$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 ! :)

share|cite|improve this answer

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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 | 

0

$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

share|cite|improve this answer

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

$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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

3

$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.

share|cite|improve this answer

edited 1 hour ago

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

$endgroup$

add a comment | 

3

$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.

share|cite|improve this answer

edited 1 hour ago

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

$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.

share|cite|improve this answer

edited 1 hour ago

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

$endgroup$

share|cite|improve this answer

edited 1 hour ago

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

answered 1 hour ago

Robert LewisRobert Lewis

47.4k23067

0

$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 ! :)

share|cite|improve this answer

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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 | 

0

$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 ! :)

share|cite|improve this answer

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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 ! :)

share|cite|improve this answer

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 4 hours ago

Graham Kemp

86.2k43478

edited 4 hours ago

Graham Kemp

86.2k43478

answered 4 hours ago

user649511user649511

234

New contributor

user649511 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered 4 hours ago

user649511user649511

234

0

$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

share|cite|improve this answer

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

$endgroup$

add a comment | 

0

$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

share|cite|improve this answer

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

$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

share|cite|improve this answer

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

$endgroup$

share|cite|improve this answer

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219

answered 1 hour ago

Dbchatto67Dbchatto67

1,301219