Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 029
AIList Digest Friday, 29 Jul 1988 Volume 8 : Issue 29
Today's Topics:
Mathematical Logic:
(This began as part of the 'free will' discussion, but
seems to have branched out since ...)
Are all reasoning systems inconsistent?
Bounded systems are too limited
Goedel's Theorem
self reference paradox
----------------------------------------------------------------------
Date: Wed, 27 Jul 88 08:47:38 EDT
From: PAUL_MALENFANT@VOID.CEO.DG.COM
Reply-to: <PAUL_MALENFANT%VOID.CEO.DG.COM@adam.DG.COM>
Subject: Re: Are all reasoning systems inconsistent?
Jon, after reading your proof beginning with S = (S -> A), I constructed
the truth table for it.
S A | (S -> A) | S = (S -> A)
=========================================
T T | T | T
F T | T | F
T F | F | F
F F | T | F
As you can see, it can only be true iffi both S and A are true, so
your proof isn't saying anything new. A must be true by definition,
not by deduction.
Similarly, S = (P(n) -> A) can be constructed in the same way.
S P(n) A | (P(n) -> A) | S = (P(n) -> A)
==============================================
T T T | T | T
F T T | T | F
T F T | T | T *
F F T | T | F
T T F | F | F
F T F | F | T *
T F F | T | T *
F F F | T | F
Here, there are more true combinations, but the ones that are marked
by * must be discarded because they violate (S = P(n)) which was not
in the original expression - if it was, then the only instance of
truth for the expression would require S, P(n) and A to be all true.
So in answer to your question, the reasoning system wasn't inconsistent,
it just revealed something which had to be true about the expression
in the first place.
Paul
------------------------------
Date: 27 Jul 88 14:30:34 GMT
From: cik@l.cc.purdue.edu (Herman Rubin)
Subject: Bounded systems are too limited
In a previous article, John B. Nagle writes:
> Goetz writes:
>
> > Goedel's Theorem showed that you WILL have an
> > unbounded number of axioms following the method you propose. That is why
> > most mathematicians consider it an important theorem - it states you can
> > never have an axiomatic system "as complex as"
> > arithmetic without having true statements which are unprovable.
>
> Always bear in mind that this implies an infinite system. Neither
> undecidability nor the halting problem apply in finite spaces. A
> constructive mathematics in a finite space should not suffer from either
> problem. Real computers, of course, can be thought of as a form of
> constructive mathematics in a finite space.
>
> There are times when I wonder if it is time to displace infinity from
> its place of importance in mathematics. The concept of infinity is often
> introduced as a mathematical convenience, so as to avoid seemingly ugly
> case analysis. The price paid for this convenience may be too high.
>
> Current thinking in physics seems to be that everything is quantized
> and that the universe is of finite size. Thus, a mathematics with infinity
> may not be needed to describe the physical universe.
>
> It's worth considering that a century from now, infinity may be looked
> upon as a mathematical crutch and a holdover from an era in which people
> believed that the universe was continuous and developed a mathematics to
> match.
>
> John Nagle
The finiteness of size of the universe is irrelevant to the question of
whether an infinite system is needed. The number of points in the smallest
interval in one dimension is the same and the number needed for any finite-
dimensional model of the universe. The resolution of the various paradoxes
require a concept of infinity, but not of an unbounded universe.
And even if the universe is finite and quantized, so that at any physical
time there are only finitely many points in space (with the appropriate
relativistic modifications), and any history has only a finite number of
time points, the probabilistic considerations require that the parameter
space is infinite.
Mathematics does not allow infinitely long arguments in most of its branches.
A proof must have finite length in its language. However, bounded length
cannot be required. I cannot imagine a remotely reasonable system which
would allow proofs to have 65535 lines but not 65536. Or a system which
would allow an argument to use 1988 variables but not 1999. The postulates
about the integers state that for every integer there is a next integer--
a next _larger_ integer. Do not confuse unboundedness with infinity.
I know of no mathematical system in which the objects and axioms are not
recursively enumerable. That means that they can be listed. I have
referred above to having arbitrarily many variables. The rules also
require a listing. The ability to substitute an expression of an appropriate
type for a variable is actually an axiom schema, a separate axiom for each
variable and each expression. Thus there must be an infinite number of
rules.
A Turing machine can do all mathematics in principle. So can any computer
with an infinite tape if it of even moderate size. But remember the infinity.
If a particular computer with a particular memory, including externals,
cannot do a particular job does not mean that that job cannot be done by
computers.
Also do not confuse the size of an object within a mathematical system
with the size as seen from a model. There are also different notions of
size, and a competent mathematician has no problems in using the appropriate
notion in a given situation.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)
------------------------------
Date: Wed, 27 Jul 88 15:42:05 +0100
From: "Gordon Joly, Statistics, UCL"
<gordon%stats.ucl.ac.uk@ESS.Cs.Ucl.AC.UK>
Subject: Re: Goedel's Theorem
> From AIList Vol 8 # 22
> Shame on you, professor! Goedel's Theorem showed that you WILL
> have an unbounded number of axioms following the method you propose.
> That is why most mathematicians consider it an important theorem - it
> states you can never have an axiomatic system "as complex as"
> arithmetic without having true statements which are unprovable.
> Phil Goetz
Shame on who? Anyway, the theorem is important to *pure*
mathematicians, in particular number theorists, as is the concept of
infinity. But does that worry *applied* computer scientists? I
believe you need to have system as complex as the real numbers
(countable infinity) to get into the "Goedel domain".
> op. cit.
> Since you CAN think of ways to disprove f=ma, you may avoid being
> run over by a bus.
> -- Rich Brandau
Einstein showed that f=ma was a first approximation. He also showed
that is was fundamentally incorrect to think if the apple as being
pulled; it falls since nothing holds it up. f=ma was DISproven in
this sense.
Gordon Joly.
P.S. Is cosmology a science?
------------------------------
Date: Wed, 27 Jul 88 11:35:48 EDT
From: "Bruce E. Nevin" <bnevin@cch.bbn.com>
Subject: self reference paradox
In AIList Digest for Wednesday, 27 Jul 1988 (Volume 8, Issue 28), in his
message of 24 Jul 88 23:36:25 GMT, buengc!bph@bu-cs.bu.edu (Blair P. Houghton)
writes:
BH> One of the simplest examples of unproveability is the paradox
|
| "This sentence is false."
|
| It drives you nuts if you analyze it semantically; but, it's blithering
| at a very low level if you hit it with logic: call the sentence S;
| the sentence then says . . .
|
| "S = not-S."
The syntactic nexus of this and related paradoxes is that there is no
referent for the deictic phrase "this sentence" at the time when it is
uttered, nor even any basis for believing that the utterance in progress
will in fact be a sentence when (or if!) it does end. A sentence cannot
be legitimately referred to qua sentence until it is a sentence, that
is, until it is ended. Therefore, it cannot contain a legitimate
reference to itself qua sentence. For this reason, the above
translation into symbolic notation is not licit. It does not even
capture what we suppose the sentence to be saying, precisely because it
does not capture the paradox. And why does it fail in this? Because it
is a metalanguage statement referring to the sentence abbreviated by S.
It is not a self-reference by a sentence to itself, it is a reference to
a separate sentence, abbreviated S.
This failure of self-reference is a limitation, if you want to think of
it that way, due to the fact that natural languages contain their own
metalanguages, rather than having a separate metalanguage. See Harris
_Mathematical Structures of Language_ and _Language and Information_ for
discussion.
The logical apparatus of deduction and other forms of inference are
required only for various uses to which language may be put, rather than
being the semantic basis for natural language, as has been sometimes
claimed. Translation of natural language texts into logical notations
is always and necessarily incomplete. (Same references, for starters.)
Bruce Nevin
bn@cch.bbn.com
<usual_disclaimer>
------------------------------
End of AIList Digest
********************
