My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

**RemiAure** · January 30th 2013, 08:27 AM

This is a thread for any major difficulties I come across in How to Prove It: A Structured Approach, 2nd edition by Daniel J. Velleman. This has a counterpart thread at Physics Forums, but it's been a day since I started it with no help yet.

The Problem

Exercise 1-(c), page 81. Analyze the logical forms of the following statements. You may use the symbols $\in$ , $\notin$ , $=$ , $\neq$ , $\wedge$ , $\vee$ , $\rightarrow$ , $\leftrightarrow$ , $\forall$ , and $\exists$ in your answers, but not $\subseteq$ , $\nsubseteq$ , $\mathcal{P}$ , $\cup$ , $\cap$ , \, $\{$ , $\}$ , or $\neg$ . (Thus, you must write out the definitions of some set theory notation, and you must use equivalences to get rid of any occurrences of $\neg$ .)

Statement (c) is $\{n^2 + n + 1\ |\ n \in \mathbb{N}\} \subseteq \{2n + 1\ |\ n \in \mathbb{N}\}$ .

My Solution Attempt

The following answer seems correct to me, based on what I think I know from all the discussion in the text coming before this point. However, his answer in the appendix seems to be derived from facts that either were too subtle for me in the text or were not introduced. My answer ends on the fourth line, before the ellipses. Velleman's answer is on the last line after the ellipses. What I would like to know are the additional standard definitions or logical equivalences needed to arrive at his answer, even if I have to back up or start over.

$\{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 . . .$

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

**Kmath** · January 30th 2013, 09:55 AM

I do now know why you complicated it like the third line. Where is the problem if it is like this

Your statement $\equiv \forall x\in\{n^2+n+1\}\to x\in\{2n+1\}$
$\equiv \forall n\in\mathbb{N}\& x=n^2+n+1\to \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)$ ?

**RemiAure** · January 30th 2013, 11:10 AM

The reason I might've overcomplicated it is because a major part of the section leading up to this problem discusses indexed families, where he says, "In general, any indexed family $A = \{x_i\ |\ i \in I\}$ can also be defined as $A = \{x\ |\ \exists i \in I(x = x_i)\}$ . It follows that the statement $x \in \{x_i\ |\ i \in I\}$ means the same thing as $\exists i \in I(x = x_i)$ ." It's possible that I would've arrived at his answer if I fully grasped one of the three examples that came immediately after these statements, the third example of these three in particular, but in the second example of these three he indicates that "the easier equivalent way" of writing out the definitions logically, which he writes out and doesn't really explain, "would require the methods we will be studying in Chapter 3 [to show how they're equivalent]."

The third example of this set of examples goes like this:

3. $\{n^2\ |\ n \in \mathbb{N}\}$ and $\{n^3\ |\ n \in \mathbb{N}\}$ are not disjoint.

We must say that the two sets have a common element, so one solution is to start by writing $\exists x(x \in \{n^2\ |\ n \in \mathbb{N}\} \wedge x \in \{n^3\ |\ n \in \mathbb{N}\})$ . However, in the last statement, there is an easier way [my emphasis, where my mind would shut down because of what he said in the previous example indicating that the easier way involves an understanding given in the next chapter]. An element common to the two sets would have to be the square of some natural number and also the cube of some (possibly different) natural number. Thus, we could say that there is such a common element by saying $\exists n \in \mathbb{N} \exists m \in \mathbb{N} (n^2 = m^3)$ . [. . .]

Now you are probably right, but I am unfamiliar with the ampersand symbol $\&$ . What does it mean exactly?

**Kmath** · January 30th 2013, 11:36 AM

it is just "and=&"

**RemiAure** · January 30th 2013, 11:59 AM

Kmath, would you be able to help me translate it? I am unable to translate the statement in a way that I know to be grammatically correct. Also, could you tell me a general rule that you use, something like

$\forall n \in \mathbb{N} \& x = P(n) \rightarrow \exists m \in \mathbb{N} \& x = Q(m)$

$\equiv \forall n \in \mathbb{N} \exists m \in \mathbb{N} (P(n) = Q(m))$ ,

