Prove that the functions $F$ and $G$ which have same domain and range are equal.

Question

The question is stated as: Consider any functions $F$ and $G$. Prove that, if

• $F$ and $G$ have the same domain $A$,
• For any $x$ in $A$, $F(x) = G(x)$,

Then $F=G$ (Hint: Show that $(x,y) \in F \Leftrightarrow (x,y) \in G$)

Here is my atempt:

First assume for some arbitrary $x$, that $(x,y) \in F$, as $F$ and $G$ have the same domain $A$, we have that some $(x,z) \in G$.

But we have that $(\forall x)(F(x) = G(x)$, thus $y=z$ and therefore $((x,y) \in F \Rightarrow (x,y) \in G)$, and as $x$ is arbitrary we have that $(\forall x)((x,y) \in F \Rightarrow (x,y) \in G)$, and following the same process the converse is true too thus.

$$(\forall x)[((x,y) \in F \Rightarrow (x,y) \in G) \land ((x,y) \in G \Rightarrow (x,y) \in F)]$$ $$(x,y) \in F \Leftrightarrow (x,y) \in G$$ $$F = G$$

I think im missing something, but when i read the two assumption from the question it seems obvious that they need to be the same function, but I need to get it right because this concept seems to be very useful when proving uniqueness and in other proves as well.

Answer 1

There is something wrong with the question, and also something wrong with your attempt. Firstly, in normal mathematics there is simply no reason to use any specific encoding of functions in the underlying foundational system. Hence we simply define that for any functions $F,G$ we have $F = G$ iff there is some set $A$ such that $F,G$ have domain $A$ and $F(x) = G(x)$ for every $x∈A$.

So in normal mathematics the question is meaningless. If you wish to work in a foundational theory instead, where a function on $A$ is defined a subset of $A×B$ for some set $B$, and treat equality of functions as equality of sets, then you still have to define what you mean by the function-application notation "$F(x)$". This is not a trivial matter, so the question still has a problem. Think about it a little. Do you want it to mean $\bigcup \{ y : ⟨x,y⟩∈F \}$? Or how about $\{ z : ⟨x,y⟩∈F ∧ z∈y \}$? Both work, but are different. And yet neither showed up in your question...

Another option is to treat only entire predicates involving "$F(x)$" as short-hand for a longer predicate given by a syntactic transformation. For instance, "$F(x) = G(x)$" is interpreted as "$∀z,w\ ( (x,z)∈F ∧ (x,w)∈G ⇒ z=w )$". This is one standard approach in a foundational treatment of functions, but then your attempt is incorrect. If you want to see this approach properly done, you would need to prove the following for any functions $F,G$:

$∀A\ ( \ ∃S\ ( \ F⊆A×S \ ) ∧ ∃T\ ( \ G⊆A×T \ )$
$\ ∧ ∀x{∈}A\ ∀z,w\ ( \ (x,z)∈F ∧ (x,w)∈G ⇒ z=w \ )$
$\ ⇒ F=G \ )$.

In this approach, this is the true symbolic expansion of:

$∀A\ ( \ dom(F) = dom(G) = A ∧ ∀x{∈}A\ ( \ F(x) = G(x) \ ) ⇒ F=G \ )$.