Discussion of 'Valid method of proof'.

[LAVRANOS]

The laws of logic used in this proof are:
1) M.Ponens ( P--->Q and P)====>Q (Where a single arrow means an implication and the double one a LOGICAL IMPLICATION)
2) Conjuction introduction P,Q =====> P and Q
3)Disjuction Elimination ( P---->S and Q---->S and P or Q)=====>S
4)The law
of Universal Elimination where if aproperty holds for a set it will hold for one of its members
5)The law of substitution
6)The law of conditional proof in some books is called the deduction theorem an it is considered some times as ametatheorem
The theorems the definition and the Trichotomy Law are well known to every one they are high school stuff

 

[LAVRANOS]

This type of proof leaves no room for imagining things in mathematics or arguing for ever and ever or a teacher in every level to pass wrong proofs to the students because he likes to.For people involved in hard core analysis where a lot of quantification is involved that machinery can solve most of your problems. Of course it takes a little pactise but it is worth while

 

[Crosson]

It is simply the case that (F=>T) is T, i.e. false implies true is true.

Hi Matt, I have a subtle disagreement on using the explanation (F=>T) is T involving the material conditional =>. The statement that theorem A can be deduced from premises S is written as S\vdash A, or in some other way than a material conditional. In other words, saying that A is a consequence of B is not the same as saying A implies B.

Here is the proof that with one false statement as premise one can derive any conclusion.

Mc = I'm posting from the moon. (This is false)
(x) ~Mx = No one can post from the moon. (A true fact)
B = anything you want!

1p. Mc
2p. (x) ~Mx
---------
2. Mc v B 1, (valid logical addition, if Mc is true then Mc v B is true)
3. ~Mc 2, (universal instantiation of a specific fact)
4. B 2,3 Disjunctive syllogism

 

[LAVRANOS]

And now i will quote couple of proofs from different books and if they are right or wrong how can we establish that
So
proof No 1
Let a' mean a to the square
IxI<y<===> IxI'<y' <===> x'-y'<0 <===> (x-y).(x+y)<0 <===> { x-y<0}
{x+y>0} or
{x-y>0}
{x+y<o}
If {x-y<0} {x<y}
{x+y>0} <===> {x>-y} <====> -y<x<y
If {x-y>0} {x>y}
{x+y<0} <====> {x<-y} not true



{x+y<0} <====>

 

[LAVRANOS]

I am sorry that did not come out all right let me try again

 

[LAVRANOS]

IxI<y <===> IxI'<y' <===> x'<y' <===> x'-y'<0 <====> [(x-y<0 and x+y>0) or(x-y>0 andx+y<0)]
If (x-y<0 and x+y>0) <===> -y<x<y
If (x-y>0 and x+y<0) <===> x>y and x<-y not true

NOTE AGAIN a' means a to the square. I wonder is that proof valid and if yes or no why
NOTE again this is the proof of IxI<y <====> -y<x<y

 

[Hurkyl]

Hi Matt, I have a subtle disagreement on using the explanation (F=>T) is T involving the material conditional =>. The statement that theorem A can be deduced from premises S is written as S\vdash A, or in some other way than a material conditional. In other words, saying that A is a consequence of B is not the same as saying A implies B.

Of course, the wonderful properties of first-order Boolean logic render all such distinctions essentially irrelevant.

 

[LAVRANOS]

T HE FOUNDER of the two values logic T,F is and will remain for ever THE GREAT ΑΡΙΣΤΟΤΕΛΗΣ. So the logic is Aristotelian Boolean is the algebra i mean Boolean algebra

 

[LAVRANOS]

Here is another proof from a book:
For x>=o we have:
(IxI<y and x>=0) <====> (x<y and x>=0) <====> 0<=x<y (1)
For x<0 we have:
(IxI<y and x<0) <=====> (-x<y and x<0) <====> (x>-y and x<0) <===> -y<x<0 (2)
Hence from (1) and (2) we have that IxI<y is true for those x for which -y<x<y .Hence the eqiuvelance IxI<y holds

 

[LAVRANOS]

Tomorrow i will write a professor's proof on question 3 and you decide whether is right or wrong

 

[LAVRANOS]

Here is another proof from a book:
For x>=o we have:
(IxI<y and x>=0) <====> (x<y and x>=0) <====> 0<=x<y (1)
For x<0 we have:
(IxI<y and x<0) <=====> (-x<y and x<0) <====> (x>-y and x<0) <===> -y<x<0 (2)
Hence from (1) and (2) we have that IxI<y is true for those x for which -y<x<y .Hence the eqiuvelance IxI<y holds

 

[LAVRANOS]

Perhaps before giving aprofessor's proof in question 3 i think i better give a step wise proof of atheorem that is closer to the axioms of the real Nos
So let us prove : For all xεR 0x=0
1) for all x, 1.x=x An axiom on real Nos2
2) 1.x=x from 1 and using Univ. Elim.
3) for all x,y,z (y+z).x= yx +zx An axiom on real Nos (distributive property)
4) (0+1).x= 0x+1x from 3and using Univ.Elim. where we put y=0,z=1,x=x
5) for all x,0+x=x An axiom in real Nos
6) 0+1=1 from 5 and using Univ.Elim.where we put x=1
7) 1x= 0x+1x by substituting 6 into 4
8) x=0x+x by substituting 1 into 7
9) for all a,b,c a=b ----> a+c=b+c An axiom in equality
10) x=ox+x -------> x+(-x)= (0x+x)+(-x) from 9 and using Univ.Elim.where we put a=x,b= 0x+x,c=(-x)
11) x+(-x)= (0x+x)+(-x) from 8 and 10 and using M.Ponens
12) for all a,b,c (a+b)+c= a+(b+c) An axiom in real Nos
13) (0x+x)+(-x) =0x +(x+(-x)) from 12 and using Univ,Elim. where we put a=0x,b=x,c=(-x)
14) x+(-x) =0x +(x+(-x)) by substituting 13 into 11
15) for all x, x+(-x) =0 An axiom in real Nos
16) x+(-x)=0 from 15 and using Univ.Elim.
17) 0 = 0x +0 by substituting 16 into 14
18) 0x + 0 = 0x from 5 and using Univ.Elim. where we put x=0x
19) 0 = 0x by substituting 18 into 17

 

[LAVRANOS]

Again here the laws used are:
1)Universal Elimination
2)Law of substitution
3)M.Ponens
And the axioms on real Nos:
1)For all, x 1x=x
2)For all, x,y,z (y+z)x= yx+zx
3)For all, x 0+x =x
4)For all, a,b,c a=b -----> a+c=b+c An axiom in equality
5)For all, a,b,c (a+b)+c = a+(b+c)
6)For all, x x+(-x) = 0

 

[LAVRANOS]

One may wonders O.K all that but how do we start to prove the above identity ( 0x=x).
In proving identities we start from
1)either L.H.S and end on R.H.S
2)OR R.H.S and end on L.H.S
3) or both sides and end on a common algebraic expression and in our case:
0x = 0x +0= 0x +(x+(-x)) = (0x + x)+(-x) = (0+1)x +(-x) = 1x +(-x)= x+(-x) =0
Another type of proof that have been mentioned previously is the double implications one i.e 0x=0<===> ox+x= o+x<====> (0+I)x=0+x<===>1x= 0+x<===> x=x
This type of proof assumes 0x=0 valid ( athing that we want to prove ) and with double implications end up on a valid statement

 

[LAVRANOS]

Let me now try to prove a well known limit which in ordinary mathematical books is proved within 5-6 lines. The limit is: lim(1/n)=0 as n-->oo (infinity)
According to the definition of a limit of a sequence we must prove that:
for all e>0 there exists an No ε N (natural numbers) such that for all n, n>=No then
|1/n-0|<e
1) e>0 assumption
2) for all, a (a>0 --> 1/a>0) theorem in inequalities
3) e>0 --> 1/e >0 from 2 and Univ.Elim.
4) 1/e>0 from 1 and 3 and M.Ponens
5) for all h (h>0 --> there exists No (No ε N and No>h)) theorem in real Nos known as Archimedean property
6) 1/e> 0 --> there exists No (No ε N and No>1/e) from 5 and Univ.Elim. where we put h=1/e
7) There exists No (No ε N and No>1/e) from 4 and 6 and M.Ponens
8) No ε N and No>1/e hypothesis for the choose rule
9) No ε N from 8 and conjuction elimination
10) 1/e<No from 8 and conjuction elimination
10a) n>=No hypothesis
11) for all k, (k ε N --> k>0) theorem in natural Nos
12) No ε Ν --> Νο > 0 from 11 and Univ.Elim. where we put k=No
13) No>0 from 9 and 12 and M.Ponens
14) For all a,b [0<a-->(a<=b<-->1/b<=1/a)] theorem in inequalities
15) 0 <No --> (No<=n <--> 1/n<=1/No) from 14 and Univ. Elim. where we put a=No and b=n


16) No <= n <--> 1/n <= 1/No from 15 and 13 and M. Ponens
17) 1/n <= 1/No from 10a and 16 and M.Ponens
18) for all a,b [0<a-->(a<b<-->1/b<1/a)] theorem in inequalities
19) 0 < 1/e --> (1/e<No <--> 1/No<e) from 20 and Univ. Elim. where we put a=1/e and b=No
20) 1/e<No <--> 1/No<e from 4 and 19 and M.Ponens
21) 1/No<e from 10 and 20 and M.Ponens
22) for all,a,b,c (a<=b and b<c ------> a<c) a theorem in real Nos
23) 1/n<= 1/No and 1/No<e ------> 1/n<e from 22 and Univ.Elim. where we put a=1/n,b= 1/No and c=e
24) 1/n<= 1/No and 1/No<e from 17 and 21 and conjuction introduction
25) 1/n<e from 23 and 24 and M.Ponens
26) for all a,b,c (a<b and b<=c-------> a<c) a theorem in inequalities
27) 0<No and No<=n -------->0<n from 26 and Univ.Elim. where we put a=0,b=No and c=n
28) 0<No and No<=n from 10a and 13 and conjuction introduction
29) 0<n from 27 and 28 and M.Ponens
30) 0<n-------> 0< 1/n from 2 and Univ.Elim. where we put a=n
31) 0<1/n from 29 and 30 and M.Ponens
32) for all x, (0<x -------> IxI=x) definition in absolute values
33) 0<1/n -------> I1/nI= I1/n-0I= 1/n from 32 and Univ.Elim. where we put x=1/n
34) I1/nI=I1/n-0I=1/n from 31 and 33 and M.Ponens
35) I1/nI<e by substituting 34 into 25
36) n>=No----------> I1/nI<e from steps 10a to 35 by using the conditional proof rule
37) for all n( n>=No -------------> I1/nI <e) from 36 and Univ.Introduction
38) Noε Ν and for all n( n>=No ------------> I1/nI<e) from 9 and 37 and conjuction introduction
39) there exists No ( No ε Ν and for all n( n>=No----------> I1/nI<e)) from 38 and existential introduction
40) there exists No ( No ε Ν and for all n( n>=No----------> I1/nI<e)) from steps 8 to 39 where according to the choose rule of logic we can discharge the hypothesis of step 8 and be left with the result of 39
41) e> 0--------> there exists No ( No ε Ν and for all n( n>=No----------> I1/nI<e)) from steps 1 to 40 and using the rule of conditional proof
42) for all e [ e>0--------> there exists No ( No ε Ν and for all n( n>=No----------> I1/nI<e)) from 41 and Univ. Introduction
HENCE WE HAVE PROVED lim 1/n =0 as n-----------> 00(infinity)

 

[Santa1]

Well don't you use a lot of unproven lemmas (i.e. 2,5,11,14,...)?

 

[LAVRANOS]

From step 10a the proof can be shortened considerably as follows:
Since NoεΝ ===> No>0 and since n>=No ===> 1/n<= 1/No ====> 1/n<e since 1/No<e , and also 1/n> 0 ====> I1/nI= 1/n since n>0. Provided we have Good command in inequalities a must in mathematical analysis.
Hence we can go straight to step 35.
Very important in analysis is,WHENEVER we start a hypothesis or assumption we must close it somewhere along the proof.
This happens particularly with proofs where we have a lot of quantification

 

[LAVRANOS]

Further more in this proof central theorem used is the Archimidean property which we can prove using the Completeness axiom in Real Nos

 

[LAVRANOS]

Do you know how many unproven theorems, lemmas, propositions,corollaries ordinary mathematical analysis books use in their proofs that they do not even mention?
WELL here at least are mentioned EXPLICITLY ,AND if you like you can check trier validity.
Besides this is the idea of the whole process ,everything to be brought up ,logic laws,theorems e.t.c so that there can be no doubt whatsoever of their validity.
Now if you can find another proof with less steps and fewer unproven theorems PLEASE DO IT

 

[DeaconJohn]

Okay, if you didn't mean "naive", what in the world is a "nabeve doctrine"?

When he wrote "your nabeve doctrine," he meant to write, "your above doctrine."

DJ

 

[dx]

When he wrote "the nabeve doctrine," he meant to write, "the above doctrine."

DJ

Read post #18...

 

[DeaconJohn]

definitely you can assume the premis and arrive at a truth and then consider your theorem truth only if the way from the premises to the truth result is connected by double implications.
see 2 examples in the attached file

Lavranos,

Your statement as written is false. There are theorems whose proofs that use only single, not double implications.

For example, consider the transitivity axiom for inequality on the real number line.

It says that (for all real x)( (x<y) and (y<z) ==> x<z ). Let's call this axiom "Transitivity" for short.

Suppose we want to prove the (very simple) theorem "2 < 3." Here's a proof.

"2" and "3" are real numbers. therefore, TRANS ==> 2<3. QED.

Notice that a double inequality is not used.

The reason your statement interests me is that when I was an undergrauate, I would think about the statement you made and try to see if i could "tweak" it to make it correct. I couldn't. Let's see if I can do it now. How about:

"The shortest proof of a statement of the form "<==>" is always a proof using the double implication sign method."

I have no idea whether the above statement is true or false. I'm not even sure it is interesting.

DJ

 

[DeaconJohn]

< originally posted by dx In fact,you can prove anything by assuming a false statement> Can you be so kind as to justify your nabeve doctrine by a couple of examples or example i.e assume a false statement and then prove a theorem.

This question (in essence) was allegedly asked by a heckler during a talk about mathmatical logic that the great logician Bertrand Russell once gave.

Bertrand Russell had just said "Give me one false statement in mathematics and I can prove anything you want me to."

O.K., challenged the heckler, "If 1 = 2, prove that I'M THE POPE."

(Note to moderator: That was the heckler shouting at Bertrand Russell, not me shouting at a fellow forum-ite.)

:)

With only a second's pause, Professor Russell replied,

"Well, you and the pope are two, but, if one equals two, then YOU'RE THE POPE."

:)

(Note to moderator: That was Professor Russell shouting back at the heckler. Professor Russell did not shout as loud as the heckler did.)

:)

I heard this story multiple times from multiple people when I was in graduate school at the Courant Institute of Mathematical Sceinces, N.Y.U., 1967-1969.

DJ

 

[LAVRANOS]

Deacon John i will wait until you finish the whole thread and i will answer afterwords

 

[DeaconJohn]

Read post #18...

Sorry DX. I made a "newbee" mistake. "Not suprising since I am a newbee."
DJ