Results 1 to 2 of 2

Thread: 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
    Thanks
    1

    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, $\displaystyle B = \oslash$ is such a set (*see the Note below), so we must assume that $\displaystyle B \ne \oslash$.

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

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

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

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

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

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

    Grandad

    *Note: the proposition $\displaystyle (p \Rightarrow q)$ is true whenever $\displaystyle p$ is false. So if $\displaystyle B = \oslash$, the proposition $\displaystyle (n \in B \Rightarrow (n-1) \in B)$ is true, because $\displaystyle n \in B$ is always false. It seems a bit crazy at first sight, but it is OK!
    Last edited by Grandad; Mar 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: Nov 14th 2011, 04:58 PM
  2. Counting Numbers
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Sep 6th 2011, 05:51 PM
  3. Another counting numbers proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 10th 2009, 11:21 PM
  4. Counting numbers proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 24th 2009, 05:16 AM
  5. counting numbers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Sep 16th 2006, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum