7
$\begingroup$

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.

  • 0
    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.2011-04-09

1 Answers 1

7

You essentially have it. In fact, the first one is pretty much done (unless you want to go down to the nitty gritty of the formal definition of function as a set of ordered pairs). The second one is a bit more confused because you have "iffs" and "implies", which tends to make reading it more difficult. It might be best to separate the two implications you are trying to establish. So let me write those out. You'll see your first is essentially done, the second just needs a bit of clarification.

  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)$.

  • 0
    Thank you, Arturo. These are very clear, and are precisely the kind of examples I was looking for.2011-04-09