# Is there such a proof?

• Feb 6th 2006, 06:23 PM
ThePerfectHacker
Is there such a proof?
Let us assume that we wish to prove something with a conjecture. We do not know whether it is true or false. But we assume that it is true and we arrive at our proof. After that we assume that it is false and we still arrive at the same conclusion. Thus we conclude that the thing we were proving must be true.
Here is the justification of the proof.
$p=\mbox{ the conjecture }$
$q=\mbox{ some theorem }$.
Thus, by the above paragraph:
$p\to q$ (1)
$\neg p \to q$ (2).
Apply contrapositive to (1):
$\neg q \to \neg p$ (3)
Apply syllogism (chain rule) between (2) and (3):
$\neg q\to q$.
Assume $q$ is false thus,
$\neg q\to q$ is false thus contradiction.
Thus, $q$ is true.
Q.E.D.

But my question remains can you possibly think of something which you can prove like this? If you can this would be one elegant and amazing proof.
• Feb 7th 2006, 04:39 AM
topsquark
It would seem to me that if both $p \rightarrow q$ and $\neg p \rightarrow q$ that p has nothing to do with q.

-Dan
• Feb 7th 2006, 05:41 AM
CaptainBlack
Quote:

Originally Posted by topsquark
It would seem to me that if both $p \rightarrow q$ and $\neg p \rightarrow q$ that p has nothing to do with q.

-Dan

Not sure that is the case, for suppose (informal language being employed
so dont expect rigor) $p$ is "true" and $p \rightarrow q$, I think we don't have a problem
with this, we accept $q$.

Now if we accept the law of the excluded middle, $\neg p$ is "false", but a false proposition
implies every proposition so $\neg p \rightarrow q$, but we still accept $q$?

If $\neg p$ is "true" we just interchance $p$ and $\neg p$ throughout.

RonL
• Feb 7th 2006, 12:12 PM
albi
Some talk
I think that this reasoning is correct. However it could be surprising.

How we can conclude from p that q is true if we doesn't know either p is true or not???

It appears that we can. We have to realise that when we are prooving some theorem we use some axioms which are true for sure.

When p implies q and ~p implies q it means that:
1. The logic value of q is independent of the q logic value
2. The q is conclusion from axioms we used during proof process.

It shows us that there is no absolute truth in mathematical logic. Everyting depends on the axioms we assumed to be true (just as the value of the q).

Let $a_1, a_2, a_3, ..., a_n$ denote axioms we assume to be true. Let $p$ be a conjecture and $q$ be our theorem. When we are prooving that p implies q (or ~p implies q) we are silently assuming that axioms are true. So we will have:

$((a_1 \land a_2 \land \ldots \land a_n \land p) \Rightarrow q) \land ((a_1 \land a_2 \land \ldots \land a_n \land \neg p) \Rightarrow q)$

Let $r = a_1 \land a_2 \land \ldots \land a_n$.

We will get:
$((r \land p) \Rightarrow q) \land ((r \land \neg p) \Rightarrow q)$

Which means:
$( \neg(r \land p) \lor q) \land ( \neg(r \land \neg p) \lor q) \Leftrightarrow$

$\Leftrightarrow (\neg r \lor \neg p \lor q) \land (\neg r \lor p \lor q) \Leftrightarrow$

$\Leftrightarrow (\neg r \lor q) \lor (p \land \neg p) \Leftrightarrow (\neg r \lor q) \Leftrightarrow (r \Rightarrow q)$

Which means that q is really conclusion from axioms.

Pretty long, huh. Ok, now back to work :(
• Feb 7th 2006, 12:26 PM
CaptainBlack
Quote:

Originally Posted by albi
I think that this reasoning is correct. However it could be surprising.

How we can conclude from p that q is true if we doesn't know either p is true or not???

It appears that we can. We have to realise that when we are prooving some theorem we use some axioms which are true for sure.

RonL
• Feb 7th 2006, 02:14 PM
ThePerfectHacker
What about my original question? Can you think of some theorem which you can prove with this method?
• Feb 7th 2006, 04:38 PM
albi
Quote:

Originally Posted by CaptainBlack

I'm quite sure about that. The only way of showing that q is conclusion from p is to construct a proof based on some axioms. No matter if p is true or not if we show that p implies q (assuming p true) and than that ~p implies q (assuming the other possibility) there is no other way than to conclude that q is true (cause there is no more logical value p can have, "tertium non datur"). Proving the implications we use axioms so q is conclusion from axioms indeed.

To PerfectHacker: I haven't ever seen proof like this. I will try to think out if I have some time.

Sorry for 'prooving' in the previous post. My English isn't very good.

Goodnight
• Feb 7th 2006, 08:30 PM
CaptainBlack
Quote:

Originally Posted by albi
I'm quite sure about that. The only way of showing that q is conclusion from p is to construct a proof based on some axioms. No matter if p is true or not if we show that p implies q (assuming p true) and than that ~p implies q (assuming the other possibility) there is no other way than to conclude that q is true (cause there is no more logical value p can have, "tertium non datur"). Proving the implications we use axioms so q is conclusion from axioms indeed.

To PerfectHacker: I haven't ever seen proof like this. I will try to think out if I have some time.

Sorry for 'prooving' in the previous post. My English isn't very good.

Goodnight

Sorry, but you missed my point. My comment was on the last sentence of
you previous post:

Quote:

It appears that we can. We have to realise that when we are prooving some theorem we use some axioms which are true for sure.
I should have been more explicit. Are you sure that the axioms are true?

The point is truth is a slippery concept, most of the time we are satisfied
with asking if the axioms and the rules of proof are consistent.

But even then we usually only arrive at relative consistency. Which means
something like: System A is consistent if System B is consistent. System
B often being the system of Russel and Whitehead's Principia Mathematica.

But we have no proof of the consistency of PM.

RonL
• Feb 7th 2006, 08:32 PM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
What about my original question? Can you think of some theorem which you can prove with this method?

I have a vague recolection of having seen a proof using this technique,
but I cant recall what it was of (its over 30 years ago :eek: ).

RonL
• Feb 8th 2006, 04:12 AM
albi
CaptainBlack:
Yes, I do agree with you that 'truth' is slippery concept. My point is that (just as I have written) there is no absolute truth. If we imagine the class of all propositions (I don't know if I have used the propper word) we can see some relations between them, but none of them will be true unless we assume some of them are true (it is that relativeness you are talking about).

If I'm wrong, please correct me. I have never read Kurt Godel's works or even a good mathematical logic book.