Is there such a proof?

**ThePerfectHacker** · February 6th 2006, 06:23 PM

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.

**topsquark** · February 7th 2006, 04:39 AM

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

**CaptainBlack** · February 7th 2006, 05:41 AM

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

**albi** · February 7th 2006, 12:12 PM

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

**CaptainBlack** · February 7th 2006, 12:26 PM

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.

Are you sure about that?

RonL

**ThePerfectHacker** · February 7th 2006, 02:14 PM

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

**albi** · February 7th 2006, 04:38 PM

Originally Posted by CaptainBlack

Are you sure about that?

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.

If you have found some mistake please tell me about it.

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

**CaptainBlack** · February 7th 2006, 08:30 PM

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.

If you have found some mistake please tell me about it.

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:

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

**CaptainBlack** · February 7th 2006, 08:32 PM

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

).

RonL

**albi** · February 8th 2006, 04:12 AM

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.

Thread: Is there such a proof?

LinkBack

Thread Tools

Display

Is there such a proof?

Some talk

Similar Math Help Forum Discussions

Proof theory: example of an existence proof of a proof?

Convert the following equational proof into a Hilbert Proof

[SOLVED] direct proof and proof by contradiction

Proof with algebra, and proof by induction (problems)

proof that the proof that .999_ = 1 is not a proof (version)

Search Tags