but that would help me understand the rule?

**Kmath** · January 30th 2013, 12:29 PM

I did not quite understand your last post, If you mean the meaning of the symbol "&" I said it means "and".

for the second part: is the following not enough?
"if x=a and x=b then a=b"
"for all x=b there is x=c is the same as for all there is b and a=b"

**emakarov** · January 30th 2013, 12:50 PM

Originally Posted by Kmath

I do now know why you complicated it like the third line. Where is the problem if it is like this

Your statement $\equiv \forall x\in\{n^2+n+1\}\to x\in\{2n+1\}$
$\equiv \forall n\in\mathbb{N}\& x=n^2+n+1\to \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)$ ?

Sorry, this is a misleading answer. First, & is not among the allowed symbols in post #1. Even if & is a synonym for ∧, $\forall n\in\mathbb{N}\land x=n^2+n+1$ is not a well-formed formula (part). Perhaps you mean $\forall n\in\mathbb{N}\,\forall x\,x=n^2+n+1$ or $\forall n\,n\in\mathbb{N}\land x=n^2+n+1$ . A similar remark can be made about the second half of the formula with ∃. Overall, it is hard to say what you mean. Also, {n² + n + 1} is a singleton; it is very different from {n² + n + 1 | n ∈ ℕ}.

**Kmath** · January 30th 2013, 01:16 PM

Originally Posted by emakarov

Sorry, this is a misleading answer. First, & is not among the allowed symbols in post #1. Even if & is a synonym for ∧, $\forall n\in\mathbb{N}\land x=n^2+n+1$ is not a well-formed formula (part). Perhaps you mean $\forall n\in\mathbb{N}\,\forall x\,x=n^2+n+1$ or $\forall n\,n\in\mathbb{N}\land x=n^2+n+1$ . A similar remark can be made about the second half of the formula with ∃. Overall, it is hard to say what you mean. Also, {n² + n + 1} is a singleton; it is very different from {n² + n + 1 | n ∈ ℕ}.

yes you are completely right. I just use contractions and I think my idea is reached.

**RemiAure** · January 30th 2013, 01:34 PM

It also seemed to me not to be a wff, but I wasn't sure. Kmath, I meant that I couldn't myself translate the logical statement in your first post into a grammatically correct one.

I looked over the second example in the text that I alluded to earlier, probably for the 20th time, and then just took it all for granted. The following is that example, and then after that is my new solution patterned after this example, which I will have to reflect on a little more so that I feel that I understand it sufficiently.

The Example

2. Analyze the logical form of the statement $\{x_i\ |\ i \in I\} \subseteq A$ by writing out the definitions of the set theory notation used.

Solution. By the definition of subset we must say that every element of $\{x_i\ |\ i \in I\}$ is also an element of $A$ , so we could start by writing $\forall x(x \in \{x_i\ |\ i \in I\} \rightarrow x \in A)$ . Filling in the meaning of $x \in \{x_i\ |\ i \in I\}$ , which we worked out earlier, we would end up with $\forall x(\exists i \in I(x = x_i) \rightarrow x \in A)$ . But since the elements of $\{x_i\ |\ i \in I\}$ are just the $x_i$ 's, for all $i \in I$ , perhaps an easier way of saying that every element of $\{x_i\ |\ i \in I\}$ is an element of $A$ would be $\forall i \in I(x_i \in A)$ . The two answers we have given are equivalent, but showing this would require the methods we will be studying in Chapter 3.

My New Solution

If Example 2 says, in regard to a certain set being a subset of another set, that "every element of $\{x_i\ |\ i \in I\}$ is an element of $A$ would be [to say] $\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)$ .

Thread: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

LinkBack

Thread Tools

Display

My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Re: My difficulties in the text _How to Prove It: A Structured Approach, 2 ed_

Similar Math Help Forum Discussions

Having some difficulties

Which approach is nicer? UK MEI approach? American approach?

Differentiation structured questions

Any approach other than axiomatic approach to Real Numbers

2 problems I am having difficulties with

Search Tags