Results 1 to 9 of 9
Like Tree3Thanks
  • 1 Post By Kmath
  • 1 Post By Kmath
  • 1 Post By emakarov

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

  1. #1
    Newbie RemiAure's Avatar
    Joined
    Jan 2013
    From
    United States
    Posts
    4

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

    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).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2012
    From
    France
    Posts
    45
    Thanks
    13

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

    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) ?
    Thanks from RemiAure
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie RemiAure's Avatar
    Joined
    Jan 2013
    From
    United States
    Posts
    4

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

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2012
    From
    France
    Posts
    45
    Thanks
    13

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

    it is just "and=&"
    Thanks from RemiAure
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie RemiAure's Avatar
    Joined
    Jan 2013
    From
    United States
    Posts
    4

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

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2012
    From
    France
    Posts
    45
    Thanks
    13

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

    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"
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,551
    Thanks
    783

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

    Quote Originally Posted by Kmath View Post
    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 ∈ ℕ}.
    Thanks from RemiAure
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2012
    From
    France
    Posts
    45
    Thanks
    13

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

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie RemiAure's Avatar
    Joined
    Jan 2013
    From
    United States
    Posts
    4

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

    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).
    Last edited by RemiAure; January 30th 2013 at 03:02 PM. Reason: Changed n to m in line 1 of equivalences
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Having some difficulties
    Posted in the Algebra Forum
    Replies: 0
    Last Post: August 14th 2012, 11:00 PM
  2. Replies: 2
    Last Post: December 18th 2011, 05:13 PM
  3. Differentiation structured questions
    Posted in the Calculus Forum
    Replies: 5
    Last Post: December 15th 2010, 05:11 AM
  4. Any approach other than axiomatic approach to Real Numbers
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 11th 2010, 12:21 PM
  5. 2 problems I am having difficulties with
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 15th 2008, 05:19 PM

Search Tags


/mathhelpforum @mathhelpforum