Perl-Sensitive Sunglasses PerlMonks

### Re^4: What do you know, and how do you know that you know it?

by hv (Parson)
 on Aug 03, 2004 at 11:17 UTC ( #379580=note: print w/replies, xml ) Need Help??

It need not necessarily be doomed to fail for that reason, if the software involved could be useful enough that from some point an increasing proportion of new maths were produced using it.

Making the technology sufficiently useful is probably the magic part though; fixing existing proofs is also likely to be a big job, since my impression is that even today they are riddled with informal appeals to reason or analogy in a manner that would in many cases be hard to formalise.

Of course any hard step can be left for later, or for someone else, simply by declaring that step as an axiom.

An interesting aspect of this - though also one with the potential to explode the problem space - is that it could make it much easier to see the overlap in accessibility of theorems under different sets of rules of logic.

I think I first started thinking about this way back when I was first reading Godel, Escher, Bach. I spent a lot of time with the Peano axioms described there, and while I could prove things like commutativity and associativity of addition and multiplication easily enough the lack of axioms for handling negatives meant it was impossible to prove something like "every integer is either even or odd":

``` Ax: (Ey: ((x = (SS0 . y) | (x = S(SS0 . y)))))

Hugo

Replies are listed 'Best First'.
Re^5: What do you know, and how do you know that you know it?
by tilly (Archbishop) on Aug 03, 2004 at 14:59 UTC
Fixing existing proofs is the key roadblock. Furthermore automated proof techniques would have different amounts of utility in different parts of math. And finally, most mathematicians like understanding their proofs. Automated proofs don't tend to be understandable. It is like the endgame studies that computers did in chess - you can see that it works, but you can't see how anyone could think of or remember it. (Which is why no human had thought of it...)

Incidentally your playing around with the Peano axioms mislead you. The Peano axioms allow you to reason about the positive integers. (Proving that every positive integer is either even or odd is simple induction.) To get from there to the integers, you model each integer as an equivalence class of pairs of integers (p, n) with (p, n) in the same equivalence class as (p', n') if p'+n = p+n'. (Think of (p, n) as p-n.) Now you have to prove that the equivalence relation is well-defined, and that definition of addition is likewise. Define the usual multiplication, and prove that that works. And that you can map the positive integers into the integers with p->(p+1, 1). Then you can start proving other things, such as that every integer is either positive or negative.

Once you have all of that, then you're in a position to prove things about the integers (like every integer is even or odd).

You have to go through the same process again to define rationals as equivalence classes of pairs of integers. You can then define real numbers as equivalence classes of Cauchy sequences of rationals. Once you've done that you then have to reprove everything. But, amazingly, you can get all of the way through Calculus with just the Peano axioms. (It takes a lot of work though.)

I am not greatly interested in automated proofs, but rather in tools to assist humans in developing proofs and studying them - I'm talking more about distributed databases and user interfaces than about anything from AI, and about using strict validation techniques to replace the need for a trust model such as peer review.

In respect of the even/odd thing, I may have misremembered what I was trying to prove: I'd have to find back my notes from my teenage years. I'm sure the problem revolved around proving a negation, and was intended to be a stepping stone to playing with prime numbers; I suspect it was less to do with the axioms as P1 .. P5, and more to do with the axioms as (P1 .. P5 plus the permitted rules of logic as described by Hofstadter).

Hugo

Create A New User
Node Status?
node history
Node Type: note [id://379580]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2021-01-16 06:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (158 votes). Check out past polls.

Notices?