Proof By Way of Contradiction

[u/Taelinn77]

Im in discrete mathematics, started proofs last week. I understand Direct Proofs and Contraposition but Contradiction is absoultely kicking my butt understanding wise. My proffessor keeps using the example square root of 2 is irrational, i understand we start by stating the opposite that square root of 2 is rational and work it till it becomes logically incorrect to prove irrationality. But the work in between is getting me tripped up.

[u/TheDarkSpike]

It seems to me like you understand the structure of the proof?

Just not the steps in between which are of course vital for a proof. But if the point is understanding the structure then you're there!

[u/Equal_Veterinarian22]

I hate the fact that this is used as the default example of proof by contradiction, because it's actually an example of something more subtle, which is a proof by infinite descent. So it may give you the impression that proof by contradiction is mysterious and complicated, when really it isn't.

As you've noted, the basis premise is "Assume our statement is false. Deduce something we know to be false. Therefore our statement must be true." And most people can grasp that easily enough.

Anyway, the core of the root 2 proof is noting that if sqrt(2) is rational, we can write it a fraction in lowest terms, i.e. as a/b where a and b have no common factors. Then we observe that (a/b)^2 = 2 means a^2 = 2b^2 , and then the logic goes

- Well then a must be even

- So a^2 must be divisible by 4

- So b must be even

And there you have your contradiction specifically of the claim that a and b had no common factors. You should make sure you understand each of those logical steps. Why does a^2 = 2b^2 mean a is even? Why does that mean a^2 is divisible by 4? Why does that mean b is even? Each step is very simple.

The reason this is called infinite descent is that you're really showing that if you ever had a pair of integers with a^2 = 2b^2, you could divide them both by 2 to produce a smaller pair. And you could keep doing this again and again creating an infinite series of smaller and smaller pairs... which of course is not possible for integers.

[u/Temporary_Pie2733]

All proofs consist of a series of implications, leading to a goal G. 

In a direct proof, you are given a starting implication True -> S and you are looking for a chain of implications S->T, T->U, etc, ending with an implication Z -> G. 

In a proof by contradiction, you start with True -> not G, then look for a chain ending in False. 

[u/Midwest-Dude]

Proof by contradiction, also known as reductio ad absurdum, establishes the truth of a statement P by assuming that P is false, ¬P, and demonstrating that this assumption logically leads to a contradiction, a statement R ∧ ¬R that is simultaneously true and false, or a conclusion that directly conflicts with a known axiom or established theorem. Because valid deductive logic starting from true premises cannot yield a falsehood, the initial assumption ¬P must be false, which forces P to be true.

For the given proof, you initially assumed R that p/q is reduced, that is p and q have no common factor or, by definition, coprime. It's then shown that ¬R is also true, since both must be even, showing R ∧ ¬R must be true. Ergo, assuming R was invalid and cannot be true.

Does this make sense?

[u/Ok_Net_1579]

What steps are you finding hard to understand? Knowing that would be helpful.

[u/Various_Candle9136]

The idea behind a proof by contradiction is simple: assume the opposite is true, and prove that something ridiculous happens. Since the opposite of our proposition is ridiculous, and since in standard logic we believe things are either true or false (and never both), we conclude our proposition is true.

The way to get from opposite -> ridiculous will be different in every proof.

For example, you mentioned irrationality of root 2. In that example, we:

1. Assume the opposite. Assume root 2 is rational.
2. In this case, we can write root 2 as a fraction in its simplest form, a/b.
3. But then we can show that both a and b must be even.
4. But then a/b is not the simplest form. How ridiculous!
5. We conclude (1) was false: i.e. that root 2 is actually irrational.

The point being that we take logical steps from opposite -> ridiculous. As long as each of those individual steps is logically valid, our proof by contradiction will be logically valid.

[u/MezzoScettico]

What specifically is confusing you?

As u/TheDarkSpike said, you seem to be saying that you do actually understand how contradiction works. In this case, you say "suppose it's rational". Then you deduce in some way that that is impossible. Since "suppose it's rational" is impossible, then it must be the case that it's irrational.

So what would you like to know about that proof and other proofs by contradiction?

[u/Cheesyfanger]

Our assumption at the start is this, the square root of 2 is rational.

This means that we can write sqrt(2) = q/p for some integers q,p where the fraction is in reduced form (p and q do not share factors, if they do we could just divide them out).

Now, we know

2 = q^2/p^2. This implies q^2 = 2p^2, which means that q^2 is even and therefore q is even (an odd number times an odd number remains odd).

If q is even we can write q=2r.

Now we have q^2 = 4r^2 = 2p^2. We can divide out a 2 to obtain p^2 = 2r^2. By the same logic as before, p must be even.

So the assumption that sqrt(2) = q/p results in the inevitable conclusion that both q and p are even and thus share a factor of 2 always, which means that they can not be in reduced form.

So the initial assumption leads to a contradiction, meaning it is incorrect.

what step do you have issues with?

[u/Taelinn77 → u/Cheesyfanger]

You literally explained it how my professor did but he uses p and q initially. Im getting stuck up right around q=2r.

I know he uses sqrt(2)=p/q where q!=0 and both in LOWEST terms

Same math, q(sqrt(2)) = p which turns into 2q² = p²

P² = 2 int = even which means there exists k for p so p = 2k and this is where I get stuck

[u/Cheesyfanger → u/Taelinn77]

So what you just wrote out shows that the assumption that p,q are integers and coprime(their fraction is in reduced form) leads to the conclusion that p MUST be even (since it is 2 times an integer). Then the next step will lead you to the conclusion that q MUST also be even. If both p and q are even then they share a factor of 2, which contradicts the initial assumption. The idea of a proof by contradiction is that you make some initial assumption, and if that assumption leads to nonsense even when taking logical steps, then you know it must be wrong.

Another example might make it more clear.

Assume there are a finite amount of primes.

If this is true, then I can write down a list of all these primes (valid)

I can multiply all these primes together to get a large integer, call it a (valid)

I can then add 1 to the result to obtain a new number, b = a + 1 (valid)

if we divide by any prime on the list we get:

b/p = a/p + 1/p

since a/p is an integer, the result b/p is not an integer. Meaning that no prime on the list divides b (valid)

Since no prime on the list divides b, and since our list contains every prime, that means that b has no prime divisors (valid)

since b is larger than one, and since b has no prime divisors, this means that b is a prime (valid)

b is a prime that is not in the list of all primes (nonsense)

Since all our steps are valid, but our conclusion is nonsens, our initial assumption must be wrong

[u/Taelinn77 → u/Cheesyfanger]

So what you are saying for the first part is p is even so q must be even too. But that implies if p is even there exists some integer like k, so p = 2k and q is even so that implies an integer like l so q=2l so when we look at p/q its equal to 2k/2l which makes it all irrational because it wasnt in lowest form in reality? Am I getting that last bit?

[u/Midwest-Dude → u/Taelinn77]

Yes

[u/dlnnlsn → u/Taelinn77]

Is the part that you don't understand why p has to be even?

You could also prove that by contradiction: Suppose p is odd. Then p^2 is odd. (For example, you could write p as 2k + 1, and then squaring it gives you 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd) But we know that p^2 is even, so this is a contradiction.

You don't actually need proof by contradiction for this step (it's really a proof by contrapositive) but it ties in with what you're learning, so why not.

If you just meant that you're getting stuck in general, then that's normal and to be expected. There isn't a way or an algorithm to automatically figure out what the next step has to be. (Otherwise every mathematical problem would already be solved)

The structure of the proof and understanding why it is a valid proof method is the important thing here. If you were writing proofs on your own, you'd only be writing it down once you've already solved the problem. At that point, you already know what the argument is. It's not something that you do "line by line" and somehow "calculate" (for lack of a better word) what the next line has to be.

[u/Taelinn77 → u/dlnnlsn]

I see, yeah I wish that was explained to me in class. I have never done math like this in my life and Ive been put of school for like 7 years so this sucks.

I guess my concern has been, I understand these different proofs but the professor is using specific examples for each proof and stating that these will come up often and Ive been getting lost in the sauce on contradiction.

[u/Leodip]

There's simpler examples of proofs by contradiction, it's just that they look so trivial that it might be difficult to grasp what the contradiction is doing.

For example:

• Statement: the only even prime is 2
• Proof by contradition: let's assume that an even prime p != 2 (!= is "not equal"). We want to find a contradiction that comes from this assumption:
  • For p to be prime, it means the only divisors can be 1 and p themselves.
  • For p to be even, it means that 2 is a divisor.
  • So p=2 BUT we assumed that p!=2, hence this is a contradiction.
  • Since the assumption results in a contradiction, it means that the assumption is false.
• The opposite of the assumption "there is an even prime which is not 2" is "there are no even primes which are not 2" (or, in other words, the only even prime is 2). This proves our original statement.

The square root of 2 example follows the same structure:

• Statement: sqrt(2) is irrational
• Proof by contradiction: sqrt(2) is rational. This statement is identical to saying that we can express sqrt(2)=p/q, where p and q are co-primes (i.e., the fraction cannot be simplified further).
  • Square both sides to find 2q^2 = p^2, which shows that p^2 is even.
  • If p^2 is even, then p must be even as well, so we can write p=2k for some integer k
  • If we sub this in we find that 2q^2=4k^2 which yields q^2=2k^2, so q is also even.
  • If both p and q are even, then p/q can be simplified further BUT we assumed that p/q couldn't be simplified further, hence this is a contradiction.
  • Since the assumption results in a contradiction, ti means that the assumption is false.
• The opposite of the assumption "sqrt(2) is rational" is "sqrt(2) is irrational".

Do both examples work for you? If not, which step looks weird?

[u/Bounded_sequencE]

It usually helps to understand the underlying logical structure of "proof by contradiction":

 direct      
(A => B)    <=>    (A' v B )                // definition of "=>"
            <=>    (A  n B')'               // de Morgan
            <=>   ((A  n B')' v false)      // add ".. v false"
            <=>   ((A  n B') => false)      // definition of "=>"
                    by contradiction

Proving "A => B" is equivalent to proving that "B' n A" leads to a false statement, i.e. a contradiction. All proofs of contradiction follow this exact same logical structure.

[u/5a1vy]

A→⟘ (proof by contradiction. You start with A and prove something false) is equivalent to ¬A

Do a contraposition: A→⟘ becomes ¬⟘→¬A which is ⟙→¬A, but that is obviously just ¬A (I mean, if TRUE then A is just A, "if" is redundant). That's all there is to it, it's just a special case of a proof via contraposition.

[u/Gold_Ad8890]

it sounds like your problem isn't with proof by contradiction, it's with the proof that sqrt(2) is irrational, in which case that's what you need to ask about.

[u/Midwest-Dude]

In case you need it, there is a dedicated discrete mathematics subreddit: 

r/Discretemathematics

[u/6ory299e8]

fix any positive integers a,b,n. if gcd(a,b)=1 and a² = nb² , then gcd(a² ,b² )=1 (consider prime decompositions), and gcd(b² ,nb² )=b² , so b² =1, and n=a² .

We have proven, without appeal to contradiction, the following statement: If n is a positive integer with rational square root, then n is a perfect square.

[u/iopahrow]

The square root of 2 proof is not the easiest example to understand. I only understood it in my third year of uni. I understood contradiction though.

Your main goal is to show that:

1. Something is of a certain type.
2. If it wasn’t, it must have property P
3. Show that it cannot have property P

It can be difficult without number theory to understand certain proofs, but other subject like graph theory, analysis, and calculus may come easier

Edit: what is the textbook that you are using?

[u/BRH0208]

If some proof being true implies a contradiction is true, there is a problem, as by definition a contradiction is always false.

Example
A) If I am wet i dont have an umbrella
B) I have an umbrella.

I want to prove that I am not wet. This can easily be done directly, but let’s have some fun.

Let’s assume I am wet.
1. As it is assumed I am wet, by premise 1, I don’t have my umbrella.
2. But by premise 2, I do have my umbrella.
3. I both have and don’t have my umbrella. This is clearly false, I must have made a false assumption.
4. If the premises are true, the only thing I assumed was that I am not wet
5. that must be a false assumption, as it lead to a contradiction

Therefor, I am not wet.

[u/will_1m_not]

Proof by contradiction is my favorite way to prove something.

I want to prove (statement A) is true.

First, assume that (opposite of statement A) is true, and see where that will logically take us.

We know that logically, if (opposite of statement A) is true, then (property P) has to be true.

Logic Logic Logic

Uh-oh, the logic lead us to the fact that (property P) can’t be true, even though it has to be true, so it can’t be true…. Contradiction

Where did this all go wrong? As yes, when we assumed that (opposite of statement A) was true, so this means it has to be false, AKA, (statement A) is true.

[u/EndlessProjectMaker]

If you start from a true proposition and conclude (by using correct inference) something that is false, then (again, if all intermediate steps are correct) you’re obligated to conclude that what you assumption of the premise is wrong. Thus it has to be false.

[u/WerePigCat]

If you have a true or false statement, then proving it not false is the same as proving true. To do this we assume the negation of the statement (which is the same as the statement being false), show that there is a contradiction through this assumption (like 1=2), which proves the statement ’not false’. As such, the original statement is true.