Results 1 to 2 of 2

Math Help - [SOLVED] Proof Help with Naturals

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    [SOLVED] Proof Help with Naturals

    Suppose
    A is a non-empty subset of N with an upper bound. In other words, suppose there is a b eN such that

    every
    y eA satis es y <= b. Then A has a maximum.

    How would I prove this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Natural numbers subset

    Hello jzellt
    Quote Originally Posted by jzellt View Post
    Suppose
    A is a non-empty subset of N with an upper bound. In other words, suppose there is a b eN such that

    every
    y eA satis es y <= b. Then A has a maximum.

    How would I prove this?
    We can do this with a combination of proof by induction and reductio ad absurdum.

    Assumption: Assume that A has no maximum. Then \forall x \in A, x+1 \in A.

    We now show by induction that y \in A \Rightarrow (y + n) \in A, \forall n \ge 1.

    So, define the propositional function P(n) as y \in A \Rightarrow (y + n) \in A. Then P(n) \wedge (x \in A \Rightarrow x+1 \in A) \Rightarrow (y + n + 1) \in A

    So P(n) \Rightarrow P(n+1).

    P(1) is true. So by induction P(n) is true \forall n \ge 1.

    In particular if n = b + 1, where b is an upper bound of A, y \in A \Rightarrow y + b +1 \in A. But y + b +1 > b, \forall y \in \mathbb{N}. Contradiction.

    So our original assumption is false, and A therefore has a maximum.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. naturals as a subset of the reals
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: January 25th 2011, 08:44 AM
  2. Countability of N x N (Naturals x Naturals)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2010, 06:26 PM
  3. 10 naturals numbers.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 8th 2009, 02:06 PM
  4. Find all naturAls numbers. X , Y..
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 4th 2009, 08:49 AM
  5. Constructing Z from N (integers from naturals)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 3rd 2007, 03:59 AM

Search Tags


/mathhelpforum @mathhelpforum