This is a problem from Discrete Mathematics and its applications enter image description here

To this proof, I am trying to use proof by contradiction. Here is how the book described the process of proof by contradiction. enter image description here

I get the idea behind this. A contradiction is basically a compound proposition that no matter what combination the propositions within it take, the compound proposition will always evaluate to false. https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture03-filled.pdf (slide 5) Because the q in this case is false, and the implication we're using, ~p -> q, is true(assuming to be true, like direct proof? Might need clarification on this as well), ~p must be false, which means p is true. So in the end p is proved to be true

Here is my work so far for the problementer image description here

What I have so far is a truth table that shows r ^ ~r is a contradiction. I am trying to prove p which is (x*y is irrational. To do proof by contradiction, I know that I am going to have to use ~p, which is x * y is rational. I express ~p with the definition of rationality - exists integers p and q, q!=0, etc... My question is what do I use for r? Just any proposition? Or does it have to relate to the problem? I know that r ^ ~r is a contradiction.

  • $\begingroup$ To clarify, are you trying to prove that the given claim is true? Why did you decide to do this instead of trying to show it's false? $\endgroup$ – Santiago Canez Jan 11 '15 at 21:09
  • $\begingroup$ think its the method of proof by contradiction $\endgroup$ – committedandroider Jan 11 '15 at 21:25

This is implicitly a universal statement. To disprove a universal statement, all you have to do is provide a counterexample. So, all it takes to disprove this statement is to find two irrational numbers that their product is rational. Can you find such a counterexample?

  • $\begingroup$ oh is proof by contradiction the same as just proving its false with a counter example? $\endgroup$ – committedandroider Jan 11 '15 at 23:14
  • $\begingroup$ It's equivalent. Usually in proof by contradiction you assume the premise and derive a contradiction in abstract. Providing a counterexample does the same, but in concrete terms, and is usually quite simpler. $\endgroup$ – Alan Jan 11 '15 at 23:16
  • $\begingroup$ yeah counter example is a much more simpler/intuitive way to disprove this. I made this too complicated. $\endgroup$ – committedandroider Jan 11 '15 at 23:21
  • $\begingroup$ But Alan, I did more research on this and millersville.edu/~bikenaga/math-proof/counter/counter.html said "Finally, do not confuse giving a counterexample with proof by contradiction. A counterexample disproves a statement by giving a situation where the statement is false; in proof by contradiction, you prove a statement by assuming its negation and obtaining a contradiction." Bottom of the page $\endgroup$ – committedandroider Jan 11 '15 at 23:21
  • $\begingroup$ What he's saying is to not confuse "proving a statement" by contradiction and providing a counterexample, indeed these are not equivalent. What is equivalent is "disproving a statement by contradiction" and providing a counterexample, but "disproving a statement" is the same as "prove the opposite/negation of the statement". And remember that the negation of a universal is the same as the existance of a counterexample $\endgroup$ – Alan Jan 11 '15 at 23:24

While in conventional language, a contradiction is a statement of the form "X and not X", for mathematical purposes, any false statement is equal to a contradiction. In logic "summer is cold" equals "today is Tuesday and today is not Tuesday" since both equal "false".

You don't actually have to form a conclusion of the form $\lnot R \land R$, just concluding any false result is enough to show false premise.

This should be fairly intuitive. If you are grasping at definitions to understand the concept, then you are making things unnecessarily difficult. "A false conclusion can only come from false premises" is all you need to understand to use proof by contradiction.

  • $\begingroup$ so what would be the next step for proof by contradiction here then? What ~r ^ r would you use for this question? I would prefer a simpler way of making this proof. $\endgroup$ – committedandroider Jan 11 '15 at 22:04
  • $\begingroup$ @committedandroider "Proof by contradiction" is a strange way to go about this example...but if you insist...then the first step is to figure out if the statement is true or false (should be easy, consider $\sqrt{2}\cdot\sqrt{2}$. Then you write out the statement you are trying to prove. Then you say "for the sake of contradiction, assume (#@&(&", where (#@&(& is the opposite of what you are trying to prove. Edit your question to show your progress, and ping me here when you have. $\endgroup$ – DanielV Jan 11 '15 at 22:51
  • $\begingroup$ Yeah Daniel, you're right. A counter example is much simpler than what I was trying to do. $\endgroup$ – committedandroider Jan 11 '15 at 23:22
  • $\begingroup$ Daniel, can you take a look at my latest question? The one where you have to use proof by contradiction. $\endgroup$ – committedandroider Jan 12 '15 at 0:09
  • $\begingroup$ @committedandroider KittyL poster a good answer to your question. $\endgroup$ – DanielV Jan 12 '15 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.