Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 036
AIList Digest Thursday, 4 Aug 1988 Volume 8 : Issue 36
Mathematics and Logic:
Non-r.e. systems, Godel, and Zermelo
Self-reference and the Liar
Re: undecidability
----------------------------------------------------------------------
Date: Fri, 29 Jul 88 21:45 CDT
From: <CMENZEL%TAMLSR.BITNET@MITVMA.MIT.EDU>
Subject: Non-r.e. systems, Godel, and Zermelo
In AIList vol. 8, no. 29 (July 29, 1988), Herman Rubin writes:
> I know of no mathematical system in which the objects and axioms are not
> recursively enumerable.
I'm not sure what Rubin means by a mathematical system here, since the notion
of an object suggests systems are mathematical structures like the natural
numbers or the finite sets, while the notion of an axiom suggests systems are
axiomatic theories. There is a counterexample to his claim in either case. If
he means the former, consider the real numbers. Since no uncountable set is
r.e., the set of reals isn't. If you want a countable set, consider the set of
Godel numbers of sentences of the first-order language of arithmetic that are
true in the natural numbers (relative to some coding for the language). Godel's
theorem says that this set is not r.e. For a non-r.e axiomatic theory, take
as axioms the set of the above true sentences of arithmetic. Same result.
Granted the theory ain't good for much; but that's another kettle of fish.
> A Turing machine can do all mathematics in principle.
Certainly you don't mean that every mathematical truth is provable; cf. Godel
again. But if not, what? Zermelo constructed an apparently--but not provably
(Godel yet again)--consistent, and very powerful, set of axioms for set theory.
Surely he was doing mathematics. Now write me a program for generating set
theoretic axioms that avoid the paradoxes of naive set theory, and preserve
arithmetic, classical analysis, and transfinite number theory.
Chris Menzel
Dept. of Philosophy/Knowledge Based Systems Lab
Texas A&M University
BITNET: cmenzel@tamlsr
ARPANET: chris.menzel@lsr.tamu.edu
------------------------------
Date: Sat, 30 Jul 88 17:09 CDT
From: <CMENZEL%TAMLSR.BITNET@MITVMA.MIT.EDU>
Subject: Self-reference and the Liar
In AIList vol. 8 no. 29 Bruce Nevin provides the following analysis of the liar
paradox arising from the sentence "This sentence is false":
> 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.
There are type-token problems here, but never mind. If what Nevin says
is right, then there is something semantically improper in general about
referring to the sentence one is uttering; note there is nothing about the
liar per se that appears in his analysis. If so, however, then there is
something semantically improper about an utterance of "This sentence is
in English", or again, "This sentence is grammatically well-formed." But
both are wholly unproblematically, aren't they? Wouldn't any English speaker
know what they meant? It won't do to trash respectable utterances like
this to solve a puzzle.
Nevin's analysis gets whatever plausibility it has by focusing on *English
utterances*, playing on the fact that, in the utterance of a self-referential
sentence, the term allegedly referring to the sentence being uttered has no
proper referent at the time of the term's utterance, since the sentence yet
isn't all the way of the speaker's mouth. But, first, it's just an accident
that noun phrases usually come first in English sentences; if they came last,
then an utterance of the liar or one of the other self-referential sentences
above would be an utterance of a complete sentence at the time of the utterance
of the term referring to it, and hence the term would have a referent after
all. Surely a good solution to the liar can't depend on anything so contingent
as word order in English. Second, the liar paradox arises just as robustly for
inscriptions, where the ephemeral character of utterances has no part. About
these, though, Nevin's analysis has nothing to say. A proper solution must
handle both cases.
Recommended reading: R. L. Martin, {\it Recent Essays on Truth and the Liar
Paradox}, Oxford, 1984.
J. Barwise and J. Etchemendy, {\it The Liar: An Essay
on Truth and Circularity}, Oxford, 1987.
---Chris Menzel
Dept. of Philosophy/Knowledge Based Systems Lab
Texas A&M University
BITNET: cmenzel@tamlsr
ARPANET: chris.menzel@lsr.tamu.edu
------------------------------
Date: 2 Aug 1988 10:43 EDT
From: pyuxf!asg
Subject: Re: undecidability
Path: pyuxf!asg
From: asg@pyuxf.UUCP (alan geller)
Newsgroups: comp.ai.digest
Subject: Re: undecidability
Summary: Infinity IS natural
Message-ID: <375@pyuxf.UUCP>
Date: 2 Aug 88 13:51:14 GMT
Article-I.D.: pyuxf.375
Posted: Tue Aug 2 09:51:14 1988
References: <19880727030404.9.NICK@HOWARD-JOHNSONS.LCS.MIT.EDU>
Organization: Bell Communications Research
Lines: 55
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
Actually, infinity arises in basic set theory, long before any notion
of 'finite space' is introduced (viewing mathematics as an inverted
pyramid, from lowest-level set theory and logic up). Two axioms suffice
to introduce infinity: the axiom of the null set, which says that there
exists a set 0, which is empty; and the axiom of construction (or of union,
or whatever you prefer to call this axiom), which says that if a and b
are sets, then so is {a, b}. These two axioms allow one to construct
0, {0}, {{0}}, etc., which is an infinite series. In fact, it is possible
to create models of set theory which are constructed using only sets of
this form.
In physics, 'quantization' does not mean 'granularization', despite
the popular understanding that this is so. While there are physicists
who work on theories of granular space, mainstream quantum physics
interprets space as a continuum. Indeed, even quantized measurables
such as energy levels are seen as selected values 'chosen' out of
a continuum by being the eigenvalues of some operator.
Also, the notion that the universe is finite is still contraversial;
while most cosmologists seem to believe that the universe is closed
(i.e., finite), there is still no experimental evidence to support
this view (this is why cosmologists talk about the 'missing mass',
which is needed to close the universe gravitationally; nobody's found
it yet).
Alan Geller
Bellcore
Nobody at Bellcore takes me seriously.
------------------------------
End of AIList Digest
********************
