1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by Reductio Ad Absurdum (Contradiction)

  1. Nov 2, 2011 #1
    Q:
    S is a subset of the natural numbers (the counting numbers) with the following property
    n [itex]\in[/itex] S [itex]\Rightarrow[/itex] {1,...,n-1} [itex]\subset[/itex] 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 [itex]\in[/itex] S means n is an element of the set S.
    - {1,...,n-1} [itex]\subset[/itex] 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 [itex]\in[/itex] S [itex]\Rightarrow[/itex] {1,...,n-1} [itex]\subset[/itex] S" is false, how should I write it in words?
     
    Last edited: Nov 2, 2011
  2. jcsd
  3. Nov 2, 2011 #2
    Suppose S is not equal to the set of natural numbers.
     
  4. Nov 2, 2011 #3

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Isn't S = {1,2,3,4} a counterexample?
     
  5. Nov 2, 2011 #4
    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?
     
  6. Nov 2, 2011 #5

    Mark44

    Staff: Mentor

    The natural numbers don't include the negative integers.
     
  7. Nov 2, 2011 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  8. Nov 3, 2011 #7
    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}?
     
  9. Nov 3, 2011 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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".
     
  10. Nov 10, 2011 #9

    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 [itex]\subseteq[/itex] N with properties n ∈ S ⇒ {1,...,n-1} <<< And we assume this is not true.


    S=N when S [itex]\subseteq[/itex] 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?
     
  11. Nov 10, 2011 #10

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That statement is nonsense.
    I have no idea what that statement is supposed to mean.
    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.
     
  12. Nov 10, 2011 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, they are not the same. One says "if A then B" and the other says "if B then A".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove by Reductio Ad Absurdum (Contradiction)
  1. Reductio ad Absurdium! (Replies: 2)

  2. Proof by contradiction (Replies: 4)

  3. Proof by contradiction (Replies: 5)

Loading...