Methods of Proof

Page 1 of 1

0 Replies - 3028 Views - Last Post: 13 January 2010 - 02:11 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=149674&amp;s=1ebf1b8ae9406a3a52411a23ba4f97ea&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

• D.I.C Regular

Reputation: 9
• Posts: 419
• Joined: 08-April 09

Methods of Proof

Posted 13 January 2010 - 02:11 AM

Here we discuss the issues of proof, to show what methods are available to show that a given claim is a logical consequence of some premises.

First, what is a proof?
A proof is a step-by-step demonstration that a conclusion (S) follows from some premises (P, Q, R).

There are two methods of proof we will be looking at, informal and formal proofs. Informal proof, in simple English, are sentences. For example,

Quote

Socrates is a man.
All men are mortal.
No mortal lives forever.
Everyone who will eventually die sometimes worries about it.
--

An informal proof of the above would be something like this:

PROOF: Since Socrates is a man and all men are mortal, it follows that Socrates is mortal. But all mortals will eventually die, since that is what it means to be mortal. So Socrates will eventually die. But we are given that everyone who will eventually die sometimes worries about it. Hence Socrates sometimes worries about dying.

The second, a formal proof, by contrast, employs a fixed stock of rules and a highly stylized method of presentation. For example, the simple argument from Cube(C ) and c = b to Cube(B ) discussed in the last section will, in our formal system, take the following form:

Quote

Cube(C )
c = b
--
Cube(B )

Next up, Proofs involving Identity Symbols.

As in the above example, we got c=b, this means that whatever is true for c is also true for b. So, since c is a cube, it makes sense that b is a cube as well. This principle is called Identity Elimination, and abbreviated as =Elim. The reason for this name is that an application of this rule “eliminates” This principle is also known as the Indiscernibility of identicals and sometimes substitution.

Another principle, reflexivity of identity: The formal rule corresponding to it is called Identity Introduction, or =Intro, since it allows us to introduce identity statements into proofs. It tells us that any sentence of the form a = a can be validly inferred from whatever premises are at hand, or from no premises at all.

Another principle, a bit more useful, is that of the symmetry of identity. It allows us to conclude b = a from a = b.

And a last one, if a = b and b = c are both true, then so is a = c. This is so obvious that there is no particular need to prove it, but it can be proved using the indiscernibility of identicals mentioned above.

Now, to put these principles into good use.

Suppose we were asked to give an informal proof of the following argument:

Quote

b = c
a = b
--
a = c

PROOF: We are told that b is equal to c. We are also told the a is equal to b, which means b is also equal to a by symmetry of identity. By indiscernibility of identicals, since whatever holds for b also holds for c, and whatever holds for b also holds for a, by transitivity of identicals this means that whatever holds for a also holds for c, and as a result reach our desire conclusion of a being equal to c.

Another example, to test our understanding of proofs:

Quote

SameRow(a, a)
a = b
b = c
SameRow(c, a)

PROOF: We are given that a is in the same row are a, by reflexivity of identity. We are given that a is equal to b and b is equal to c. By indiscernbility of identicals, whatever holds for a also holds for b. And whatever holds for b also holds for c. Therefore whatever holds for a also holds for c, and thus, we arrive at our conclusion, that c is in the same row as a.

This proof can also be given using the transitivity of identicals.

Next tutorial, Formal Proofs, which is also known as a “deductive system”.

Attached File(s)

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }