# The idea's clear; the proof isn't

I'm working through Enderton's book on set theory. In chapter 3, there are a series of exercises regarding functions. For instance

• Prove that if $F$ and $G$ are functions, $dom(F) = dom(G)$, and $F(x) = G(x)$ for all $x$ in the common domain, then $F = G$.
• Assume that $F$ and $G$ are functions. Show that $F \subseteq G$ if and only if $dom(F) \subseteq dom(G)$ and $F(x) = G(x)$ for all $x \in dom(F)$.

If I think about the statements, I come up with the following "sketches:"

• Suppose $(x,F(x)) \in F$. Then $x \in dom(F)$. Since $dom(F) = dom(G)$, $x \in dom(G)$ and $(x,G(x)) \in G$. Since $G(x) = F(x)$ for all $x$ in the common domain, $(x,F(x)) \in G$. The other direction is similar.
• Assume $F$ and $G$ are functions. Then $F \subseteq G$ iff $(x,y) \in F$ implies $(x,y) \in G$. Hence, $x \in dom(F)$ implies $x \in dom(G)$ and $dom(F) \subseteq dom(G)$. Similarly, $(x,y) \in F$ implies $(x,y) \in G$ iff $F(x) = G(x)$ for all $x \in dom(F)$ since $F$ and $G$ are functions and $y$ is uniquely determined by $x$.

But these are not formal proofs. I am having trouble in these exercises with formalizing the idea that I want to express. Hence, the question (request) is for an example of a formalization, so that I can see the appropriate style and level of detail involved.

-
Dear danportin, These seem like formal proofs to me. Regards, – Matt E Apr 7 '11 at 4:59
Hi danportin, I too am working through Enderton's set theory. If you ever want to discuss the problems or contribute to this manual I'm working on, please don't hesitate to send me an email. – yunone Apr 7 '11 at 5:42
Yunone, I'm not sure I could contribute anything that you haven't, or anything better than what you could. But I've been working through all the exercises, so if I get "ahead," I'll shoot you an email. – danportin Apr 9 '11 at 1:16

1. To prove tht $F=G$, you need to prove that $F\subseteq G$ and $G\subseteq F$. So let $(x,y)\in F$ ($F$ is a function, so all its elements are ordered pairs). In particular, $x\in\mathrm{dom}(F)=\mathrm{dom}(G)$, so there exists $z$ such that $(x,z)\in G$. Note that $(x,y)\in F$ means $F(x)=y$, and $(x,z)\in G$ means $G(x)=z$. Thus, $y = F(x) = G(x) = z$, so $(x,z)=(x,y)\in G$. Thus, $F\subseteq G$. The converse follows by symmetry (or you can try to write it out yourself).
2. You have an "if and only if" statement, so you may want to do it in two parts. Start by proving the "if" statement: if $\mathrm{dom}(F)=\mathrm{dom}(G)$ and $F(x)=G(x)$ for all $x\in\mathrm{dom}(F)$, then $F\subseteq G$. The proof should be similar to the one above.
Once you're done with the "if", prove the "only if": If $F\subseteq G$, then $\mathrm{dom}(F)\subseteq \mathrm{dom}(G)$ and $F(x)=G(x)$ for all $x\in\mathrm{dom}(F)$.
How do you prove this? Well, $\mathrm{dom}(F) = \{x\mid \text{there exists }y\text{ such that }(x,y)\in F\}$; similarly for $\mathrm{dom}(G)$. So let $x\in\mathrm{dom}(F)$. Then there exists $y$ such that $(x,y)\in F$. Since $F\subseteq G$, then $(x,y)\in F$ implies $(x,y)\in G$. But $(x,y)\in G$ implies $x\in\mathrm{dom}(G)$, which is what we needed to prove. So $\mathrm{dom}(F)\subseteq \mathrm{dom}(G)$. Then you want to prove that for each $x\in\mathrm{dom}(F)$, $F(x)=G(x)$. So take $x\in\mathrm{dom}(F)$; this means there exists $y$ with $(x,y)\in F$; and since $\mathrm{dom}(F)\subseteq \mathrm{dom}(G)$, you have $x\in\mathrm{dom}(G)$ so there exists $z$ such that $(x,z)\in G$. Since $F\subseteq G$, then $(x,y),(x,z)\in G$. Since $G$ is a function, $y=z$. So $(x,y)\in G$, hence $y = G(x) = F(x)$.