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

Originally Posted by algebrapro18

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 , so you have a contradiction so no smallest counter example exists, and so no counter example exists.