Re: Godel's Theorem under Fuzzy Logic?

Christian Borgelt (borgelt@hp827.cs.Uni-Magdeburg.DE)
Sat, 28 Mar 1998 21:48:02 +0100 (MET)

greenrd@hotmail.com wrote:
> Can Godel's Incompleteness Theorem be extended to formal systems based on
> fuzzy logic?
>
> This is a crucial question, IMO, with regard to Artificial Intelligence,
> because as I understand it, Roger Penrose's whole argument in his book
> "Shadows of the Mind" that convincingly attempts to show that AI is
> in principle unachievable on any algorithmic computer, assumes that the
> posited machine intelligence thinks in terms of either-or (Aristotlean) logic
> rather than fuzzy logic. Surely fuzzy logic would invalidate Godel's Theorem
> and hence his whole argument? - therefore AI might in fact be possible after
> all.
>
> However, I wonder whether Godel's Theorem can be extended to formal systems
> based on fuzzy logic. In this case, Penrose might be correct after all!
>
> I am only a first-year mathematics student, so please try to keep your replies
> as simple as possible.

Hi noname (Mr Green?),

G"odel's Theorem is not restricted to (Aristotelian) logic, in fact,
it does not hold for pure (Aristotelian) logic. What G"odel proved
is that any formal system that is powerful enough to cover number
theory is either incomplete or inconsistent. Of course, pure logic
does not cover number theory. [Frege's trial to base mathematics on
logic, which he carried out in his book ``Grundgesetze der Arithmetik'',
has to be considered a failure, due to the flaw Russell found in it
--- the famous set of all sets that do not contain themselves ---
which disproves the ``unbeschr"ankte Komprehensionsprinzip'' (sorry,
I don't know the English word for this; this principle, which is at
the basis of Frege's approach, says that any property can be used to
form a set). Russel's own approach to the problem, which he carried
out together with Whitehead in the ``Principia Mathematica'', uses
some axioms (e.g. the selection axiom, the infinity axiom) which are
definitely not part of pure logic.]
Since you are a first year mathematics student, it may be a good
idea to explain the terms completeness and consistency of a formal
system. A formal system --- in brief: a set of axioms and a set of
inference rules (not: implications!) --- is said to be consistent, if
starting from the axioms and applying only the allowed inference rules,
you can never reach a situation in which you have proven a contradiction,
i.e. a formula and its negation. Of course, this way of stating it
assumes that the formal system contains an operation that can be
interpreted as a negation. Not all formal systems do, so a more general
way of stating it is to say that starting from the axioms and applying
only the allowed inference rules, you cannot prove all possible formulae
of the formal system. These two ways of stating consistency are equivalent,
since ``ex contradictio quodlibet'' --- from a contradiction everything
can be inferred.
Completeness means that starting from the axioms and applying only
the allowed inference rules you can, in principle, prove any true
formula of the formal system. The proof may consist of a very long
chain of inferences, but for any true formula, there is such a proof.
G"odel's clever idea was to construct, within a formal system S, a
formula that says something about its own ``provability''. Intuitively,
this formula says: ``I, formula, cannot be proven in the system S.''
(Actually, in his paper ``"Uber formal unentscheidbare Probleme der
Principia Mathematica und verwandter Systeme I'', he carried out this
construction for the formal system developed in Russell and Whitehead's
``Principia Mathematica'', but his construction is not restricted to
this system.) The main problem was to find a way to represent such a
formula in a formal system. G"odel used a special coding, which we
nowadays call ``G"odelization''. This coding is based on numbers,
especially prime numbers, hence the formal system must cover number
theory. I will not go into details here, you can find them in any
book on the theory of computer science.
Let's take a look at the intuitive form of G"odel's formula (let's
call it F). Obviously, F states: ``F cannot be proven in S''. Assume
that actually F cannot be proven in S. Then F is obviously true. But
since it cannot be proven in S, the system S is incomplete. To be
complete, it must be possible to prove F, but F cannot be proven (by
assumption). Now assume that F can be proven in S, so S may be complete.
But F says that F cannot be proven in S. Starting from F, which can
be proven (by assumption), we infer that F cannot be proven. We have
reached a contradiction. Hence S is not consistent. Summing up, we can
only choose between a system that is incomplete or inconsistent. We
cannot have both (provided the system is ``expressive'' enough, i.e.
covers number theory or some equivalent thereof).
Finally, let's consider your question. To me it seems obvious that
fuzzy logic does not provide a way to escape from G"odel's theorem,
since fuzzy logic can be formulated as a formal system and can easily be
extended to cover number theory. Hence G"odel's theorem holds. Of course,
there are some difficulties involved. Due to the introduction of degrees
of truth, we have to define carefully what we mean by ``proof'', by
``consistency'' and by ``completeness''. But I think that, if in doubt,
we can always code the necessary interpretation into the G"odel formula
F we construct in the system, for example, code F as saying intuitively
``I, formula, cannot be derived with a degree of truth of 1.''
Another difficulty, which is not limited to fuzzy logic, is whether
G"odel's proof is actually a proof. To prove incompleteness, we have
to interpret the formula and have to understand that what it says is
true. That is, the result is not achieved by formal reasoning, but
by some meta-reasoning done from outside the system. Hence it is not
a ``formal'' proof. It takes insight to see the truth of the formula.
With fuzzy logic, we face the additional complication that we have to
fix our meta-interpretation of truth (looking from outside the system),
in order to compare the result to the formal result in the system.
But all this, in the end, comes to no more than the question whether
only a formal proof is proof and whether you, in your meta-reasoning,
accept degrees of truth. This, obviously, cannot be decided by a
formal system. You have to choose.

Regards,

Chris

-----------------------------------------------------------------------
Christian Borgelt

Otto-von-Guericke-University of Magdeburg
Department of Information and Communication Systems
Working Group Neural and Fuzzy Systems

Universit"atsplatz 2 Phone : +49.391.67.12700
D-39106 Magdeburg Fax : +49.391.67.12018
Germany E-mail: borgelt@iik.cs.uni-magdeburg.de
-----------------------------------------------------------------------