Sfrgttk

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

Why do stocks necessarily drop during a recession?

Early credit roll before the end of the film

Would a National Army of mercenaries be a feasible idea?

How do you funnel food off a cutting board?

How would an AI self awareness kill switch work?

Is it a fallacy if someone claims they need an explanation for every word of your argument to the point where they don't understand common terms?

Why is mind meld hard for T'pol in Star Trek: Enterprise?

Eww, those bytes are gross

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

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

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

Citing paywalled articles accessed via illegal web sharing

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

Can I write a book of my D&D game?

Difference between `vector<int> v;` and `vector<int> v = vector<int>();`

How to prevent users from executing commands through browser URL

Why do neural networks need so many training examples to perform?

Can making a creature unable to attack after it has been assigned as an attacker remove it from combat?

How to say "Brexit" in Latin?

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

Is a debit card dangerous in my situation?

Avoiding morning and evening handshakes

Can a hotel cancel a confirmed reservation?

a problem on composition of functions

Can surjective functions map an element from the domain…Proving whether functions are one-to-one and onto.Surjectivity of Composite FunctionsOn left and right inverses of functionsDetermine if the following composition function is ontoProof about composed functionsThe notion of equality when considering composition of functionsProof of $f(x)=sin x +x$ is Surjective2 questions regarding basic functionsDomain and Codomain determining if it is a function

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 16 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 16 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 16 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 16 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 16 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 3 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 3 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 3 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 3 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 3 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 3 hours ago

Graham Kemp

86.2k43478

edited 3 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