Results 1 to 2 of 2

Math Help - Counting numbers/set proof

  1. #1
    Member
    Joined
    Oct 2008
    Posts
    124

    Counting numbers/set proof

    Prove by contradiction that there is no set B of counting numbers such that if n is an element of B, then (n-1) is an element of B.
    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

    Proof by induction and contradiction

    Hello noles2188
    Quote Originally Posted by noles2188 View Post
    Prove by contradiction that there is no set B of counting numbers such that if n is an element of B, then (n-1) is an element of B.
    In fact, B = \oslash is such a set (*see the Note below), so we must assume that B \ne \oslash.

    So, let us assume that \exists B \subseteq \mathbb{N}, (B \ne \oslash), and (n \in B) \Rightarrow (n-1) \in B. (In other words, let's assume the opposite of what we want to prove.)

    Then let P(n) be the propositional function: n \in B

    Then by hypothesis P(n) \Rightarrow P(n-1)

    Now B \ne \oslash \Rightarrow P(k) is true for some k \in B

    So, by induction P(n) is true \forall n \le k, n \in \mathbb{Z}

    \Rightarrow P(0) is true \Rightarrow 0 \in B. But 0 \notin \mathbb{N}. Contradiction. Therefore the original assumption is false.

    Grandad

    *Note: the proposition (p \Rightarrow q) is true whenever p is false. So if B = \oslash, the proposition (n \in B \Rightarrow (n-1) \in B) is true, because n \in B is always false. It seems a bit crazy at first sight, but it is OK!
    Last edited by Grandad; March 9th 2009 at 05:05 AM. Reason: Improved solution
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. counting numbers...
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: November 14th 2011, 04:58 PM
  2. Counting Numbers
    Posted in the Statistics Forum
    Replies: 3
    Last Post: September 6th 2011, 05:51 PM
  3. Another counting numbers proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 10th 2009, 11:21 PM
  4. Counting numbers proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 05:16 AM
  5. counting numbers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 16th 2006, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum