Gödel’s Incompleteness and Consistency Theorems Elucidated with Principles of Abstraction Levels, Complementarity, and Self-Re



Yüklə 0,53 Mb.
tarix01.08.2018
ölçüsü0,53 Mb.
#60047

GÖDEL’S INCOMPLETENESS AND CONSISTENCY THEOREMS ELUCIDATED WITH PRINCIPLES OF ABSTRACTION LEVELS, COMPLEMENTARITY, AND SELF-REFERENCE

Eric D. Smith
University of Texas at El Paso

ESmith2@UTEP.edu


ABSTRACT

The question “What is a system?” can be asked and answered differently, but the fact that the question refers to a whole -- called a system -- remains. While formal engineering design and modeling languages describe system parts, the practice of systems engineering results when there is reference to holistic systems, often via self-reference. Self-reference creates the possibility of circular, paradoxical reasoning where multiple outcomes can occur. Conceptual structuring by abstraction levels with complementarity clarifies paradoxes without resort to strict hierarchical decomposition that nullifies complexity. Gödel’s Incompleteness and Inconsistency Theorems prove truths about formal languages that have the ability of self-reference, elucidating analogous relations among: informal natural language statements about systems, systems, and formal languages that describe systems. The goal of this work is to foster cognizance in system descriptions.


Key Words: Gödel, Self-reference, Incompleteness, Inconsistency, Complementarity, Syntactic, Semantic, Principia Mathematica, Axiomatization, Deductive, Levels, Abstraction

1, INTRODUCTION
Complicated systems have a great number of mechanical or deterministic parts, which despite the possibly great effort needed for their deciphering, are nonetheless fully understandable by formal means, such as formal logic or deterministic mathematical formulations. The configurations of a complicated system are enumerable, even if not all enumerations are available with current computational abilities. For example, a large collection of ideal pre-arranged billiard balls may be struck by a cue ball, invoking the question: “In what direction and at what speed will the billiard balls propagate?” or, “What is the resultant vector of the billiard ball placed at the very back?” Any collective ‘emergent’ behavior that complicated systems evince can in fact be predicted by accounting for the behavior of the constituent parts. The most useful and widely applied tools of Systems Engineering arguably remain methods that effectively decompose and mechanize complex systems so as to render their models as merely complicated.
Complexity in mathematical formalizations can be perceived through the presence of intriguing members of mathematics, including: 1, Random numbers, 2, Transcendental numbers, and 3, Imaginary numbers. Random numbers cannot be produced by established algorithms, and are thus only truly available via non-determinable generators, such as the quantum nature of reality. Transcendental numbers, like irrational numbers, cannot be described succinctly as the quotient of two integers, and never exhibit patterns. The transcendental number π is essential to the description of the completeness of a circle, and the transcendental number e is the only consistent base for a natural logarithm. The fundamental nature of imaginary numbers remains a mystery, despite the laconic definition, . Imaginary numbers are constructively employed in complex numbers, and provide a bridge between phases in wave mechanics and real objects. In so far as any system requires characterization by these three types of numbers, the system can be classified as complex. As a practical matter, systems in this universe, with the examples of humans and other phenomena in the natural world, are complex systems.
Emergence is a fascinating and vexing feature of complex systems, giving rise to system properties that are not present in their constituent parts [Warfield, 2002]. Emergence is approached in this paper via concept structuring.
Complementarity, a dualistic principle that is a touchstone of complexity and found in the description and mathematics of quantum mechanics, describes the relation of emergent qualitative attributes [Smith and Bahill, 2010], as contrasted with incommensurable concrete and logical parts of a system. The principle of complementarity structures natural language descriptions of systems and clarifies discussions in systems engineering and architecting [Smith, 2008]. Complementarity diagrams show qualitative attributes as distinct, yet coexisting with, logical elements, as shown in Figure 1.

Figure 1: Complementary sides of a system
Complementarity in nature gives rise to an infinite interplay between irreconcilably different aspects of reality. Complementarity diagrams reduce the aspects of naturally complementary systems to a perceivable and distinct two-sided description.
Levels of abstraction [Bahill, Szidarovszky, Botta and Smith, 2008] are a primary construct for the descriptions of systems that exhibit encompassing layers. Figure 2 illustrates encompassing levels of abstraction.

Figure 2: Encompassing abstraction levels
Note that the encompassing abstraction is shown at higher levels, but to be fair, the numerous details observable at lower levels could alternatively be shown as encompassing the more vacuous abstract levels. Alternatively, if the upper levels have fuller and greater detail, they are not abstract. Discussions in this paper are facilitated by the depiction of complementarity at different levels of abstraction as shown in Figure 3.

Figure 3: Levels with complementary aspects at different levels of abstraction
At any particular level, the attribute side of the complementarity dual is characterized by the qualities apparent at that level, while the logical side is the collection of concrete logical elements and their interfaces. The influences and effects of qualitative or logical elements on other qualitative or logical elements identified on other levels are diagrammed in Figure 4.

Figure 4: Effects of complementary levels
The effects, by letter label, can be described as follows:

Concrete / Logic relations between adjacent levels:

A, Lower-level concrete/logic elements composing upper-level concrete/logic elements

B, Upper-level concrete/logic elements decomposed into lower-level concrete/logic elements

Qualitative/Attribute relations between adjacent levels:

C, Qualitative attributes are holistically and abstractly combined at the next higher level.

D, Holistically qualitative attribute provides the context (scope) for attribute decomposition.

Complementary relations on same level:

E, Logical elements create holistic attributes at the same level. (Example: Reliability calculated)

F, Attributes set global scope of possibilities and imbue logical elements at same level. (Example: Reliability as a mandated quality )

Additional relations available:

G, Lower-level logic contributing to whole upper level

H, Lower-level attributes contributing to whole upper level

I, Upper-level logic encompassing whole lower level

J, Upper-level attributes encompassing whole lower level

K, Whole level influencing upper-level logic

L, Whole level influencing upper-level attributes

M, Whole level encompassing lower-level logic

N, Whole level encompassing lower-level attributes

Extensive use of this framework has not yet been demonstrated.


Mathematical logic, in its own idealized world, could limit the number of attributes to only two: True and False, which are absolute attributes arising from logic. Such a view leads to the Mathematician’s Credo [Hofstadter, 2007, pp. 120-122]:

(1) X is True because there is a proof of X. – consistency of logical system

(2) X is True and so there is a proof of X. – completeness of logical system

The first statement speaks to the consistency of the logical system – because an inconsistent logical system could contain both the proof and counterproof of X. A related statement is: X is False and so there is no proof of X.

The second statement speaks to the completeness of a logical system; that is, the logical system does contain a proof for all true Xs, and no proof for false Xs. The second statement can be re-phrased as: X is False because there is no proof of X.

This perfect alignment of strict bi-directional relations creates tightly-bound dyads between truth and logic, and is illustrated in Figure 5.



Figure 5: Idealized, perfect correspondence in mathematics
Historically, the effort to uncover this perfect alignment between truth and presence of proof, and between falsity and the absence of proof, was memorialized in the movement to axiomatize all of mathematics, beginning with the axiomatization of arithmetic. The climax of this movement was the appearance of Principia Mathematica, published 1910-1913 as the magnum opus of Bertrand Russell and Alfred North Whitehead. Principia Mathematica sought to implement this perfect alignment between truth and logic, with seed axioms producing all true theorems, and of course, no untruths [Hofstadter, 2007, p. 129].

Kurt Gödel (1906-1978), Austrian logician, mathematician and philosopher, ultimately proved that such a tight binding is not possible. Gödel’s theorem utilizes the conceptual framework of complementary mathematical languages at different levels of abstraction, as will be illustrated. “The utterly shocking import of Gödel’s theorem … is that the mighty edifice of mathematics is ultimately built on sand, because the nexus between proof and truth is demonstrably shaky. The problem that Gödel uncovered is that in mathematics, and in fact in almost all formal systems of reasoning, statements can be true yet unprovable – not just unproved, but unprovable, even in principle” [Davies, 2007, p. vi]. A seemingly tight binding between qualitative attributes and logical proofs in mathematics is made more complex by reference in mathematics to many more qualities and attributes besides True and False, for example, strength, soundness, adequacy, and well-formedness. Logical mathematics cannot advance without sophisticated perception of a plethora of qualitative attributes, as memorialized by Leibniz:

Sans les mathématiques on ne pénètre point au fond de la philosophie.

Sans la philosophie on ne pénètre point au fond des mathématiques.

Sans les deux on ne pénètre au fond de rien.” — Leibniz

(Without mathematics we cannot penetrate deeply into philosophy.

Without philosophy we cannot penetrate deeply into mathematics.

Without both we cannot penetrate deeply into anything.)

1686 Discours de Métaphysique [Montgomery, 1962]
Expressive systems employ complementary semantic and syntactic sides.

Specifically, the system must have quality-expressive semantics, and must be logically expressive in syntactic terms as illustrated in Figure 6.



Figure 6: Semantics and Syntactics in an expressive system
A parallel can be drawn to the validation of a system – in that the system holistically satisfies the totality of customer needs – and the verification of specific logical requirements.
Self-Reference can only occur where a higher level system encompasses a lower-level system. Self-Reference is possible when syntactic terms in a lower-level expressive system typographically refer to syntactic and semantic terms that only properly exist in a more abstract, encompassing and higher-level expressive system. Reference to any holistic quality of a lower-level system, from within the lower level system, can only truly occur with a reference to the holistic total quality emergent and fully sensed only at a higher level, as illustrated in Figure 7.

Figure 7: Self-Reference: Typographic terms referring to “System 2” from within System 2 truly refer to holistic (qualitative and logical) terms that only make full sense within a higher-level System 1
Some examples of self-reference within a systems engineering enterprise include: 1, A requirements database for an industry program contains the requirement: “This program shall remain within schedule.”, and, 2, A Systems Modeling Language (SysML) context block within a diagram referring to the “entire design process.”

Self-Reference is produced often, effortlessly and almost without notice in the human mind, and can be easily written into systems engineering documents. Cognizance of the occurrence of self-reference is vital to the production of properly organized systems engineering design materials. For example, unnoticed self-reference in a systemic decomposition can quickly and erroneously insert, in lower levels of the decomposition, elements of the design that simply do not exist at lower-levels of the decomposition – for example, high-level attributes. Such errors often result because the human mind – even when supposedly focused only on lower decomposition levels, has easy access to the total system, and quickly generates terms that refer to the total system.

Self-referring expressions imply the integration of an entire system. Systems engineering vaunts the practice of integrating systems; consequently, self-reference to the totality of a system is typical within the many languages of systems engineering. As an example: Systems engineering processes that shape entire systems are often referenced within systems engineering documents. Therefore, this question can be asked: How can integrative efforts be improved by recognition of the concept and practice of self-reference within natural and system-theoretic languages?

Complexity exists wherever a self-reference has been made. In addition to the previously noted three (3) succinct mathematical indices of complexity, self-reference also indicates the presence of a complex situation. Note the concept of self-reference was only reachable in this introductory section after developing two concepts which are complex – 1, complementarity, and 2, levels of abstraction which imply emergence.

Self-reference gives rise to the possibility of infinite self-reference in a series of loops. “In short, there are surprising new structures that looping [self-reference] gives rise to that constitute a new level of reality that could in principle be deduced from the basic loop and its detailed properties, but that in practice have a different kind of “life of their own” and that demand – at least when it comes to extremely finite, simplicity-seeking, pattern-loving creatures like us – a new vocabulary and a new level of description that transcend the basic level of out of which they emerge” [Hofstadter, 2007, p. 71].

Self-reference is arguably the beginning of self-awareness. In lieu of a definition and discussion of self-awareness, the description of a Universal Turing Machine, which can observe and model itself, can be examined:

“Inspired by Gödel’s mapping of PM [Principia Mathematica] into itself, Alan Turing realized that the critical threshold for this kind of computational universality comes at exactly that point where a machine is flexible enough to read and correctly interpret a set of data that describe its own structure. At this crucial juncture, a machine can, in principle, explicitly watch how it does any particular task, step by step. Turing realized that a machine that has this critical level of flexibility can imitate any other machine, no matter how complex the latter is. Universality is as far as you can go!” [Hofstadter, 2007, p. 242].
Fractals, vivid illustrations of mathematical complexity, are generated by self-reference. For example, the Mandelbrot Set, is generated by the iterative application of the mathematical feedback loop:

.

A complex number, c, is in the Mandelbrot set if, when starting with z0 = 0 and applying the iteration repeatedly, the absolute value of zn never exceeds a certain number that depends on c. When computed and graphed on a complex plane, the Mandelbrot set is seen to have an elaborate boundary which does not simplify at any given magnification. This qualifies the boundary as a fractal – a touchstone of complexity.


As a prelude to outlining Gödel’s Theorems, this paper now turns to the explanation of paradoxes via the application of the previously illustrated concepts of complementarity, levels, and self-reference. The insights gained are then applied to the current taxonomy of systems engineering methods.

2, PARADOXES CLARIFIED
“Much work in the foundations of mathematics has been motivated by the need to resolve the philosophically disquieting situation created by the discovery of the paradoxes” [Resnik, 1988, p. 115]. Paradoxes produce mutually exclusive and incommensurate outcomes when different initial assumptions are applied. Paradoxes in expressive systems occur in the presence of:

1, Self-reference -- by means of syntactic and semantic duality, or,

2, Self-reference – by syntactic logic alone.

The second case involves the use of only syntactic terms at different levels, and possibly the suppression of semantic qualities. Varela [1975] provided purely logical notations for self-reference. On the exclusively qualitative side, it would be interesting to see a paradox couched solely in semantic terms. Actually the complete separation of syntactic and semantic elements may only be an approximation to reality.


Liar Paradox: “This statement is false.”

“Gödel’s original proof of the incompleteness theorem is based on the paradox of the liar” [Chaitin, 2007, p. 49]. The Liar Paradox refers to itself in two complementary ways: The Liar’s Paradox, with the syntactic terms ‘this statement,’ makes reference to the whole Liar Statement – which can only be comprehended from a higher syntactic level. The syntactic term ‘false’ refers to the quality False – which can only characterize the whole statement from a higher attribute level. A complementary levels diagram of the Liar Paradox appears in Figure 8, where the reasoning that gives rise to the paradox is also indicated.



Figure 8: Liar Paradox depicted in complementary levels, with sequence developing from left to right
The diagram shows that the top-level assumption of the quality of False affects the attribute of equal in the lower-level, causing the reversal of the syntactic “=” sign into a “≠” sign. The ramification of this reversal is that the statement as a whole now has to be semantically acknowledged as True – causing a contradiction with the original assumption of False at the top-level. A similar sequence of events leads from a global top-level assumption of True, through the lower-level syntax, to a global conclusion of qualitative False – a contradiction.

Consider the statement, “This system never works,” which could be generated by a system-diagnostic sub-system, perhaps within a huge software application. The statement, “This system never works,” in fact creates a self-referential loop similar to the Liar Statement. A person standing aside from the system, making the same statement, would not create a self-referential loop. Note that the Liar Paradox statement “This statement is false” was initially reduced to the logical form: “This statement = false.” “Is” was converted to “=” which has the binary opposite “≠”. Consider what happens when the conversion of the statement “This system always works” to logical form does not create a logical binary. This is shown in Figure 9.



Figure 9: Logical ambiguity in a syntactic term prevents a paradox
For the statement, “This system always works,” the syntactic element chosen for questioning was “always,” which is an absolute that can be diametrically denied with its conversion either to the absolute “never,” or avoided with its conversion to the ambiguous word “sometimes” – which avoids a paradox. Note that the quality False could also apply to ‘this system’ or ‘works.’
Cantor’s Paradox in Infinite Sets: “There is no greatest cardinal number.”

Cantor’s Paradox is proven by disproving its opposite: “There is a greatest cardinal number C.” If there is a cardinal number C, then there is a greater logical entity Set C on a higher level, and there is a still greater logical entity Power Set 2C on a higher level. By Cantor’s Theorem, the Power Set 2C has a cardinality strictly larger than that of C. This reasoning ultimately leads to the conclusion that the collection of “infinite sizes” is itself infinite – a perpetual reference to larger sets at higher levels. Note that no semantic elements enter into the proof, which is shown in Figure 10.



Figure 10: Cantor’s Paradox proved with three (3) logical levels
Cantor’s Paradox involves infinitistic reasoning – which is arguably a prelude to semantic meaning. Cantor’s Paradox is sometimes called an antinomy, a word used by Immanuel Kant in reference to transcending spheres.
Russell’s Paradox

‘Classes seem to be of two kinds [giving rise to the definitions]:

[1,] those which do not contain themselves as members [ = normal],

(class of mathematicians is not a mathematician)

[2,] those which do [ = non-normal]

(class of ‘all thinkable things’ is itself thinkable)’ [Nagel and Newman, 2001, p. 23].

Suppose N is a class of all normal classes.

Is N a normal class itself?



  • If N is normal, then it is non-normal

  • If N is non-normal, then it is normal.

Russell’s Antimony can be elucidated with the set diagrams in Figure 11.

Figure 11: Russell’s Antimony illustrated
Decomposition is used to analyze the assumptions first made, and the secondary distinctions which give rise to the paradox. Note that Russell’s Paradox corresponds to a decomposition which cannot occur, because of the non-separate-ability of the tree branches.
Russell’s Loop in Set Theory: “The set of all sets that don’t contain themselves.”

Russell’s loop is legitimate in set theory but also a self-contradiction that led Russell to develop a Theory of Types, a …

“novel kind of set theory in which a definition of a set could never invoke that set, and moreover, in which a strict linguistic hierarchy was set up, rigidly preventing any sentence from referring to itself. In Principia Mathematica, there was to be no twisting-back of sets on themselves, no turning-back of language upon itself. If some formal language has a word like ‘word’, that word could not refer to or apply to itself, but only to entities on the levels below itself.”

This seems a “pathological retreat from common sense, as well as from the fascination of loops. What on earth could be wrong with the word ‘word’ being a member of the category ‘word’?”[Hofstadter, 2007, p. 61].

Herein is seen the broad utility of decomposition hierarchies in systems engineering: Prevention of self-reference and the exclusion of complexity.
Barber Paradox: “Village barber shaves all those in the village who don’t shave themselves.”

Russell converted his contradictory loop in set theory to the more colloquial Barber Paradox. The Barber Paradox, although it at first seems an ideal candidate for decomposition, results in a paradox when separate decomposition branches end up commingled, as Figure 12 shows.



Figure 12: Barber’s Paradox, commingling of separate decomposition branches
The caveat here for systems engineering is that a decomposition that is not perfect leaves open the possibility for paradox.
Richardian Paradox

Let us define y as Richardian when y does not have the property designated by the defining expression with which y is correlated in a serially ordered set of definitions.

Thus,

1 – Property1 (if 1 has Property1, 1 is not Richardian)



2 – Property2 (if 2 does not have Property2, 2 is Richardian)

What happens when the definition of property x Richardian is reached? Figure 13 illustrates.




Figure 13: Fallacious Richardian mapping
Gödel avoided the fallacious mapping used in the Richardian Paradox [Nagel and Newman, 2001, p. 66].
Syntactic Paradoxes and Non-Linear Logic [Goff, 2006]

Goff [2006] has demonstrated that when a paradox is confined to purely logical syntax, the logic can be diagrammed in digital electric circuit notation, embodying Non-Linear Logic (NNL). Such a circuit will oscillate between contradictory conclusions as the conclusions are fed back into the circuit as inputs. Given initial conditions, chaotic attractors characterize the future states of the feedback logic circuit.

Goff [2006, p. 5] gives a representation of the flipping result, True to False and False to True, as a NOT gate with feedback to itself, as seen in Figure 14.

Figure 14: True and False conclusions alternate in this digital logic circuit with feedback
Note that this picture does not show all the syntax and semantics of the Liar Paradox, it only models the flipping conclusion.
“Smullyan [1994] created a series of self-referential logic puzzles based in Sanity Land where there is a tight relationship between sanity (S), belief (B), and matter of fact (M). There are two types of people in Sanity Land, the sane and the insane. The sane believe matters of fact while the insane do not. Similarly, the insane do believe in false matters of fact while the sane do not. In NLL, this basic relationship is represented as a flip-flop composed of two COMPARATOR (NOT XOR) gates with the free inputs tied together. The tied input is the matter of fact, the two outputs sanity and belief.

We’ll only consider one of Smullyan’s puzzles, his first one, “What is the situation for a patient who believes that not both he and his doctor are sane?” The matters of fact are the doctor’s sanity (D), that not both are sane (M) the patient’s belief (B) which by the puzzle is true, and his sanity (S). The NLL expression, circuit, and attractor structure are shown in [Figure 15]. The node number is a binary interpretation of DMBS (8-4-2-1). For example, node 5 (0101) implies an insane doctor, not both sane, patient insane but believes that not both he and the doctor are sane. Node 5 has node 6 as a successor, (and vice versa) so this combination is paradoxical.



[Figure 15: Non-linear logic circuit models a syntactic paradox]

One of Smullyan’s Sanity Land puzzles


If the doctor is sane, the patient’s belief is either paradoxical or false, not true as given. The only attractor that meets the criteria is the singlet with node 7. The binary representation of node seven reveals that the doctor is insane, the patient sane, not both are sane, and the patient believes that. This is precisely the answer that Smullyan gives. However, instead of reasoning to it, NLL permits the answer to be computed” [Goff, 2006, p. 8].
Self-Referential logic allows for the contradiction-free expression of paradoxes within logic – because the feedback circuit simply cycles among different states according to a clock. NNL employs only logical terms and conditions -- in contrast to Gödel’s Theorems, which straddle the complementary aspects of logic and qualities that require ‘infinite definitions.’

3, Gödel’s Theorems explained
This section recasts the development and proof of Gödel’s Theorems in terms of complementarity. “For Gödel, the distinction between intuitions and rigorous proof was always vividly clear. … it was the unavoidability of that very distinction that ha[s] been so strongly suggested by his famous proof” [Goldstein, 2005, p. 204]. “The text of his dissertation (1929) already exhibits the concise clarity that was to become a hallmark of Gödel’s writings. Following his introductory remarks, Gödel describes the details of the formalism to be employed and makes precise the terminology he will use. He takes particular care to distinguish semantic from syntactic notions, as of course he must” [Dawson, 1997, p. 56].

This section also employs the concepts of levels of abstraction and self-reference. “Gödel’s paper is difficult. Forty-six preliminary definitions, together with several important preliminary propositions, must be mastered before the main results are reached. We shall take a much easier road; nevertheless, it should afford the reader glimpses of the ascent and of the crowning structure.” [Nagel and Newman, 2001, p. 68]. The following is only an graphical outline of the rigorous proof.

Principia Mathematica logically described a progressing syntactic axiomatic derivation of mathematics, developed by mechanical symbol shunting, which becomes a rather lifeless formalization divorced from the intuitiveness of the real numbers. Principia Mathematica came to be a “labyrinthine palace of mindless, mechanical, symbol-churning, meaning-lacking mechanical reasoning” [Hofstadter, 2007, p. 130]. Figure 16 shows that Principia Mathematica is really only the syntactic side of mathematics.

Figure 16: Complementary Mathematics versus syntactic Principia Mathematica
Russell & Whitehead saw Principia Mathematica as an ultimately complete and consistent description of all of mathematics. Gödel proved that Principia Mathematica was incomplete, and would always be incomplete, no matter how many more axioms and logical rules were added to Principia Mathematica.

“Wittgenstein (e.g. in his Lectures on the Foundations of Mathematics, Cambridge 1939) criticised Principia on various grounds, such as:

• It purports to reveal the fundamental basis for arithmetic. However, it is our everyday arithmetical practices such as counting which are fundamental; for if a persistent discrepancy arose between counting and Principia, this would be treated as evidence of an error in Principia (e.g. that Principia did not characterize numbers or addition correctly), not as evidence of an error in everyday counting.

• The calculating methods in Principia can only be used in practice with very small numbers. To calculate using large numbers (e.g. billions), the formulae would become too long, and some short-cut method would have to be used, which would no doubt rely on everyday techniques such as counting (or else on non-fundamental - and hence questionable - methods such as induction). So again Principia depends on everyday techniques, not vice versa.

However Wittgenstein did concede that Principia may nonetheless make some aspects of everyday arithmetic clearer.” [Wikipedia, 2010]
Interestingly, Gödel was a Platonist, a believer in perfect mathematical truths whose purity derived from transcendent, perfect archetypes in the heavens. “Gödel’s philosophy of mathematics, Casti and DePauli make clear, was one of extreme Platonic Realism. He thought mathematical objects such as numbers, triangles, and even Cantor’s transfinite sets, are as real and independent of human thoughts, though in a different way, as pebbles and planets” [Gardner, 2003, p. 70]. Perhaps only with such an ideology could someone derive an exacting logical proof about formal systems and their incompleteness because of a lack of mathematical complementarity.
Meta-Mathematics: Patently Complementary

In order to embody the paradoxical statement necessary for his proofs, Gödel ascended a level in abstraction to the realm of Meta-Mathematics, where complementary statements, including both syntactic and semantic parts, are more easily invoked and expressed. It is evident that Meta-Mathematics approaches the free expressiveness of natural language, which describes the whole of the universe from the human perspective. If Gödel could construct a consistent and reversible mapping from Meta-Mathematics to Mathematics, it would demonstrate that Mathematics is not only logical but also ineffably semantic. The mapping would prove that Mathematics is complementary, even though this is not always obvious. For his proofs, it was sufficient to work with Arithmetic – which is based on the natural numbers and simple counting. “PM” is Gödel’s (relatively undeveloped) collection of syntactic representations of Arithmetic, and is employed in his proofs. The hierarchical relation of the complete complementary levels of Meta-Mathematics, Mathematics, Arithmetic is shown in Figure 17.



Figure 17: Arithmetics, Mathematics and the more abstract Meta-Mathematics as complete and complementary systems – with both syntactic and semantic sides -- at different levels of abstraction
Principia Mathematica embodied the attempt to describe Mathematics solely syntactically. In order to show the incompleteness of Principia Mathematica in relation to Mathematics, Gödel worked with the analogous relation between PM and Arithmetic, proving that holistic complementary statements are expressible in Arithmetic, but not in PM – which is incomplete like Principia Mathematica.

Gödel’s ultimately employed a complementary Meta-Mathematical statement, whose syntax is: “This statement is un-provable,” with includes both syntactical parts and the absolute semantic quality of “un-provability.” Note that “un-provability” can be seen as both an unquestionable, absolute top-down attribute with the purely semantic quality of “un-provability,” or as a logical conclusion deduced from exhaustive logical syntactic reasoning. Gödel had the task of proving that the sentence “This statement is un-provable” could be mapped to Arithmetic, but not to PM. Curiously, the mapping employed the help of PM’s purely syntactic symbols. Gödel’s mapping would ultimately show that Arithmetics is a complementary system like Meta-Mathematics, but that PM is purely syntactic. Gödel’s mapping is graphically shown in Figure 18.



Figure 18: Gödel mapping between Meta-Mathematics and Arithmetics, with the aid of the syntactic PM
Gödel Numbering: Mapping Meta-Mathematics to Arithmetic

Gödel accomplished the coding of a Meta-Mathematical statement within Arithmetics with the aid of Gödel Numbering, which transferred Meta-Mathematical reasoning squarely into the domain of the natural numbers.

Interestingly, Gödel numbering is only possible with the aid of the typographically rigorous PM, whose elementary signs form a fundamental vocabulary, similar that found in Principia Mathematica. The typographical vocabulary is first used to express primitive Axioms, from which Theorems are derived with the help of a limited number of Rules of Inference. Note that the goal of Principia Mathematica, and PM, was to formalize mathematics by: 1, first devising a empty and meaningless computation system that could mechanically arrive at all inferences available from an original set of axiomatic expressions, and, 2, secondly, endowing the axiomatic expression with the meaning of the axioms of mathematics.

“Gödel first showed that it is possible to assign a unique number to each elementary sign, each formula (or sequence of signs), and each proof (or finite sequence of formulas). This number, which serves as a distinctive tag or label, is called the “Gödel number” of the sign, formula, or proof” [Nagel and Newman, 2001, p. 69]. Table 1 from Nagel and Newman [2001, p. 70] illustrates.




Constant Sign

Gödel Number

Usual Meaning


~

1

Not

V

2

Or



3

If … Then …



4

There is an …

+

5

Equals

0

6

Zero

S

7

Immediate Successor of

(

8

Punctuation Mark

)

9

Punctuation Mark

,

10

Punctuation Mark

+

11

Plus

×

12

Minus

Table 1: Gödel number corresponding to signs of PM, with usual meanings


Variables are assigned prime numbers greater than 12, as seen in Table 2.


Numerical Variable

Gödel number

A possible substitution instance

X

13

0

Y

17

s0

Z

19

Y

Table 2: Variables and their Gödel numbers [Nagel and Newman, 2001, p. 74]


Sentential variables are assigned the squares of prime numbers greater than 12, as seen in Table 3.


Sentential Variable

Gödel number

A possible substitution instance

P

132

0 = 0

Q

172

(∃ x) (x = sy)

R

192

p q

Table 3: Sentential variables and associated square of a prime number [Nagel and Newman, 2001, p. 74]


Predicate variables are assigned the cubes of prime numbers greater than 12, as seen in Table 4.


Predicate Variable

Gödel number

A possible substitution instance

P

133

x = sy

Q

173

~ (x = ss0 × y)

R

193

(∃x) (x = y + sz)

Table 4: Predicate variables and associated cube of a prime number [Nagel and Newman, 2001, p. 75]


Consider the example formula: (Ex)(x = sy), for which each symbol is associated with a Gödel number in Table 5.


(

E

x

)

(

x

=

S

y

)





















8

4

13

9

8

13

5

7

17

9

Table 5: Typographical symbols with corresponding Gödel numbers [Nagel and Newman, 2001, p. 75]


Next, each prime number in an ordered sequence of all prime number beginning with two (2), is raised to the power of the corresponding Gödel number:
28 × 34 × 513 × 79 × 118 × 1313 × 175 × 197 × 2317 × 299 = 1.4105 × 1023
Therefore, every formula is associated with a unique number, and every number can be factored into prime numbers, whose numerical quantities indicate the sequence of signs which compose its underlying formula. In this way, any written Meta-Mathematical statement, and thus any string of symbols, is arithmetized.

“Since every [syntactic] expression in PM is associated with a particular (Gödel) number, a meta-mathematical statement about formal expressions and their typographical relations to one another may be constructed as a statement about the corresponding (Gödel) numbers and their arithmetical relations to one another. In this way meta-mathematics becomes completely ‘arithmetized’.” (Nagel, p. 80). The mapping in fact shows that the complementarity that exists in meta-mathematics, which is basically semi-formal natural language talk about mathematics, also exists in the seemingly-bare but actually very rich mathematics and arithmetics.

Note that no Meta-Mathematical statement can be arithmetized unless it is well-formed according the typographical relations of PM [Hofstadter, 2007, p. 133]. The fact that Gödel Numbering is impossible without PM is remarkable, generally indicating that precise descriptions will always need to be based in typography. Mathematics, or any other complementary, dualistic whole, may always need to be precisely described by it formal logical part. “The famous technique of Gödel numbering statements was but one of the many ingenious ideas brought to bear by Gödel to construct a number-theoretic assertion which says of itself that it is unprovable” [Chaitin, 2007, p. 49].
Self-Referential Gödel Statement: “This statement is un-provable within PM”

In order to understand Gödel’s proof, review the Liar Paradox statement, in which the typographical ‘this statement’ and ‘false’ are both on the syntactic side of one complementary level, with the paradox arising with the consideration of semantic truth or falsity of the entire statement arising on a higher level.

To get to the heart of the complementarity of syntax and semantic meaning, Gödel showed that a sufficiently developed PM could make the statement: “This statement is unprovable.” Note that ‘unprovability’ is an attribute that can arise in two different ways: 1, unprovability can be determined by exhaustive logical attempts to prove a statement, or, 2, unprovability can be posited ‘from above’ as an unquestioningly existing attribute. “Provability” thus includes the two sides of complementarity, and with a paradoxical statement, provides the opportunity to prove significant truths about complementarity.

Reasoning from the Gödel Statement follows two assumptions:

[1] If the word ‘unprovable’ has the attribute correct, then the Gödel’s statement as a whole has the attribute of True, and PM, that is, the formalization of number theory in question, is Incomplete because a true but unprovable statement has been found within PM. In the words of Kurt Gödel: “So the proposition which is undecidable in the system PM yet turns out to be decided by metamathematical considerations” [1962, p. 41].

[2] If the word ‘unprovable’ is incorrect, then the Gödel’s statement as a whole has the attribute of False, and PM is Inconsistent, because PM expressed an inconsistent statement.

The cruxes of these arguments are summarized in Figure 19.

Figure 19: Complementary levels show assumptions and reasoning of Gödel’s proofs


Thus, Gödel’s conclusion was that PM is always either incomplete or inconsistent.

“The original proof was quite intricate, much like a long program in machine language” [Chaitin, 2007, p. 49]. In fact, Gödel’s Statement is wrapped within Gödel’s Statement, because the syntax ‘statement’ can be replaced with the entire Gödel’s Statement – creating a potentially infinite regress! Note that this encapsulation and self-reference to the entire Gödel Statement indicates that PM is capable referring to its own structure. Gödel’s conclusions, however, can be understood by just considering the Gödel Statement once, as described above.

Gödel’s Incompleteness conclusion ultimately rests on the fact that Gödel’s Statement is understandable within Meta-Mathematics, and through the Gödel Mapping exists in Arithmetic, but is not demonstrable within PM. Gödel’s Consistency conclusion ultimately shows that the consistency of PM is not provable within PM; that is, PM cannot prove own consistency. Gödel 's Theorems prove that all but the most simple axiomatic systems for mathematics are either incomplete or inconsistent.

Gödel theorems ultimately comment on systems that are powerful enough to describe themselves by self-reference. “No one before Gödel had realized that one of the domains that mathematics can model is the doing of mathematics itself” [Hofstadter, 2007, p. 161]. Mathematics is thus able to examine itself, as a Universal Turing Machine can, and, through typographical translations, is able to simulate anything. Breaking out of the restriction of the logical side of complementarity remains a computer science challenge. One of the ultimate goals in computer science is to reach meta-programming by creating a meta-language, capable of self-reference, subjective self-reflection and self-modification.



4, Application to Systems Engineering & SysML Modeling
The relations among meta-mathematics, mathematics and arithmetics elucidate analogous relationships among systems-of-systems, systems and components, which are described, for example, by natural language, system languages such as the Systems Modeling Language (SysML), and diagrammatical syntax, respectively. This is shown in Figure 20.

Figure 20: Complementary levels in a systems hierarchy
Natural language is cable of expressing abstract concepts with semantic meaning through syntactic symbols. Systems engineering languages, such as SysML, also abstractly describe systems, and have both syntactic and semantic sides, with strict constraints placed on semantic meanings. Note an analogy to the Gödel proof: System-of-Systems realities can be mapped into Systems with the help of the strict typographical notation available in SysML. The strictness of SysML syntactic rules mimic rules in Russell’s Theory of Types, allowing no self-reference, with reference only to things below. On the semantic side, relations among the attributes at different levels of abstraction form a hierarchical decomposition of qualities.

Formalized, axiomatic and strongly syntactic system languages are beset by the weakness that they cannot describe the complementarity inherent in the whole of systems. For example, with such methods, the following analogies to the Gödel's Statement arise:

1, This (complementary) system-of-system cannot be described in natural language syntax.

2, Natural language syntax is incomplete as a description of systems-of-systems, or can reach inconsistent conclusions about systems-of-systems.

1, This (complementary) system cannot be described with SysML syntax.

2, SysML is either incomplete as a description of real systems, or can reach inconsistent conclusions about real systems.

Some related conclusions include:


  • This project is unmanageable as expressed in formal management methods.

  • Formal management methods are either incomplete or inconsistent in describing projects.

  • This system is not describable in terms of well-formed requirements.

  • Well-formed requirements are either incomplete or inconsistent as a system description.

  • This system architecture is not describe-able with the Department of Defense Architectural Framework (DoDAF).

  • DoDAF is either incomplete or inconsistent as a description of system architecture.

  • Processes can be expressed as formal process flows.

  • Formal process flows are either incomplete or inconsistent in modeling real processes.

Interestingly, although Systems Engineering often sees itself as encompassing and superseding traditional engineering disciplines, the analogy of Gödel Numbering indicates that System Engineering can be mapped to Traditional Engineering. Further, just as the Gödel Mapping could not be accomplished without the rigorous syntax of PM, the mapping between systems engineering and traditional engineering can only be made rigorous with the aid of the formalized typographical language of precise engineering analysis. See Figure 21.

Figure 21: ‘Gödel Mapping’ of systems engineering
Similarly, System Science can only be mapped to Systems Engineering with the well-formed typography of SysML, which allows precise system descriptions. As a caveat, note that assertions in systems engineering are not provable without recourse to rigorous syntactic rules.

Beade [2000] talks about complexity in term of system boundaries. Beade indicates that if the system boundary can be identified, the system can be exactly decomposed and understood logically. This is the same as saying a system can be described by an outside observer, but not by the system itself employing self-reference. In fact, a reference by the system to itself makes the system boundary uncertain, allowing real complexity to enter the system description, including the location of the system boundary as well as the erstwhile unquestioned decompositions. See Figure 22.



Figure 22: Boundaries and decompositions in light of reference originating either extrinsically or intrinsically
Self-reference necessarily reintroduces the complexity of complementarity into system descriptions. A hierarchical nested set theory can only describe systems adequately under analogous conditions to in which the Theory of Types holds, and any such system description will be either incomplete or inconsistent.


5, Conclusions
Eliminating self-reference is a first step in forcing a complementary complex system into an axiomatized description; however, the description will always be either incomplete or inconsistent. If the system is consistent, there will be truths within the system that it cannot prove. If the system makes reference to its own consistency, then it is provably inconsistent. An example lies in voting systems. Arrow’s Impossibility Theorem proves that a consistent voting system is incomplete as to fairness (a semantic attribute); further, a voting system that claims to be consistent can be shown to be inconsistent.

Gödel proofs indicate that the nature of reality is complementary. Complex system understanding can be increased when systems are described with complementarity recurring at each level of abstraction. A holistic and levels-based complementary framework, consisting of both qualitative and quantitative sides, is capable of conceptualizing self-reference. Mappings can translate the description of a complementary system into an adjacent level of abstraction, provided that the adjacent level is complementary and sufficiently expressive. A rigorous mapping will rely on a rigorously syntax.

Degradation of a system or system description occurs when it is reduced to either its syntactic or semantic side. Awareness of such degradation is an important leading indicator of system understanding, and consequently of system capability. An example is the qualitative description of a discrete square ‘wave,’ where a perfect Fourier Series description of a square wave requires an infinite summation of component waves. Just as a wavelike description can never truly create a discrete object, logic can never truly describe qualitative attributes. Emergence and complementarity are also related through Gödel’s Theorems. The existence of a logical argument that seems to lead to a qualitatively emergent attribute is elusive, and, contrariwise, the existence of a qualitative attribute does not guarantee a logical explanation. Also, a self-referential claim that the consistency of an axiomatic system will preclude emergence indicates, prima facie, that the system is inconsistent.

Gödel’s Theorems are stated in different ways in different literature, indicating that Gödel’s conclusions are general and abstract. In the final analysis, although the syntax and semantic meaning of Gödel’s Proof has been approved and time-honored by communities of logicians and mathematicians, perhaps there is room to question the precise matching of the syntactical notations to meanings. Note that any reading of the proof involves pre-existing, orthodox interpretations of the meanings of each symbol, and the subsequent use of such interpretations in driving toward the final conclusion. Every bit of notation used by Gödel is subject to a human interpretation which may not be stable under re-interpretation. Once any reasonable uncertainty occurs, the precise form of the proof is open to modification, and may lead to the situation that previously dry syntactical parts may become imbued with meaning just as parts that were exclusively semantic may become solely products of logic.

Systems thinking is facilitated by awareness of both the logical and qualitative sides of complementarity. Humans easily shift, sometimes exclusively or extremely, from qualitative to logical reasoning without being aware of the dichotomy between the mediums of thought. Often, the separation between the semantic and syntactic sides of complementarity is fuzzy, unless forced by an adamant observer.

References
A. T. Bahill, F. Szidarovszky, R. Botta, and E. D. Smith, Valid models require defined levels, International Journal of General Systems 37(5) (2008), 553-571.

D. M. Buede, The engineering design of systems: Models and methods, John Wiley and Sons, Inc., New York, 2000.

G. J. Chaitin, Thinking about Gödel and Turing: Essays on complexity, 1970 - 2007, World Scientific, London, 2007.

P. Davies, "Foreword," in Thinking about Gödel and Turing: Essays on Complexity, 1970-2007, World Scientific, Singapore, 2007, pp. v-xi.

J. W. J. Dawson, Logical dilemmas: The life and work of Kurt Gödel, A. K. Peters, Wellesley, MA, 1997.

M. Gardner, Are universes thicker than blackberries? Discourse on Gödel, magic hexagrams, little red riding hood, and other mathematical and pseudoscientific topics, W. W. Norton & Company, New York, 2003.

K. Gödel, On formally undecidable propositions of Principia Mathematica and related systems, Basic Books Inc., New York, 1962.

A. Goff, Nonlinear logic (NLL) -- Making sense out of logical self reference, 42nd Joint Propulsion Conference, 2006.

R. Goldstein, Incompleteness: The proof and paradox of Kurt Gödel, Atlas Books, New York, 2005.

D. Hofstadter, I am a strange loop, Basic Books, New York, 2007.

G. R. Montgomery (Editor), Discourse on metaphysics, Open Court Publishing Co., La Salle, 1962.

E. Nagel, and J. R. Newman, Gödel's proof, New York University Press, New York, 2001.

M. D. Resnik, "On the philosophical significance of consistency proofs," in Gödel's theorem in focus, S.G. Shanker (Editor), Croom Helm, New York, 1988, pp. 115-130.

E. D. Smith, Complementarity in systems architecting, Conference on systems engineering research (CSER), 2008.

E. D. Smith, and A. T. Bahill, Attribute substitution in systems engineering, Systems Engineering 13(2) (2010).

R. Smullyan, Diagonalization and self-reference, Oxford University Press, New York, 1994.

F. J. Varela, A calculus for self-reference, International Journal of General Systems 2 (1975), 5-24.

J. N. Warfield, Understanding complexity: Thought and behavior, AJAR Publishing Company, Palm Harbor, FL, 2002.



Wikipedia, "Principia Mathematica," 2010. Retrieved May 2010 from Wikimedia Foundation:
Yüklə 0,53 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©www.genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə