Copy Link
Add to Bookmark
Report
AIList Digest Volume 8 Issue 051
AIList Digest Tuesday, 16 Aug 1988 Volume 8 : Issue 51
Mathematics and Logic:
Nitpicking about the Axiom of Choice
Are all Reasoning Systems Inconsistent?
Ineluctable self reference
----------------------------------------------------------------------
Date: 1 Aug 1988 1819-PDT (Monday)
From: aspnes@decwrl.dec.com (Jim Aspnes)
Subject: Nitpicking about the Axiom of Choice
> From: bwk@mitre-bedford.ARPA (Barry W. Kort)
> In the above scenarios, the resolution is to pick a path at random
> and pursue it first. To operationalize the decision, one needs to
> implement the Axiom of Choice. One needs a random number generator.
> Fortunately, it is possible to build one using a Quantum Amplifier.
> (Casting lots will do, if you live in a low-tech society.)
Technically speaking, the Axiom of Choice claims only that choice
functions exist for collections of infinite sets. These choice
functions _must_ be deterministic (although what the function maps
each set to is not specified by the axiom), and always exist for finite
sets with or without the Axiom of Choice.
So Quantum Amplifiers would not be terribly useful in the
operationalization of the Axiom of Choice, unless your scenario included
a previous operationalization of a representationalization of arbitrary
infinite sets.
Jim Aspnes <asp@cs.cmu.edu>
------------------------------
Date: Mon, 8 Aug 88 13:16:12 EDT
From: jon@XN.LL.MIT.EDU (Jonathan Leivent)
Subject: Are all Reasoning Systems Inconsistent?
It seems that I keep making the same mistakes.
Here is a full version of the contradiction that I am claiming exists. I'm
making this as complete as possible because previous versions of my assertion
have all suffered from my own clumsiness (abstractly, they were on the right
track; formally, they were all wrong). So here goes:
Definition of functions and predicates:
Q(a,b) : equality of numbers predicate (so we don't get mixed up with =)
Aa[Q(a,a)], AaAb[Distinct(a,b) -> ~Q(a,b)]
"X" : the Godel number of X
s("X",a) : the Godel number of X with all occurrences of * replaced by the
Godel number of the number a : s("R(*)",14) is "R(14)"
P(a) : the predicate of provability within this reasoning system
I won't go into proofs of the existence of s and P. Chapter 24 of Doug
Hofstadter's book _Godel, Escher, Bach_ has the best explanations of these I've
seen (Hofstadter's versions of the functions are a bit different from mine -
I've chosen mine for conciseness, Hofstadter probably chose his to simplify
the proofs of their existence).
Theorems:
T1. AaAb[Q(a,b)P(a) = P(b)] ; just says that P behaves normally
T2. Aa[P(s("~P(*)",a)) -> ~P(a)] ; If I can prove that I can't prove X, then I
can't prove X
T3. If X can be proven within this reasoning system, then P("X") is true
Definitions of numbers:
Let F such that Q(F,"~P(s(*,*))")
Let G such that Q(G,s(F,F)) ; this means that G is s("~P(s(*,*))",F), which is
"~P(s(F,F))" : so Q(G,"~P(G)") and G is our Godel sentence
(remember that F and G are numbers, not variables)
The inconsistency itself:
1. P(G) = P("~P(G)") ; from T1 and the defintion of G
2. P("~P(G)") -> ~P(G) ; from T2
3. P(G) -> ~P(G) ; from 1 and 2 by substitution of P(G) for P("~P(G)")
4. ~P(G) ; from 3 (3 is equivalent to ~P(G) v ~P(G))
5. P("~P(G)") ; from T3 and the fact that 1 thru 4 proves ~P(G)
6. P(G) ; from 1 and 5
4 and 6 contradict.
All that I have done is to show that the existence of a Godel sentence within
a reasoning system equipped to reason about itself is inconsistent. This
differs from Godel's theorem in that Godel shows that a Godel sentence cannot
be proven within a reasoning system in which it is true.
Perhaps the weak link in the contradiction is step 5, which is somewhat of a
"meta" step. What bothers me most is that there seems to be no formal way of
writing T3, even though it seems to be obviously true (it is only asserting
the equivalence of P with the implied proof predicate in this reasoning
system, which is true by definition of P). Note that T3 does not claim that
if X is true, then P("X") is true - it requires X to be proven within this
reasoning system, which is a stronger requirement than truth (because of the
incompleteness of P).
Well, I hope I haven't goofed up here as I did previously. This finally seems
to be a formal statement of what was on my mind after reading Smullyan's
article "Logicians who Reason about Themselves".
-- Jon Leivent
------------------------------
Date: Mon, 8 Aug 88 14:26:16 EDT
From: "Bruce E. Nevin" <bnevin@cch.bbn.com>
Subject: ineluctable self reference
In AIList Digest for Sunday, 7 Aug 1988 (Volume 8, Issue 39),
Mike Dante <DANTE@EDWARDS-2060.ARPA> writes:
MD>| Bruce Nevin suggests that the solution to the "liar's paradox" lies in
| the self reference to an incomplete utterance. How would that analysis
| apply to the following pair of sentences?
| The next sentence I write will be true.
| The previous sentence is false.
These are both metalanguage sentences. Each is talking about a
metalanguage sentence (the other). Part of the construal of the
metalanguage predicate `false' is the inference that the negation of its
argument is true. Thus, in the metalinguistic baggage that sentence 2
carries with it is the negation of sentence 1. But since sentence 1
incorporates a reference to sentence 2, sentence 2 incorporates (as part
of the metalanguage baggage required to understand it) a reference to
itself.
In more intuitive terms: what's wrong here is that somewhere it is
being asserted that sentence 1 is both true and false. Thus, there must
be two distinct series of readings of sentence 1: an odd-numbered
series in which it is true in what it asserts of sentence 2, and an
even-numbered series in which it is false because of what sentence 2
asserts. (The same goes, ceteris paribus, for sentence 2.) When you
get tired of that loop, you fall back on assuming that the two readings
are but one sentence, even while trying to reconcile the two readings
(which leads into the next two reading-tokens, and so on, each round
`meta-' wrt the prior).
+---+==>[I affirm that] the next sentence I write will be true.
| +-|-->[I affirm that] the previous sentence is false [and so I deny that]+
| | | |
| | +----------------------------------------------(loop 1)----------------+
| | [and so I deny that] +
| | | (loop 2)
| +--------------------------+
| [and so] +
| | (loop 3)
+----------------+
Added metalanguage material is in square braces. The loop is perhaps
clearer (although misrepresented a bit) this way:
+->I affirm S1
| I affirm S2,
| and so I deny S1 (loop 1)
| and so I deny S2 (loop 2)
| and so +
| | (loop 3)
+---------------+
All of the looping is part of S2, even though it is by reference to both
S1 and S2, because it is a succession of conjunctions to S2 under `and
so' or `therefore' or the like. And until you have finished construing
all the metalanguage conjuncts that you need to understand the sentence
you haven't finished understanding the sentence, and so it is not
available to you as an object of reference as regards its meaning. (As
regards spelling, or handwriting, or depth of incision in stone, or
authorship, etc., it is of course available for reference, but that is
reference with different ends, and that is why it does not matter
whether the referential comes at the end or not.)
It is the metalanguage performative predicates of assertion that bring
about self-referentiality. (You see the need for these in e.g.
`Clearly, John has left' where the adverb cannot apply to the verb
`leave', still less to its argument `John', but can only apply to an
elided `I infer' or the like. See _A Grammar of English on Mathematical
Principles_ for discussion.)
Again, self reference (where one reading-token of the sentence is
`meta-' with respect to the other) is the syntactic core of these
paradoxes. And this is why the obvious (but incomplete) translation
into symbolic logic is something like S <=> ~S: you have to represent
both readings separately to represent the fallacy.
This is not a claim that all inferencing is part of the `metalinguistic
baggage' that language users presume as though overtly conjoined when
construing sentences and texts. Only that which can be thought of as
obvious common knowledge. I realize this is a very large can of worms,
but I won't take credit for opening it--the problem of coping with
common knowledge in language understanding and language generation is
hardly a new one.
Barry W. Kort (bwk@mitre-bedford.ARPA) writes:
BK>| While we are having fun with self-referential sentences, perhaps
| we can have a go at this one:
| My advice to you is: Take no advice from me,
| including this piece.
| (At least the self referential part comes at the end, so that
| the listener has the whole sentence before parsing the deictic
| phrase, "this piece".)
This is straightforwardly self-referential. I addressed the confusion
about `having the whole sentence' vs `resolving all the referentials in
the sentence' in my contribution to AIList 8.39.
Bruce Nevin
bn@cch.bbn.com
<usual_disclaimer>
------------------------------
End of AIList Digest
********************
