5

Sorry if this seems trivial, I'm having some difficulty understanding a proof.

I'm doing exercise 5.1.14 of Velleman's How to Prove It and a solution posted in this question, including the comments, does not make sense to me. I'll restate the problem here:

Suppose $A$ is a nonempty set and $f:A\longrightarrow A$. Also suppose that for all $g:A\longrightarrow A, f\circ g=f$. Prove that f is a constant function. Hint: What happens if $g$ is constant?

Proving $f$ is constant, if $g$ is constant was easy, but I don't understand how that helps solve the problem. The way I read the question, $g$ has to be an arbitrary function from $A$ to $A$, and restricting it to a constant one no longer makes it arbitrary. As an example, if $g=\text{id}_A$, then $g$ is not constant, but still satisfies the conditions and $f\circ g=f$.

My question boils down to: why can we discount all non-constant functions $g$?

Community
  • 1
Marco
  • 357

3 Answers3

4

The question you have posted states: Suppose for all $g$(which is also a function on $A$), composition of functions $f$ and $g$ is $f$, then $f$ is a constant function.

The relationship doesn't hold for just one arbitrarily chosen $g$. It holds for all $g$. One of those $g$ is a constant function.

muaddib
  • 8,267
4

Here's a simpler statement along the same lines:

What real $y$ satisfies that, for all other real numbers $x$, we have $yx=y$?

We could look at any $x$ we wanted to, but it just happens to be convenient to notice that $x=0$ causes us to conclude $0=y$. This suffices to show us "if such a $y$ exists, it is $0$". Then, all that's left to do is to check whether $y=0$ actually has the desired property for all other $x$.

You're in a similar situation: You've proven, by looking at only constant functions, that if such an $f$ exists, it is constant. Then, your only remaining task is to show all constant $f$ satisfy the given property. So, we're not discounting the other cases - we should still check them, but that's easy after we've leveraged the case of constant $g$ to show that $f$ must be constant.

Milo Brandt
  • 60,888
  • So you're saying that instead of: Let $g:A\longrightarrow A$ and $f\circ g=f$, it should be $\forall_{g:A\longrightarrow A} f\circ g = f$? It seems like I separated the hypothesis incorrectly. That makes a lot more sense. – Marco Jul 26 '15 at 17:58
  • @Marco Yeah - that's exactly it. (If it were the former, you would be quite right) – Milo Brandt Jul 26 '15 at 18:10
  • Thanks, your algebraic explanation filled in the missing gap. – Marco Jul 26 '15 at 18:12
1

This took me a while to figure it out. I'm able to understand this much better when the proof is written like this:

We know that $\forall g. (f \circ g) = f$. From universal instantiation, we get $f \circ h = f$ where $h$ is some constant function on $A$. So, for arbitrary $a \in A$, $h(a) = b$ for some $b \in A$. Now, $f(a) = f(h(a)) = f(b)$. Since $a$ is an arbitrary element and $b$ is some element in $A$, from $f(a) = f(b)$, we can conclude that $f$ is an constant function.

Sibi
  • 1,207