-3

My question is already in the title.

Let us look at some example.

I would like to prove that a game $G(n,m,u)$ does not have a pure Nash equilibrium (PNE), for example. I did it like this: Suppose that the game $G(n,m,u)$ does admit at least one PNE. For some $n=n_0$, $m=m_0$ and $u=u_0$, I construct an example where the game $G(n_0,m_0,u_0)$ does not have a PNE. So, I construct a counterexample but is this a proof by contradiction?

Learning
  • 105
  • 6
  • 2
    Maybe, but does it really matter? – anomaly Jul 03 '15 at 17:20
  • 2
    @anomaly: I very much agree about the does it really matter part. A proof is a proof is a proof, and classification seems like a pointless exercise, unless we are looking at technical issues, such as whether one can avoid excluded middle. – André Nicolas Jul 03 '15 at 17:25
  • 1
    @AndréNicolas I think it does matter, as far as someone learning these different directions of proof is concerned. When you reach a certain level of comfort with proofs, no it doesn't matter. But when you are first learning these proof directions, it definitely matters in my opinion. – layman Jul 03 '15 at 17:29
  • 1
    If it does not matter, why we give them names then? Does it matter to say I will prove it by induction or I will prove it by contraposition? Suppose you are reviewing a paper and the authors wrote something like "We will prove Theorem 1 by induction ..." but then you found that the proof is a proof by contradiction, what will your comment be as a reviewer? @anomaly – Learning Jul 03 '15 at 18:10
  • @Learning I agree with you that it matters. But just remember when you are reading the other users' comments that they have a different perspective than you. From the level they are at, they have seen enough to believe that it doesn't actually matter. This is just a difference of opinion. But I agree with you that for someone in the beginning stages of learning proof writing, it definitely matters. So, I'm apologizing for their dismissal of your question. – layman Jul 03 '15 at 18:13
  • 1
    Thank you very much @user46944. There is no problem at all. I just write my opinion also. – Learning Jul 03 '15 at 18:15

2 Answers2

4

Usually, a proof by contradiction of the statement $p \implies q$ is when you assume that the opposite of the desired conclusion is true (i.e., assume the negation of $q$ is true), and follow a few logical implications until you reach a statement that somehow explicitly or implicitly contradicts an initial assumption from the statement $p$.

Meanwhile, a counterexample of the same statement $p \implies q$ is when you say, "Hold on! This statement can't be true, because here is an example where $p$ holds, but $q$ does not."

In proof by contradiction of the statement $p \implies q$, at the end of the day you actually are proving that $p$ implies $q$. But if you find a counterexample for the statement $p \implies q$, then you are actually disproving the claim $p \implies q$, so applying proof by contradiction to a statement does the opposite of applying proof by counterexample.

layman
  • 20,191
1

This is not a proof by contradiction, I suspect this is not a proof at all

you showed that $\forall (n_0,m_0,u_0), G(n_0,m_0,u_0) $ admits an example which has no PNE's. This is not the same as saying that $G(n_0,m_0,u_0)$ has no PNE's.

note This will be a direct proof if you knew that if for some example $G(n_0,m_0,u_0)$ has no PNE's then $G(n_0,m_0,u_0)$ has no PNE's

Conrado Costa
  • 6,071