T-norm fuzzy logics

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/T-norm_fuzzy_logics 

T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called t-norms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning.

T-norm fuzzy logics belong in broader classes of fuzzy logics and many-valued logics. In order to generate a well-behaved implication, the t-norms are usually required to be left-continuous; logics of left-continuous t-norms further belong in the class of substructural logics, among which they are marked with the validity of the law of prelinearity, (A → B) ∨ (B → A). Both propositional and first-order (or higher-order) t-norm fuzzy logics, as well as their expansions by modal and other operators, are studied. Logics that restrict the t-norm semantics to a subset of the real unit interval (for example, finitely valued Łukasiewicz logics) are usually included in the class as well.

Important examples of t-norm fuzzy logics are monoidal t-norm logic MTL of all left-continuous t-norms, basic logic BL of all continuous t-norms, product fuzzy logic of the product t-norm, or the nilpotent minimum logic of the nilpotent minimum t-norm. Some independently motivated logics belong among t-norm fuzzy logics, too, for example Łukasiewicz logic (which is the logic of the Łukasiewicz t-norm) or Gödel–Dummett logic (which is the logic of the minimum t-norm).

Motivation

As members of the family of fuzzy logics, t-norm fuzzy logics primarily aim at generalizing classical two-valued logic by admitting intermediary truth values between 1 (truth) and 0 (falsity) representing degrees of truth of propositions. The degrees are assumed to be real numbers from the unit interval [0, 1]. In propositional t-norm fuzzy logics, propositional connectives are stipulated to be truth-functional, that is, the truth value of a complex proposition formed by a propositional connective from some constituent propositions is a function (called the truth function of the connective) of the truth values of the constituent propositions. The truth functions operate on the set of truth degrees (in the standard semantics, on the [0, 1] interval); thus the truth function of an n-ary propositional connective c is a function F_c: [0, 1]ⁿ → [0, 1]. Truth functions generalize truth tables of propositional connectives known from classical logic to operate on the larger system of truth values.

T-norm fuzzy logics impose certain natural constraints on the truth function of conjunction. The truth function ${\displaystyle *\colon [0,1]^{2}\to [0,1]}$ of conjunction is assumed to satisfy the following conditions:

• Commutativity, that is, ${\displaystyle x*y=y*x}$ for all x and y in [0, 1]. This expresses the assumption that the order of fuzzy propositions is immaterial in conjunction, even if intermediary truth degrees are admitted.
• Associativity, that is, ${\displaystyle (x*y)*z=x*(y*z)}$ for all x, y, and z in [0, 1]. This expresses the assumption that the order of performing conjunction is immaterial, even if intermediary truth degrees are admitted.
• Monotony, that is, if ${\displaystyle x\leq y}$ then ${\displaystyle x*z\leq y*z}$ for all x, y, and z in [0, 1]. This expresses the assumption that increasing the truth degree of a conjunct should not decrease the truth degree of the conjunction.
• Neutrality of 1, that is, ${\displaystyle 1*x=x}$ for all x in [0, 1]. This assumption corresponds to regarding the truth degree 1 as full truth, conjunction with which does not decrease the truth value of the other conjunct. Together with the previous conditions this condition ensures that also ${\displaystyle 0*x=0}$ for all x in [0, 1], which corresponds to regarding the truth degree 0 as full falsity, conjunction with which is always fully false.
• Continuity of the function ${\displaystyle *}$ (the previous conditions reduce this requirement to the continuity in either argument). Informally this expresses the assumption that microscopic changes of the truth degrees of conjuncts should not result in a macroscopic change of the truth degree of their conjunction. This condition, among other things, ensures a good behavior of (residual) implication derived from conjunction; to ensure the good behavior, however, left-continuity (in either argument) of the function ${\displaystyle *}$ is sufficient. In general t-norm fuzzy logics, therefore, only left-continuity of ${\displaystyle *}$ is required, which expresses the assumption that a microscopic decrease of the truth degree of a conjunct should not macroscopically decrease the truth degree of conjunction.

These assumptions make the truth function of conjunction a left-continuous t-norm, which explains the name of the family of fuzzy logics (t-norm based). Particular logics of the family can make further assumptions about the behavior of conjunction (for example, Gödel logic requires its idempotence) or other connectives (for example, the logic IMTL (involutive monoidal t-norm logic) requires the involutiveness of negation).

All left-continuous t-norms ${\displaystyle *}$ have a unique residuum, that is, a binary function ${\displaystyle \Rightarrow }$ such that for all x, y, and z in [0, 1],

${\displaystyle x*y\leq z}$ if and only if ${\displaystyle x\leq y\Rightarrow z.}$

The residuum of a left-continuous t-norm can explicitly be defined as

${\displaystyle (x\Rightarrow y)=\sup\{z\mid z*x\leq y\}.}$

This ensures that the residuum is the pointwise largest function such that for all x and y,

${\displaystyle x*(x\Rightarrow y)\leq y.}$

The latter can be interpreted as a fuzzy version of the modus ponens rule of inference. The residuum of a left-continuous t-norm thus can be characterized as the weakest function that makes the fuzzy modus ponens valid, which makes it a suitable truth function for implication in fuzzy logic. Left-continuity of the t-norm is the necessary and sufficient condition for this relationship between a t-norm conjunction and its residual implication to hold.

Truth functions of further propositional connectives can be defined by means of the t-norm and its residuum, for instance the residual negation ${\displaystyle \neg x=(x\Rightarrow 0)}$ or bi-residual equivalence ${\displaystyle x\Leftrightarrow y=(x\Rightarrow y)*(y\Rightarrow x).}$ Truth functions of propositional connectives may also be introduced by additional definitions: the most usual ones are the minimum (which plays a role of another conjunctive connective), the maximum (which plays a role of a disjunctive connective), or the Baaz Delta operator, defined in [0, 1] as ${\displaystyle \Delta x=1}$ if ${\displaystyle x=1}$ and ${\displaystyle \Delta x=0}$ otherwise. In this way, a left-continuous t-norm, its residuum, and the truth functions of additional propositional connectives determine the truth values of complex propositional formulae in [0, 1].

Formulae that always evaluate to 1 are called tautologies with respect to the given left-continuous t-norm ${\displaystyle *,}$ or ${\displaystyle *{\mbox{-}}}$tautologies. The set of all ${\displaystyle *{\mbox{-}}}$tautologies is called the logic of the t-norm ${\displaystyle *,}$ as these formulae represent the laws of fuzzy logic (determined by the t-norm) that hold (to degree 1) regardless of the truth degrees of atomic formulae. Some formulae are tautologies with respect to a larger class of left-continuous t-norms; the set of such formulae is called the logic of the class. Important t-norm logics are the logics of particular t-norms or classes of t-norms, for example:

• Łukasiewicz logic is the logic of the Łukasiewicz t-norm ${\displaystyle x*y=\max(x+y-1,0)}$
• Gödel–Dummett logic is the logic of the minimum t-norm ${\displaystyle x*y=\min(x,y)}$
• Product fuzzy logic is the logic of the product t-norm ${\displaystyle x*y=x\cdot y}$
• Monoidal t-norm logic MTL is the logic of (the class of) all left-continuous t-norms
• Basic fuzzy logic BL is the logic of (the class of) all continuous t-norms

It turns out that many logics of particular t-norms and classes of t-norms are axiomatizable. The completeness theorem of the axiomatic system with respect to the corresponding t-norm semantics on [0, 1] is then called the standard completeness of the logic. Besides the standard real-valued semantics on [0, 1], the logics are sound and complete with respect to general algebraic semantics, formed by suitable classes of prelinear commutative bounded integral residuated lattices.

History

Some particular t-norm fuzzy logics have been introduced and investigated long before the family was recognized (even before the notions of fuzzy logic or t-norm emerged):

• Łukasiewicz logic (the logic of the Łukasiewicz t-norm) was originally defined by Jan Łukasiewicz (1920) as a three-valued logic; it was later generalized to n-valued (for all finite n) as well as infinitely-many-valued variants, both propositional and first-order.
• Gödel–Dummett logic (the logic of the minimum t-norm) was implicit in Gödel's 1932 proof of infinite-valuedness of intuitionistic logic. Later (1959) it was explicitly studied by Dummett who proved a completeness theorem for the logic.

A systematic study of particular t-norm fuzzy logics and their classes began with Hájek's (1998) monograph Metamathematics of Fuzzy Logic, which presented the notion of the logic of a continuous t-norm, the logics of the three basic continuous t-norms (Łukasiewicz, Gödel, and product), and the 'basic' fuzzy logic BL of all continuous t-norms (all of them both propositional and first-order). The book also started the investigation of fuzzy logics as non-classical logics with Hilbert-style calculi, algebraic semantics, and metamathematical properties known from other logics (completeness theorems, deduction theorems, complexity, etc.).

Since then, a plethora of t-norm fuzzy logics have been introduced and their metamathematical properties have been investigated. Some of the most important t-norm fuzzy logics were introduced in 2001, by Esteva and Godo (MTL, IMTL, SMTL, NM, WNM), Esteva, Godo, and Montagna (propositional ŁΠ), and Cintula (first-order ŁΠ).

Logical language

The logical vocabulary of propositional t-norm fuzzy logics standardly comprises the following connectives:

• Implication ${\displaystyle \rightarrow }$ (binary). In the context of other than t-norm-based fuzzy logics, the t-norm-based implication is sometimes called residual implication or R-implication, as its standard semantics is the residuum of the t-norm that realizes strong conjunction.
• Strong conjunction ${\displaystyle \And }$ (binary). In the context of substructural logics, the sign ${\displaystyle \otimes }$ and the names group, intensional, multiplicative, or parallel conjunction are often used for strong conjunction.
• Weak conjunction ${\displaystyle \wedge }$ (binary), also called lattice conjunction (as it is always realized by the lattice operation of meet in algebraic semantics). In the context of substructural logics, the names additive, extensional, or comparative conjunction are sometimes used for lattice conjunction. In the logic BL and its extensions (though not in t-norm logics in general), weak conjunction is definable in terms of implication and strong conjunction, by

${\displaystyle A\wedge B\equiv A{\mathbin {\And }}(A\rightarrow B).}$

The presence of two conjunction connectives is a common feature of contraction-free substructural logics.

• Bottom ${\displaystyle \bot }$ (nullary); ${\displaystyle 0}$ or ${\displaystyle {\overline {0}}}$ are common alternative signs and zero a common alternative name for the propositional constant (as the constants bottom and zero of substructural logics coincide in t-norm fuzzy logics). The proposition ${\displaystyle \bot }$ represents the falsity or absurdum and corresponds to the classical truth value false.
• Negation ${\displaystyle \neg }$ (unary), sometimes called residual negation if other negation connectives are considered, as it is defined from the residual implication by the reductio ad absurdum:

${\displaystyle \neg A\equiv A\rightarrow \bot }$

• Equivalence ${\displaystyle \leftrightarrow }$ (binary), defined as

${\displaystyle A\leftrightarrow B\equiv (A\rightarrow B)\wedge (B\rightarrow A)}$

In t-norm logics, the definition is equivalent to ${\displaystyle (A\rightarrow B){\mathbin {\And }}(B\rightarrow A).}$

• (Weak) disjunction ${\displaystyle \vee }$ (binary), also called lattice disjunction (as it is always realized by the lattice operation of join in algebraic semantics). In t-norm logics it is definable in terms of other connectives as

${\displaystyle A\vee B\equiv ((A\rightarrow B)\rightarrow B)\wedge ((B\rightarrow A)\rightarrow A)}$

• Top ${\displaystyle \top }$ (nullary), also called one and denoted by ${\displaystyle 1}$ or ${\displaystyle {\overline {1}}}$ (as the constants top and zero of substructural logics coincide in t-norm fuzzy logics). The proposition ${\displaystyle \top }$ corresponds to the classical truth value true and can in t-norm logics be defined as

${\displaystyle \top \equiv \bot \rightarrow \bot .}$

Some propositional t-norm logics add further propositional connectives to the above language, most often the following ones:

• The Delta connective ${\displaystyle \triangle }$ is a unary connective that asserts classical truth of a proposition, as the formulae of the form ${\displaystyle \triangle A}$ behave as in classical logic. Also called the Baaz Delta, as it was first used by Matthias Baaz for Gödel–Dummett logic. The expansion of a t-norm logic ${\displaystyle L}$ by the Delta connective is usually denoted by ${\displaystyle L_{\triangle }.}$
• Truth constants are nullary connectives representing particular truth values between 0 and 1 in the standard real-valued semantics. For the real number ${\displaystyle r}$, the corresponding truth constant is usually denoted by ${\displaystyle {\overline {r}}.}$ Most often, the truth constants for all rational numbers are added. The system of all truth constants in the language is supposed to satisfy the bookkeeping axioms:^[9]

${\displaystyle {\overline {r{\mathbin {\And }}s}}\leftrightarrow ({\overline {r}}{\mathbin {\And }}{\overline {s}}),}$ ${\displaystyle {\overline {r\rightarrow s}}\leftrightarrow ({\overline {r}}{\mathbin {\rightarrow }}{\overline {s}}),}$ etc. for all propositional connectives and all truth constants definable in the language.

• Involutive negation ${\displaystyle \sim }$ (unary) can be added as an additional negation to t-norm logics whose residual negation is not itself involutive, that is, if it does not obey the law of double negation ${\displaystyle \neg \neg A\leftrightarrow A}$. A t-norm logic ${\displaystyle L}$ expanded with involutive negation is usually denoted by ${\displaystyle L_{\sim }}$ and called ${\displaystyle L}$ with involution.
• Strong disjunction ${\displaystyle \oplus }$ (binary). In the context of substructural logics it is also called group, intensional, multiplicative, or parallel disjunction. Even though standard in contraction-free substructural logics, in t-norm fuzzy logics it is usually used only in the presence of involutive negation, which makes it definable (and so axiomatizable) by de Morgan's law from strong conjunction:

${\displaystyle A\oplus B\equiv \mathrm {\sim } (\mathrm {\sim } A{\mathbin {\And }}\mathrm {\sim } B).}$

• Additional t-norm conjunctions and residual implications. Some expressively strong t-norm logics, for instance the logic ŁΠ, have more than one strong conjunction or residual implication in their language. In the standard real-valued semantics, all such strong conjunctions are realized by different t-norms and the residual implications by their residua.

Well-formed formulae of propositional t-norm logics are defined from propositional variables (usually countably many) by the above logical connectives, as usual in propositional logics. In order to save parentheses, it is common to use the following order of precedence:

• Unary connectives (bind most closely)
• Binary connectives other than implication and equivalence
• Implication and equivalence (bind most loosely)

First-order variants of t-norm logics employ the usual logical language of first-order logic with the above propositional connectives and the following quantifiers:

• General quantifier ${\displaystyle \forall }$
• Existential quantifier ${\displaystyle \exists }$

The first-order variant of a propositional t-norm logic ${\displaystyle L}$ is usually denoted by ${\displaystyle L\forall .}$

Semantics

Algebraic semantics is predominantly used for propositional t-norm fuzzy logics, with three main classes of algebras with respect to which a t-norm fuzzy logic ${\displaystyle L}$ is complete:

• General semantics, formed of all ${\displaystyle L}$-algebras — that is, all algebras for which the logic is sound.
• Linear semantics, formed of all linear ${\displaystyle L}$-algebras — that is, all ${\displaystyle L}$-algebras whose lattice order is linear.
• Standard semantics, formed of all standard ${\displaystyle L}$-algebras — that is, all ${\displaystyle L}$-algebras whose lattice reduct is the real unit interval [0, 1] with the usual order. In standard ${\displaystyle L}$-algebras, the interpretation of strong conjunction is a left-continuous t-norm and the interpretation of most propositional connectives is determined by the t-norm (hence the names t-norm-based logics and t-norm ${\displaystyle L}$-algebras, which is also used for ${\displaystyle L}$-algebras on the lattice [0, 1]). In t-norm logics with additional connectives, however, the real-valued interpretation of the additional connectives may be restricted by further conditions for the t-norm algebra to be called standard: for example, in standard ${\displaystyle L_{\sim }}$-algebras of the logic ${\displaystyle L}$ with involution, the interpretation of the additional involutive negation ${\displaystyle \sim }$ is required to be the standard involution ${\displaystyle f_{\sim }(x)=1-x,}$ rather than other involutions that can also interpret ${\displaystyle \sim }$ over t-norm ${\displaystyle L_{\sim }}$-algebras. In general, therefore, the definition of standard t-norm algebras has to be explicitly given for t-norm logics with additional connectives.

Bibliography

• Esteva F. & Godo L., 2001, "Monoidal t-norm based logic: Towards a logic of left-continuous t-norms". Fuzzy Sets and Systems 124: 271–288.
• Flaminio T. & Marchioni E., 2006, T-norm based logics with an independent involutive negation. Fuzzy Sets and Systems 157: 3125–3144.
• Gottwald S. & Hájek P., 2005, Triangular norm based mathematical fuzzy logic. In E.P. Klement & R. Mesiar (eds.), Logical, Algebraic, Analytic and Probabilistic Aspects of Triangular Norms, pp. 275–300. Elsevier, Amsterdam 2005.
• Hájek P., 1998, Metamathematics of Fuzzy Logic. Dordrecht: Kluwer. ISBN 0-7923-5238-6.

 

Kurt Gödel

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Kurt_G%C3%B6del 

Kurt Gödel
Born	Kurt Friedrich Gödel April 28, 1906 Brünn, Austria-Hungary (now Brno, Czech Republic)
Died	January 14, 1978 (aged 71) Princeton, New Jersey, U.S.
Cause of death	Starvation
Citizenship	Czechoslovak Austrian American
Alma mater	University of Vienna
Known for	Gödel's incompleteness theorems Gödel's completeness theorem Gödel's constructible universe Gödel metric (closed timelike curve) Gödel logic Gödel–Dummett logic Gödel's β function Gödel numbering Gödel operation Gödel's speed-up theorem Gödel's ontological proof Gödel–Gentzen translation Von Neumann–Bernays–Gödel set theory ω-consistent theory The consistency of the continuum hypothesis with ZFC Axiom of constructibility Condensation lemma Dialectica interpretation Slingshot argument
Spouse(s)	Adele Nimbursky ​ (m. 1938)​
Awards	Albert Einstein Award (1951) ForMemRS (1968)[1] National Medal of Science (1974)
Scientific career
Fields	Mathematics, mathematical logic, analytic philosophy, physics
Institutions	Institute for Advanced Study
Thesis	Über die Vollständigkeit des Logikkalküls (On the Completeness of the Calculus of Logic) (1929)
Doctoral advisor	Hans Hahn
Signature

Kurt Friedrich Gödel (/ˈɡɜːrdəl/; German: [ˈkʊɐ̯t ˈɡøːdl̩]; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an immense effect upon scientific and philosophical thinking in the 20th century, a time when others such as Bertrand Russell, Alfred North Whitehead, and David Hilbert were using logic and set theory to investigate the foundations of mathematics, building on earlier work by the likes of Richard Dedekind, Georg Cantor and Gottlob Frege.

Gödel published his first incompleteness theorem in 1931 when he was 25 years old, one year after finishing his doctorate at the University of Vienna. The first incompleteness theorem states that for any ω-consistent recursive axiomatic system powerful enough to describe the arithmetic of the natural numbers (for example Peano arithmetic), there are true propositions about the natural numbers that can be neither proved nor disproved from the axioms. To prove this, Gödel developed a technique now known as Gödel numbering, which codes formal expressions as natural numbers. The second incompleteness theorem, which follows from the first, states that the system cannot prove its own consistency.

Gödel also showed that neither the axiom of choice nor the continuum hypothesis can be disproved from the accepted Zermelo-Fraenkel set theory, assuming that its axioms are consistent. The former result opened the door for mathematicians to assume the axiom of choice in their proofs. He also made important contributions to proof theory by clarifying the connections between classical logic, intuitionistic logic, and modal logic.

Early life and education

Childhood

Gödel was born April 28, 1906, in Brünn, Austria-Hungary (now Brno, Czech Republic) into the German-speaking family of Rudolf Gödel (1874–1929), the manager of a textile factory, and Marianne Gödel (née Handschuh, 1879–1966). Throughout his life, Gödel would remain close to his mother; their correspondence was frequent and wide-ranging. At the time of his birth the city had a German-speaking majority which included his parents. His father was Catholic and his mother was Protestant and the children were raised Protestant. The ancestors of Kurt Gödel were often active in Brünn's cultural life. For example, his grandfather Joseph Gödel was a famous singer in his time and for some years a member of the Brünner Männergesangverein (Men's Choral Union of Brünn).

Gödel automatically became a citizen of Czechoslovakia at age 12 when the Austro-Hungarian Empire collapsed following its defeat in the First World War. (According to his classmate Klepetař, like many residents of the predominantly German Sudetenländer, "Gödel considered himself always Austrian and an exile in Czechoslovakia".) In February 1929, he was granted release from his Czechoslovakian citizenship and then, in April, granted Austrian citizenship. When Germany annexed Austria in 1938, Gödel automatically became a German citizen at age 32. In 1948, after World War II, at the age of 42, he became an American citizen.

