Mistake in problem statement?

[Uncanny]

TL;DR Summary

This is a problem in my textbook on set theory, in a section on properties of compositions of functions and inverse functions. The problem is number 5.

Is it just me, or is the statement simply untrue? I have created a simple counterexample that is consistent with the hypotheses, but results in a contradiction of the result. It is included in pictorial form as the second attachment. Any insights?

 

[Uncanny]

I’m pretty sure the author meant to include the phrase “...for every surjective function f: A -> B...” instead of merely “...for every function f: A -> B...” in problem 5.. And analogously for injective functions f in problem 6.

 

[TeethWhitener]

In your example, for your chosen $g$ and $h$, does $g\circ f = h\circ f$ for every function $f$?

 

[martinbn]

I’m pretty sure the author meant to include the phrase “...for every surjective function f: A -> B...” instead of merely “...for every function f: A -> B...” in problem 5.. And analogously for injective functions f in problem 6.

What do you mean by merely? The set of all functions contains the set of all surjective functions.

 

[martinbn]

Summary:: This is a problem in my textbook on set theory, in a section on properties of compositions of functions and inverse functions. The problem is number 5.

Is it just me, or is the statement simply untrue? I have created a simple counterexample that is consistent with the hypotheses, but results in a contradiction of the result. It is included in pictorial form as the second attachment. Any insights?

In your example you have considered only on function $f$. The statement is that if it hold for every function, then $h$ and $g$ are equal. In your example there is an $f$ for which the condition is not satisfied.

 

[Uncanny]

So if I take an arbitrary surjective function, f, which by hypothesis satisfies the composition equality with g,h, then I can complete the proof. Basically, since the property holds by hypothesis for arbitrary f, take an f with a useful property to help you complete the proof.

 

[Uncanny]

The only way I can see this happening in practicality is if C is a singleton. Otherwise, I can always pick an f to **** up the day (no pun intended)

 

[TeethWhitener]

The only way I can see this happening in practicality is if C is a singleton. Otherwise, I can always pick an f to **** up the day (no pun intended)

The problem clearly says “for every function $f$,” not for a single $f$ of your choosing.

 

[martinbn]

The only way I can see this happening in practicality is if C is a singleton. Otherwise, I can always pick an f to **** up the day (no pun intended)

Same mistake. One f is not enough, that's why the statement is for every f.

 

[Uncanny]

No, I do get it now. What I’m saying is, if it came down to actually specifying some properties for g and h such that their composition with any f actually holds, I’d imagine they need be somewhat ‘simple’ functions.

 

[Uncanny]

I guess no one really cares what the functions g,h might end up “looking like” to satisfy equality with arbitrary f, but if I’m not mistaken, the proof would go something like:

Let f be any arbitrary surjective function from A into B... [rest is easy]

 

[Uncanny]

Also, while you guys are here, maybe someone can check my post on a proof involving functional graphs a few threads below

 

[Uncanny]

I’m working on problem 8 now (captured in the attachment below). I hope no one minds me posting a different- albeit somewhat related- question in the same thread.

Surely, in this problem statement, there is a slight mistake. Shouldn’t the phrase, “A must be a set with more than one element,” or something of the likes, be included- as in problem 6?

If so, and one proceeds via proof by contradiction, the axiom of choice is unneeded. This does, however, seem like a premature spot for this problem to appear for that reason though; AC has not been touched on as of yet in the text.

 

[martinbn]

No, there is no mistake.

 

[Uncanny]

Actually, let’s more carefully consider the set C. If C is a singleton, a contradiction may be reached. Thus, perhaps there is, indeed, a mistake present: C must be restricted be contain at least two (distinct) elements.

It does seem strange that this statement is omitted, since the earlier companion problem (#6) does include this necessary detail.

 

[martinbn]

Actually, let’s more carefully consider the set C. If C is a singleton, a contradiction may be reached. Thus, perhaps there is, indeed, a mistake present: C must be restricted be contain at least two (distinct) elements.

It does seem strange that this statement is omitted, since the earlier companion problem (#6) does include this necessary detail.

This doesn't make sense. What is the contradiction you think you can reach?

 

[Uncanny]

Consider C = {c}, B = {b2, b1}. Let g = h = B x C. f need not be surjective, even though g o f = h o f implies g = h.

 

[martinbn]

Consider C = {c}, B = {b2, b1}. Let g = h = B x C. f need not be surjective, even though g o f = h o f implies g = h.

That is not the statement of the problem. The problem says if for any g, h and C, then f is surjective. It doesn't say if for one g, h and C.

 

[Uncanny]

I’m working in the “if” direction, so I’m trying to “prove” f is surjective. I assume for any g,h etc...

If I suppose it’s true for any g,h that etc.. then I can pick whichever I like, and the property will hold. Again: I assume it’s true for all, so it’s true for any particular one (or two). I choose two particular functions that satisfy the supposed hypotheses, and it leads to a contradiction (f not needing to be surjective).

This can be avoided if C is simply forced to have at least two elements.

 

[martinbn]

I’m working in the “if” direction, so I’m trying to “prove” f is surjective. I assume for any g,h etc...

If I suppose it’s true for any g,h that etc.. then I can pick whichever I like, and the property will hold. Again: I assume it’s true for all, so it’s true for any particular one (or two). I choose two particular functions that satisfy the supposed hypotheses, and it leads to a contradiction (f not needing to be surjective).

This can be avoided if C is simply forced to have at least two elements.

Well, no. The statement "If for all X something is true, then f must be surjective" and the statement "If for one X something is true, then f need not be surjective" do not contradict each other.

 

[Uncanny]

Tell you what, find me a proof where C may be a singleton.

 

[TeethWhitener]

Consider C = {c}, B = {b2, b1}. Let g = h = B x C. f need not be surjective, even though g o f = h o f implies g = h.

I don’t understand this at all. $g$ and $h$ are functions from $B$ to $C$. How can $g=h=B\times C$?

 

[Uncanny]

It just means g = h = {(b1,c), (b2,c)} in that case. I’m showing that if C is allowed to be a singleton, a counterexample can be constructed.

 

[Uncanny]

Let’s try this instead: I challenge anyone to a proof of the surjectivity of f without resorting to placing any restrictions on C.

 

[TeethWhitener]

Let’s try this instead: I challenge anyone to a proof of the surjectivity of f without resorting to placing any restrictions on C.

It sounds like you’re asking us to do your homework for you.

 

[Uncanny]

it sounds like you talked yourself into a hole you’ve realized you can’t dig yourself out of

 

[PeterDonis]

it sounds like you talked yourself into a hole you’ve realized you can’t dig yourself out of

It sounds like it's time for this thread to be closed.