Prove by Reductio Ad Absurdum (Contradiction)

[bubokribuck]

Q:
S is a subset of the natural numbers (the counting numbers) with the following property
n $\in$ S $\Rightarrow$ {1,...,n-1} $\subset$ S.
Prove, by Reductio Ad Absurdum, that S is equal to the set of all natural numbers.


First of all, I want to make sure I got all the meanings of the symbols right, so are the following correct?
- n $\in$ S means n is an element of the set S.
- {1,...,n-1} $\subset$ S means every element of {1,...,n-1} is also an element of S, but {1,...,1-n} ≠ S

So that means S must contain more elements than {1,...,n-1} does, right? (i.e. S can be {1,...,n-1,n} ??)

If the above statements are correct and I'm performing a proof by contradiction, how should I start the first sentence?

I know that if I want to prove "1/3 is rational", I'll start by assuming the statement is false, i.e. I'll assume that 1/3 is irrational.

But this question is too complicated, if I am to assume that "n $\in$ S $\Rightarrow$ {1,...,n-1} $\subset$ S" is false, how should I write it in words?

 

[ArcanaNoir]

Suppose S is not equal to the set of natural numbers.

 

[LCKurtz]

Q:
S is a subset of the natural numbers (the counting numbers) with the following property
n $\in$ S $\Rightarrow$ {1,...,n-1} $\subset$ S.
Prove, by Reductio Ad Absurdum, that S is equal to the set of all natural numbers.

Isn't S = {1,2,3,4} a counterexample?

 

[bubokribuck]

Suppose S is not equal to the set of natural numbers.

If S is not equal to the set of all natural numbers, can it be equal to the set of integers (positive and negative)? Or the assumption only means S is only a subset of all natural numbers, i.e. S={1,2,3,4,...100}, for example.

Isn't S = {1,2,3,4} a counterexample?

It is indeed. But how about S={-4,-3,-2,-1} ?? Is this a counterexample too?

 

[Mark44]

The natural numbers don't include the negative integers.

 

[LCKurtz]

If S is not equal to the set of all natural numbers, can it be equal to the set of integers (positive and negative)? Or the assumption only means S is only a subset of all natural numbers, i.e. S={1,2,3,4,...100}, for example.


It is indeed. But how about S={-4,-3,-2,-1} ?? Is this a counterexample too?

No. It doesn't satisfy that it is a subset of the natural numbers to begin with. And even if you were thinking of all integers, it still doesn't satisfy the hypothesis that n ε S implies the integers less than are all in S.

I don't know where you got this problem, but my guess is that you stated it incorrectly in your original post.

 

[bubokribuck]

No. It doesn't satisfy that it is a subset of the natural numbers to begin with. And even if you were thinking of all integers, it still doesn't satisfy the hypothesis that n ε S implies the integers less than are all in S.

I don't know where you got this problem, but my guess is that you stated it incorrectly in your original post.

I was given this question as homework.

I think I got what you say now. So I'll assume "S is not equal to the set of all natural numbers", i.e. it is not equal to the set {1,2,3,...,n}.

However, my question is that if S is not equal to the set of all natural numbers, then what will it be? How should I write it? Maybe S={1,2,3,...,n-1}?

 

[HallsofIvy]

You can't say "S= {1, 2, 3, ..., n-1}" without speciying what n is. You could, for example, say "S= {1, 2, 3, ..., n-1} where n is any positive integer."

In any case, the crucial point is that the statement in your original post, "If S is a subset of the natural numbers (the counting numbers) with the following property
n ∈ S ⇒ {1,...,n-1}, then S is equal to the set of all natural numbers" is NOT true.

What is true is that "if S is a subset of the natural numbers with the property that {1, ..., n-1}is a subset of S⇒ n∈ S then S is the set of all natural numbers". That is the "weak induction principal".

 

[bubokribuck]

You can't say "S= {1, 2, 3, ..., n-1}" without speciying what n is. You could, for example, say "S= {1, 2, 3, ..., n-1} where n is any positive integer."

Aren't the following two statements just the same? If we write them out as symbols:

In any case, the crucial point is that the statement in your original post, "If S is a subset of the natural numbers (the counting numbers) with the following property
n ∈ S ⇒ {1,...,n-1}, then S is equal to the set of all natural numbers" is NOT true.

If N = set of all natural numbers = {1,...,n}

S=N when S $\subseteq$ N with properties n ∈ S ⇒ {1,...,n-1} <<< And we assume this is not true.

What is true is that "if S is a subset of the natural numbers with the property that {1, ..., n-1}is a subset of S⇒ n∈ S then S is the set of all natural numbers". That is the "weak induction principal".

S=N when S $\subseteq$ N with properties {1,...,n-1} ⇒ n ∈ S <<< Isn't this just the same as the above one?


Or it differs if "⇒ n ∈ S" is placed differently? But I thought "⇒ n ∈ S" just means "that implies n is an element of S", so it should make no difference to either statement. Is this not what it is?

 

[LCKurtz]

Aren't the following two statements just the same? If we write them out as symbols:


If N = set of all natural numbers = {1,...,n}

That statement is nonsense.

S=N when S $\subseteq$ N with properties n ∈ S ⇒ {1,...,n-1} <<< And we assume this is not true.

I have no idea what that statement is supposed to mean.

S=N when S $\subseteq$ N with properties {1,...,n-1} ⇒ n ∈ S <<< Isn't this just the same as the above one?


Or it differs if "⇒ n ∈ S" is placed differently? But I thought "⇒ n ∈ S" just means "that implies n is an element of S", so it should make no difference to either statement. Is this not what it is?

It is very difficult to discuss this with you when we can't figure out what you mean. It would help if you would first write what problem you are trying to solve in the form:

If (the hypotheses here) then (the conclusion here).

Then if you are using an indirect argument would start: Suppose the theorem is false. Then (what would be true here).

I pointed out in my first post that the proposition you were trying to prove is false. There is nothing to discuss until you first state a correct proposition . Start with that.

 

[HallsofIvy]

Aren't the following two statements just the same? If we write them out as symbols:




If N = set of all natural numbers = {1,...,n}

S=N when S $\subseteq$ N with properties n ∈ S ⇒ {1,...,n-1} <<< And we assume this is not true.




S=N when S $\subseteq$ N with properties {1,...,n-1} ⇒ n ∈ S <<< Isn't this just the same as the above one?


Or it differs if "⇒ n ∈ S" is placed differently? But I thought "⇒ n ∈ S" just means "that implies n is an element of S", so it should make no difference to either statement. Is this not what it is?

No, they are not the same. One says "if A then B" and the other says "if B then A".