In his family, the young Gödel was nicknamed Herr Warum ("Mr. Why") because of his insatiable curiosity. According to his brother Rudolf, at the age of six or seven, Kurt suffered from rheumatic fever; he completely recovered, but for the rest of his life he remained convinced that his heart had suffered permanent damage. Beginning at age four, Gödel suffered from "frequent episodes of poor health", which would continue for his entire life.

Gödel attended the Evangelische Volksschule, a Lutheran school in Brünn from 1912 to 1916, and was enrolled in the Deutsches Staats-Realgymnasium from 1916 to 1924, excelling with honors in all his subjects, particularly in mathematics, languages and religion. Although Gödel had first excelled in languages, he later became more interested in history and mathematics. His interest in mathematics increased when in 1920 his older brother Rudolf (born 1902) left for Vienna, where he attended medical school at the University of Vienna. During his teens, Gödel studied Gabelsberger shorthand, Goethe's Theory of Colours and criticisms of Isaac Newton, and the writings of Immanuel Kant.

Studies in Vienna

At the age of 18, Gödel joined his brother at the University of Vienna. By that time, he had already mastered university-level mathematics. Although initially intending to study theoretical physics, he also attended courses on mathematics and philosophy. During this time, he adopted ideas of mathematical realism. He read Kant's Metaphysische Anfangsgründe der Naturwissenschaft, and participated in the Vienna Circle with Moritz Schlick, Hans Hahn, and Rudolf Carnap. Gödel then studied number theory, but when he took part in a seminar run by Moritz Schlick which studied Bertrand Russell's book Introduction to Mathematical Philosophy, he became interested in mathematical logic. According to Gödel, mathematical logic was "a science prior to all others, which contains the ideas and principles underlying all sciences."

Attending a lecture by David Hilbert in Bologna on completeness and consistency in mathematical systems may have set Gödel's life course. In 1928, Hilbert and Wilhelm Ackermann published Grundzüge der theoretischen Logik (Principles of Mathematical Logic), an introduction to first-order logic in which the problem of completeness was posed: "Are the axioms of a formal system sufficient to derive every statement that is true in all models of the system?"

This problem became the topic that Gödel chose for his doctoral work. In 1929, at the age of 23, he completed his doctoral dissertation under Hans Hahn's supervision. In it, he established his eponymous completeness theorem regarding the first-order predicate calculus. He was awarded his doctorate in 1930, and his thesis (accompanied by some additional work) was published by the Vienna Academy of Science.

Career

Incompleteness theorem

Kurt Gödel's achievement in modern logic is singular and monumental—indeed it is more than a monument, it is a landmark which will remain visible far in space and time. ... The subject of logic has certainly completely changed its nature and possibilities with Gödel's achievement.

— John von Neumann

In 1930 Gödel attended the Second Conference on the Epistemology of the Exact Sciences, held in Königsberg, 5–7 September. Here he delivered his incompleteness theorems.

Gödel published his incompleteness theorems in Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (called in English "On Formally Undecidable Propositions of Principia Mathematica and Related Systems"). In that article, he proved for any computable axiomatic system that is powerful enough to describe the arithmetic of the natural numbers (e.g., the Peano axioms or Zermelo–Fraenkel set theory with the axiom of choice), that:

1. If a (logical or axiomatic formal) system is omega-consistent, it cannot be syntactically complete.
2. The consistency of axioms cannot be proved within their own system.

These theorems ended a half-century of attempts, beginning with the work of Frege and culminating in Principia Mathematica and Hilbert's formalism, to find a set of axioms sufficient for all mathematics.

In hindsight, the basic idea at the heart of the incompleteness theorem is rather simple. Gödel essentially constructed a formula that claims that it is unprovable in a given formal system. If it were provable, it would be false. Thus there will always be at least one true but unprovable statement. That is, for any computably enumerable set of axioms for arithmetic (that is, a set that can in principle be printed out by an idealized computer with unlimited resources), there is a formula that is true of arithmetic, but which is not provable in that system. To make this precise, however, Gödel needed to produce a method to encode (as natural numbers) statements, proofs, and the concept of provability; he did this using a process known as Gödel numbering.

In his two-page paper Zum intuitionistischen Aussagenkalkül (1932) Gödel refuted the finite-valuedness of intuitionistic logic. In the proof, he implicitly used what has later become known as Gödel–Dummett intermediate logic (or Gödel fuzzy logic).

Mid-1930s: further work and U.S. visits

Gödel earned his habilitation at Vienna in 1932, and in 1933 he became a Privatdozent (unpaid lecturer) there. In 1933 Adolf Hitler came to power in Germany, and over the following years the Nazis rose in influence in Austria, and among Vienna's mathematicians. In June 1936, Moritz Schlick, whose seminar had aroused Gödel's interest in logic, was assassinated by one of his former students, Johann Nelböck. This triggered "a severe nervous crisis" in Gödel. He developed paranoid symptoms, including a fear of being poisoned, and spent several months in a sanitarium for nervous diseases.

In 1933, Gödel first traveled to the U.S., where he met Albert Einstein, who became a good friend. He delivered an address to the annual meeting of the American Mathematical Society. During this year, Gödel also developed the ideas of computability and recursive functions to the point where he was able to present a lecture on general recursive functions and the concept of truth. This work was developed in number theory, using Gödel numbering.

In 1934, Gödel gave a series of lectures at the Institute for Advanced Study (IAS) in Princeton, New Jersey, entitled On undecidable propositions of formal mathematical systems. Stephen Kleene, who had just completed his PhD at Princeton, took notes of these lectures that have been subsequently published.

Gödel visited the IAS again in the autumn of 1935. The travelling and the hard work had exhausted him and the next year he took a break to recover from a depressive episode. He returned to teaching in 1937. During this time, he worked on the proof of consistency of the axiom of choice and of the continuum hypothesis; he went on to show that these hypotheses cannot be disproved from the common system of axioms of set theory.

He married Adele Nimbursky [es; ast] (née Porkert, 1899–1981), whom he had known for over 10 years, on September 20, 1938. Gödel's parents had opposed their relationship because she was a divorced dancer, six years older than he was.

Subsequently, he left for another visit to the United States, spending the autumn of 1938 at the IAS and publishing Consistency of the axiom of choice and of the generalized continuum-hypothesis with the axioms of set theory, a classic of modern mathematics. In that work he introduced the constructible universe, a model of set theory in which the only sets that exist are those that can be constructed from simpler sets. Gödel showed that both the axiom of choice (AC) and the generalized continuum hypothesis (GCH) are true in the constructible universe, and therefore must be consistent with the Zermelo–Fraenkel axioms for set theory (ZF). This result has had considerable consequences for working mathematicians, as it means they can assume the axiom of choice when proving the Hahn–Banach theorem. Paul Cohen later constructed a model of ZF in which AC and GCH are false; together these proofs mean that AC and GCH are independent of the ZF axioms for set theory.

Gödel spent the spring of 1939 at the University of Notre Dame.

Princeton, Einstein, U.S. citizenship

After the Anschluss on 12 March 1938, Austria had become a part of Nazi Germany. Germany abolished the title Privatdozent, so Gödel had to apply for a different position under the new order. His former association with Jewish members of the Vienna Circle, especially with Hahn, weighed against him. The University of Vienna turned his application down.

His predicament intensified when the German army found him fit for conscription. World War II started in September 1939. Before the year was up, Gödel and his wife left Vienna for Princeton. To avoid the difficulty of an Atlantic crossing, the Gödels took the Trans-Siberian Railway to the Pacific, sailed from Japan to San Francisco (which they reached on March 4, 1940), then crossed the US by train to Princeton. There Gödel accepted a position at the Institute for Advanced Study (IAS), which he had previously visited during 1933–34.

Albert Einstein was also living at Princeton during this time. Gödel and Einstein developed a strong friendship, and were known to take long walks together to and from the Institute for Advanced Study. The nature of their conversations was a mystery to the other Institute members. Economist Oskar Morgenstern recounts that toward the end of his life Einstein confided that his "own work no longer meant much, that he came to the Institute merely ... to have the privilege of walking home with Gödel".

Gödel and his wife, Adele, spent the summer of 1942 in Blue Hill, Maine, at the Blue Hill Inn at the top of the bay. Gödel was not merely vacationing but had a very productive summer of work. Using Heft 15 [volume 15] of Gödel's still-unpublished Arbeitshefte [working notebooks], John W. Dawson Jr. conjectures that Gödel discovered a proof for the independence of the axiom of choice from finite type theory, a weakened form of set theory, while in Blue Hill in 1942. Gödel's close friend Hao Wang supports this conjecture, noting that Gödel's Blue Hill notebooks contain his most extensive treatment of the problem.

On December 5, 1947, Einstein and Morgenstern accompanied Gödel to his U.S. citizenship exam, where they acted as witnesses. Gödel had confided in them that he had discovered an inconsistency in the U.S. Constitution that could allow the U.S. to become a dictatorship; this has since been dubbed Gödel's Loophole. Einstein and Morgenstern were concerned that their friend's unpredictable behavior might jeopardize his application. The judge turned out to be Phillip Forman, who knew Einstein and had administered the oath at Einstein's own citizenship hearing. Everything went smoothly until Forman happened to ask Gödel if he thought a dictatorship like the Nazi regime could happen in the U.S. Gödel then started to explain his discovery to Forman. Forman understood what was going on, cut Gödel off, and moved the hearing on to other questions and a routine conclusion.

Gödel became a permanent member of the Institute for Advanced Study at Princeton in 1946. Around this time he stopped publishing, though he continued to work. He became a full professor at the Institute in 1953 and an emeritus professor in 1976.

During his time at the Institute, Gödel's interests turned to philosophy and physics. In 1949, he demonstrated the existence of solutions involving closed timelike curves, to Einstein's field equations in general relativity. He is said to have given this elaboration to Einstein as a present for his 70th birthday. His "rotating universes" would allow time travel to the past and caused Einstein to have doubts about his own theory. His solutions are known as the Gödel metric (an exact solution of the Einstein field equation).

He studied and admired the works of Gottfried Leibniz, but came to believe that a hostile conspiracy had caused some of Leibniz's works to be suppressed. To a lesser extent he studied Immanuel Kant and Edmund Husserl. In the early 1970s, Gödel circulated among his friends an elaboration of Leibniz's version of Anselm of Canterbury's ontological proof of God's existence. This is now known as Gödel's ontological proof.

Awards and honours

Gödel was awarded (with Julian Schwinger) the first Albert Einstein Award in 1951, and was also awarded the National Medal of Science, in 1974. Gödel was elected a resident member of the American Philosophical Society in 1961 and a Foreign Member of the Royal Society (ForMemRS) in 1968. He was a Plenary Speaker of the ICM in 1950 in Cambridge, Massachusetts. The Gödel Prize, an annual prize for outstanding papers in the area of theoretical computer science, is named after him.

Gravestone of Kurt and Adele Gödel in the Princeton, N.J., cemetery

Later life and death

Later in his life, Gödel suffered periods of mental instability and illness. Following the assassination of his close friend Moritz Schlick, Gödel had an obsessive fear of being poisoned; he would eat only food that his wife, Adele, prepared for him. Late in 1977, she was hospitalized for six months and could subsequently no longer prepare her husband's food. In her absence, he refused to eat, eventually starving to death. He weighed 29 kilograms (65 lb) when he died. His death certificate reported that he died of "malnutrition and inanition caused by personality disturbance" in Princeton Hospital on January 14, 1978. He was buried in Princeton Cemetery. Adele's death followed in 1981.

Personal life

Religious views

Gödel was a theist in the Christian tradition. He believed that God was personal, and called his philosophy "rationalistic, idealistic, optimistic, and theological".

Gödel believed firmly in an afterlife, saying, "Of course this supposes that there are many relationships which today's science and received wisdom haven't any inkling of. But I am convinced of this [the afterlife], independently of any theology." It is "possible today to perceive, by pure reasoning" that it "is entirely consistent with known facts." "If the world is rationally constructed and has meaning, then there must be such a thing [as an afterlife]."

In an unmailed answer to a questionnaire, Gödel described his religion as "baptized Lutheran (but not member of any religious congregation). My belief is theistic, not pantheistic, following Leibniz rather than Spinoza." Of religion(s) in general, he said: "Religions are, for the most part, bad—but religion is not". According to his wife Adele, "Gödel, although he did not go to church, was religious and read the Bible in bed every Sunday morning", while of Islam, he said, "I like Islam: it is a consistent [or consequential] idea of religion and open-minded."

Legacy

The Kurt Gödel Society, founded in 1987, was named in his honor. It is an international organization for the promotion of research in logic, philosophy, and the history of mathematics. The University of Vienna hosts the Kurt Gödel Research Center for Mathematical Logic. The Association for Symbolic Logic has invited an annual Kurt Gödel lecturer each year since 1990. Gödel's Philosophical Notebooks are edited at the Kurt Gödel Research Centre which is situated at the Berlin-Brandenburg Academy of Sciences and Humanities in Germany.

Five volumes of Gödel's collected works have been published. The first two include his publications; the third includes unpublished manuscripts from his Nachlass, and the final two include correspondence.

in 2005 John Dawson published a biography of Gödel, Logical Dilemmas: The Life and Work of Kurt Gödel (A. K. Peters, Wellesley, MA, ISBN 1-56881-256-6). Gödel was also one of four mathematicians examined in David Malone's 2008 BBC documentary Dangerous Knowledge.

Douglas Hofstadter wrote the 1979 book Gödel, Escher, Bach to celebrate the work and ideas of Gödel, M. C. Escher and Johann Sebastian Bach. It partly explores the ramifications of the fact that Gödel's incompleteness theorem can be applied to any Turing-complete computational system, which may include the human brain.

Lou Jacobi plays Gödel in the 1994 film I.Q.

 

The Structure of Science

From Wikipedia, the free encyclopedia

Cover of the first edition
Author	Ernest Nagel
Country	United States
Language	English
Subject	Philosophy of science
Publisher	Harcourt, Brace & World
Publication date	1961
Media type	Print (Hardcover and Paperback)
Pages	618
ISBN	978-0915144716

The Structure of Science: Problems in the Logic of Scientific Explanation is a 1961 book about the philosophy of science by the philosopher Ernest Nagel, in which the author discusses the nature of scientific inquiry with reference to both natural science and social science. Nagel explores the role of reduction in scientific theories and the relationship of wholes to their parts, and also evaluates the views of philosophers such as Isaiah Berlin.

The book received positive reviews, as well as some more mixed assessments. It is considered a classic work, and commentators have praised it for Nagel's discussion of reductionism and holism, as well as for his criticism of Berlin. However, critics of The Structure of Science have found Nagel's discussion of social science less convincing than his discussion of natural science.

Summary

Nagel describes the book as "an essay in the philosophy of science" concerned with "analyzing the logic of scientific inquiry and the logical structure of its intellectual products", adding that it was written for a larger audience than only "professional students of philosophy". He discusses branches of natural science such as physics and social sciences such as history. Topics discussed include the role of reduction in scientific theories and the relationship of wholes to their parts. Nagel also discusses the philosopher of science Henri Poincaré and criticizes the philosopher Isaiah Berlin.

Publication history

The Structure of Science was first published by Harcourt, Brace & World in 1961.

Reception

The Structure of Science is considered a classic work. The book has been praised by philosophers such as Horace Romano Harré, Douglas Hofstadter, Alexander Rosenberg, Isaac Levi, Roger Scruton, and Colin Klein, as well as by the historian Peter Gay and the economists H. Scott Gordon and Grażyna Musiał. It was described by Harré as the "best single book on the philosophy of science". Nagel's discussions of reductionism and holism and teleological and non-telological explanations have been praised by Hofstadter, while his discussion of the "dispute over the nature of theories and theoretical terms" has been praised by Scruton. Klein believed that Nagel, despite flaws in his account of reduction, provided a largely correct account of "intertheoretic connection". While he wrote that discussions of the role of reduction in scientific explanation published after The Structure of Science moved away from Nagel's views because of perceived shortcomings in Nagel's theory, he considered this trend a mistake. Gay considered the book an important and clear exposition of positivism. He credited Nagel with refuting opposing points of view. In 1990, he described the book as one on which "many of us grew up", and stated that it "remains valuable". Gordon credited Nagel with providing the best modern examination of the possibility of establishing a science independent of moral value judgments. However, he was unconvinced by Nagel's conclusion that it is possible to do this in the case of the study of social phenomena. He found Nagel's case that it was possible in the case of the natural sciences more convincing. Musiał wrote that the book was "a source of inspiring conclusions" and is regarded as one of the "fundamental works on the contemporary methodology of science." She added that Nagel's "position left numerous opened questions that were further developed" by other authors. She concluded that The Structure of Science is "still a valuable reading for junior research workers in economics who wish to reinforce their knowledge."

The book received positive reviews from the philosopher A. J. Ayer in Scientific American, the sociologist Otis Dudley Duncan in American Sociological Review, the philosopher G. B. Keene in Philosophy, and the philosopher Michael Scriven in The Review of Metaphysics. The book received mixed reviews from the philosopher Raziel Abelson in Commentary and the philosopher Paul Feyerabend in the British Journal for the Philosophy of Science, and a negative review from William Gilman in The Nation.

Ayer described the book as a well-written work that avoided being overly technical, should have wide appeal, and was an "important contribution toward the essential task of building a bridge between philosophy and science." He credited Nagel with providing a diverse range of examples in his discussion of scientific explanation, and considered his views about geometry and physics, while not novel, to be "sensible and convincing"; he complimented Nagel for his discussion of history and the social sciences, and praised his discussion of "the question of causality and indeterminism." However, he was not fully satisfied by Nagel's discussion of the distinction between a scientific law and a "generalization of fact".

Duncan credited Nagel with clarifying ideas such as those of cause, model, and analogy and demonstrating that at least some sciences can reach a high state of development without resolving all questions about their underlying concepts. He also complimented Nagel's discussions of both reductionism and the social sciences, including history. However, he believed that Nagel should have put more effort into explaining "how explanations of statistical generalizations are effected."

Keene described the book as "an admirable model of methodical inquiry", with only minor defects. He praised Nagel for the thoroughness of his treatment of the nature of scientific inquiry, his discussion of explanation in the biological sciences, his criticism of functionalism in the social sciences, and his discussion of historical explanation. Scriven described the book as a "great work", and considered Nagel's treatment of some subjects definitive. He praised Nagel's discussion of the history of science and careful analysis of "alternative positions", pointing in particular to Nagel's "discussion of the ontological status of theories and models" and "his treatment of fallacious arguments for holism"; he also complimented Nagel for his criticism of Berlin and his discussion of the meaning of scientific laws. However, he noted that the book was not easy to read; he also criticized Nagel for being too willing to accept the analyses of certain concepts proposed by symbolic logicians, for failing to fully pursue the implications of his ideas about scientific practice, giving his treatment of historical explanation as an example. Though he found Nagel's analysis of telological explanations "thorough and enlightening", he was not fully satisfied by Nagel's conclusions about their distinguishing features. He found Nagel's criticism of approaches in the social sciences less convincing than other parts of the book.

Abelson considered the book's publication an important event in American philosophy. He credited Nagel with consolidating the rival insights of logical positivism and pragmatism, demonstrating how four different kinds of explanation function in different types of inquiry, refuting the view that science does nothing more than describe "sequences of phenomena", and convincingly criticizing Berlin. However, he argued that Nagel's account of science was strained and that some of Nagel's views were unclear. He believed that Nagel was less successful in discussing sociology and history than he was in discussing the natural sciences. He also charged Nagel with vacillating between the "mechanistic" view of social knowledge and that of "pragmatic pluralism", arguing that each of these perspectives has merit, but only when adopted with full commitment. Feyerabend credited Nagel with adding significant detail to the "hypothetico-deductive account" of explanation, and with making interesting observations about "the cognitive status of theories." However, he argued that Nagel neglected the larger issue of the "cognitive status of all notions of our language" and that his account of reduction was flawed.

Gilman considered Nagel's objective of helping a wide audience to understand scientific method laudable, but found the book poorly written and repetitive. He suggested that Nagel might have personal reasons for favoring belief in determinism over belief in free will, and criticized him for failing to discuss the relationship between science and "big business". He concluded that, "the reader who mistrusts science will remain mistrustful after reading the book." The book has also been criticized by the philosophers Adolf Grünbaum and Michael Ruse. Grünbaum criticized Nagel for misinterpreting Poincaré, while Ruse maintained that while The Structure of Science was Nagel's "definitive work", the philosopher Thomas Kuhn's The Structure of Scientific Revolutions (1962) discredited its "ahistorical and prescriptive" approach to the philosophy of science.