1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: My difficulties in the text, How to Prove It 2e by Velleman

  1. Jan 29, 2013 #1
    I'm creating this thread for any major difficulties I come across in How to Prove It: A Structured Approach, 2nd edition by Daniel J. Velleman. This is a self-study (with any assistance if I can get it).

    1. The problem statement, all variables and given/known data

    The problem is to analyze the logical form of the given statement, using only the symbols [itex]\in[/itex], [itex]\notin[/itex], [itex]=[/itex], [itex]≠[/itex], [itex]\wedge[/itex], [itex]\vee[/itex], [itex]\rightarrow[/itex], [itex]\leftrightarrow[/itex], [itex]\forall[/itex], and [itex]\exists[/itex] in our answer, but not [itex]\subseteq[/itex], is-not-[itex]\subseteq[/itex], [itex]\wp[/itex], [itex]\cup[/itex], [itex]\cap[/itex], \, [itex]\{[/itex], [itex]\}[/itex], or [itex]\neg[/itex]. (Thus, as the text goes on to say, we must write out the definitions of some set theory notation, and we must use equivalences to get rid of any occurrences of [itex]\neg[/itex].) This is Exercise 1-(c) on page 81.

    2. Relevant equations

    The statement is [itex]\{n^2 + n + 1\ |\ n \in \mathbb N\} \subseteq \{2n + 1\ |\ n \in \mathbb N\}[/itex].

    3. The attempt at a solution

    Although it seems correct to me, it's not exactly the solution given in the Appendix of solutions. His answer seems to be derived from facts that I can't find or discern from any of the previous discussion. What I ideally want is to see his solution derived in a way that I should've known from what's been explained in the text so far. If not that then one or two standard definitions or logical equivalences that might or might not have been introduced but nonetheless work to get me to the same result.

    My answer:

    [itex]\{n^2 + n + 1\ |\ n \in \mathbb N\} \subseteq \{2n + 1\ |\ n \in \mathbb N\}[/itex]​
    [itex]\equiv \forall x(x \in \{n^2 + n + 1\ |\ n \in \mathbb N\} \rightarrow x \in \{2n + 1\ |\ n \in \mathbb N\})[/itex]​
    [itex]\equiv \forall x(x \in \{y\ |\ \exists n \in \mathbb N (y = n^2 + n + 1)\} \rightarrow x \in \{y\ |\ \exists n \in \mathbb N (y = 2n + 1)\})[/itex]​
    [itex]\equiv \forall x(\exists n \in \mathbb N (x = n^2 + n + 1) \rightarrow \exists n \in \mathbb N (x = 2n + 1)).[/itex]​

    His answer:
    [itex]. . . \equiv \forall n \in \mathbb N \exists m \in \mathbb N (n^2 + n + 1 = 2m + 1).[/itex]​
    Last edited: Jan 29, 2013
  2. jcsd
  3. Jan 31, 2013 #2
    After a day, I made a parallel thread at mathhelpforum.com,


    I eventually found a solution while interacting with that thread, but since Physics Forums is broader in scope and since these epic study threads are the only kinds I plan to make over a long period, I'll keep the developments of the cross-site threads congruous.

    Critical or other feedback is always welcome.

    New Solution to Exercise 1-(c) page 81

    If one of the examples on page 74 says that the logical form of [itex]\{x_i\ |\ i \in I\} \subseteq A[/itex] can be analyzed as [itex]\forall i \in I(x_i \in A)[/itex], then the logical form of the statement [itex]\{n^2 + n + 1\ |\ n \in \mathbb{N}\} \subseteq \{2n + 1\ |\ n \in \mathbb{N}\}[/itex] can be analyzed as

    [itex]\equiv \forall n \in \mathbb{N} (n^2 + n + 1 \in \{2m + 1\ |\ m \in \mathbb{N}\})[/itex]

    [itex]\equiv \forall n \in \mathbb{N} (n^2 + n + 1 \in \{x\ |\ \exists m \in \mathbb{N} (x = 2m + 1)\})[/itex]

    [itex]\equiv \forall n \in \mathbb{N} (\exists m \in \mathbb{N} (n^2 + n + 1 = 2m + 1))[/itex]

    [itex]\equiv \forall n \in \mathbb{N} \exists m \in \mathbb{N} (n^2 + n + 1 = 2m + 1)[/itex].​
    Last edited: Jan 31, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook