Results 1 to 2 of 2

Math Help - Proof by Smallest counter example and set proof

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    37

    Proof by Smallest counter example and set proof

    I have a question on how to finish a proof by counter example and how to even start a set proof(I am horrable at them).

    3. n < 2^n for every natural number n
    Pf: Assume that this statement is false, i.e.
    there exists a natural number x such that x ≥ 2^x .
    Let X = {natural number n : n ≥ 2^n }
    = > X ≠ the empty set
    => This set X has the smallest x in X such that x is greater than or equal to 2^x . Note that x is not 0 because 0 is not greater than or equal to 2^0 = 1.
    => 0 ≤ x-1 < x
    => x-1 is not in X
    => x -1 is less than 2^(x-1)
    This is where I get stuck.

    For the next problem we need to prove the following but I'm not even sure how to start.
    4. If |A Union B| = |A| + |B| then A intersect B = the empty set

    Pf:
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by algebrapro18 View Post
    I have a question on how to finish a proof by counter example and how to even start a set proof(I am horrable at them).

    3. n < 2^n for every natural number n
    Pf: Assume that this statement is false, i.e.
    there exists a natural number x such that x ≥ 2^x .
    Let X = {natural number n : n ≥ 2^n }
    = > X ≠ the empty set
    => This set X has the smallest x in X such that x is greater than or equal to 2^x . Note that x is not 0 because 0 is not greater than or equal to 2^0 = 1.
    => 0 ≤ x-1 < x
    => x-1 is not in X
    => x -1 is less than 2^(x-1)
    But x-1 \ge 2^x-1 > 2^{x-1}, so you have a contradiction so no smallest counter example exists, and so no counter example exists.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Smallest Element proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 16th 2012, 02:06 AM
  2. Replies: 13
    Last Post: May 12th 2011, 05:32 AM
  3. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  4. Replies: 2
    Last Post: March 26th 2009, 07:58 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum