0

I do not know if this is the right place to ask but Googling failed.

Whenever I do a "prove something" question, I try to formally restate in an if-then form.

But when a statement can't be naturally restated to an if-then form, by process of elimination of the proof methods(by exhaustion, construction, generalization, counter-example, induction, contraposition, contradiction) I have read on a book, I usually end up at the method: "Proof by contradiction".

For an if-then statement, I can assume the premise is true and start from there to prove the conclusion is true.

For statements without if-then form like

"Prove the set of prime numbers is infinite ".

I have no idea where to start from(all I know is I must use proof by contradiction). It baffles me to see the solution and makes me wonder "How did he arrive at the solution from an unorthodox way"?

Is there a logical thought process to proving such statements without an if-else form? OR do we just have to brute-force? OR does it simply boils down to lack of practice on my part(I'm a newbie)?

Leon
  • 413
  • Just assume the opposite of the statement, and see where that leads you? So with the infinite primes, you would assume the opposite (there are finite primes) and this may lead you down the path of listing them, and then multiplying them. Or similarly with root 2 being irrational, you start by assuming the opposite (that it is rational) and this may lead you to write it as a general fraction. Both of these cases lead to a more natural contradiction under some algebra. – Jamminermit May 29 '20 at 09:43
  • That's exactly the part I don't get. Why would have a reason to multiply the primes and such? I don't see a reason till I see the answer(sadly) and I go "What made him think that to do this?" – Leon May 29 '20 at 09:51
  • Isn't that naturally an if-then statement? If $X$ is the set of... Then $X$ is infinite. And that's exactly how you would start proving it, whether by contradiction or not. Of course it might take some practice inventing dummy variables like a set $X$, the same way it would take practice for someone new to algebra to phrase word problems in terms of variables. – Maxim Gilula May 29 '20 at 10:05
  • The proof is very understandable but when you begin learning proof-writing and construction for the first time it may seem as though these ideas come from nowhere. Eventually with practice you will develop an intuition for such problems. It may help to look at the methods to prove things similar to your questions. – atul ganju May 29 '20 at 10:10
  • @MaximGilula, maybe its just me. But it looks kind of forced. – Leon May 29 '20 at 11:11
  • Seems like the consensual answer boils down to practice – Leon May 29 '20 at 11:11
  • 1
    Also be mindful that many proofs are not created in a similar way to how you may solve a problem on a test. There is often lots more trial and error and days/weeks/years of thinking required. – Jamminermit May 29 '20 at 20:42

0 Answers0