Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Dear danportin, These seem like formal proofs to me. Regards, –  Matt E Apr 7 '11 at 4:59
1  
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 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
Thank you, Arturo. These are very clear, and are precisely the kind of examples I was looking for. –  danportin Apr 9 '11 at 1:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.