Mrthfx

How long is the D&D Starter Set campaign?

Are there any modern advantages of a fire piston?

Can a hotel cancel a confirmed reservation?

What is the lore-based reason that the Spectator has the Create Food and Water trait, instead of simply not requiring food and water?

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

If I delete my router's history can my ISP still provide it to my parents?

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

Why has the mole been redefined for 2019?

Can a person refuse a presidential pardon?

Why zero tolerance on nudity in space?

Am I a Rude Number?

How can my powered armor quickly replace its ceramic plates?

Roman Numerals equation 1

How can I deliver in-universe written lore to players without it being dry exposition?

Porting Linux to another platform requirements

Why are the books in the Game of Thrones citadel library shelved spine inwards?

Eww, those bytes are gross

If I deleted a game I lost the disc for, can I reinstall it digitally?

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

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

Cookies - Should the toggles be on?

How would an AI self awareness kill switch work?

Who is this Ant Woman character in this image alongside the Wasp?

How to say "Brexit" in Latin?

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 24 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 24 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 24 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 24 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 24 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
  4 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
  4 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
  4 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