# My difficulties in the text, How to Prove It 2e by Velleman

1. Jan 29, 2013

### Remi Aure

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 $\in$, $\notin$, $=$, $≠$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$, and $\exists$ in our answer, but not $\subseteq$, is-not-$\subseteq$, $\wp$, $\cup$, $\cap$, \, $\{$, $\}$, or $\neg$. (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 $\neg$.) This is Exercise 1-(c) on page 81.

2. Relevant equations

The statement is $\{n^2 + n + 1\ |\ n \in \mathbb N\} \subseteq \{2n + 1\ |\ n \in \mathbb N\}$.

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.

$\{n^2 + n + 1\ |\ n \in \mathbb N\} \subseteq \{2n + 1\ |\ n \in \mathbb N\}$​
$\equiv \forall x(x \in \{n^2 + n + 1\ |\ n \in \mathbb N\} \rightarrow x \in \{2n + 1\ |\ n \in \mathbb N\})$​
$\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)\})$​
$\equiv \forall x(\exists n \in \mathbb N (x = n^2 + n + 1) \rightarrow \exists n \in \mathbb N (x = 2n + 1)).$​

$. . . \equiv \forall n \in \mathbb N \exists m \in \mathbb N (n^2 + n + 1 = 2m + 1).$​

Last edited: Jan 29, 2013
2. Jan 31, 2013

### Remi Aure

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 $\{x_i\ |\ i \in I\} \subseteq A$ can be analyzed as $\forall i \in I(x_i \in A)$, then the logical form of the statement $\{n^2 + n + 1\ |\ n \in \mathbb{N}\} \subseteq \{2n + 1\ |\ n \in \mathbb{N}\}$ can be analyzed as

$\equiv \forall n \in \mathbb{N} (n^2 + n + 1 \in \{2m + 1\ |\ m \in \mathbb{N}\})$

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

$\equiv \forall n \in \mathbb{N} (\exists m \in \mathbb{N} (n^2 + n + 1 = 2m + 1))$

$\equiv \forall n \in \mathbb{N} \exists m \in \mathbb{N} (n^2 + n + 1 = 2m + 1)$.​

Last edited: Jan 31, 2013