Namespaces
Variants
Actions

Hilbert 2nd problem

From Encyclopedia of Mathematics
Revision as of 19:11, 24 February 2016 by Whayes43 (talk | contribs)
Jump to: navigation, search

a history of the mathematics preceding and relevant to Hilbert’s statement of his 2nd problem, initiating his program for the foundations of mathematics -- see Hilbert problems

By about 1820, mathematicians had developed deductively a large part of analysis using the real numbers and their properties as a starting point.

During the 50 years that followed, in a program that came to be known as the Arithmetization of analysis, Bolzano, Cauchy, Weierstrass, Dedekind, Cantor, and others succeeded in “reducing” analysis to the arithmetic of natural numbers $\mathbb{N}$.

Dedekind himself expressed this as follows:[1]

... every theorem of algebra and higher analysis, no matter how remote, can be expressed as a theorem about natural numbers, -- a declaration I have heard repeatedly from the lips of Dirichlet.

In the final three decades of the 19th century, efforts were underway to axiomatize the whole of mathematics.[2]

It thus became clear that (with the aid of a certain amount of set theoretic and logical apparatus) the entire body of traditional pure mathematics could be constructed rigorously starting from the theory of natural numbers.

These efforts proceeded piecemeal and depended greatly on concurrent developments in logic. Major contributors were these:

  • in logic: Boole, Peirce, and Frege
  • in set theory: Cantor and Dedekind
  • in arithmetic: Frege, Dedekind, and Peano
  • in geometry: Pasch and Hilbert

In a 1900 lecture to the International Congress of Mathematicians in Paris, David Hilbert presented a list of open problems in mathematics. The 2nd of these problems, known variously as the compatibility of the arithmetical axioms and the consistency of arithmetic, served as an introduction to his program for the foundations of mathematics.

The article views the 30-year period from 1872 to 1900 as historical background to Hilbert’s program for the foundations of mathematics. There are other, different and equally interesting views of this same period:

  • as a continuation and, indeed, culmination of the previous half-century (1822-1872) during which “mathematicians restored and surpassed the standards of rigour” that had long been established, but then neglected, the whole 80-year period called “the formalisation of mathematics.”[3]
  • as the first half of the decades-long effort (1872-193X) “from the days of Cantor and Dedekind in the 1870s, through Russell in the 1900s, to the work of Godel in the 1930s” that resulted in the solid establishment of “the modern discipline of foundations.”[4]

However viewed, this 30-year period, from the construction of the real numbers to the Hilbert Problems address, saw “mathematicians of the first rank” engaged with these questions:[5]

  • the character of the infinite
  • the relationship between logic and arithmetic
  • the status of geometry
  • the nature of mathematics itself

For a history of the subsequent development of Hilbert’s program for the foundations of mathematics, which was initiated by his 2nd problem, see the article Hilbert program.

Non-mathematical issues

As is the case for other, especially older programs and periods of mathematics, the history of Hilbert’s program was complicated by non-mathematical issues.[6] Some authors were slow to publish their results; others published only selectively, leaving some important results to be published by students and successors. The works of still others, though published, were partially or completely ignored.

As a first example, consider the work of Galileo. His concerns about the “paradoxical” property of infinite sets are often mentioned in published discussions of the potentially infinite and the actually infinite. Yet, even today, doubts are expressed about whether or not Galileo had influence either on Cantor, the mathematician whose name is most often and most closely associated with the notion of infinite sets, or on any other mathematician.[7]

Further, consider Gauss’ well-known comment about actual infinities and Cantor’s “answer” -- made 55 years later:

  • Gauss (in a letter dated 1831): I protest against the use of infinite magnitude as something completed, which in mathematics is never permissible. Infinity is merely a facon de parler, the real meaning being a limit which certain ratios approach indefinitely near, while others are permitted to increase without restriction.
  • Cantor (in an article dated 1886): I answered [Gauss] thoroughly, and on this point did not accept the authority of Gauss, which I respect so highly in all other areas ...

There is some doubt even today about whether we really understand either Gauss’ comment or Cantor’s response.[8]

Again, consider the work of Bolzano. His paper “Paradoxes of the Infinite” contains some remarkable results related to the theory of infinite sets:[9]

  • the word “set” appears here for the first time
  • examples of 1-1 correspondences between the elements of an infinite set and the elements of a proper subset

Yet Bolzano himself never published these results. The paper itself was not published until 1851, three years after his death, by one of his students. Further, Cantor appears not to have become aware of Bolzano’s paper until 1882, some years after he began his own work on infinite sets, which was motivated by the Arithmetization of analysis. Nor did Cantor mention Bolzano's paper in his own work until 1883[10] A related historical anomaly is that while Bolzano both knew of and referred to Galileo’s work on the infinite, Cantor did neither.[11]

C S Peirce may hold the record in this regard, having made the following “discoveries in formal logic and foundational mathematics, nearly all of which came to be appreciated only long after he died”:[12]

  • In 1860, years before Cantor, “he suggested a cardinal arithmetic for infinite numbers.”
  • In 1880–81, anticipating Sheffer by 33 years, he invented the Peirce arrow, a binary operator (logical NOR: “(neither) … nor …”) sufficient in itself for Boolean algebra.
  • In 1881, he set out the axiomatization of natural number arithmetic, a few years before Dedekind and Peano.
  • In the same paper, years before Dedekind, he gave the first purely cardinal definition of a "Dedekind-finite" set and an (implied) formal definition of a “Dedekind-infinite” set, i.e., one that can be put into a one-to-one correspondence with one of its proper subsets.
  • In 1885, he distinguished between first-order and second-order quantification
  • In the same paper, anticipating Zermelo by about two decades, he set out what can be read as a (primitive) axiomatic set theory.

The achievements of Christine Ladd-Franklin in the algebra of logic provide a further, unsettling example of outstanding work not only ignored in the past by logicians, but also forgotten in the present by historians of logic:[13]

In 1883, while a student of C. S. Peirce at Johns Hopkins University, Christine Ladd-Franklin published a paper titled “On the Algebra of Logic,” in which she develops an elegant and powerful test for the validity of syllogisms that constitutes the most significant advance in syllogistic logic in two thousand years.

That her work was overlooked probably resulted, in part, from the simple fact that she was a woman. The extent to which the lack of attention to Ladd-Franklin’s work was gender-related is evidenced by this additional, unhappy fact:[14]

Ladd-Franklin had completed all the requirements for the Ph.D. at Johns Hopkins University by 1882, [but] since the university did not admit women, she was not awarded the degree until 1926.

As a final example, consider that Frege’s work “seems to have been largely ignored by his contemporaries.”[15][16]

  • Three [of six] reviews of the “revolutionary” Begriffsschrift,” including one by no less than Venn, show that their authors were either uninterested in Frege's innovations or had completely misunderstood them.
  • The Grundlagen only received a single review, and that one was “a devastatingly hostile” one, by Cantor, whose ideas were [ironically] the closest to Frege's.
  • Die Grundgesetze der Arithmetik … except for one review by Peano, was ignored by his contemporaries.

It was not until Russell acknowledged Frege’s work as the trailblazing foundation for the Principia that the greatness of his accomplishment was recognized.[17] Russell himself contrasted the greatness of Frege’s contributions with the limited nature of his influence among his contemporaries as follows:[18]

In spite of the epoch-making nature of [Frege's] discoveries, he remained wholly without recognition until I drew attention to him in 1903.

As a consequence of these and other non-mathematical issues, some mathematical results in the period under examination were achieved multiple times, albeit in slightly different forms or using somewhat different methods, by different authors. Even without the effects of such issues, the mathematics of the past (both long- and recent-past) is still replete with achievements that are said to be “roughly” or “more or less” or “just about” what we know today. About De Morgan’s work on mathematical induction, for example, two types of claims have been made:

  1. that he put a process that had been used without clarity on a rigorous basis[19]
  2. that he introduced and defined the term “mathematical induction” itself[20]

Yet, another source, citing the contents of De Morgan’s own published papers, has refuted both of these claims.[21]

Finally, a note on some quasi-mathematical matters that are purposely not discussed in this article. Without doubt, positions in the philosophy of mathematics known as Logicism, Formalism, and Intuitionism, along with important methodological and epistemological considerations, grew out of the mathematical practice of the late 19th and early 20th centuries.[22] Further, these philosophical positions were of great interest to some mathematicians and certainly influenced the mathematical problems on which they chose to work. Yet a discussion of either the past origins of or the current nature and status of these philosophical positions would not significantly aid our understanding of the mathematics that resulted from the work of those mathematicians.[23]

Much of the existing literature [of the period surrounding the Hilbert Problems address] has been philosophically motivated and preoccupied with the exegesis of individual thinkers, notably Frege and Russell, who are widely (and rightly) viewed as founding giants of analytical philosophy. But the wider mathematical context has in the process often been lost from sight.

A discussion of these philosophical positions is here omitted. It is that “wider mathematical context” on which this article focuses.

Introduction of infinite sets

In mathematics, uses of infinity and the infinite (and great concerns about those uses) are as old as Grecian urns. Greek mathematicians followed Aristotle in dividing such uses into two major types, one called “potential infinity”, the other called “actual infinity.”[24]

With respect to magnitudes:[25]

  • a potential infinity was something endlessly extendible, and yet forever finite;
  • an actual infinity was something such as the number of points on a line.

Similarly, with respect to sets:

  • a potentially infinite set was, for example, a finite collection of numbers that can be enlarged as much as one wished
  • an actually infinite set was, for example, the complete collection of all such natural numbers

Ancient Greek mathematicians developed rigourous methods for using potential infinities. However, with the apparent exception of Archimedes noted below, they avoided using actual infinities.[26] Important early examples of uses of infinity and the infinite include these:

  • Euclid skirted the notion of the actually infinitely large in proving that the primes are potentially infinite. This is how he stated his theorem:[27]
Prime numbers are more than any assigned magnitude of prime numbers.
  • Archimedes, however, appears to have investigated actually infinite numbers of objects:[28]
... certain objects, infinite in number, are "equal in magnitude" to others [implying] that not all such objects, infinite in number, are so equal. ... [thus] infinitely many objects [of] definite, and different magnitudes … are manipulated in a concrete way, apparently by something rather like a one-one correspondence...

Oresme, an early (12th century) mathematician, examined infinite sets using a method prescient of Cantor’s method of one-to-one correspondence. Oresme demonstrated that two actually infinite sets (the set of odd natural numbers and the set of all natural numbers) could be “different” and “unequal” and yet “equinumerous” with one another. He concluded that notions of equal, greater, and less do not apply to the infinite.[29]

Mathematical induction, as a technique for proving the truth of propositions for an infinite (indefinitely large) number of values, was used for hundreds of years before any rigorous formulation of the method was made[30]

Galileo produced the standard one-to-one correspondence between the positive integers and their squares, reminiscent of Oresme’s work. He termed this a “paradox” that results “unavoidably” from the property of infinite sets and concluded, alike with Oresme, that infinite sets are incomparable.[31]

... the totality of all numbers is infinite, and ... the number of squares is infinite; neither is the number of squares less than the totality of all numbers, nor the latter greater than the former; and, finally, the attributes "equal", "greater", and "less" are not applicable to the infinite, but only to finite quantities.

As recently as 1831, Gauss himself argued against the actually infinite:[32]

I protest against the use of infinite magnitude as something completed, which in mathematics is never permissible. Infinity is merely a facon de parler, the real meaning being a limit which certain ratios approach indefinitely near, while others are permitted to increase without restriction.

For the most part, however, mathematicians of the 19th and 20th centuries developed and readily took up methods for using actual infinities that were as rigorous as those the Greeks developed for potential infinities.[33] Certainly Bolzano had no concerns about the “paradoxical” property of infinite sets. Indeed, his theories of mathematical infinity anticipated Cantor's theory of infinite sets. His contribution to the understanding of the nature of the infinite was threefold:[34]

1. he defined the idea of a set
I call a set a collection where the order of its parts is irrelevant and where nothing essential is changed if only the order is changed.
2. he argued that the infinite set does exist
if the integers are a set, then arbitrarily large subsets of integers are subsets of the set of integers, which must itself be actually infinite
3. he gave examples to show that, unlike for finite sets, the elements of an infinite set could be put in 1-1 correspondence with elements of one of its proper subsets.

The actual infinite is said to have entered algebra in the 1850s in Dedekind’s work with quotient constructions for modular arithmetic:[35]

[T]he whole system of infinitely many functions of a variable congruent to each other modulo $p$ behaves here like a single concrete number in number theory.… The system of infinitely many incongruent classes—infinitely many, since the degree may grow indefinitely—corresponds to the series of whole numbers in number theory.

The five-year period 1868–1872 has been called "the birth of set-theoretic mathematics." A salient milestone was 1871, when Dedekind introduced “an essentially set-theoretic viewpoint … using set operations and … structure-preserving mappings … and terminology that Cantor was later (1880) to use in his own work.[36]

By 1872, procedures involving infinite sets were employed in constructions of irrational real numbers developed during the Arithmetization of analysis by Weierstrass, Dedekind, and Cantor. “Thus analysis [had been reduced] not simply to the theory of natural numbers, but to the theory of natural numbers together with the theory of infinite sets.”[37]

The constructions of Cantor and Dedekind especially relied implicitly on set theory and, further, “involve the assumption of a Power Set principle.”[38]

The realization that (apparently) all the material needed for analysis could be constructed out of the natural numbers using set-theoretic means led to these new questions:[39]

  • What further could be said about set-theoretic procedures and assumptions of logic, both of which underlay these accounts of the real numbers?
  • Do we have to take the natural numbers themselves as simply given, or can anything further be said about those numbers, perhaps by reducing them to something even more fundamental?

In the 1870s, the notions of set and class themselves appeared straightforward. Their problematic aspects did not become apparent until Cantor's theory of transfinite numbers gave rise to various paradoxes of set theory.[40]

Early development of mathematical logic

The history of logic has been described, “with some slight degree of oversimplification,” as having three stages: (1) Greek logic, (2) Scholastic logic, and (3) mathematical logic.[41] From ancient times through the first half of the 19th century, the state of logic was as follows:[42][43]

  • logic was understood to be “the laws of thought”
  • the Aristotelian syllogism was the ultimate form of all reasoning
  • the logic that a mathematician used did not affect the mathematics that she did

The mathematical context in which logic developed played a role in its shaping. The broad motives behind its development started a two-phased movement:[44]

  • initially, there was a great expansion in the scope of logic
  • subsequently, a progressive restriction occurred

Both the initial expansion and the subsequent restriction of logic were linked to work in the foundations of mathematics.

The initial expansion of the scope of mathematical logic began during the second half of the 19th century with these two steps:

  1. the algebraization of syllogistic logic
  2. the development of the predicate calculus

Taken together, these steps accomplished the following:

  • they extended the use of symbolism “beyond the subject matter of mathematics, to the reasoning used in mathematics.”[45]
  • they provided “the technical basis for … the transition from informal to formal proof.”[46]

Looking back, these developments may seem to us almost natural, perhaps because we know of their beneficial results. Somewhat concurrently, the scope of mathematical logic expanded a step further to include the theories of sets and of relations.[47] This further development, however, was accompanied by highly unexpected and seriously problematic consequences.

The algebra of logic

The beginning of mathematical logic has been dated from the years in which Boole and De Morgan published their works on the algebraization of Aristotelian logic.[48]

Whereas in [Greek and Scholastic logic] theorems were derived from ordinary language, [mathematical logic] proceeds in a contrary manner—it first constructs a purely formal system, and only later does it look for an interpretation in everyday speech.

Thus, with the advent of mathematical logic, the logic of the syllogism came to be treated as one interpretation of a calculus of logic.

Syllogistic logic

Aristotle’s system of syllogistic logic is closely linked to the grammatical structure of natural language.[49]

A syllogism is a logical argument consisting (usually) of three statements, one of which (the conclusion) is inferred from the other two (the premises).

Here is an Example Syllogism:

All $Greeks$ are $Sapiens$
All $Sapiens$ are $Mortal$
therefore
All $Greeks$ are $Mortal$

Each statement of this syllogism has two parts: a Subject and a Predicate:

the Subject consists of a Quantifier (All, Some, No, or Not All) and a Common Noun
the Predicate consists of a Copula Verb (are) and a Common Noun

We can think of the Common Nouns in the statements of a syllogism either as expressing properties of things or as referring to classes of things that have those properties.

In each syllogism, there is always one Common Noun that occurs in both premises, but not in the conclusion. This Common Noun, which links the two premises of the syllogism, is called the middle term of the syllogism. In the Example Syllogism above, the middle term is the Common Noun “Sapiens”.

A syllogism is valid if the conclusion follows logically from the premises, no matter what Common Nouns are used in its statements; otherwise, the syllogism is invalid. If the syllogism is valid and the premises are true, then the conclusion is true.

The Example Syllogism is valid. Its validity has nothing to do with the particular Common Nouns that are used. If the Common Nouns in the Example Syllogism were replaced by different Common Nouns, the result would still be a valid syllogism. It is the form of the Example Syllogism that makes it valid, not the Common Nouns used in its statements. Replacing the Common Nouns in the Example Syllogism by symbols for classes makes this clear:

All $A$ are $B$
All $B$ are $C$
therefore
All $A$ are $C$

Each statement of a syllogism is one of 4 types, as follows:

Type Statement Alternative
A All $A$ are $B$
E No $A$ are $B$ (= All $A$ are not $B$)
I Some $A$ are $B$
O Not All $A$ are $B$ (= Some $A$ are not $B$)

(In ordinary language, the forms E and O have the alternate forms shown. Note that by introducing an additional Copula Verb are not and using the equivalent forms, we can eliminate the Quantifiers No and Not All, reducing them to just All and Some.)

The statements of the Example Syllogism are all of type A and, therefore, the Example Syllogism itself is said to be of type AAA.

Aristotle hypothesized that all valid syllogisms have something fundamental in common, which he attempted to find. Efforts to do so continued for two millennia. Finally, in 1883, in a volume edited by Peirce himself, Christine Ladd-Franklin published a paper describing a logical system that sufficed to “capture this common feature.”[50] Her system was described as having provided “the definitive solution of the problem of the reduction of syllogism.”[51]

Peacock's and De Morgan’s contributions

Even before Boole’s work, important steps were taken towards the development of a calculus of logic. As early as 1830, Peacock suggested that the symbols for algebraic objects need not be understood only as numbers.[52][53]

'Algebra' … has been termed Universal Arithmetic: but this definition is defective, in as much as it assigns for the general object of the science, what can only be considered as one of its applications.

In his treatise, Peacock distinguished between arithmetical algebra, with laws derived from operations on numbers, and symbolic algebra, which he describes as follows:[54]

the science which treats the combinations of arbitrary signs and symbols by means defined through arbitrary laws…. We may assume any laws for the combination and incorporation of such symbols, so long as our assumptions are independent, and therefore not inconsistent with each other.

In 1847, De Morgan extended Peacock’s vision for a symbolic algebra with the notion that the interpretations of symbols not only for algebraic objects, but also for algebraic operations were arbitrary.[55]

De Morgan’s contribution to logic was twofold. First, he insisted on the purely formal or, as he put it, “symbolic” nature of algebra, the study of which has as it object “symbols and their laws of combination, giving a symbolic algebra which may hereafter become the grammar of a hundred distinct significant algebras.”[56][57] Consider his example of a commutative algebra to which he provided five interpretations, among which are the three listed:[58]

Given symbols $M, N, +$, and one sole relation of combination, namely that $M + N$ is the same as $N + M$:
  1. $M$ and $N$ may be magnitudes, and $+$ the sign of addition of the second to the first
  2. $M$ and $N$ may be numbers, and $+$ the sign of multiplying the first to the second
  3. $M$ and $N$ may be nations, and $+$ the sign of the consequent having fought a battle with the antecedent

De Morgan's second contribution was to clarify the nature of logical validity as “that part of reasoning which depends upon the manner in which inferences are formed…. Whether the premises be true or false, is not a question of logic…. the question of logic is, does the conclusion certainly follow if the premises be true?”[59]

Boole’s algebra of logic

Both Boole and De Morgan were aware of the limitations of syllogistic logic, in particular, that there were inferences known to be valid, but whose validity could not be demonstrated by syllogistic logic. Their intent was to develop “a general method for representing and manipulating all logically valid inferences.”[60] The significant difference in Boole’s approach from De Morgan's was the algebraic methods that Boole adopted.

In 1847, in “a little book that De Morgan himself recognized as epoch-making,” Boole undertook the following:[61][62]

  • the goal: “to express traditional logic more perspicuously using the techniques of algebra” such that deduction becomes calculation
  • the program: to develop an algebraic calculus and show that the doctrines of traditional logic can be expressed using this calculus.

In this early work, Boole extended De Morgan’s view about the formal nature of algebra by presenting the view that the essential character of the whole of mathematics is formal, somewhat as follows:[63]

If any topic is presented in such a way that it consists of symbols and precise rules of operation upon these symbols, subject only to the requirement of inner consistency, this topic is part of mathematics.

In 1854, Boole published a second book, the completion of his efforts “to incorporate logic into mathematics by reducing it to a simple algebra, pointing out the analogy between algebraic symbols and those that represent logical forms, and beginning the algebra of logic that came to be called Boolean algebra.”[64]

Boole eventually gave his uninterpreted calculus three interpretations, in terms of classes, of probabilities, and also of propositions. These various interpretations were possible because of analogies among the concepts of a class, an event, and a statement. As a consequence, the "order" relation in a Boolean algebra can be interpreted variously as set-theoretical inclusion, as causal follow-up of events, as logical follow-up of statements.[65] A modified version of the third interpretation of his calculus became modern propositional logic. This latter is today the lowest level of modern logic, but at the time and in effect, it was all of logic, because it was able to be used for Aristotelian syllogistic logic:[66]

  • it used symbols for statements rather than numbers
  • it defined operations on statements rather than on numbers
  • it defined deductions as equations and as the transformation of equations

Boole’s second (1854) book was an effort “to correct and perfect” his first. He introduced the formalisms of his algebra, including these:[67]

  • Classes were $x, y, z$.
  • There was a universal class $1$ and an empty class $0$.
  • Multiplication $x \cdot y$ was intersection, yielding $x \cdot y = y \cdot x$.
  • Next, he gave the idempotent law $x \cdot x = x$.
  • Addition $x+y$ was aggregation (for $x, y$ disjoint), yielding $x + y = y+x$ and $z(x + y) = z \cdot x + z \cdot y$.
  • Also, $x − y = − y + x$ and $z(x − y) = z \cdot x − z \cdot y$.

Boole did not, however, go on from all of this to build an axiomatic foundation for his algebra of logic. Instead, he introduced three theorems (Expansion, Reduction, Elimination) and used them in his “General Method” for analyzing syllogistic arguments.

Boole's introduction of an Elimination theorem is interesting as an example of his commitment to an algebraic approach to logic. As shown in the Example Syllogism above, the middle term of a syllogism is a Common Noun that occurs in both of the premises. In effect, it links the two other Common Nouns of the syllogism, allowing them to be joined in the conclusion. Observing this, Boole reasoned that syllogistic logic produces a conclusion by eliminating that middle term, so he introduced into his algebra of logic an Elimination theorem, which he borrowed from the ordinary algebraic theory of equations.[68]

The final version of Boole’s method “for analyzing the consequences of propositional premises,” briefly stated, is as follows:[69]

  1. convert (or translate) the premise statements of the syllogism into equations,
  2. apply a prescribed sequence of algebraic processes to the equations, including application of the three theorems mentioned above, yielding equational conclusions
  3. re-convert the equational conclusions back into statements, yielding the desired conclusions of the syllogism.

With this method Boole had replaced the art of reasoning from premise statements to conclusion statements with a routine mechanical algebraic procedure.

Boole showed, with somewhat mixed results, that his algebra provided “an easy algorithm for syllogistic reasoning,” an elementary example of which is as follows:[70][71]

an Aristotelian syllogism of the AAA type:
# Statement Calculation Explanation
(1) $\text{All } A \text{ are } B$ $A \cdot B = A$
(2) $\text{All } B \text{ are } C$ $B \cdot C = B$
(3) $A (B \cdot C) = A$ substituting in (1) the value of $B$ given by (2)
(4) $(A \cdot B)C = A$ applying associative law for multiplication
(5) $\text{All } A \text{ are } C$ $A \cdot C = A$ substituting in (4) the value of $AB$ from (1)

No less than De Morgan himself praised Boole’s work as a remarkable proof that “the symbolic processes of algebra, invented as tools of numerical calculation, [are] competent to express every act of thought, and to furnish the grammar and dictionary of an all-containing system of logic.”[72]

Taken at face value, De Morgan’s praise overstated the adequacy of Boole’s logic of propositions without quantification, in two ways:

  1. it was inadequate to express some important statements of mathematics such as the law of mathematical induction, on which De Morgan himself had worked;
  2. it was also inadequate to express some statements of ordinary language with a form such as, “If all horses are animals, then all heads of horses are heads of animals.”

In fact, this example was De Morgan’s own, intended “to show the inadequacy of traditional logic” and that, for a logic adequate to express this example, “binary relations are essential.”[73] If, however, we take De Morgan’s comment to be about some yet-to-be-developed logic with quantification, then we can accept that his optimism about Boole's calculus was not misplaced.

Jevons and De Morgan’s extensions

For three decades after Boole introduced his calculus in 1847, “most researchers interested in formal logic worked on extending and improving [his] system.”[74]

In 1864, Jevons published an alternative system of algebraic logic, retaining Boole’s use of algebraic equations as the basic form of logical statements, but rejecting Boole’s desire to retain “dependence on” the ordinary algebra of numbers. More generally, Jevons replaced the use of classes (associated with quantity) with predicates (associated with quality).[75]

Both Boole and Jevons understood logic to be an expression of “the laws of thought.” Yet Boole had more of an algebraic concept of logic and saw deduction as calculation, while Jevons argued that mathematics proceeds from logic, seeing calculation as deduction.[76] Further on, we shall see that, alike with Jevons, Frege envisioned logic as a predicate-based foundation to mathematics, though his method of realizing this vision was not algebraic, but axiomatic -- see Frege's predicate logic.

De Morgan himself extended Boole’s calculus with a law of duality that asserts for every theorem involving addition and multiplication, there is a corresponding theorem in which the words addition and multiplication are interchanged.[77]

Interpreted as a logic of classes, we have this:

If $x$ and $y$ are subsets of a set $S$, then
  • the complement of the union of $x$ and $y$ is the intersection of the complements of $x$ and $y$
  • the complement of the intersection of $x$ and $y$ is the union of the complements of $x$ and $y$

Interpreted as a logic of propositions, we have this:

If $p$ and $q$ are propositions, then
  • not $(p$ or $q)$ equals not $p$ and not $q$
  • not $(p$ and $q)$ equals not $p$ or not $q$

C S Peirce’s logic

Peirce was convinced of the general notion that "Mathematics is the science which draws necessary conclusions."[78] Further, he was “committed to the broadly ‘algebraic’ tradition' of his father, Benjamin, and of his colleague, Boole. It is not surprising that, on reading of Frege’s belief that mathematics could be derived from logic, Peirce responded that logic was properly seen as a branch of mathematics, not vice versa.[79]

Though De Morgan had clearly located the inadequacy of syllogistic logic in its inability to express binary relations, he himself lacked “an adequate apparatus for treating the subject.” The title “creator of the theory of relations” has been awarded to C. S. Peirce.[80]

In several papers published between 1870 and 1882, [Peirce] introduced and made precise all the fundamental concepts of the theory of relations and formulated and established its fundamental laws … in a form “much like the calculus of classes developed by G. Boole and W. S. Jevons, but which greatly exceeds it in richness of expression.”

In a series of papers, Peirce introduced his “claw” symbolism $\prec$ and used it to develop his logic of inferences:[81]

  • he defined $\prec$ as follows:
  • $A \prec B$ is explicitly defined as $A$ implies $B$, and
  • $A \overline{\prec} B$ defines $A$ does not imply $B$.
  • he defined illation (material implication or logical inference) as follows:
  • $A \prec A$, whatever $A$ may be.
  • If $A \prec B$, and $B \prec C$, then $A \prec C$.
  • he distinguished universal and particular propositions, affirmative and negative, according to the following scheme:
Type Statement Calculation
A All A are B $a \prec b$
E No A is B $a \prec \bar{b}$
I Some A is B $\bar{a} \prec b$
O Some A is not B $\bar{a} \prec \bar{b}$

By means of all the above, Peirce transformed the Aristotelian syllogism into a hypothetical proposition, “with material implication as its main connective.” For example, he symbolized the syllogistic form AAA of our Example Syllogism (discussed previously) as follows:[82]

If $x \prec y$, and $y \prec z$, then $x \prec z$.

Comparing Peirce’s formalism above with the remarkably similar formalism of the familiar Peano-Russell notation below

$[(x ⊃ y) ⋅ (y ⊃ z)] ⊃ (x ⊃ z)$. it is difficult to conclude other than that “the differences are entirely and solely notational.”'"`UNIQ--ref-00000052-QINU`"' Here is a succinct summary of how syllogistic logic was transformed by the algebraic tradition:'"`UNIQ--ref-00000053-QINU`"' * Aristotle’s syllogistic logic, entirely linguistic, was a ''logic of terms'' that were connected by a ''copula of existence'', expressing the inherence of a property in a subject; * Boole’s formal logic, expressed algebraically, was a ''logic of classes'' that were connected by a ''copula of class inclusion''; * De Morgan’s formal logic, also algebraic, was a ''logic of relations'' whose relata were connected by a ''copula of relations''. * Peirce’s formal logic was a ''logic of inference'' that took in, combined, and went beyond each of these. His terms (of syllogisms), classes, and propositions were connected by a ''copula of illation''. Subsequently, Peirce extended his logic into a predicate calculus by adding a theory of quantification to his logic of relations -- see [[#Peirce.27s logic of quantifiers|Peirce's logic of quantifiers]]. Peirce's work on (binary) relations and quantification was continued and extended in a very thorough and systematic way by Schröder, whose published work of 1895 was lauded in 1941 as “so far the only exhaustive account of the calculus of relations.”'"`UNIQ--ref-00000054-QINU`"' =='"`UNIQ--h-9--QINU`"'Cantor’s early theory of sets== Set theory is the study sets, their properties, and the operations that can be performed on them. It has been especially concerned with sets that have infinitly many elements.'"`UNIQ--ref-00000055-QINU`"' Broadly defined, the term ''naive set theory'' connotes an informal set theory developed in a natural language in which such words as "and", "or", "if ... then", "not", "for some", and "for every" are not rigorously defined. The term includes these various versions of set theory:'"`UNIQ--ref-00000056-QINU`"''"`UNIQ--ref-00000057-QINU`"' # Cantor’s early (pre-1883 ''Grundlagen'') theory of sets # Cantor’s later general theory of sets, the basis of the theory of transfinite numbers # informally developed set theories (axiomatic or otherwise) developed by Dedekind, Peano, and Frege # modern, informally developed versions of an axiomatic set theory, as in ''Naive Set Theory'' by Paul Halmos. This section examines the first of these, namely, Cantor’s early theory of sets. ==='"`UNIQ--h-10--QINU`"'Bolzano’s contribution=== In spite of Cantor’s pre-eminence in the area of set theory, the first to work with sets was Bolzano, as was noted above in [[#Introduction of infinite sets|Introduction of infinite sets]]. It is from him that we have the following early definitions: ::... an embodiment of the idea or concept which we conceive when we regard the arrangement of its parts as a matter of indifference (1847)'"`UNIQ--ref-00000058-QINU`"' ::... an aggregate so conceived that it is indifferent to the arrangement of its parts (1851)'"`UNIQ--ref-00000059-QINU`"' It was also Bolzano who first used the German word ''Menge'' for set, a usage that Cantor himself continued in his theory.'"`UNIQ--ref-0000005A-QINU`"' Despite this, Bolzano’s understanding of the notion of set was incomplete, especially with respect to the important distinction between the element/set relation and the part/whole relation. Consider, as evidence, his use of the word “parts” (''Teile'') to refer to the elements of a set in his description given above.”'"`UNIQ--ref-0000005B-QINU`"' Further, Bolzano thought absurd consideration of a set with only one element, while he failed entirely to consider the null set.'"`UNIQ--ref-0000005C-QINU`"' Nevertheless, it was Bolzano who identified sets as “the carriers of the property finite or infinite in mathematics.”'"`UNIQ--ref-0000005D-QINU`"' ==='"`UNIQ--h-11--QINU`"'Cantor’s discoveries=== Traditional views give to Cantor (not entirely undeservedly) all or most of the credit for having developed set theory: ::naive set theory is primarily due to Cantor'"`UNIQ--ref-0000005E-QINU`"' ::the first development of set theory was a naive set theory … created at the end of the 19th century by Georg Cantor.'"`UNIQ--ref-0000005F-QINU`"' ::“For most areas [of mathematics] a long process can usually be traced in which ideas evolve until an ultimate flash of inspiration, often by a number of mathematicians almost simultaneously, produces a discovery of major importance. Set theory however is rather different. It is the creation of one person, Georg Cantor.”'"`UNIQ--ref-00000060-QINU`"' ::Set theory, as a separate mathematical discipline, was born in late 1873 in the work of Georg Cantor.'"`UNIQ--ref-00000061-QINU`"' To this needs to be added a nuanced caveat, such as these: ::Cantor’s work should be considered as a completion of a long historical process'"`UNIQ--ref-00000062-QINU`"' ::The concept of set is no Athena: school children understand it now; but its development was long drawn out, beginning with the earliest counting and reckoning and extending into the late nineteenth century.'"`UNIQ--ref-00000063-QINU`"' This statement seems a reasonable summary: ::Both the theory of real numbers and the idea of a function depended upon an informal notion of set. Cantor turned the very simple idea of a set into a rich theory which was to become the foundation of modern mathematics.'"`UNIQ--ref-00000064-QINU`"' Even today, it is known that early study of naive set theory and early work with naive sets are useful in mathematics education:'"`UNIQ--ref-00000065-QINU`"' * they aid in developing a facility for working more formally with sets * they aid in understanding the motivation for axiomatic set theory Cantor’s first ideas on set theory were contained in papers on trigonometric series, but for the most part he developed the set concept and its theory as a consistent basis for his work with infinite sets.'"`UNIQ--ref-00000066-QINU`"''"`UNIQ--ref-00000067-QINU`"' In 1873, he discovered that the linear continuum is not countable, which he treated as an invitation to investigate the “different sizes of infinity” and the domain of the transfinite.'"`UNIQ--ref-00000068-QINU`"''"`UNIQ--ref-00000069-QINU`"' The following is a brief account of how his discovery came about:'"`UNIQ--ref-0000006A-QINU`"' ::* Cantor, in correspondence with Dedekind, asked the question whether the infinite sets $\mathbb{N}$ of the natural numbers and $\mathbb{R}$ of real numbers can be placed in one-to-one correspondence. ::* Dedekind, in reply, offered a proof of the following: ::::the set $\mathbb{A}$ of all algebraic numbers, the set of all real roots of equations of the form an $x_n + a_{n-1} x_{n-1} + a_{n-2} x_{n-2} + . . . + a_1 x + a_0 = 0$, where $a_i$ is an integer, is denumerable (i.e., there is a one-to-one correspondence with $\mathbb{N}$). ::* Cantor, a few days later, proved that the assumption that $\mathbb{R}$ is denumerable leads to a contradiction, using the Bolzano-Weierstrass principle of completeness. Thus, Cantor showed that “there are more elements in $\mathbb{R}$ than in $\mathbb{N}$ or $\mathbb{Q}$ or $\mathbb{A}$,” in this precise sense: ::::the cardinality of $\mathbb{R}$ is strictly greater than that of $\mathbb{N}$. A consequence of all this, Cantor noted, was proving anew an old (1844) result of Liouville's, namely, the existence (in every interval) of (uncountably many) transcendental numbers. In effect, there are in any real interval, more transcendental numbers than algebraic numbers.'"`UNIQ--ref-0000006B-QINU`"''"`UNIQ--ref-0000006C-QINU`"' In 1874, ''Crelle’s Journal'' published Cantor’s paper reporting this remarkable result and, in doing so, marked the birth of set theory. Previously, all infinite collections were assumed to be of "the same size." Cantor invoked the concept of a 1-to-1 correspondence to show that “there was more than one kind of infinity.”'"`UNIQ--ref-0000006D-QINU`"''"`UNIQ--ref-0000006E-QINU`"''"`UNIQ--ref-0000006F-QINU`"' Here is a summary of Cantor’s published results involving the early version of his naive set theory:'"`UNIQ--ref-00000070-QINU`"''"`UNIQ--ref-00000071-QINU`"' # in 1874, a proof that the set of real numbers is not denumerable, i.e. is not in one-to-one correspondence with (is not equipollent to) the set of natural numbers. # in 1878, a definition of what it means for two sets $M$ and $N$ to have the same power or cardinal number; namely that they be equipollent. # also in 1878, a proof that the set of real numbers and the set of points in n-dimensional Euclidean space have the same power, using a precisely developed notion of a one-to-one correspondence. Cantor actually achieved this last result -- at the time quite paradoxical -- in 1877, after which he wrote to Dedekind to report it, saying “I see it, but I don't believe it!”'"`UNIQ--ref-00000072-QINU`"' There were others who really didn’t believe it! Cantor submitted a paper reporting the result to ''Crelle's Journal''. Kronecker, who had significant influence over what was published in the journal, disliked much of Cantor's set theory and fundamentally disagreed with Cantor's work with infinite sets. The paper was published only after Dedekind intervened on Cantor's behalf.'"`UNIQ--ref-00000073-QINU`"' In 1878, Cantor stated his [[Continuum hypothesis|Continuum Hypothesis]], asserting that every infinite set of real numbers is either countable, i.e., it has the same cardinality as $\mathbb{N}$, or has the same cardinality as $\mathbb{R}$. From that point until 1883, these were the only two infinite powers or cardinal numbers.'"`UNIQ--ref-00000074-QINU`"' In all of these early papers, up to his development of the theory of transfinite numbers in 1883, Cantor’s notion of a set was essentially as follows:'"`UNIQ--ref-00000075-QINU`"' ::a set is a collection of elements that constitute the extension of a (mathematical) concept with the further important understanding that ::the concept involved is defined only for objects of some given (mathematical) domain. With the proviso noted, we can make these further points about this:'"`UNIQ--ref-00000076-QINU`"' * Cantor’s early notion is the notion of set as it is most often applied in mathematics * the proviso noted ensures that the paradoxes of set theory simply do not arise Finally, in an 1882 paper, Cantor made the following point with respect to what were termed “undecidable” concepts:'"`UNIQ--ref-00000077-QINU`"' ::an algorithm for deciding whether or not the concept determining a set applies to any particular object in the given domain is not needed for the concept to be the basis of a well-defined set. He gives, as an example, the set of algebraic numbers, which (as mentioned above) he himself had determined was countable. This set, Cantor insisted, is well-defined, even though determining whether or not a particular real number is algebraic “may or may not be possible at a given time with the available techiniques.” ==='"`UNIQ--h-12--QINU`"'Two presentations of naive set theory=== ''Set theory'' begins with two fundamental notions, ''objects'' and ''sets'' of those objects.'"`UNIQ--ref-00000078-QINU`"' ''Membership'' is a fundamental binary relation between objects $o$ and sets $A$. If $o$ is a ''member'' (or element) of $A$, write $o \in A$. ''Set inclusion'' is a derived binary relation between two sets. If all the members of set $A$ are also members of set $B$, then $A$ is a '''subset''' of $B$, denoted $A \subseteq B$. $A$ is called a '''proper subset''' of $B$ if and only if $A$ is a subset of $B$, but $B$ is not a subset of $A$. Set theory features binary operations on sets, such as these: * ''Union'' of the sets $A$ and $B$, denoted $A \cup B$, is the set of all objects that are a member of $A$, or $B$, or both. * ''Intersection'' of the sets $A$ and $B$, denoted $A \cap B$, is the set of all objects that are members of both $A$ and $B$. * ''Set difference'' of $U$ and $A$, denoted $U \setminus A$, is the set of all members of $U$ that are not members of $A$. When $A$ is a subset of $U$, the set difference $U \setminus A$ is also called the complement of $A$ in $U$. In this case, if the choice of $U$ is clear from the context, the notation $A^c$ is sometimes used instead of $U \setminus A$. * ''Symmetric difference'' of sets $A$ and $B$, denoted $A \bigtriangleup B$ or $A \ominus B$, is the set of all objects that are a member of exactly one of $A$ and $B$ (elements which are in one of the sets, but not in both). It is the set difference of the union and the intersection,$(A \cup B) \setminus (A \cap B)$ or $(A \setminus B) \cup (B \setminus A)$. * ''Cartesian product'' of $A$ and $B$, denoted $A \times B$, is the set whose members are all possible ordered pairs $(a,b)$ where $a$ is a member of $A$ and $b$ is a member of $B$. * ''Power set'' of a set $A$ is the set whose members are all possible subsets of $A$. - - - - - Beginning with the fundamental notions of ''set'' and ''belongs to'' or ''is a member of'' and assuming that sets have properties usually associated with collections of objects, Paul Halmos, in his 1960 text, developed informally an axiomatic set theory that presented the binary relation of set inclusion and the binary operations noted above, as follows:'"`UNIQ--ref-00000079-QINU`"' # ''Axiom of Extension'': Two sets are equal if and only if they have the same elements. # ''Axiom of Specification'': For every set $S$ and every proposition $P$, there is a set which contains those elements of $S$ which satisfy $P$ and nothing else. # ''Axiom of Pairs'': For any two sets there is a set which contain both of them and nothing else. # ''Axiom of Union'': For every collection of sets, there is a set that contains all the elements and only those that belong to at least one set in the collection. # ''Axiom of Powers'': For each set $A$ there is a collection of sets that contains all the subsets of the set $A$ and nothing else. # ''Axiom of Infinity'': There is a set containing $0$ and the $successor$ of each of its elements. # ''Axiom of Choice'': The Cartesian product of a non-empty indexed collection of non-empty sets is non-empty. In addition, there is an axiom stipulating (more or less) that anything intelligent one can do to the elements of a set yields a set: :8. ''Axiom of substitution'': If $S(a,b)$ is a sentence such that for each $a$ in set $A$ the set $\{b: S(a,b)\}$ can be formed, then there exists a function $F$ with domain $A$ such that ::::$F(a) = \{b:S(a,b)\}$ for each $a$ in $A$. An informally developed naive set theory with these axioms is equipped to do the following:'"`UNIQ--ref-0000007A-QINU`"' * develop concepts of ''ordered pair'', ''relation'', and ''function'', and to discusses their properties * discuss ''numbers'', ''cardinals'', ''ordinals'', and their arithmetics, * discuss different kinds of ''infinity'', in particular, the uncountability of the set of real numbers ==='"`UNIQ--h-13--QINU`"'Paradoxes and Cantor’s early set theory=== A discussion of paradoxes is relevant in two ways to the theory of sets: * the “paradoxes of the infinite” that had to be overcome before set theory could be developed * the paradoxes that later arose out of the development of set theory itself It is interesting to consider that Cantor succeeded in resolving the “paradoxes of the infinite” and providing a coherent account of cardinal number for infinite multiplicities, while Bolzano, though he made great progress with the use and understanding of sets, failed to do so. Two points have been made to account for this. First, there were notions about which, when applied to infinite sets, Bolzano was confused:'"`UNIQ--ref-0000007B-QINU`"' * the cardinal number of the set of points in an interval * the magnitude of the line interval as a geometric object Cantor accepted for infinite sets what had long been accepted for finite sets, namely, that “the relation of having the same cardinal number is defined in terms of equipollence.” Thus, since “the interval (0, 1) of real numbers is equipollent to the ‘larger’ interval (0, 2),” then these two sets of points, though different in magnitude, nevertheless have the same cardinal number. Bolzano, along many, rejected this.'"`UNIQ--ref-0000007C-QINU`"' Second, Euclid’s Common Notion 5, that ''the whole is greater than the part'', was a barrier to working with infinite sets. Euclid’s principle does indeed apply to geometric magnitude. It may be that Cantor’s clear understanding of the first point above allowed him to see that in the domain of sets, infinite sets are simply a counterexample to Euclid’s principle. Whatever the reason, Bolzano did not see this.'"`UNIQ--ref-0000007D-QINU`"' As a final issue, it is worth commenting on the oft-repeated claim that working with naive set theory inexorably leads one to paradoxes. One such claim is the following:'"`UNIQ--ref-0000007E-QINU`"' ::Naïve set theory is intuitive and simple, but unfortunately leads very soon to controversial statements [, because] it relies on an informal understanding of sets as collections of objects, called the elements or members of the set, that is [, it relies] on a predicate indicating that a collection is a set and a relation type symbol to represent set membership. This claim, however, does not apply to Cantor’s early theory of sets, which is the naive set theory that we have been examining. Certainly an aspect of set theory (naive or otherwise) that can lead to controversy and paradoxes is the use of ''unrestricted'' predicates (properties/concepts) to determine sets. Cantor’s early theory of sets, however, determines sets using ''restricted'' concepts. It is worth repeating here Cantor’s early notion of set: ::a set is a collection of elements that constitute the extension of a (mathematical) concept that is defined only for objects of some given (mathematical) domain. Sets determined in accordance with such a notion do not give rise to paradoxes. =='"`UNIQ--h-14--QINU`"'Dedekind’s theory of sets== The intention to get rid of geometrical intuitions as a genuine source of mathematical knowledge was the impetus for the two great programs of 19th century mathematics: rigorization and foundations.'"`UNIQ--ref-0000007F-QINU`"''"`UNIQ--ref-00000080-QINU`"' ::[...] There is a natural transition from the arithmetization of analysis that came to fruition in the 1870’s to interest in the foundations of arithmetic that flowered in the 1880’s. Dedekind played a major role in both of these programs. One goal of his was to examine set-theoretic procedures and their connections to the assumptions of logic.'"`UNIQ--ref-00000081-QINU`"' ==='"`UNIQ--h-15--QINU`"'Dedekind's “logic”=== In 1888, Dedekind published his major work on the foundations of arithmetic. For him, sets were logical objects and the corresponding notion was a fundamental concept of logic.'"`UNIQ--ref-00000082-QINU`"' In fact, he identified three basic logical notions:'"`UNIQ--ref-00000083-QINU`"' ::# ''object'' (“Ding”) ::# ''set'' (or system, “System”) ::# ''function'' (mapping, “Abbildung”) He held these logical notions to be “fundamental for human thought” and yet, at the same time, “capable of being elucidated,” in part, by “observing what can be done with them, including how arithmetic can be developed in terms of them.” Dedekind, emphasizing that both sets and functions were to be defined extensionally, connected his three notions of logic as follows:'"`UNIQ--ref-00000084-QINU`"' * "sets are a certain kind of object ... about which we reason by considering their elements, and this is all that matters about sets.” * functions, arbitrary ways of correlating the elements of sets, are yet not reducible to sets; neither are they presented by formulas nor representable in intuition (via graphs) nor decidable by formal procedures. Dedekind defined the concept of infinity using his three basic (undefined) notions of logic along with definable notions, such as subset, union, and intersection:'"`UNIQ--ref-00000085-QINU`"' ::a set of objects is ''infinite'' … if it can be mapped one-to-one onto a proper subset of itself. Dedekind’s theory of sets (systems) … made an appeal (for the most part implicit -- but see below) to a principle of unrestricted comprehension, a principle according to which every condition defines a set.'"`UNIQ--ref-00000086-QINU`"' Dedekind accepted “general notions of set and function and the actual infinite.” His notion of set was “unrestricted” in these three senses:'"`UNIQ--ref-00000087-QINU`"' # it involved an implicit acceptance of a general comprehension principle # it involved a universal set: “the totality of all things that can be objects of my thought” -- the ''Gedankenwelt'' # it involved consideration of arbitrary subsets of that totality -- a general ''Aussonderungsaxiom'' Dedekind’s presentations proceeded informally. He presented his theory using some formal machinery, though without a great deal of precision and explicitness, but he provided no explicit list of axioms or rules of inference. '"`UNIQ--ref-00000088-QINU`"''"`UNIQ--ref-00000089-QINU`"' ::Dedekind ... has not [an] over-ruling passion … to demonstrate his position conclusively, and is content with the usual informal mathematical standard of rigour. As a result, [however,] his work has … mathematical elegance [absent in more formal presentations]. Frege himself commented on Dedekind’s book as follows:'"`UNIQ--ref-0000008A-QINU`"' # his expressions set and belongs to “are not usual in logic and are not reduced to acknowledged logical notions” # an inventory of the logical laws taken by him as basic is nowhere to be found.” The first remark is fair comment, but the second “is not altogether true” since "Dedekind does state some of the basic principles of set theory, ''which for him are part of logic''."'"`UNIQ--ref-0000008B-QINU`"' Such a view of sets leads rather to axiomatic set theory than to higher-order logics.'"`UNIQ--ref-0000008C-QINU`"' All of this is in keeping with Dedekind’s ultimate purpose, which was not to axiomatize arithmetic, but to define mathematical notions in terms of logical ones.'"`UNIQ--ref-0000008D-QINU`"' Judged retrospectively, [Dedekind’s] contributions belong more to modern mathematics and algebra than to mathematical logic narrowly construed.'"`UNIQ--ref-0000008E-QINU`"' ==='"`UNIQ--h-16--QINU`"'Two versions of Dedekind’s principles=== Dedekind stated various principles satisfied by his notion of set.'"`UNIQ--ref-0000008F-QINU`"' “These principles are not explicitly introduced as axioms, but they nonetheless bear a close relation to the later axioms of set theory.”'"`UNIQ--ref-00000090-QINU`"' The notion of set: different things $a, b, c$ can be considered from a common point of view … and we say that they form a set (system) # the set $S$ is the same as the set $T$ ($S = T$) when every element of $S$ is also an element of $T$” [and vice versa] # a set $A$ is said to be a subset (part) of a set $S$ when every element of $A$ is also [an] element of $S$. Unfortunately, in discussing this concept, Dedekind fails somewhat to distinguish the two notions member and subset, thereby “identifying an element $s$ with its unit set ${s}$.”'"`UNIQ--ref-00000091-QINU`"' # the empty set $\emptyset$ is “wholly excluded” from Dedekind’s logic for “certain reasons.”'"`UNIQ--ref-00000092-QINU`"' # the Union of any arbitrary sets $A, B, C, …$ is defined # the Intersection of any sets $A, B, C, …$ is defined, with the proviso that the sets have at least one common element -- arising from the absence of the empty set! # the principle of Comprehension is not stated, but is assumed implicitly and is appealed to explicitly in the proof of one Dedekind’s theorems, which contains the following text: “If we denote by 𝐄 the set of all things possessing the property 𝜠….” # a set is infinite (said to be Dedekind-infinite) if it can be put in 1-1 correspondence with (is similar to) a proper subset of itself; otherwise it is finite. - - - - - The above principles of Dedekind’s logical framework “bear a remarkably close relationship to [the axioms of] modern axiomatic set theory,” devised by Zermelo and set out below.'"`UNIQ--ref-00000093-QINU`"' The notes to the axioms show connections to Dedekind’s Principles. ''Set'' is an undefined notion, introduced as follows: Set theory is concerned with a domain B of individuals, which we shall call simply objects and among which are the sets. * I ''Axiom of Extensionality'': sets are defined by their members -- Dedekind’s Principle 1 * II ''Axiom of 'Elementary Sets'': **(a) ''the empty set'' -- Dedekind's Principle 3 **(b) ''the unit set'' $\{a\}$ of $a$ **(c) ''the unordered pair set'' $\{a,b\}$ of any objects $a, b$ * III ''Axiom of Separation'': This axiom and parts (b) and (c) of Axiom II replace an intuitive (naive) ''Axiom of Comprehension'', stating given any property there exists the set of all things having that property and (unfortunately) leading directly to Russell’s paradox -- Dedekind's Principle 6 * IV ''Axiom of Power Set'': to every set $A$ there corresponds the set of all subsets of $A$, $P(A)$ -- Dedekind does not deal with infinite sets, so does not need the concept of Power Set * V ''Axiom of Union'': -- Dedekind’s Principle 4. A special axiom for Intersection is not needed, since it follows from the other axioms. * VI ''Axiom of Choice'': needed to prove that sets ''ordinary-infinite'' are also ''Dedekind-infinite'' -- Dedekind's Principle 7 * VII ''Axiom of Infinity'': Dedekind's Principle 7 -- “essentially due to Dedekind” owing to his failure to prove the existence of an infinite set =='"`UNIQ--h-17--QINU`"'The predicate calculus== For millennia mathematics had been a science based on deductive logic. But no account of logic had ever been produced which was adequate for the purposes of mathematics.'"`UNIQ--ref-00000094-QINU`"' The logic of propositions, for example, was not powerful enough either to represent all types of assertions used specifically in mathematics or to express certain types of equivalence relationships that hold generally between assertions. Consider the following two examples:'"`UNIQ--ref-00000095-QINU`"' 1. Assertions such as $x \text{ is greater than } 1$, where $x$ is a variable, appear quite often in mathematical inferences. :However, the logic of propositions can deal with such assertions only when stated with an explicit value for $x$, such as $2 \text{ is greater than } 1$. Otherwise, such assertions are not propositions: until the value of $x$ is explicitly stated, they are neither true nor false. 2. The patterns involved in the following logical equivalences are common in inferences: ::* "Not all birds fly" is equivalent to "Some birds don't fly" ::* "Not all integers are even" is equivalent to "Some integers are not even" ::* "Not all cars are expensive" is equivalent to "Some cars are not expensive" :However, the logic of propositions treats the two assertions in such equivalences independently. ::Let $P$ represent "Not all birds fly" and $Q$ represent "Some integers are not even" ::There is no general mechanism in the logic of propositions to determine whether or not $P$ is equivalent to $Q$. Each such equivalence must be listed individually to be used in inferencing. :Instead, we want to have a rule of inference that covers all these equivalences collectively and can be used when necessary. In other words, we need a more powerful logic to deal with these assertions. ==='"`UNIQ--h-18--QINU`"'Peirce's logic of quantifiers=== As a way of affirming his intention to develop a theory in which ''logic becomes calculation'', Peirce defined quantifiers to emphasize their analogy with arithmetic operations:'"`UNIQ--ref-00000096-QINU`"' ::Here, in order to render the notation as iconical as possible, we may use $\sum$ for the quantifier '''Some''', suggesting a sum, and $\prod$ for the quantifier '''AII''', suggesting a product. Thus $\sum_i x_i$ means that $x$ is true of some one of the individuals denoted by $i$ or ::::$\sum_i x_i = x_i + x_j + x_k + \text{etc.}$ ::In the same way, ::::$\prod_i x_i = x_i x_j x_k \text{etc.}$ ::If $x$ is a simple relation, ::::$\prod_i \prod_j x_{i, j}$ means that every $i$ is in this relation to every $j$, ::::$\sum_i \prod_j x_{i, j}$ means that some one $i$ is in this relation to every $j$. Applying Peirce’s quantifiers as defined above to his logic of relations, we can then write as follows:'"`UNIQ--ref-00000097-QINU`"' ::for the relation $i$ $loves$ $j$ ::::$loves_{i,j}$ ::for the statement using this relation “Everybody $loves$ somebody” ::::$\prod_i \sum_j loves_{i,j}$ ==='"`UNIQ--h-19--QINU`"'Frege's predicate logic=== Frege well knew of the inadequacies of propositional logic. Further, he understood that the various constructions of the real numbers and the associated introduction of infinite sets into mathematics rested on two pillars:'"`UNIQ--ref-00000098-QINU`"' # the procedures of set theory # the assumptions of logic Having determined that set-theoretic procedures were somehow “founded in logic,” he sought to answer this question: What, then, were the basic notions of logic? As we have seen above, Boole developed his algebraic logic as a means by which ''deduction becomes calculation''. In 1879, Frege published his “axiomatic-deductive” logic, which stood Boole’s purpose on its head:'"`UNIQ--ref-00000099-QINU`"' * Frege’s goal: “to establish ... that arithmetic could be reduced to logic” and, thus, to create a logic by means of which ''calculation becomes deduction'' * Frege’s program: to develop arithmetic as an axiomatic system and show that all the axioms were truths of logic An essential point of Frege’s project has been summarized as an effort “to get beyond the ‘deductive’ reasoning of syllogisms [of classical logic] to all the ‘inductive’ rules [used in mathematical proofs, which] require writing down, not just true … statements about [specific] numbers (etc), but reasoning about collections of numbers together.” '"`UNIQ--ref-0000009A-QINU`"' There is a further, perhaps more essential point to Frege’s project. Those working on the mid-19th-century arithmetization of analysis sought a precise manner of defining fundamental concepts of mathematics, such as limit, convergence, and continuity. In developing his logic, Dedekind sought a precise way of stating the results of his investigations into the nature of set and of numbers. Frege went further, however, seeking “a precise way not only of stating results, but also of proving them.” His insight was to realize “the difficulties of doing so using ordinary language, which was ... imprecise and ambiguous.”'"`UNIQ--ref-0000009B-QINU`"' In 1879, Frege published a system of predicate logic that proved sufficient for the formalisation of mathematics. He achieved this by abandoning the Subject-Predicate analysis of sentences used in Aristotle’s syllogistic logic.'"`UNIQ--ref-0000009C-QINU`"' The inspiration for Frege's predicate logic came from the mathematical concept of a function. He saw that the predicates in the statements of a syllogism could be expressed as concepts with variables that take arguments. The predicate “is Mortal” can be expressed as a concept that takes one argument, $\operatorname{Mortal}(x)$. The predicate “is a Teacher of” can be expressed as a concept that takes two arguments, $\operatorname{Teacher}(x, y)$. Viewed as such, predicates behave like functions in this sense:'"`UNIQ--ref-0000009D-QINU`"' ::when specific values (names) replace the concept variables, the predicate is transformed into a statement that is true or false. Frege strongly urged the adoption of this functional interpretation of predicates:'"`UNIQ--ref-0000009E-QINU`"' ::Logic has hitherto always followed ordinary language and grammar too closely…. I believe that the replacement of the … subject and predicate by argument and function, respectively, will stand the test of time. The greatest advance of Frege's logic over Aristotle's was its generality. It could handle all of the following:'"`UNIQ--ref-0000009F-QINU`"' ::* conjunctions, disjunctions, conditionals, and biconditionals of propositional logic ::* the logical equivalences involving negation described above ::* all combinations of quantifiers (All, Some, No, Not All) ::* relations, i.e., predicates involving two (or more) subjects In addition, Frege “drew attention to numerous important distinctions, e.g. between $x$ and $\{x\}$ and between $\in$ and $\subseteq$, which distinctions Dedekind failed somewhat to make in his theory of sets.'"`UNIQ--ref-000000A0-QINU`"' Using his logic, Frege defined with precision a formal deductive system, for which reason above all others he is nowadays commonly regarded as the founding father of modern logic.'"`UNIQ--ref-000000A1-QINU`"' Unfortunately, Frege symbolized statements using a far from intuitive 2-dimensional graphical method (Begriffsschrift -- 'concept-script' or 'ideography'). Here are his symbolizations for the four Aristotelian syllogistic sentence forms: '''A''', '''E''', '''I''', and '''O''':'"`UNIQ--ref-000000A2-QINU`"' ::{| class="wikitable" |- ! A: All a that are X are P !! E: All a that are X are not P !! I: Not all a that are X are not P !! O: Not all a that are X are P |- | style="text-align: center;" | [[File:Fregea1.jpg]] || style="text-align: center;" | [[File:Fregee1.jpg]] || style="text-align: center;" | [[File:Fregei1.jpg]] || style="text-align: center;" | [[File:Fregeo1.jpg]] |} It is thought that Frege’s cumbersome symbolism was what kept his logic from being adopted initially. Eventually, Frege’s logic was combined with Peano’s more intuitive notation, to create the predicate calculus used today. We will only mention briefly here what will be discussed farther on, namely, two essential elements of Frege’s logic that bear on his theory of arithmetic:'"`UNIQ--ref-000000A3-QINU`"''"`UNIQ--ref-000000A4-QINU`"' :1. ''concepts'' are the basic notions of logic, while ''sets'', which Frege defines as the extensions of predicates, are derivative notions: thus the set $\{x:P(x)\}$ is the extension of the predicate $P(x)$ :This view of sets is a broadening of Cantor’s early (restricted) view of naive sets, which were defined only for objects of a given mathematical domain. :2. for any logically definable predicate $P(x)$, we can form the set $\{a:P(a)\}$ :This ''naive comprehension principle'' has an analog stated implicitly in the Principles of Dedekind’s theory of sets. ==='"`UNIQ--h-20--QINU`"'A note on notation=== As set out above, somewhat contemporaneous with and quite independent of Frege’s invention of quantifiers for his axiomatic logic, C. S. Peirce invented quantifiers for Boole’s algebraic logic or, more precisely, for an algebra of relations that extended Boole’s logic. Frege disagreed with the assertion of Peirce that mathematics and logic are clearly distinct. To the contrary, as we have noted, Frege's view was that mathematics was reducible to logic or, more to the point, derivable from logic.'"`UNIQ--ref-000000A5-QINU`"''"`UNIQ--ref-000000A6-QINU`"' It is an irony that, though Frege invented his “logic of quantifiers” in order to support this view, his cumbersome 2-dimensional notation led to his invention being overlooked at the time. It was a linear notation somewhat similar to Peirce's that was adopted and that we use today. Here is an illuminating (and somewhat amusing) chronology of notational variants in the predicate calculus:'"`UNIQ--ref-000000A7-QINU`"' * In 1879, Frege developed his ''Begriffsschrift'' (concept writing), but for the next 30 years, his work was largely ignored. * In 1880, Peirce began to use the symbols $\prod$ and $\sum$, which he called quantifiers. * In 1885, Peirce added rules for quantifiers to Boolean algebra and published complete rules of inference for first-order logic. * In Germany (1890-95), Schröder adopted Peirce's notation, which became the standard for 20+ years. * In Italy, the logicians followed Peano, who had declared Frege's notation to be unreadable. * In England, Russell praised Frege’s logic, but adopted the Peirce-Peano notation, which came to be called Peano-Russell notation. The following table summarizes the symbolism of the Boole/Peirce algebra of logic:'"`UNIQ--ref-000000A8-QINU`"' ::{| class="wikitable" |- ! Operation !! Symbol !! Explanation |- | Disjunction || style="text-align: center;" | $+$ || Logical sum |- | Conjunction || style="text-align: center;" | $\times$ || Logical product |- | Negation || style="text-align: center;" | $-$ || $−1=0$ and $−0=1$ |- | Implication || style="text-align: center;" | $\prec$ || Equal or less than |- | Existential Quantifier || style="text-align: center;" | $\sum$ || Iterated sum |- | Universal Quantifier || style="text-align: center;" | $\prod$ || Iterated product |} The top three lines of the table are Boole’s. For his logical algebra, he used $1$ for truth and $0$ for falsehood, and he chose the symbols $+$, $\times$, and $−$ to represent ''disjunction'', ''conjunction'', and ''negation''. The bottom three lines of the table are Peirce's innovations:'"`UNIQ--ref-000000A9-QINU`"' * ''Implication'': Peirce observed that if $p \text{ implies } q$, then $q$ must always be true when $p$ is true, but $q$ might also be true for some reason independent of $p$. Therefore, the truth value of $p$ is ''always less than or equal to'' the truth value of $q$. Instead of using the symbol $≤$, which combines two operators, Peirce invented the claw symbol $\prec$ because it suggests a single, indivisible operation. * ''Existential quantifier'': In Boole's algebra, $1+1=1$. Therefore, Peirce adopted $\sum$ to indicate a logical summation of any number of terms, which would be true ''if at least one of the terms happened to be true''. * ''Universal quantifier'': In Boole's algebra, $1 \times 1 = 1$, so Peirce adopted $\prod$ to indicate a logical product of any number of terms, which would only be true ''if every one of the terms happened to be true''. It has been suggested that Peirce in algebraic logic and Frege in axiomatic logic did not so much invent the notion of quantifier, but rather separated and freed that notion from two tethers:'"`UNIQ--ref-000000AA-QINU`"' * from the notion of predicate in Aristotle’s syllogism, on the one hand * from the connectives in Boole’s algebra of logic, on the other After Frege and Peirce put the logic of predicates, variables and quantifiers into the language of logic, it became possible to apply this language to questions in the foundations of arithmetic, in particular, and of mathematics, generally .'"`UNIQ--ref-000000AB-QINU`"' =='"`UNIQ--h-21--QINU`"'Axiomatic development of arithmetic== The modern theory of arithmetic was developed in the last decades of the nineteenth century. The people most closely associated with this development and the dates of their initial publications are as follows:'"`UNIQ--ref-000000AC-QINU`"' * Gottlob Frege (1884) * Richard Dedekind (1888) * Giuseppe Peano (1889) Though their published works have much in common, we judge from their statements that each completed his own work before becoming aware of the work of the others. ==='"`UNIQ--h-22--QINU`"'Grassmann's and Peirce's contributions=== A great deal of the work involved in axiomatizing arithmetic was done in the decades before Frege, Dedekind, and Peano published. As much as 90% of that work is said to have been done by one person, Hermann Grassmann. Certainly Peano knew of and acknowledged his use of Grassmann’s work, which was published in 1861 and included the following results:'"`UNIQ--ref-000000AD-QINU`"''"`UNIQ--ref-000000AE-QINU`"' * recursive definitions of addition and multiplication from one single argument operation, i.e. the successor operation $x+1$: ::$x+0=x$; $x+(y+1)=(x+y)+1$; ::$x \times 0=0$; $x \times (y+1)=(x \times y)+x$. * a definition of the induction principle, stated as follows in modern terminology: ::Let variables $x, y, …$ range over natural numbers, and let :::$0$ denote the number "zero" :::$Sx$ denote the operation $x+1$ :::$F$ range over sets of natural numbers. ::$0 \in F \wedge \forall x(x \in F \Rightarrow Sx \in F)) \Rightarrow \forall x(x \in F)$ * a demonstration that the commutative law can be derived from the associative law by means of this induction principle. In 1881, Peirce published a set of axioms of number theory. His purpose was to use his quantified logic of relations to construct the system of natural numbers based on definitions and axioms. In his own words, he published his axioms for natural numbers to establish that “elementary propositions concerning number ... are strictly syllogistic consequences from a few primary propositions.”'"`UNIQ--ref-000000AF-QINU`"' Starting from his definition of ''finite set'', Peirce’s axioms are (in modern terminology) as follows:'"`UNIQ--ref-000000B0-QINU`"' ::Given the following: ::* a set $N$ ::* $R$, a relation on $N$ ::* $1$, an element of $N$ ::* definitions of minimum, maximum, and predecessor with respect to $R$ and $N$ ::Peirce’s axioms: # $N$ is partially ordered by $R$. # $N$ is connected by $R$. # $N$ is closed with respect to predecessors. # $1$ is the minimum element of $N$; $N$ has no maximum. # Mathematical induction holds for $N$. Peirce’s axioms for the natural numbers start from finite sets, but they are nonetheless equivalent both to the defining conditions stated by Dedekind and to the axioms developed by Peano.'"`UNIQ--ref-000000B1-QINU`"' ==='"`UNIQ--h-23--QINU`"'Frege's theory of arithmetic=== Frege, by virtue of his work creating predicate logic, is one of the founders of modern (mathematical) logic. His view was that mathematics is reducible to logic. His major works published with the goal of doing this are these:'"`UNIQ--ref-000000B2-QINU`"' * in 1879 -- ''Begriffsschrift'', defining his “axiomatic-deductive” predicate calculus for the ultimate purpose of proving the basic truths of arithmetic "by means of pure logic." * in 1884 -- ''Die Grundlagen der Arithmetik'', using his predicate calculus to present an axiomatic theory of arithmetic. * in 1893/1903 -- ''Die Grundgesetze der Arithmetik'', presenting formal proofs of number theory from an intuitive collection of axioms. As we have seen, Boole’s developed his algebra of logic as a means by which ''deduction becomes calculation''. Frege's predicate calculus in the ''Begriffsschrift'' stood Boole’s purpose on its head:'"`UNIQ--ref-000000B3-QINU`"' * Frege’s goal: “to establish ... that arithmetic could be reduced to logic” and, thus, to create a logic by means of which ''calculation becomes deduction'' * Frege’s program: to develop arithmetic as an axiomatic system such that all the axioms were truths of logic Driven by “an over-ruling passion to demonstrate his position conclusively” and not “content with the usual informal mathematical standard of rigour,” Frege’s exposition in ''Grundgesetze'' is characterized by a great degree by precision and explicitness.'"`UNIQ--ref-000000B4-QINU`"' He himself tells us why this is so:'"`UNIQ--ref-000000B5-QINU`"' ::[T]he fundamental propositions of arithmetic should be proved…with the utmost rigour; for only if every gap in the chain of deductions is eliminated with the greatest care can we say with certainty upon what primitive truths the proof depend. Frege gave the following reason for developing his logic as an axiomatic system:'"`UNIQ--ref-000000B6-QINU`"' ::Because we cannot enumerate all of the boundless number of laws that can be established, we can obtain ''completeness'' only by a search for those [laws] which, potentially, imply all the others. Frege also commented on the role of proof in mathematics:'"`UNIQ--ref-000000B7-QINU`"' ::The aim of proof is not merely to place the truth of a proposition beyond all doubt, but also to afford us insight into the ''dependence'' of truths upon one another. Frege identified as the ''kernel'' of his system the axioms (laws) of his logic that potentially imply all the other laws. His statements above imply that he thought his system to be complete and his axioms to be independent. He did not, however, provide precise definitions of completeness and independence nor did he attempt a proof that his system was complete and his axioms independent. Early in his first book on the foundations of arithmetic, Frege established his purpose:'"`UNIQ--ref-000000B8-QINU`"' ::[I]t is above all $Number$ which has to be ''either defined or recognized as indefinable''. This is the point which the present work is meant to settle. Frege began the introduction of numbers into his logic by defining what is meant by saying that two $Numbers$ are equal:'"`UNIQ--ref-000000B9-QINU`"''"`UNIQ--ref-000000BA-QINU`"' ::two concepts $F$ and $G$ are equal if the things that fall under them can be put into one-one correspondence From this he arrives at the notion that “a $Number$ is a set of concepts”: * §72 the $Number$ that belongs to the concept $F$ is the extension of the concept “equal to the concept $F$” :and then continues as follows by defining the expression ::::$n$ is a $Number$ :to mean ::::there exists a concept such that $n$ is the $Number$ that belongs to it. * §73 he draws this inference ::::the concept $F$ is equal to the concept $G$ :implies ::::the $Number$ belonging to the concept $F$ is identical to the $Number$ belonging to the concept $G$ The natural numbers can be used as ''ordinals'' and as ''cardinals''. * ordinal numbers are used to count elements and place them in a succession: they correspond to expressions such as ''first'', ''second'', ''third''... and so forth. * cardinal numbers are used to count how many elements of some kind there are: ''one'' cat, ''two'' dogs, ''three'' horses, and so forth. As developed above, Frege interpreted statements about natural numbers to be statements about concepts. This interpretation stemmed from his understanding that natural numbers themselves were essentially ''cardinals'', “contrary to the general tendency in the late nineteenth century on foundations of arithmetic.”'"`UNIQ--ref-000000BB-QINU`"' Hence, Frege's definition of numbers was based on their uses as cardinals.'"`UNIQ--ref-000000BC-QINU`"' Frege continued as follows: * §74 he defines the $Number$ $0$ as ::::the $Number$ that belongs to the concept “not identical with itself” * §75 he immediately clarifies this, stating ::::Every concept under which no object falls is equal to every other concept under which no object falls, and to them alone. :and therefore ::::$0$ is the $Number$ which belongs to any such concept, and no object falls under any concept if the number which belongs to that concept is $0$. From this point (§76) onwards, Frege discussed the succession of natural numbers, starting from the number zero so defined, and (eventually) proved the five Peano axioms of arithmetic.'"`UNIQ--ref-000000BD-QINU`"' * §76 he defines the $Successor$ relation ::::$n$ follows in the series of $Numbers$ directly after $m$ :to mean ::::there exists a concept $F$ and an object falling under it, $x$, such that ::::::the $Number$ belonging to the concept $F$ is $n$ ::::and ::::::the $Number$ belonging to the concept “falling under $F$ but not equal to $x$” is $m$ * §77 he defines the $Number$ $1$ as ::::“the $Number$ belonging to the concept ‘identical with $0$’” :from which it follows that ::::$1$ is the $Number$ that follows directly after $0$ * §78-81 he proves or gives a proof sketch for several propositions regarding the $Successor$ relation, using definitions of $series$ and $following$ $in$ $a$ $series$ from his earlier work of 1879 ::* the $Successor$ relation is 1-1 ::* every $Number$ except $0$ is a $Successor$ ::* every $Number$ has a $Successor$ * §82 he outlines a proof that there is no last member in the series of $Numbers$ * §83 he provides a definition of finite Number, noting that no finite Number follows in the series of natural numbers after itself * §84 he notes that the $Number$ which belongs to the concept 'finite N$umber$' is an infinite $Number$. Central to all of this work was a distinction that Frege was developing, but only finally published in 1892 and incorporated in the ''Grundgesetze'', namely, that every concept, mathematical or otherwise, had two important, entirely distinct aspects:'"`UNIQ--ref-000000BE-QINU`"''"`UNIQ--ref-000000BF-QINU`"' # ''Sinn'': a “meaning” or “sense” or “connotation” # ''Bedeutung'': an “extension” or “reference” or “denotation” This distinction of Frege's is the basis of what Gödel (many years later) characterized as the ''dichotomic conception'':'"`UNIQ--ref-000000C0-QINU`"' ::Any well-defined concept (property or predicate) $P(x)$ establishes a dichotomy of all things into those that are $P$s and those that are non-$P$s. :In other words, ::a concept partitions $V$ (the universe of discourse) into two classes: the class $\{ x : P(x) \}$ and its absolute complement, the class $\{ x : \neg P(x) \}$. Underlying this notion are two key assumptions: # the existence of a ''Universal Set'', $V$ -- what we have seen as Dedekind’s ''Gedankenwelt'' # the unrestricted principle of ''Comprehension'' -- ''any'' well-defined property determines, a set. For “naïve” set theory, these two assumptions are equivalent and either one of them suffices to derive the other: * to derive ''Universal Set'' from ''Comprehension'': ::::replace $P(x)$ by a truism, such as the property $x = x$. * to derive ''Comprehension'' from the ''Universal Set'': ::assume an all-encompassing set $V$, ::::note that any part of $V$ is also a set, ::::and that any well-defined concept $P(x)$ defines a subset of $V$, ::therefore the set $\{ x : P(x) \}$ exists! To these two assumptions, add Dedekind's principle of ''Extensionality''. Frege intended the ''Grundgesetze'' to be the implementation of his program to demonstrate “every proposition of arithmetic” to be ”a [derivative] law of logic.” In this work of 19 years duration, there was no explicit appeal to an ''unrestricted'' principle of Comprehension. Instead, Frege's theory of arithmetic appealed to Comprehension by virtue of its symbolism, according to which for any predicate $P(x)$ (concept or property) one can form an expression $S = \{ x : P(x)\}$ defining a set. Frege's theory assumes that (somehow) there is a mapping which associates an object (a set of objects) to every concept, but he does not present comprehension as an explicit assumption. All of this is in contrast to the use of ''restricted'' predicates in Cantor's early theory of sets.'"`UNIQ--ref-000000C1-QINU`"''"`UNIQ--ref-000000C2-QINU`"' ==='"`UNIQ--h-24--QINU`"'Dedekind’s theory of numbers=== Dedekind’s work through 1872 was concerned with the rigourization and arithmetization of analysis. More specifically, he focused on providing a rigorous definition of real numbers and of the real-number continuum upon which to establish mathematical analysis.'"`UNIQ--ref-000000C3-QINU`"' His subsequent work in foundations was based on the further thought that the concepts and the rules of arithmetic also needed rigourization, which he sought to provide using logic and set theory.'"`UNIQ--ref-000000C4-QINU`"' A goal for Dedekind (as for Frege, though in a somewhat different sense) was to “reduce” the natural numbers and arithmetic to logic and set theory. A second goal (again for both of them) was to examine set-theoretic procedures and establish to what extent they themselves were founded in logic. “But then, what are the basic notions of logic?”'"`UNIQ--ref-000000C5-QINU`"' The ultimate basis of a mathematician’s knowledge was, according to Dedekind, the clarification of the concept of natural numbers in a non-mathematical fashion, which involves this two-fold task:'"`UNIQ--ref-000000C6-QINU`"' # to define numerical concepts (natural numbers) through logical ones # to characterize mathematical induction (the passage from n to n+1) as a logical inference. The “clarification” that Dedekind provided was in answer to questions that he himself posed:'"`UNIQ--ref-000000C7-QINU`"' * What are the mutually independent fundamental properties of the sequence $N$, that is, those properties that are not derivable from one another but from which all others follow? * How should we divest these properties of their specifically arithmetic character so that they are subsumed under more general notions and under activities of the understanding ''without'' which no thinking is possible at all, but ''with'' which a foundation is provided for the reliability and completeness of proofs and for the construction of consistent notions and definitions? Dedekind developed what has been called a “set-theoretic” presentation of the natural numbers, which (in a modern formulation) is captured in the following four ''conditions'':'"`UNIQ--ref-000000C8-QINU`"' ::A ''simply infinite'' set $N$ has a distinguished element $e$ and an ordering mapping $ϕ$ such that ::# $ϕ(N) ⊆ N$ ::# $e \notin ϕ(N)$ ::# $N = ϕ0(e)$, i.e. $N$ is the $ϕ-chain$ of the unitary set $\{e\}$ ::# $ϕ$ is an injective mapping from $N$ to $N$, i.e. if $ϕ(a) = ϕ(b)$ then $a = b$. The contrast between Dedekind’s conditions and Peano’s axioms has been described as follows:'"`UNIQ--ref-000000C9-QINU`"' * Conditions 2 and 4 are easily related to Peano’s axioms, which tend to impose conditions on the behaviour of … the natural numbers, and the operations on them. * Conditions 1 and 3, however, are “set-theoretic” in character, “establishing structural conditions on subsets of the (structured) sets [and/or] on the behaviour of relevant maps." Dedekind's intention here was not to axiomatize arithmetic, but to give an "algebraic" characterization of natural numbers as a mathematical structure.'"`UNIQ--ref-000000CA-QINU`"' Dedekind then introduced the natural numbers as follows:'"`UNIQ--ref-000000CB-QINU`"' # he proved that every infinite set contains a ''simply infinite'' subset # he showed (in contemporary terminology) that any two simply infinite systems ... are isomorphic (so that the axiom system is categorical) It is interesting to note how Dedekind's approach contrasts with Peirce's and Frege's. With Dedekind we have a theory of numbers, while with Peirce we have an axiomatization of number theory. Further, in defining natural numbers, Dedekind started from infinite sets rather than finite sets, and was explicitly and specifically concerned with the real number continuum, that is, with infinite sets.'"`UNIQ--ref-000000CC-QINU`"' With Frege, too, we have an axiomatization of number theory. Further, Frege considered the natural numbers 1, 2, 3, … to be essentially cardinals, which are used to count how many objects of some kind there are, while Dedekind considered natural numbers to be essentially ordinals. Any set meeting Dedekind’s four conditions for a simple infinity will consist of a first element $1$, a second element $f(1)$, a third $f(f(1))$, then $f(f(f(1)))$, and so on.'"`UNIQ--ref-000000CD-QINU`"' Thus, in his definition of a simple infinity, Dedekind captured the ordinality of the natural numbers.'"`UNIQ--ref-000000CE-QINU`"' He subsequently provided an explanation of how to derive the cardinality of the natural numbers, using initial segments of the number series as tallies:'"`UNIQ--ref-000000CF-QINU`"' ::for any set we can ask which such segment, if any, can be mapped one-to-one onto it, thus measuring its cardinality. (A set turns out to be finite, in the sense defined above, if and only if there exists such an initial segment of the natural numbers series.) ==='"`UNIQ--h-25--QINU`"'Peano’s axioms of arithmetic=== From 1891 until 1906, Peano and his colleagues published substantial amounts of formalized mathematics in his journal ''Rivista di Matematica''. Their objective was not to reduce mathematics to a logical foundation, but to rewrite mathematics “in a formal framework,” that is, to use a formal notation as an aid to precision. Peano’s substantial interest in stating mathematical results and arguments precisely rose out of his teaching experience. '"`UNIQ--ref-000000D0-QINU`"' Peano knew of and studied the work of both Grassmann and Frege “before he began his ''Arithmetices principia''. Along with them, he believed that ordinary language -- and therefore any mathematics that was explained in it -- was too ambiguous. Peano’s goals were these:'"`UNIQ--ref-000000D1-QINU`"' # to set up a solid system of arithmetic # to improve logic symbols and notation # to establish axioms that would serve as the basis for all arithmetic Thus, ::"Peano Arithmetic does not tell us what the numbers are… Rather, [it] provides a means of deducing the various arithmetic facts about them [, telling] us how the numbers are inter-related."'"`UNIQ--ref-000000D2-QINU`"' Like Dedekind, Peano accepted “class” as a logical notion, but, unlike Frege, Peano did not think that number could be defined in terms of logical notions.'"`UNIQ--ref-000000D3-QINU`"' In 1889, Peano published his first system of axioms for the natural numbers, in which he defined “every sign ... except ... four”:'"`UNIQ--ref-000000D4-QINU`"''"`UNIQ--ref-000000D5-QINU`"' # ’’number’’ (positive integer) # ’’unity’’ # ’’successor’’ # ’’equality’’ (of numbers) Peano wrote his axioms, definitions, and proofs using the symbols that he defined in the preface to booklet. He intended the structure so created to be sufficient to derive “every result in arithmetic.”'"`UNIQ--ref-000000D6-QINU`"' In 1891, Peano published a 2nd, simplified system of axioms, using only three undefined terms: $\mathbb{N}$ ($number$), $1$ ($One$), and $a^+$ (the $successor$ of $a$, where $a$ is a $number$).'"`UNIQ--ref-000000D7-QINU`"' These may be stated informally as follows: # $One$ is a $number$ # The sign $^+$ placed after a $number$ $a$ produces a $number$ $a^+$ # If $a$ and $b$ are two $numbers$, and if their $successors$ are equal, then they are also equal # $One$ is not the $successor$ of any $number$ # If $s$ is a class containing $One$, and if the class made up of the $successors$ of $s$ is contained in $s$, then every $number$ is contained in the class $s$. In 1898, Peano published a third system of axioms in which the undefined term $0$ ($Zero$) replaced the term $1$ ($One$). It is this system of axioms that is commonly known today as [[Peano axioms]] and that can be stated informally as follows:'"`UNIQ--ref-000000D8-QINU`"' # $Zero$ is a $number$ # The $successor$ of any $number$ is another $number$ # There are no two $numbers$ with the same $successor$ # $Zero$ is not the $successor$ of a $number$ # Every property of $Zero$, which belongs to the $successor$ of every $number$ with this property, belongs to all $numbers$ Note particularly the language of induction axiom 5, in which talk of "classes" is replaced by talk of "properties". This change stems from Frege’s notion (discussed above) about the relationship between the ’’extension’’ and the ’’meaning’’ of a concept. ::The extension of a mathematical predicate (property, concept) $P(x)$ is just $\{x:P(x)\}$, the collection of everything for which the predicate is true. In a remark immediately following his 1898 statement of the axioms, Peano noted this:'"`UNIQ--ref-000000D9-QINU`"' ::These primitive propositions . . . suffice to deduce all the properties of the numbers that we shall meet in the sequel. There is, however, an infinity of systems which satisfy the five primitive propositions. . . . All systems which satisfy the five primitive propositions are in one-to-one correspondence with the natural numbers. The natural numbers are what one obtains by abstraction from all these systems; in other words, the natural numbers are the system which has all the properties and only those properties listed in the five primitive propositions. ([14], p. 218). Finally, in 1901, Peano added another axiom, which he numbered axiom 0, to the five axioms noted above.'"`UNIQ--ref-000000DA-QINU`"' :0. The (natural) $numbers$ form a class Various and diverse modern formalizations of Peano’s axioms exist. Typical differences among them involve the following:'"`UNIQ--ref-000000DB-QINU`"' * alternate orders of stating the axioms, especially with the axiom of induction stated last * alternate formulations of the axiom of induction itself, for example: ::::* $\forall S \in Sets : (0 \in S \wedge \forall n : n \in S \to n’ \in S) \to \mathbb{N} \subset S$ ::::* $\forall P \in Predicates : (P(0) \wedge \forall n : P(n) \to P(n’)) \to \forall n : P(n)$ All of Peano’s formulations of the induction axiom (and those above) are second-order statements. Peano did not discuss the consistency of his axioms. He did, however, examine the independence of his axioms, that is, whether or not all of his axioms are actually needed, by defining, for each axiom, a set for which the axiom being considered was false, but for which the other axioms remained true, as follows:'"`UNIQ--ref-000000DC-QINU`"''"`UNIQ--ref-000000DD-QINU`"' An alternate way of demonstrating the independence of axioms is as follows:'"`UNIQ--ref-000000DE-QINU`"' ::To prove that every axiom is needed to define the natural numbers, we need to remove each one from the set of axioms and demonstrate that the remaining axiom set has models that are not isomorphic to the natural numbers. ==='"`UNIQ--h-26--QINU`"'Another note on notation=== Peano and his colleagues were seeking to “rewrite” mathematics in a logical framework and needed logical symbols that could be freely mixed with mathematical symbols in formulas. Peano therefore replaced Peirce's logical symbols with new ones, occasionally turning letters upside down and/or backwards to form them. The following table lists Peirce's symbols and Peano's replacements:'"`UNIQ--ref-000000DF-QINU`"' ::{| class="wikitable" |- ! Operation !! Peirce !! Explanation !! Peano !! Explanation |- | Disjunction || style="text-align: center;" | $+$ || Logical sum || style="text-align: center;" | $\lor$ || v for ’’vel’’ |- | Conjunction || style="text-align: center;" | $\times$ || Logical product || style="text-align: center;" | $\land$ || Upside down v |- | Negation || style="text-align: center;" | $-$ || $−1=0$ and $−0=1$ || style="text-align: center;" | $\sim$ || Curly minus sign |- | Implication || style="text-align: center;" | $\prec$ || Equal or less than || style="text-align: center;" | $\supset$ || C for ''consequentia'' |- | Existential Quantifier || style="text-align: center;" | $\sum$ || Iterated sum || style="text-align: center;" | $\exists$ || E for ''existere'' |- | Universal Quantifier || style="text-align: center;" | $\prod$ || Iterated product || style="text-align: center;" | $( )$ || O for ''omnis'' |} ==='"`UNIQ--h-27--QINU`"'Whose axioms are they -- anyway?=== A terminological dispute has arisen over the use of “Peano axioms” to designate the axioms of arithmetic. This designation has been called into question by some since, in developing his axioms, Peano himself acknowledged the following:'"`UNIQ--ref-000000E0-QINU`"' * he made extensive use of Grassmann's work * he “borrowed” the axioms themselves from Dedekind Indeed, as Peano himself stated it:'"`UNIQ--ref-000000E1-QINU`"' ::... I used the book of H. Grassmann … and the recent work by R. Dedekind…. Certainly, as we have seen above, in 1888, one year before Peano’s work, Dedekind did publish a similar system of axioms and obtained similar results. As a result, some have argued that Dedekind deserves at least as much (if not more) credit than Peano for the postulates on the natural numbers, referring to them as Dedekind-Peano axioms:'"`UNIQ--ref-000000E2-QINU`"' ::What it means to be “simply infinite” is captured in four ‘Dedekindian’ conditions, which are “a notational variant of Peano's axioms for the natural numbers” and, hence, “are thus properly called the Dedekind-Peano axioms.” As to whether Peano knew of and, therefore, may have borrowed something from Dedekind work, there are conflicting claims: * one source claims that Peano was completely unaware of Dedekind’s book ''until after his own was published''.'"`UNIQ--ref-000000E3-QINU`"' * a more nuanced claim is that Peano read Dedekind’s essay only ''as his own book was going to press'' and stated in his own preface that he had found Dedekind’s essay “useful”… meaning (perhaps) that he found confirmation of “the independence of the primitive propositions from which I started.”'"`UNIQ--ref-000000E4-QINU`"' The argument has been made that the “much more clear and more thorough” nature of Peano’s work is reason enough for remembering him as the “creator” of the axioms, with the following suggested as deficiencies in Dedekind’s work:'"`UNIQ--ref-000000E5-QINU`"' ::* Dedekind only writes three axioms, equivalent to Peano’s 1889 axioms 1, 7, and 9 ::* he omits any discussion of the equality relation ::* he does not explicitly define the successor function in an axiom In the same regard, Dedekind’s notation for the successor of a number $a$ as $a’$ is less preferred than Peano’s notation of $a +1$, which makes the definition more obvious.'"`UNIQ--ref-000000E6-QINU`"' Finally, support for nominating the axioms as Peano’s rather than Dedekind’s has been based on the differences in their purposes: * ”Peano’s primary interest was in axiomatics”: he neither developed nor used his logic for the purpose of “reducing” mathematical concepts to logical concepts and, indeed, “he denied the validity of such a reduction.”'"`UNIQ--ref-000000E7-QINU`"' * It is correct to call the axioms Peano’s rather than Dedekind’s, because Peano was not trying to define the primitive notions of arithmetic, but rather to characterize them axiomatically; whereas Dedekind was not trying to axiomatize arithmetic, but rather to define arithmetical notions in terms of logical ones.'"`UNIQ--ref-000000E8-QINU`"' This last point may be the most telling, suggesting as it does that Dedekind himself would not have wanted his ‘Dedekindian’ conditions to be called axioms. =='"`UNIQ--h-28--QINU`"'Cantor's general theory of sets== It was a widespread belief in the late 19th century that pure mathematics was nothing but an elaborate form of arithmetic and that the “arithmetization” of mathematics had brought about higher standards of rigor. This belief led to the idea of grounding all of pure mathematics in logic and set theory. The implementation of this idea which proceeded in two steps:'"`UNIQ--ref-000000E9-QINU`"' # the establishment of a theory of real numbers (arithmetization of analysis) # the definition of the natural numbers and the axiomatization of arithmetic Infinite sets had been needed for an adequate definition of important mathematical notions, such as limit and irrational numbers. It was this initial use that led Cantor himself to begin studying infinite sets “in their own right.”'"`UNIQ--ref-000000EA-QINU`"' In 1883, Cantor began his general theory of sets with the publication of ''Foundations of a General Theory of Manifolds'' (the ''Grundlagen''). Among other things, in this paper he made the interesting and somewhat self-justifying claim of the autonomy of pure mathematics: * pure mathematics may be concerned with systems of objects which have no known relation to empirical phenomena at all'"`UNIQ--ref-000000EB-QINU`"' * any concepts may be introduced subject only to the condition that they are free of contradiction and defined in terms of previously accepted concepts'"`UNIQ--ref-000000EC-QINU`"' In the ''Grundlagen'', there was a significant change in Cantor’s conception of a set, which he defined as follows:'"`UNIQ--ref-000000ED-QINU`"' ::any multiplicity which can be thought of as one, i.e. any aggregate (''inbegriff'') of determinate elements ''that can be united into a whole'' by some law. The notable changes in this from his earlier explanation of the concept of set are these:'"`UNIQ--ref-000000EE-QINU`"' * the absence of any reference to a prior conceptual sphere or domain from which the elements of the set are drawn * the modification according to which the property or “law” which determines elementhood in the set “unites them into a whole” Cantor’s overall reason for introducing a new conception of ''set'' was to support the development of his theory of transfinite numbers.'"`UNIQ--ref-000000EF-QINU`"' ==='"`UNIQ--h-29--QINU`"'The theory of transfinite numbers=== Cantor's intention was "to generalize in a rigorous way the very notion of number in itself ... by building transfinite and finite numbers, using the same principles."'"`UNIQ--ref-000000F0-QINU`"' In order to do this, Cantor employed the notion of set in an entirely new way:'"`UNIQ--ref-000000F1-QINU`"' * Cantor’s previous notion of a set involved specifying a set of objects from some given domain, ''albeit'' one which was already well-defined. * Cantor’s new notion of a set introduced the transfinite numbers in terms of the notion of a ''set'' of objects ''of that very same domain''. Briefly, Cantor defined (ordinal) numbers to be what can be obtained, by starting with the initial number ($0$) and applying two operations, which he called ''principles of generation'':'"`UNIQ--ref-000000F2-QINU`"' ::# the usual process of taking successors, which yields, for every given number $a$, its successor $a + 1$ ::# a new process of taking limits of increasing "sequences", which yields, after any given "sequence" of numbers without a last element, a number $b$ In this, Cantor seems not only to be introducing a new understanding for the term ''set'', but (almost) also to be proposing a new (and clearly perverse) understanding for the term ''sequence'', which is defined only for countable sets -- a fact that was at the heart of his demonstration that the set of reals $\mathbb{R}$ cannot be written as a sequence and, hence, is not countable. It has been noted that Cantor's mention of "sequences" of numbers rather than "sets" is, while inaccurate, of no consequence, "since the sequences in question are in their natural order and so are determined by the set of their members."'"`UNIQ--ref-000000F3-QINU`"' Cantor defined ''numbers'' (both finite and transfinite numbers) in terms of the notion of a ''class of numbers'', as follows:'"`UNIQ--ref-000000F4-QINU`"''"`UNIQ--ref-000000F5-QINU`"' ::Let $Ω$ denote the class of all (ordinal) numbers :::and $X$ range over sets :::and $S(X)$ be the least number greater than every number in $X$, given by one of the two “generating principles” noted above. :::and $X \text{ is a subset of } Ω ⇒ S(X) ∈ Ω$. ::Then we have ::* $0$ the least number is $∅$ (the null set) ::* $1$ is $S(0)$ or $\{0\}$ ::* $2$ is $S(1)$ or $\{0, 1\}$ ::* $n$ is $S(n - 1)$ or $\{0, 1, 2, … n-1\}$ :::$\vdots$ ::* $\omega$ is limit of $\{0, 1, 2, … \}$ (the set of all finite ordinals) ::* $\omega + 1$ is $S(\omega)$ :::$\vdots$ ::* $\omega_1$ (the set of all countable ordinals) :::$\vdots$ ::* $\omega_2$ (the set of all countable and $ℵ_1$ ordinals) :::$\vdots$ ::* $\omega_{\omega}$ (the set of all finite ordinals and $ℵ_k$ ordinals for non-negative integers $k$) :::$\vdots$ In order of increasing size, the (ordinal) numbers are then ::$0, 1, 2, ..., \omega, \omega+1, \omega+2, ..., \omega+\omega = ω·2, …, ω·n, ω·n +1, …,ω^2, ω^2+1, …, ω^ω, … \text{ and so on and on }$ Finally, ::$Ω$ is well-ordered by $<$ (there are no infinite descending sequences of $a_n$). In 1892, Cantor proved this theorem:'"`UNIQ--ref-000000F6-QINU`"' ::given any set $S$, there exists another set, what we now call the power set $p(S)$, whose cardinality is greater than $S$ (Cantor’s Theorem). Reasoning by analogy, Cantor also argued that there is an entire infinite and very precise hierarchy of transfinite (cardinal) numbers, as follows:'"`UNIQ--ref-000000F7-QINU`"' # for a finite set of $n$ elements, its power set, i.e. $p(n)$, has exactly $2^n$ elements # the set of natural numbers $\mathbb{N}$ has power (cardinality) $ℵ_0$ # the power set of $\mathbb{N}$, i.e. $p(\mathbb{N})$, has cardinality $2^{ℵ_0}$ # the power set of this new set, i.e. $p(p(\mathbb{N}))$, has cardinality $2^{2^{ℵ_0}}$ # and so on ... thus defining an infinite hierarchy of transfinite cardinals ordered as follows: $ℵ_0 < 2^{ℵ_0} < 2^{2^{ℵ_0}} < … $. Cantor classified the transfinite ordinals and related them to cardinals as follows: * the “first number class” consisted of the finite ordinals, the set $\mathbb{N}$ of natural numbers with cardinality $ℵ_0$, all of which have only a finite set of predecessors. * the “second number class” was formed by $ω$ and all numbers following it (including $ω^ω$, etc.) with cardinality $ℵ_1$, all of which have only a set of predecessors with cardinality $ℵ_0$. * the “third number class” consisted of transfinite ordinals with cardinality $ℵ_2$, all of which have only a set of predecessors with cardinality $ℵ_1$. * and so on and so on.... The transfinite ordinals thus formed the basis of a well-defined scale of increasing transfinite cardinalities:'"`UNIQ--ref-000000F8-QINU`"' Since 1878, Cantor had known that the reals $\mathbb{R}$ formed a non-denumerable set, i.e. a set with a power higher than the naturals $\mathbb{N}$. Now he proved this further result:'"`UNIQ--ref-000000F9-QINU`"' ::The number of elements in the set of real numbers, which he had previously termed $c$, is the same as the number of elements in the power set of the natural numbers. In other words, he proved the equation $c = 2^{ℵ_0}$ to be true, meaning that the number of points of the continuum provided by the real line had exactly $2^{ℵ_0}$ points. All of this permitted a more precise formulation of Cantor’s Continuum Hypothesis as $c = ℵ_1$.'"`UNIQ--ref-000000FA-QINU`"' A partial summary of Cantor’s achievements arising from his theory of transfinite numbers includes an “almost modern” exposition of the theory of [[Well-ordered set|well-ordered sets]] and also the theory of [[Cardinal number|cardinal numbers]] and [[Ordinal number|ordinal numbers]].'"`UNIQ--ref-000000FB-QINU`"' In the view of some (but certainly not all) mathematicians, Cantor’s study of infinite sets and transfinite numbers introduced little that was alien to a “natural foundation” for mathematics, which “would, after all … need to talk about sets of real numbers” and “should be able to cope with one-to-one correspondences and well-orderings.”'"`UNIQ--ref-000000FC-QINU`"' Here is a succinct and robust defence of what Hilbert subsequently called “Cantor’s paradise”:'"`UNIQ--ref-000000FD-QINU`"' ::There are many mathematicians who will accept the ... theory of functions as developed in the 19th century, but will, if not reject, at least put aside the theory of transfinite numbers, on the grounds that it is not needed for analysis. Of course, on such grounds, one might also ask what analysis is needed for; and if the answer is basic physics, one might then ask what that is needed for. When it comes down to putting food in one’s mouth, the ‘need’ for any real mathematics becomes somewhat tenuous. Cantor started us on an intellectual journey. One can peel off at any point; but no one should make a virtue of doing so. ==='"`UNIQ--h-30--QINU`"'The paradoxes=== Cantor came to recognize that his new notion of set, which he introduced to support the development of the transfinite numbers, was problematic:'"`UNIQ--ref-000000FE-QINU`"' ::not every property of numbers “unites the objects possessing it into a whole” A significant consequence of Cantor’s general theory of sets not only for the process of mathematical rigourization generally, but also for what Hilbert would later state as his 2nd problem particularly, was this:'"`UNIQ--ref-000000FF-QINU`"' ::precisely when mathematicians were celebrating that “full rigor” had been finally attained, serious problems emerged for the foundations of set theory. The “serious problems” that emerged were, of course, paradoxes. Neither the initial introduction of infinite sets by others nor their use in his early theory of sets by Cantor himself had been problematic. However, his subsequent introduction of transfinite numbers and development of transfinite arithmetic made him aware of the potential for paradoxes within set theory. Cantor is said to have attributed the source of these paradoxes to the following:'"`UNIQ--ref-00000100-QINU`"' * the use (by Frege) of an unrestricted principle of comprehension * the acceptance (by Dedekind) of arbitrary subsets of a Universal Set (''Gedankenwelt'') More specifically, the claim is that Cantor himself traced the paradoxes to a faulty understanding (by others) of what constitutes a legitimate mathematical collection. For Cantor, the mathematically relevant notion of a collection is said to have been based on the “combinatorial concept” of a set:'"`UNIQ--ref-00000101-QINU`"' ::In order to be treated as a whole, [a mathematical collection] must be capable of being counted, in a broad sense of "count" which means ''well-orderable''. In contrast to this was the “logical concept” of a set, developed by Frege, accepted by Dedekind, and championed by Russell, which “treats collections as the extensIons of concepts”:'"`UNIQ--ref-00000102-QINU`"' ::For a multiplicity to be treated as a mathematical whole, we must have some propositional function which acts as a rule for picking out all of the members. The point of this contrast rests on the claim that the set-theoretic paradoxes are a problem only for the logical concept of a set, which includes the inconsistent Comprehension Principle, and has Russell's Paradox as a result.'"`UNIQ--ref-00000103-QINU`"' The general consensus, both then and now, however, is that Cantor’s own construction of the system of transfinite numbers introduced foundational problems in the form of paradoxes into mathematics.'"`UNIQ--ref-00000104-QINU`"' It is known that he was aware of at least two such paradoxes:'"`UNIQ--ref-00000105-QINU`"' '''Burali-Forti Paradox''' (paradox of the ordinals) ::As Cantor defined them, each transfinite ordinal is the order type of the set of its predecessors: ::* $ω$ is the order type of $\{0, 1, 2, 3, …\}$ ::* $ω+2$ is the order type of $\{0, 1, 2, 3, …, ω, ω+1\}$ ::* and so on, so that to each initial segment of the series of ordinals, there corresponds an immediately greater ordinal. ::Now, the “whole series” of all transfinite ordinals would form a well-ordered set, and to it there would, therefore, correspond a new ordinal number, $o$, that would have to be greater than all members of the “whole series”, and in particular $o < o$. '''Cantor’s paradox''' (paradox of the alephs): ::As Cantor defined them, to each aleph is the cardinality of a class of transfinite ordinals (as described above) ::If there existed a “set of all” cardinal numbers (alephs), applying Cantor's Theorem yields a new aleph $ℵ$, such that $ℵ < ℵ$. There are disagreements concerning Cantor’s notion of number and how that notion related to the concept of a well-ordered set. There are also disagreements concerning the paradoxes of which he was actually aware and when he became aware of them. There is, on the other hand, general agreement that Cantor understood the paradoxes to be “a fatal blow to the ‘logical’ approaches to sets favoured by Frege and Dedekind” and that, as a result, he attempted to put forth views that were opposed to the “naïve assumption that all well-defined collections, or systems, are also ‘consistent systems’.”'"`UNIQ--ref-00000106-QINU`"' The paradoxes convinced both Hilbert and Dedekind that there were important doubts concerning the foundations of set theory. Cantor apparently planned to discuss the paradoxes and the problem of well-ordering in a paper that he never actually published, but the contents of which he discussed in correspondence with Dedekind and Hilbert.'"`UNIQ--ref-00000107-QINU`"''"`UNIQ--ref-00000108-QINU`"' Cantor did not regard the paradoxes (of which he was aware) as a crisis in set theory, but rather as a spur for the overall delimitation of sets. He considered the class $Ω$ of ordinals $\omega_n$ and the class of cardinals $ℵ_n$ to be “inconsistent multiplicities”:'"`UNIQ--ref-00000109-QINU`"' He argued that whatever is deemed a ''set'' “can be well-ordered using a procedure whereby a well-ordering is defined through successive (recursive) choices":'"`UNIQ--ref-0000010A-QINU`"' ::The set must get well-ordered, else all of $Ω$ would be injectible into it, so that the set would have been an inconsistent multiplicity instead. Thus, in the ''Grundlagen'' Cantor introduced a distinction between totalities as sets and totalities as what came to be called "proper classes":'"`UNIQ--ref-0000010B-QINU`"' ::Every well-defined set has a power, but there are totalities, such as the totality of all whole numbers or of all powers, which have no power. His intention was to restrict the term ''set'' to "determinate infinites" (represented by the number classes) as distinguished from "absolute infinities" (represented by the totality of transfinite numbers or the totality of the number classes or powers). The late 19th century initially saw the scope of logic expand immensely, but then saw it contract. The work of Dedekind, Frege, et. al. appeared to link both propositional and predicate logic inextricably with set theory and the theory of relations. Subsequently, the discovery of the paradoxes led to changed understandings about logic, set theory, and mathematics:'"`UNIQ--ref-0000010C-QINU`"' * the theory of sets goes well beyond the logic of mathematics * the language of mathematics requires a strict formalization Paradoxes led to these changes without, ironically, leading to a single new theorem or metatheorem -- though they eventually led to new, very challenging axioms!'"`UNIQ--ref-0000010D-QINU`"' =='"`UNIQ--h-31--QINU`"'Axiomatic development of geometry== For two thousand years, Euclid's Elements, with its approach of proving its theorems starting from definitions and axioms, was unique in mathematics. It was not only “the one and only geometry,” but also “the structural paradigm for all other fields of mathematics.” The development of non-Euclidean geometries both arose out of and gave rise to questions about the geometry of Euclid. Euclid’s ''Elements'' was based on 5 axioms and 5 postulates and had a logical structure that enabled the development of proofs. However, it also had serious deficiencies, consisting of concealed assumptions, meaningless definitions, and logical inadequacies.'"`UNIQ--ref-0000010E-QINU`"''"`UNIQ--ref-0000010F-QINU`"' * Specifically and very importantly, Gauss had pointed out that the notion of ''betweenness'' was often used in Euclid, but was never defined. * More generally, the discovery of non-Euclidean geometries had, in itself, stimulated a general determination among mathematicians to bring out unstated assumptions and either justify them or avoid them. ==='"`UNIQ--h-32--QINU`"'Early efforts by Pasch=== Chief among those asking and answering questions about Euclid's ''Elements'' was Moritz Pasch, who laboured a half century in the foundations of geometry, “a field that didn’t really exist before he took a hard look at Euclid’s Elements and found a number of hidden assumptions in it that nobody had noticed before.”'"`UNIQ--ref-00000110-QINU`"' Pasch observed that Euclid's “definitions” of some of his common notions ($point$, $line$, and $plane$) were insufficient. To say, for example, that a point is “that which has no part” is not say what a point is, since we then further need to say what a “part” is! Others before Pasch had realized that attempting to define every concept of a mathematical discipline would result in an infinite regress of definitions. It was he who raised this issue specifically for geometry by asking, What terms of geometry must be left undefined? In answering this question for projective geometry, Pasch left these three primitive terms undefined, choosing the last two because, as he himself remarked, no one has actually had any experience of a line or a plane.:'"`UNIQ--ref-00000111-QINU`"' * $point$ * $line$ $segment$ -- rather than Euclid’s $line$ * $planar$ $section$ -- rather than Euclid’s $plane$ Agreeing with Gauss, Pasch addressed the deficiency in Euclid’s geometry arising from the absence of axioms relating to the order of points on a line and in the plane, such as the following:'"`UNIQ--ref-00000112-QINU`"' * if a point $B$ is between a point $A$ and a point $C$, then $C$ is not between $A$ and $B$. * every line divides a plane into two parts. * if a line enters a triangle $ABC$ through the side $AB$ and does not pass through $C$, then it must leave the triangle either between $B$ and $C$ or between $C$ and $A$. Before Pasch, students could draw diagrams to illustrate these things, but geometers had no basis for dealing logically with the observations given by those diagrams. In 1882, Pasch published ''Lectures on Modern Geometry'', which has been called a "truly satisfactory and … serious instance of axiomatization of a branch of knowledge.“'"`UNIQ--ref-00000113-QINU`"' Pasch’s book was an axiomatic development of projective geometry embodying the following ideas about axioms:'"`UNIQ--ref-00000114-QINU`"' * axioms were assertions about terms and notions, which remained otherwise undefined * experience could suggest axioms, but could not be appealed to in proofs from axioms Pasch’s axioms, then, served two purposes: they (implicitly) gave meaning to the undefined terms and notions of his geometry and they (alone) yielded its theorems. Pasch believed that a too great reliance on physical intuition was the root cause of the problems in geometry. He supported his belief referring to an application of the following principle of duality that had been known for more than a half century:'"`UNIQ--ref-00000115-QINU`"' ::Any true statement of projective ''plane'' geometry gives rise to another, equally true, dual statement obtained by substituting ‘point’ for ‘line’, ‘collinear’ for ‘concurrent’, ‘meet’ for ‘join’, and vice versa, wherever these words occur in the former. (For projective ''space'' geometry, duality holds for points and planes.) Pasch noted that our physical intuitions about points and lines contradict this duality principle and, as a consequence, though we ''know'' the principle to be true, we don’t really ''believe'' that the terms ‘points’ and ‘lines’ are really interchangeable! Pasch believed that argument in mathematics should proceed not intuitively from physical interpretations of primitive terms, but logically from proofs based on axioms that related those primitive terms to one another. He saw that two different, but related tasks underlay the development of an axiomatic theory of geometry:'"`UNIQ--ref-00000116-QINU`"' * specifically, the identification of the hidden assumptions of Euclid’s (and others’) geometry * generally, the determination of what actually constitutes an axiom system Pasch played a role in accomplishing both of these tasks. Hilbert was greatly influenced by his work. ==='"`UNIQ--h-33--QINU`"'Hilbert's ''Grundlagen''=== Hilbert understood that the arithmetization of analysis and the axiomatization of arithmetic were notable achievements of nineteenth century mathematics. Through them, most of mathematics had been provided with a strict axiomatic foundation. What he objected to was any suggestion that the concepts of arithmetic alone were susceptible of a fully rigorous treatment. He felt that another, equally notable achievement of the nineteenth century was the flourishing of geometry and, in particular, the development of non-Euclidean geometries. What remained, then, was to establish a purely formal and deductive basis for geometry.'"`UNIQ--ref-00000117-QINU`"' Hilbert himself did the pioneer work towards the end of giving geometry the purely formal character found in algebra and analysis. In 1893, he prepared a course on non-Euclidean geometry. He was familiar with Pasch’s previous work in geometry and adopted his axiomatic approach in preparing the course. In 1899, the year before his Paris Problems Address, he published his theory of geometry, ''Grundlagen der Geometrie'', the importance of which can be summarized as follows: * it provided an axiomatic foundation that addressed the deficiencies of Euclid’s ''Elements'' * it examined meta-mathematical notions associated with the axiomatization process itself Hilbert intended that ''Grundlagen'' serve multiple purposes: a specifically geometrical purpose, a larger mathematical purpose involving geometry and analysis, and an overall meta-mathematical purpose.'"`UNIQ--ref-00000118-QINU`"' ==='"`UNIQ--h-34--QINU`"'The specific geometric purpose=== The specific purpose of ''Grundlagen'' was to lay down a foundation, different from the evidence of intuition, by means of which all (known) theorems of Euclidean geometry might be rigourously deduced in a manner that was true to ''the spirit'', if not to ''the letter'' of Euclid’s ''Elements''. As the “sufficiently general and comprehensive principle” necessary for his purpose, Hilbert chose the axiomatic method.'"`UNIQ--ref-00000119-QINU`"' Hilbert's geometry was based on the following:'"`UNIQ--ref-0000011A-QINU`"''"`UNIQ--ref-0000011B-QINU`"' * primitive elements: $point$, $line$, and $plane$ * primitive relations: ::of ''incidence'' between (i) a point and a straight line and (ii) a straight line and a plane ::of ''order'' between (iii) three points ::of ''congruence'' between (iv) two pairs of points (‘segments’) and (v) two equivalence classes of point triples (‘angles’). * axioms, in groups: ''incidence'', ''order'', ''parallelism'', ''congruence'', and ''continuity''. In 1902, an authorized English translation of the ''Grundlagen'' was published. It is instructive to exaimine how Hilbert himself first presented his theory. In the first two paragraphs, Hilbert introduced (1) the primitive terms of his geometry and (2) the groups of axioms connecting these terms:'"`UNIQ--ref-0000011C-QINU`"' ::1. Let us consider three distinct systems of things. ::* The things composing the first system, we will call $points$ and designate them by the letters $A, B, C,. . .$ ::* those of the second, we will call straight $lines$ and designate them by the letters $a, b, c,. . .$ ::* those of the third system, we will call $planes$ and designate them by the Greek letters $α, β, γ,. . .$ ::The points are called the elements of linear geometry; the points and straight lines, the elements of plane geometry; and the points, lines, and planes, the elements of the geometry of space or the elements of space. ::2. We think of these points, straight lines, and planes as having certain mutual relations, which we indicate by means of such words as “are situated,” “between,” “parallel,” “congruent,” “continuous,” etc. The complete and exact description of these relations follows as a consequence of the axioms of geometry. These axioms may be arranged in five groups. Each of these groups expresses, by itself, certain related fundamental facts of our intuition. We will name these groups as follows: :::I, 1–7. Axioms of connection. :::II, 1–5. Axioms of order. :::III. Axiom of parallels (Euclid’s axiom). :::IV, 1–6. Axioms of congruence. :::V. Axiom of continuity (Archimedes’s axiom). Following this, Hilbert introduced the axioms of his geometry, one group at a time, noting some alternative, equivalent language used to express them and noting some theorems derivable from them. Here are some interesting details about the first two groups of axioms:'"`UNIQ--ref-0000011D-QINU`"' ::Group I: The axioms of this group establish a connection between the concepts indicated above; namely, points, straight lines, and planes…. :Instead of [saying, for example, that “two distinct points $A$ and $B$ always completely “determine” a straight line $a$,] we may also employ other forms of expression; for example, we may say $A$ “lies upon” $a$, $A$ “is a point of” $a$, $a$ “goes through” $A$ “and through” $B$, $a$ “joins” $A$ “and” or “with” $B$, etc. If $A$ lies upon $a$ and at the same time upon another straight line $b$, we make use also of the expression: “The straight lines” $a$ “and” $b$ “have the point $A$ in common,” etc. ::Group II: The axioms of this group define the idea expressed by the word “between,” and make possible, upon the basis of this idea, an order of sequence of the points upon a straight line, in a plane, and in space. The points of a straight line have a certain relation to one another which the word “between” serves to describe. As Hilbert intended, the primitive relations connected the primitive elements and the axioms of connection (incidence), order, and congruence defined (implicitly) the three primitive relations. The primitive elements and relations remained otherwise undefined. Taken together, the axioms expressed “certain related fundamental facts of our [spatial] intuition.”'"`UNIQ--ref-0000011E-QINU`"''"`UNIQ--ref-0000011F-QINU`"''"`UNIQ--ref-00000120-QINU`"' The sense in which axioms are ''implicit definitions'' is made apparent by considering that if the terms of a theory (the theory of geometry, for example) support multiple interpretations, then the sentences of that theory, and sets of those sentences, provide definitions ''of a certain kind'':'"`UNIQ--ref-00000121-QINU`"' ::A set $AX$ of sentences containing $n$ (geometric) terms defines an $n-place$ relation $R_{AX}$ holding of just those $n-tuples$ which, when taken respectively as the interpretations of $AX$'s (geometric) terms, render the members of $AX$ true. Thus the $n$ terms of $AX$ serve as "place-holders" that are devoid of meaning in themselves, but that yield to multiple interpretations. The initial choice of a system of axioms was not, then, the end of an enquiry into the foundations of a theory. Rather, the enquiry would not be complete until the axioms, which define the concepts and relations of a theory, are such that ''no other characteristics of those concepts and relations can be added''.'"`UNIQ--ref-00000122-QINU`"' Enquiry into foundations is thus an evolution in the direction of an ever better understanding of the basic concepts and relations of a theory, for which the axioms provide definitions. Hence, further experience working with a theory can lead to a widening of those definitions and, consequently, a widening of our understanding of those basic concepts and of the entire theory itself.'"`UNIQ--ref-00000123-QINU`"' Thus, in developing his theory of geometry, Hilbert discarded the “intuitive-empirical” level of the older geometrical views by making all his assumptions explicit and by giving his undefined terms no properties beyond those indicated in the axioms:'"`UNIQ--ref-00000124-QINU`"' * points, lines, and planes were to be understood as elements of certain given sets * undefined relations were to be treated as abstract correspondences or mappings In this regard, and as Hilbert put it in a letter to Frege, “every theory is only an abstract structure or schema of concepts together with their necessary relations to one another, [while] the basic elements can be thought of in any way one likes.”'"`UNIQ--ref-00000125-QINU`"' The following anecdote speaks to the earnestness of Hilbert’s intentions with respect to leaving his notions undefined:'"`UNIQ--ref-00000126-QINU`"' ::In 1891, Hilbert attended a lecture on the foundations of geometry given at the Deutsche Mathematiker-Vereinigung meeting in Halle. Decades later (in 1935) it was reported that Hilbert came out of that meeting greatly excited by what he had just heard and made his famous declaration: “it must be possible to replace 'point, line, and plane' with 'table, chair, and beer mug' without thereby changing the validity of the theorems of geometry.” An example of a serious deficiency in the ''Elements'' was Euclid's use of the same word ”equal” for the many different equivalence relations that are important for geometry, among which are these:'"`UNIQ--ref-00000127-QINU`"' * equality * congruence of segments * congruence of angles * similarity for triangles and other figures * having same area for figures * having same volume for three dimensional polyhedra Hilbert (and those who continued his work) distinguished these relations by providing explicit definitions for them, using different symbols for them, and proving their properties -- with the exception of "equality" which is not a relation of geometry, but of logic. Hilbert would have understood this from the example of Peano's first axiomatization of arithmetic. Among the insufficiencies of Euclid’s Elements noted above was the lack of any definition (adequate or otherwise) for the notion of betweenness. Hilbert addressed this with specific axioms for this notion, known as the Axioms of Order, stating the first four as follows:'"`UNIQ--ref-00000128-QINU`"' ::II.1. If $A, B, C$ are points of a straight line and $B$ lies between $A$ and $C$, then $B$ lies also between $C$ and $A$. ::II.2. If $A$ and $C$ are two points of a straight line, then there exists at least one point $B$ lying between $A$ and $C$ and at least one point $D$ so situated that $C$ lies between $A$ and $D$ ::II.3. Of any three points situated on a straight line, there is always one and only one which lies between the other two. ::II.4. Any four points $A, B, C, D$ of a straight line can always be so arranged that $B$ shall lie between $A$ and $C$ and also between $A$ and $D$, and, furthermore, that $C$ shall lie between $A$ and $D$ and also between $B$ and $D$. Hilbert next introduced the following definition, followed by the fifth and last axiom of order:'"`UNIQ--ref-00000129-QINU`"' ::::''Definition''. We will call the system of two points $A$ and $B$, lying upon a straight line, a segment and denote it by $AB$ or $BA$. The points lying between $A$ and $B$ are called the points of the segment $AB$ or the points lying within the segment $AB$. All other points of the straight line are referred to as the points lying outside the segment $AB$. The points $A$ and $B$ are called the extremities of the segment $AB$. ::II.5. Let $A, B, C$ be three points not lying in the same straight line and let $a$ be a straight line lying in the plane $ABC$ and not passing through any of the points $A, B, C$. Then, if the straight line $a$ passes through a point of the segment $AB$, it will also pass through either a point of the segment $BC$ or a point of the segment $AC$. ::Axioms II, 1–4 contain statements concerning the points of a straight line only, and, hence, we will call them the linear axioms of group II. Axiom II, 5 relates to the elements of plane geometry and, consequently, shall be called the plane axiom of group II. As is obvious from reading his introduction, Hilbert developed his geometry axiomatically, but stated it informally, i.e. in ordinary language rather than in the language of a formal logic, a consequence of the simple fact that, as noted previously, he lacked the logical tools to do otherwise. Also obvious in Hilbert's presentation is the fact that running alongside his mathematics was a non-mathematical urging: ::Hilbert (writing in German) clearly wanted us (reading in English) to accept that his geometry, developed axiomatically using his undefined terms, was a (faithful) translation of the notions and concepts of our geometrical intuition(s) expressed in our ordinary language(s). In this regard, it is interesting to compare Hilbert’s informally stated axioms of order with axioms stated just slightly more formally. The following is a presentation of axioms of order for plane geometry:'"`UNIQ--ref-0000012A-QINU`"' :Given the following: :* A set $\alpha$ called a ''plane'', elements $P, Q, R, ... $ of this set called ''points'', and certain subsets $l, m, n, ... $of the plane called ''lines''. :* An undefined relation, symbolized $∗$. :Definitions: :* A line $l$ is the set of all points $P$ in the plane such that $P \in l$. :* Two lines $l, m$ are equal if $P \in l \iff P \in m$, for all points $P$. :* Points $P, Q$ are ''collinear'' if there is a line $l$ in the plane such that $P, Q \in l$. :Axioms of order are these: ::# If $A ∗ B ∗ C$, then both $A, B, C \in l$ for some line $l$ and also $C ∗ B ∗ A$. ::# Given two distinct points $A$ and $B$, there exists a point $C$ such that $A ∗ B ∗ C$. ::# If $A, B, C \in l$, then exactly one of the statements $A ∗ B ∗ C$, $A ∗ C ∗ B$, and $B ∗ A ∗ C$ is true. ::# Let $A, B, C \notin l$ be non-''collinear'' points. If there exists $D \in l$ so that $A ∗ D ∗ C$, then there exists an $X \in l$ such that $A ∗ X ∗ B$ or $B ∗ X ∗ C$. Unlike Hilbert's presentation, these axioms of order develop the undefined geometric property $∗$ without appeal to the ordinary language words that we use to express our geometrical intuitions. A linguistically sparer presentation would result from omitting entirely the terms "point," "line," and "plane". ==='"`UNIQ--h-35--QINU`"'The larger mathematical purpose=== The larger purpose of ''Grundlagen'' was to provide an axiomatic foundation sufficient not only for Euclid’s geometry, but also for the various non-Euclidean geometries and, further, to enable those various theories of geometry to be related to other mathematical theories, specifically, the theory of real numbers. Hilbert described the specific purpose of ''Grundlagen'' as an attempt to lay down a “simple” and “complete” system of “mutually independent” axioms, from which all known theorems of (Euclidean) geometry might be deduced. His larger overall purpose was to provide a foundation both different from the evidence of intuition and sufficient not only for Euclid’s geometry, but (eventually) also for the various non-Euclidean geometries.'"`UNIQ--ref-0000012B-QINU`"' In his early (thru 1905) writings, Hilbert considered axiomatic systems to be ''open'' systems:'"`UNIQ--ref-0000012C-QINU`"' ::If geometry is to serve as a model for the treatment of physical axioms, we shall try first by a small number of axioms to include as large a class as possible of physical phenomena, and then by adjoining new axioms to arrive gradually at the more special theories. Hilbert elaborated this in stating what he considered to be “the principal task of non-Euclidean geometry”:'"`UNIQ--ref-0000012D-QINU`"' ::constructing the various ''possible'' geometries by the successive introduction of elementary axioms, up until the ''final construction of the only remaining one'', Euclidean geometry. This process of successively introducing axioms has been used in at least one presentation of Hilbert’s axiom system for plane geometry, whose author described the process as follows:'"`UNIQ--ref-0000012E-QINU`"' ::As we introduce Hilbert’s axioms, we will gradually put more and more restrictions on these [basic] ingredients [points and lines in a plane] and in the end they will essentially determine Euclidean plane geometry uniquely. Finally, the introductory paragraphs of Hilbert’s first (German) edition mention only one axiom of continuity, the axiom of Archimedes. However, Hilbert added the following remark to the subsequent (French and English) translations: ::Remark. To the preceding five groups of axioms, we may add the following one, which, although not of a purely geometrical nature, merits particular attention from a theoretical point of view. It may be expressed in the following form: ::::Axiom of Completeness. (Vollstandigkeit): To a system of points, straight lines, and planes, it is impossible to add other elements in such a manner that the system thus generalized shall form a new geometry obeying all of the five groups of axioms. In other words, the elements of geometry form a system which is not susceptible of extension, if we regard the five groups of axioms as valid. Thus, we can say that, even in his first edition, Hilbert introduced two axioms of continuity, which have come to be identified in the subsequent literature as V.1 and V.2: ::V.1 the Archimedean axiom ::V.2 the axiom of completeness and about which we know the following:'"`UNIQ--ref-0000012F-QINU`"' :* Axiom V.1 allows the measurement of segments and angles using real numbers…. Since Hilbert, this axiom is also known as the axiom of measurement…. :* There are several [alternative] axioms for completeness, with very similar implications, which nevertheless have slight but deep differences…. Hilbert [himself] suggested different axioms of continuity in different editions of his Foundations of Geometry. :* The version of axiom V.2 introduced in Hilbert's first edition is based on Cantor’s definition of the real numbers. Alternative versions are based on the definitions of Dedekind and Weierstrass. Speaking generally, we can say this about how the hierarchy of geometries is related to the axioms as Hilbert has grouped them:'"`UNIQ--ref-00000130-QINU`"' * A ''Hilbert plane'' is any model for two-dimensional geometry where Hilbert’s axioms of incidence, order, and congruence hold. The axioms of the Hilbert plane form the basis of both Euclidean and non-Euclidean geometry. Neither the axioms of continuity (the Archimedean axiom and the axiom of completeness) nor the parallel axiom need to hold for an arbitrary Hilbert plane. The geometry of the Hilbert plane has been termed ''neutral geometry'', “because it neither affirms nor denies the parallel axiom.”'"`UNIQ--ref-00000131-QINU`"' * A ''Pythagorean plane'' is a Hilbert plane for which the axiom of parallelism holds. * A ''Euclidean plane'' is a Pythagorean plane for which the axioms of continuity hold. Hilbert knew that developing Euclid’s geometry with “a simple and complete set of independent axioms” required decisions resulting in his being true to ''the spirit'' rather than to ''the letter'' of the ''Elements''. Among those decisions, the following two are closely related: * the introduction of $circle$ as a defined (non-primitive) unaxiomatized term * the use of a “completeness” axiom that introduced real numbers Indeed, some modern authors have suggested that “a more natural way to do geometry” would result from an approach such as follows:'"`UNIQ--ref-00000132-QINU`"' * introducing circles in a natural, classical way * introducing continuity in a way directly related to proofs. However, adding $circle$ to the other primitive terms would have introduced a redundancy, a criticism that Hilbert himself levelled against Pasch’s geometry. Hilbert’s intention was that the assumptions (terms and axioms) should be in some sense a minimal set necessary to prove the propositions and support the construction. Even so, it would have been possible to introduce axioms for circles that supported the completeness necessary for various propositions and constructions of Euclid’s ''Elements'' without introducing the real numbers. Here are two such axioms:'"`UNIQ--ref-00000133-QINU`"' ::''Line-circle Intersection property'': A line that contains a point inside a circle does intersect the circle. ::''Circle-circle intersection property'': Given two circles $\gamma$, $\delta$, if $\delta$ contains at least one point inside $\gamma$ and at least one point outside $\gamma$, then $\gamma$ and $\delta$ will meet. However, Hilbert's larger mathematical purpose was broader than doing geometry in a rigourous, natural way. His choice of a more powerful axiom of completeness, an easy road towards his larger mathematical and meta-mathematical purposes, enabled the following: * expanding the Euclidean plane to the Cartesian plane * proving of the relative consistency of geometry and analysis * establishing a categorical axiom system for geometry ==='"`UNIQ--h-36--QINU`"'The overall meta-mathematical purpose=== The overall purpose of ''Grundlagen'' was to examine various meta-mathematical notions that applied not to mathematical objects, such as points, lines, integers, reals, etc., but rather to axioms of mathematical theories, such as geometry and analysis. An early example of Hilbert’s concern with the meta-mathematics of axiomatization arose from his familiarity with Pasch’s axioms for geometry, which he knew included a redundancy. Specifically, Pasch’s Archimedean axiom could be derived from others in his system. Hilbert considered this to be a deficiency. Even at this early date, then, Hilbert understood that the axioms for a geometry should be, in some sense, a ''minimal'' set of assertions from which the whole of the geometry could be deduced.'"`UNIQ--ref-00000134-QINU`"' These are the meta-mathematical notions that Hilbert (to some extent) examined in ''Grundlagen'' and applied to its system of axioms: ''simplicity'', ''completeness'', (mutual) ''independence'', ''compatibility'', and ''consistency''. For Hilbert, the simplicity of an axiom was its intention to contain or express “no more than a single idea." This notion was little referred to subsequently and was never formally defined. It was apparently received from Hertz and has been called an "aesthetic desideratum" of no mathematical significance.'"`UNIQ--ref-00000135-QINU`"' The notion of completeness that Hilbert required of his axioms of geometry was what he would have required of an adequate axiomatization of any discipline, namely, that the axioms should yield all the known theorems of the discipline in question. The ''Grundlagen'' itself was evidence that Hilbert’s axioms were indeed complete in this sense that he had derived from them all the known theorems in which he was interested, either of Euclidean geometry or, independently of the parallel postulate, of “absolute” or “neutral” geometry. However, ''evidence'' for completeness is not ''proof'' of completeness. Hilbert had no method of formally proving the completeness of his axioms that corresponded to his formal proof of their independence.'"`UNIQ--ref-00000136-QINU`"' In ''Grundlagen'', Hilbert actually succeeded (more or less) in demonstrating the following:'"`UNIQ--ref-00000137-QINU`"''"`UNIQ--ref-00000138-QINU`"' * the independence of the SAS axiom, of the axiom of parallels from the other Euclidean axioms, and of some important theorems from specific groups of axioms * the consistency of various sub-groups of the axioms * the relative consistency of the entire set of axioms for Euclidean geometry, assuming the consistency of the real number system * various relations of provability Hilbert’s demonstrations of the consistency and the independence of his axioms were demonstrations he made relative to a familiar, background theory whose consistency was accepted. More specifically, he proved that the consistency of geometry could be reduced to proving the consistency of arithmetic. The method he used to do this was as follows:'"`UNIQ--ref-00000139-QINU`"''"`UNIQ--ref-0000013A-QINU`"' * ''Consistency'': Given a set $AX$ of sentences (described as above) and a familiar, background theory $B$, which is assumed to be consistent, construct an interpretation of the $n$ terms of $AX$ under which the members of $AX$ express theorems of $B$. This interpretation is an $n-tuple$ satisfying the relation $R_{AX}$ defined by $AX$. Its existence demonstrates the satisfiability of $R_{AX}$ and consequently the consistency of $AX$, relative to that of $B$. * ''Independence'': Given set $AX$ of sentences, another statement $I$, and a familiar, background theory $B$, which is assumed to be consistent, construct an interpretation of $AX$'s and $I$’s terms under which the members of $AX$ express theorems of $B$, while $I$ expresses the negation of a theorem of $B$. Proceeding as above, the consistency of $AX \cup \{\sim I\}$ relative to that of $B$ demonstrates the independence of $I$ from $AX$, relative to consistency of $B$. As Hilbert understood it, consistency applied to the abstract structure of concepts and relations that were defined by $AX$ when its (geometric) terms were taken as place-holders. The consistency that he had in mind held of $AX_\mathbb{G}$ $\iff$ it held of $AX_\mathbb{R}$, since both shared (were instances of) the same abstract structure. '"`UNIQ--ref-0000013B-QINU`"' Equivalently, if there is an interpretation under which the sentences of $AX_\mathbb{G}$ expressed truths of $AX_\mathbb{R}$, then the question of the consistency for $AX_\mathbb{G}$ relative to $AX_\mathbb{R}$ was answered in the affirmative. In the context of formal theories, Hilbert’s conception of consistency and his associated methodology for consistency-proofs are, for the most part standard today.[317]

All this notwithstanding, the question has been asked,

Why did Hilbert actually address the consistency of his axioms?

It seems unlikely that he really entertained the possibility that Euclidean geometry contained contradictions, since he conceived it as “an empirically motivated discipline, turned into a purely mathematical science after a long, historical process of evolution and depuration.”

Further, Hilbert had (in his first German edition) presented a model of Euclidean geometry “on a countable, proper sub-field—of whose consistency he may have been confident—and not the whole field of real numbers.” The issue of continuity of the real numbers might have raised difficulties, but there were no such difficulties arising from these fields of numbers.

The suggested explanation is that Hilbert’s attention to consistency arose as a result of his belief that “the axiomatic treatment of geometry was part of a larger enterprise, relevant also for other physical theories.” He considered that contradictions might have been introduced into geometry as a result of the particular way in which he had formulated his axioms, not only in order to account for the theorems of physical science, but also as a result of the recent development of non-Euclidean geometries.[318]

The rigour required for the axiomatic analysis underlying Grundlagen made necessary many additions, corrections, and improvements over the years following the books first edition. Most of these changes concerned only details. The basic structure of Grundlagen (the groups of axioms, the theorems considered, and the innovative methodological approach) remained unchanged through many editions.[319]

The ideas and methods that Hilbert put to work in his early efforts at axiomatization not only made possible at the time a foundation for geometry and the theory of real numbers, but also are still at work today shaping contemporary mathematical practice.[320]

Two curious aspects of Grundlagen

There are two somewhat curious aspects of Hilbert’s understanding of the axiomatization of geometry:

  1. the role of intuition in developing axioms
  2. the relationship of geometry to the physical sciences

The influence of both of these is reflected in the manner in which Hilbert discussed the axioms of his geometry -- see Some specifics of the Hilbert axiomatization.

With respect to the role of intuition, even if it was not to serve as the foundation for geometry, Hilbert nevertheless understood that the process of axiomatization began with intuitions of a domain of facts [Tatsachen]. In summary, Hilbert’s description of the way the axiomatic method proceeds is as follows:[321]

  1. it analyzes the theorems and concepts of a mathematical theory
  2. it isolates the basic principles that correspond to intuitive ideas
  3. it formalizes these principles as axioms.

In 1905, in a course titled “The Logical Principles of Mathematical Thinking,” Hilbert presented his geometry anew. His discussion, which included the many corrections and additions introduced since 1900, started with the same three kinds of undefined elements: points, lines, and planes. He described this choice as “arbitrary,” by which he meant constrained not merely by the mathematical requirement of consistency, but also “by the need to remain close to the ‘intuitive facts of geometry’.” Thus, instead of his three chosen elements, Hilbert said he could have started with “circles and spheres,” formulating axioms of geometry “that are still in agreement with the usual, intuitive geometry.”[322]

With respect to the relationship of geometry to the physical sciences, Hilbert viewed the axiomatization of geometry as part of a larger task: the axiomatization of natural science, in general, and of physics, especially mechanics, in particular. This view stemmed in part from his having taught (between 1897-1899) seminars on mechanics and also a full course on mechanics. In this latter, he compared geometry and mechanics as follows:[323]

Geometry also [like mechanics] emerges from the observation of nature, from experience. To this extent, it is an experimental science. ... But its experimental foundations are so irrefutably and so generally acknowledged, they have been confirmed to such a degree, that no further proof of them is deemed necessary. Moreover, all that is needed is to derive these foundations from a minimal set of independent axioms and thus to construct the whole edifice of geometry by purely logical means. In this way [i.e., by means of the axiomatic treatment] geometry is turned into a pure mathematical science.

Hilbert’s view of geometry as a close relation of mechanics also had roots in his acquaintance with Hertz and his knowledge and respect for Hertz’s writings. In his 1899 course of Euclidean geometry, Hilbert stated his goals for the axiomatization of geometry as follows:[324]

a complete description, by means of independent statements, of the basic facts from which all known theorems of geometry can be derived

Hilbert credited Hertz’s Principles of Mechanics as the source of this statement.

Hilbert’s 2nd problem

In his 1990 lecture to the International Congress of Mathematicians in Paris, David Hilbert presented a list of open problems in mathematics. He expressed the 2nd of these problems, known variously as the compatibility of the arithmetical axioms and the consistency of arithmetic, as follows:[325]

When we are engaged in investigating the foundations of a science, we must set up a system of axioms which contains an exact and complete description of the relations subsisting between the elementary ideas of that science. The axioms so set up are at the same time the definitions of those elementary ideas; and no statement within the realm of the science whose foundation we are testing is held to be correct unless it can be derived from those axioms by means of a finite number of logical steps. Upon closer consideration the question arises: Whether, in any way, certain statements of single axioms depend upon one another, and whether the axioms may not therefore contain certain parts in common, which must be isolated if one wishes to arrive at a system of axioms that shall be altogether independent of one another.
But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms: To prove that they are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results.

Thus, we can see that Hilbert’s 2nd problem arose from a principle that had emerged in his thought during his work on the foundations of geometry:[326]

“mathematical existence is nothing other than consistency”

Hilbert had successfully provided axioms for geometry. He now sought to introduce a program for axiomatizing the whole of mathematics. Such a program would require not only axioms for analysis, but also a direct proof of the consistency of analysis:[327]

... a direct method is needed for the proof of the compatibility of the arithmetical axioms. The axioms of arithmetic are essentially nothing else than the known rules of calculation, with the addition of the axiom of continuity. I recently … replaced the axiom of continuity by two simpler axioms, namely, the well-known axiom of Archimedes, and a new axiom essentially as follows:
that numbers form a system of things which is capable of no further extension, as long as all the other axioms hold (axiom of completeness).
I am convinced that it must be possible to find a direct proof for the compatibility of the arithmetical axioms, by means of a careful study and suitable modification of the known methods of reasoning in the theory of irrational numbers.

Clearly, Hilbert's wording of the "new axiom" (of completeness) for arithmetic used in the 2nd problem parallels his initial wording of the axiom of completeness that he introduced for geometry in the Grundlagen. More generally, however, the whole of the 2nd problem is itself heir to the three decades-long effort, which preceded his lecture, to axiomatize not only geometry, but also arithmetic, set theory, and logic itself.

In the decades following his initial statement of the 2nd problem, Hilbert made it more explicit by developing “a formal system of explicit assumptions” (see Axiom and Axiomatic method) upon which he intended to base the methods of mathematical reasoning, eventually stipulating that any such system must be shown to have these characteristics:[328][329]

  1. the assumptions should be "independent" of one another (see Independence)
  2. the assumptions should be “consistent” (free of contradictions) (see Consistency)
  3. the assumptions should be “complete” (represents all the truths of mathematics) (see Completeness)
  4. there should be a procedure for deciding whether any statement expressed using the system is true or not (see Decision problem and Undecidability)

Hilbert's 2nd problem is said by some to have been solved, albeit in a negative sense, by K. Gödel (see Hilbert problems and Gödel incompleteness theorem).

For a history of the subsequent development of Hilbert’s program for the foundations of mathematics, which was initiated by his 2nd problem, see the article Hilbert program.

Notes

  1. Dedekind (1888) p. 35 cited in Gillies p. 8
  2. Dasgupta p. 29
  3. Jones (1996)
  4. Ewald (2002) p. 2
  5. Ewald (2002) p. 2
  6. Compare this section with a related discussion of non-mathematical issues in the Arithmetization of analysis program.
  7. Renfro
  8. Waterhouse p. 435, cited in Renfro. In Renfro’s opinion, Cantor’s “disagreement is only with the words, not with Gauss' actual ideas…. Cantor objected not to Gauss' statement in context but to the meaning attributed to it by his own contemporaries.”
  9. O’Connor and Robertson (2005)
  10. Grattan-Guinness p. 125 footnote cited in Renfro
  11. Boyer (1939) pp. 270-271 cited in Renfro
  12. Wikipedia “C S Peirce” § “Mathematics” emphasis added. Readers are encouraged to review the Mathematics section of this Wikipedia article for its notes and references for these and others of Peirce’s discoveries.
  13. Russinoff p. 451 emphasis added
  14. Edwards cited in Russinoff p. 451
  15. O’Connor and Robertson (2002) “Frege”
  16. Gillies p. 78
  17. Reck (2013)
  18. Russell cited in O’Connor and Robertson (2002) “Frege”
  19. O’Connor and Robertson
  20. Encyclopedia Britannica “Augustus De Morgan”
  21. Hodges (2015)
  22. Reck (2013) Abstract
  23. Ewald (2002)
  24. For related modern mathematical notions, see Abstraction, mathematical, Abstraction of actual infinity, Abstraction of potential realizability, and Infinity
  25. Netz
  26. Netz
  27. Spalt cited in O'Connor and Robertson (2002)
  28. Netz, Saito, and Tchernetska cited in O'Connor and Robertson (2002)
  29. Kirschner 2.6 Mathematics
  30. O'Connor and Robertson, (2002)
  31. O'Connor and Robertson, (2002). The property that an infinite set can be put into one-to-one correspondence with a proper subset of itself is today known as the Hilbert infinite hotel property.
  32. Waterhouse cited in O’Connor and Robertson (2002)
  33. Netz
  34. Bolzano cited in O’Connor and Robertson (1996) (2002) (2005)
  35. Dedekind (1930/32) Vol. 1, pp. 46-47, quoted in Kanamori (2012) p. 49, cited in Reck (2013) slide 5
  36. Ferreirós (2011b) §1
  37. Gillies p. 8 emphasis added
  38. Ferreirós (2011b) §1
  39. Reck (2011) §2.2
  40. Gillies p. 8
  41. Bochenski cited in Boyer (1968) p. 633
  42. See the Historical sketch in Mathematical logic
  43. Moore p. 96
  44. Ferreirós (2001) p. 442
  45. Jones “The History of Formal Logic”
  46. Jones “A Short History of Rigour in Mathematics”
  47. Ferreirós (2001) p. 441
  48. Boyer (1968) p. 633
  49. van Benthem et. al. (2014). The expository material on Aristotelian syllogisms is excerpted from Chapter 3 of the text.
  50. Russinoff p. 454
  51. Josiah Royce quoted in Shen cited in Russinoff p. 451
  52. Boyer (1968) pp. 633-634 emphasis added
  53. Peacock cited in O’Connor and Robertson (2015)
  54. Peacock cited in O’Connor and Robertson (2015) emphasis added
  55. Boyer (1968) pp. 633-634 emphasis added
  56. O’Connor and Robertson “Augustus De Morgan”
  57. Boyer (1968) p. 623
  58. De Morgan (1849) cited in Barnett p. 3
  59. De Morgan (1847) cited in Barnett p. 1
  60. Barnett p. 1
  61. Boyer (1968) p. 633
  62. Gillies pp. 74-75
  63. Boyer (1968) pp. 633-634
  64. O’Connor and Robertson (2004)
  65. See Boolean algebra.
  66. Moore p. 96
  67. Burris (2014) §4.
  68. Burris (2014) §3.
  69. Burris (2014). Burris provides a detailed, step-by-step description of the process that Boole used to analyze arguments using his algebraic logic.
  70. Boyer (1968) p.635
  71. Burris (2014) provides a selection of examples illustrating the workings of his methods, including “a substantial example” of the workings of Boole’s General Method found in his 1854 work.
  72. O’Connor and Robertson (2004) emphasis added
  73. van Benthem 2. The shift from classical to modern logic
  74. Gillies p. 73
  75. Burris (2015) §4. Jevons...
  76. Grattan-Guinness (1991) cited in O’Connor and Robertson (2000)
  77. Boyer (1968) p. 636. See De Morgan laws for a modern formal statement of these laws. See Duality principle for a general discussion of mutual substitution of logical operations in the formulas of formal logical and logical-objective languages.
  78. Boyer (1968) pp. 636-638
  79. Encyclopædia Britannica “History of Logic § C S Peirce” emphasis added
  80. Tarski p. 73
  81. Anellis (2012b) § 2
  82. Peirce cited in Anellis (2012b) § 2
  83. Anellis (2012a) p. 246
  84. Anellis (2012a) pp. 252-253
  85. Tarski pp. 73-74
  86. Set theory
  87. Wikipedia “Naive set theory”
  88. Porubsky notes that the term naive set theory came into broad use in the 1960s following its use as the title of Halmos’ text.
  89. Bolzano cited in Porubsky
  90. Bolzano §4 cited in Tait p. 2
  91. Porubsky
  92. Tait p. 2
  93. Bolzano §3 cited in Tait p. 3. Tait tempers this criticism of Bolzano’s understanding, noting that both Cantor and Dedekind also avoided the null set -- “no whole has zero parts” -- and that “as late as 1930, Zermelo chose in his important paper [1930] on the foundations of set theory to axiomatize set theory without the null set.”
  94. Bolzano §11 cited in Tait p. 3
  95. Brown (2010) §"Naive Set vs. Axiomatic Set Theories"
  96. Wikipedia “Naive set theory”
  97. O’Connor and Robertson “A history of set theory”
  98. Bagaria §1
  99. Ebbinghaus p. 298 cited in Porubsky
  100. Tait p. 3
  101. Jones (1996) § The Formalization of Mathematics
  102. Wikipedia “Naive set theory”
  103. O’Connor and Robertson “A history of set theory”
  104. Ebbinghaus p. 298 cited in Porubsky
  105. Bagaria (2014) §1
  106. Ferreirós (2011b) §1
  107. Ferreirós (2011b) §1 citing Ewald (1996) Vol. 2
  108. Burris (1997)
  109. O’Connor and Robertson “A history of set theory”
  110. El Naschie (2015)
  111. O’Connor and Robertson “A history of set theory”
  112. Burris (1997)
  113. Tait p. 2
  114. El Naschie, M S. (2015)
  115. Burris (1997)
  116. El Naschie, M S. (2015)
  117. Bagaria (2014)
  118. Tait p. 5-6
  119. Tait pp. 5-6
  120. Tait p. 4
  121. Wikipedia "Set theory"
  122. Halmos cited in Toida (2013) §"Naive Set Theory vs. Axiomatic Set Theory"
  123. Toida (2013) §"Naive Set Theory vs. Axiomatic Set Theory"
  124. Tait p. 2
  125. Tait p. 3
  126. Tait p. 2
  127. Porubsky
  128. Azzano p. 8
  129. Gillies (1982) p. 8
  130. Reck (2011) §2.2
  131. Azzano p. 12
  132. Reck (2011) 2.1
  133. Reck (2011) §2.3
  134. Reck (2011) §2.2
  135. Azzano p. 10
  136. Reck (2011) §2.3
  137. Azzano p. 12
  138. Gillies p. 51
  139. Frege (1893) cited in Gillies p. 51
  140. Gillies p. 52 emphasis added
  141. Gillies p. 51
  142. Gillies p. 66
  143. Ferreirós (2011a) p. 6
  144. Dedekind (1888) cited in Gillies pp. 52-58
  145. Gillies pp. 52-53.
  146. Gillies notes that these two notions, basic to set theory, were not completely distinguished, both notationally and conceptually, until Peano did so in 1894.
  147. Gillies speculates that Dedekind’s “certain reasons” for excluding the empty set arise from difficulties caused by his conflating $a \in S$ and $A \subseteq S$.
  148. Zermelo (1908) cited in Gillies pp. 52-58. Gillies notes that Dedekind's 1888 work "is the principal source" for Zermelo's 1908 paper, in which "Zermelo frequently refers to Dedekind."
  149. Jones § The Formalization of Mathematics
  150. Toida 4.1 Why Predicate Logic?
  151. Peirce pp. 194-195 cited in Moore p. 99
  152. Anellis (2012a) p. 256
  153. Reck (2011) 2.2
  154. Gillies pp. 74-75
  155. HTFB (2015)
  156. O’Connor and Robertson (2002)
  157. Jones § The Formalization of Mathematics
  158. Mattey § Gottlob Frege
  159. Frege (1879) cited in Mattey § Gottlob Frege
  160. Mattey § Gottlob Frege
  161. Harrison (1996) § The History of Formal Logic
  162. Harrison (1996) § The History of Formal Logic
  163. Frege (1879) cited in Mattey § Gottlob Frege
  164. Azzano p. 12
  165. Math Stack Exch
  166. Boyer (1968) p. 644
  167. O’Connor and Robertson (2002)
  168. Sowa “Comments on Peirce’s …” § 1. Historical Background
  169. Sowa § 1. Historical Background
  170. Sowa § 1. Historical Background -- emphasis added
  171. Moore p. 98
  172. See the Historical sketch in Mathematical logic
  173. Bezhanishvil p. 1
  174. Podnieks § 3.1
  175. Kennedy (1963)
  176. Peirce (1881) p. 85 cited in Anellis (2012a) pp. 260-261. Anellis notes that, though Peirce uses the word “syllogistic” here, he was already translating syllogisms in his algebraic logic into implications using a conditional connective.
  177. Anellis (2012a) p. 259
  178. Shields cited by Anellis (2012a) p. 259-260
  179. O’Connor and Robertson (2002) "Frege"
  180. Gillies pp. 74-75
  181. Azzano p. 12
  182. Frege (1884) cited in Demopoulos p. 7
  183. Frege (1879) p. 136 cited in Gillies p. 71 emphasis added
  184. Frege (1884) § 2 cited in ”Philosophical Summaries” emphasis added
  185. Frege (1884) § 4 cited in Demopoulos p. 5 emphasis added
  186. Frege (1884) cited in Gillies p. 46-48
  187. Frege (1884) cited in Dietz
  188. Tait p.8
  189. Azzano p. 16
  190. Azzano p. 22
  191. Frege (1892)
  192. Gillies p. 83
  193. Ferreirós (1996) pp. 18-19
  194. Azzano p. 10
  195. Ferreirós (1996) pp. 18-19. Ferreirós notes (with surprise) that, in spite of its importance to naive set theory, the unrestricted principle of Comprehension was almost nowhere stated clearly before it was proved to be contradictory!
  196. Anellis (2012?) p. 260
  197. Azzano p. 8
  198. Reck (2011) § 2.2
  199. Gillies cited in Azzano p. 5
  200. Dedekind (1888) pp. 99-100 cited in Awodey and Reck p. 8
  201. Ferreirós (2011a) p. 19
  202. Ferreirós (2011a) p. 19. Ferreirós restates Dedekind’s conditions as follows: Condition 1. “$N$ is closed under the map $ϕ$”; Condition 3: “$N$ is the minimal closure of the unitary set $\{e\}$ under $ϕ$.”
  203. Podnieks § 3.1
  204. Reck (2011) § 2.2
  205. Anellis (2012a) p. 259
  206. Reck (2011) §2.2
  207. Azzano p. 16
  208. Reck (2011) §2.2
  209. Harrison (1996)
  210. Staub p. 96
  211. Hardegree p. 11 n. 13
  212. Gillies p. 66
  213. Kennedy (1974) p.41
  214. Peano p. 102 cited in GIllies p. 66
  215. Nidditch cited in Staub p. 96
  216. Peano cited in Kennedy (2002) p. 40-41
  217. Kennedy (2002) p. 42
  218. Kennedy (2002) p. 8
  219. Kennedy (2002) p. 42
  220. See Peano axioms and Wikipedia § Peano axioms for modern formalizations of Peano’s axioms.
  221. Pon p. 5
  222. See Peano axioms and Wikipedia § Peano axioms for discussions of consistency and independence of the axioms.
  223. Stepanov Slide 31
  224. Sowa § 1. Historical Background
  225. Wang p. 145 cited in Podnieks p.93
  226. Peano (1889) trans. by Kennedy p.103 cited in Gillies p. 66
  227. Reck (2011) § 2.2. To further make his case, Reck notes, albeit parenthetically, that “Peano, who published his corresponding work in 1889, [one year after Dedekind published his conditions,] acknowledged Dedekind's priority.”
  228. Staub p. 98 emphasis added
  229. Kennedy (2002) p. 41 emphasis added
  230. Nidditch cited in Staub p. 98
  231. Joyce cited in Staub p. 98
  232. Kennedy (2002) p. 11
  233. Gillies p. 66
  234. Ferreirós (2011b) § 3
  235. Lavine pp. 38, 41 cited in Curtis p. 87
  236. Tait p. 11
  237. O’Connor and Robertson (1996)
  238. Tait p. 18 emphasis added
  239. Tait p. 18
  240. Tait p. 6
  241. Nunez p. 1732
  242. Tait pp. 18
  243. Ferreirós (2011b) § 2
  244. Tait p. 19, note 14
  245. Tait pp. 18-19
  246. Weisstein “Ordinal Numbers”
  247. Ferreirós (2011b) § 2
  248. Nunez p. 1726
  249. Ferreirós (2011b) § 2
  250. Nunez p. 1726
  251. Ferreirós (2011b) § 2
  252. Set theory, Encyclopedia of Mathematics
  253. Burris (1997)
  254. Tait pp. 21-22
  255. Tait p. 23
  256. Ferreirós (2011b) § 3
  257. Ferreirós (2011b) § 3
  258. Lavine pp. 53-54 cited in Curtis pp. 87-88
  259. Lavine p. 63 cited in Curtis
  260. Lavine p. 66 cited in Curtis
  261. Tait p. 21
  262. Ferreirós (2011b) § 3
  263. Ferreirós (2011b) § 3
  264. Ferreirós (2011b) § 3. Ferreirós notes that Zermelo and others “believed that most of those paradoxes dissolved as soon as one worked within a restricted axiomatic system,” which is to say a system in which mathematicians typically work.
  265. Lavine p. 144 cited in Curtis p. 88, notes that Zermelo subsequently developed the “iterative concept” of a set, on which view “no set can be a member of itself, which rules out the set of all sets not members of themselves,” i.e. it rules out Russell’s paradox.
  266. Kanamori p. 17
  267. Kanamori p. 17. Kanamori notes that Zermelo agreed, quoting him as writing “if in set theory we confine ourselves to a number of established principles … that enable us to form initial sets and to derive new sets from given ones…, then all such contradictions can be avoided.”
  268. Tait p. 11
  269. Ferreiros (2001) pp. 443-444
  270. Ferreiros (2011a) p. 6
  271. Boyer (1968) p. 658
  272. Harrison (1996) § Rigour and the axiomatic method
  273. Nowlan “Moritz Pasch”
  274. Nowlan “Moritz Pasch”
  275. Seidenberg (2008) cited in O’Connor and Robertson "Moritz Pasch"
  276. Toretti (2010) § 4
  277. Nowlan “Moritz Pasch”
  278. Toretti (2010) § 4. Toretti credits this version of the principle of duality to Gergonne (1825) and notes, “The same result is secured … by exchanging not the words, [‘point’ for ‘line’, etc.,] but their meanings.
  279. Moritz Pasch
  280. Boyer (1968) p. 654 ff.
  281. Corry p. 147
  282. Venturi (2012) p. 12. Venturi comments (n. 37) that Hilbert made his choice of axiomatics as the method he would use to establish a sound basis for geometry even though, at the time, he “lacked the logical tools” to implement that method fully.
  283. Rothe p. 31
  284. Toretti (2010) § 4
  285. Hilbert (1899) p. 2
  286. Hilbert pp. 2-3
  287. Sterrett p. 1
  288. Corry p. 147
  289. Hilbert (1899) p. 1 cited in Venturi (2012) p. 3
  290. Blanchette § 2
  291. Venturi (2012) p. 3 emphasis added
  292. Venturi (2012) p. 18
  293. Boyer (1968) p. 658
  294. Hilbert cited in Blanchette § 2
  295. Blumenthal p. 402-403 cited in Corry (2011) p. 140
  296. Rothe (2015) p. 35
  297. Hilbert (1902). pp. 3-4. Axiom II.4 was discarded after it proved to be redundant.
  298. Hilbert (1902) pp. 4-5. Hilbert credits Pasch as having been the first to study these axioms and states that “Axiom II, 5 is in particular due to him.” p. 3. n. 2
  299. Richter pp. 3-4. The actual presentation is somewhat modified from Richter's original.
  300. Corry p. 147
  301. Hilbert (1900)
  302. Hilbert in a letter to Klein cited in Corry p. 141 emphasis added
  303. Jahren p. 1
  304. Rothe p. 36. See also p. 256, where Rothe notes that a “very strong” continuity axiom based on Dedekind’s definition of the real numbers introduces the real numbers into geometry, and then comments, “which is not in the spirit of Euclid.”
  305. Rothe p. 34
  306. Hartshorne p. 97
  307. Rothe p. 364 ff.
  308. Rothe p. 291 ff.
  309. Corry pp. 140-141
  310. Corry p. 148
  311. Corry pp. 148-149
  312. Blanchette § 2
  313. Rothe p. 37. Rothe suggests, in view of what we know today about the limitations of such investigations, that only a person of Hilbert’s great optimism could/would have addressed such questions at that time.
  314. Corry p. 153
  315. Blanchette § 2
  316. Blanchette § 4
  317. Blanchette § 5
  318. Corry p. 149
  319. Corry p. 147
  320. Venturi (2012) p. 24
  321. Venturi (2012) p. 3
  322. Hilbert (1905) cited in Corry p. 162
  323. Hilbert (1898-1899) cited in Corry pp. 144-145
  324. Corry p. 144-145
  325. Hilbert (1902) § 2
  326. Ferreirós (1996) p. 2 Ferreirós notes: “the first published formulation of the idea that mathematical existence can be derived from consistency” appeared in Hilbert’s 1900 paper “Über den Zahlbegriff.” This paper appeared immediately prior to the published version of his Problems Address.
  327. Hilbert (1900) § 2 emphasis added.
  328. Calude and Chaitin
  329. Pon

Primary sources

  • Blumenthal, Otto. (1935). “Lebensgeschichte.” (Hilbert 1932–1935, vol. 3, 387–429).
  • Bolzano, B. (1851). Paradoxien des Unendlichen (ed. by F. Pryhonsky), Reclam'; [English translation by D. A. Steele, ‘’Paradoxes of the Infinite’’, London: Routledge & Kegan Paul, 1950].
  • Boole, G. (1847, [1951]). The Mathematical Analysis of Logic, Being an Essay Towards a Calculus of Deductive Reasoning, Macmillan, Barclay, & Macmillan, [Reprinted Basil Blackwell].
  • Boole, G. (1854, [19158]). An Investigation of The Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities, Macmillan, [Reprinte Dover].
  • Dedekind, R. (1888). Was sind und was sollen die Zahlen?, Vieweg, [English trans., (1901) “The Nature and Meaning of Numbers”, in Essays on the Theory of Numbers, W.W. Beman, ed. and trans., Open Court Publishing Company].
  • Dedekind, R. (1930-32). Gesammelte Mathematische Werke, Vols. 1-3, R. Fricke et al., eds., Vieweg.
  • De Morgan, A. (1847). Formal Logic: or, The Calculus of Inference, Necessary and Probable, Taylor and Walton.
  • De Morgan, A. (1849). Trigonometry and Double Algebra, Taylor, Walton & Maberly.
  • Frege, G. (1879) Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, [“Conceptual Notation …”, English translation by T W Bynum, Oxford University Press, 1972].
  • Frege, G. (1884). Die Grundlagen der Arithmetik, [The Foundations of Arithmetic, English translation J L Austin, Basil Blackwell, 1968].
  • Frege, G. (1892) Uber Sinn und Bedeuting, [“On Sense and Reference,” Translations from the Philosophical Writings of Gottlob Frege, Geach and Black (eds.) Blackwell, 1960, pp. 56-78].
  • Frege, G. (1893) Grundgesetze, [The Basic Laws of Arithmetic, English translation by M Firth, University of California, 1964].
  • Grassmann, H. (1861). Lehrbuch der Arithmetik, Enslin, Berlin.
  • Hilbert, D. (1898–1899). Mechanik. Nachlass David Hilbert, (Cod. Ms. D. Hilbert, 553).
  • Hilbert, D. (1900). “Über den Zahlbegriff,” Jahresbericht der Deutschen, Mathematiker-Vereinigung 8, 180–184. (English translation in Ewald, W. (1996). From Kant to Hilbert: A source book in the foundations of mathematics, vol. 2, Oxford University Press.
  • Hilbert, D.(1900). "Mathematische Probleme," Nachr. K. Ges. Wiss. Göttingen, Math.-Phys. Klasse (Göttinger Nachrichten) , 3 pp. 253–297 (Reprint: Archiv Math. Physik 3:1 (1901), 44-63; 213-237; also: Gesammelte Abh., dritter Band, Chelsea, 1965, pp. 290-329) Zbl 31.0068.03, URL: https://www.math.uni-bielefeld.de/~kersten/hilbert/rede.html, Accessed: 2015/06/03.
  • Hilbert, D. (1902). "Mathematical problems," Bull. Amer. Math. Soc. , 8 pp. 437–479, MR1557926 Zbl 33.0976.07, (Reprint: ‘’Mathematical Developments Arising from Hilbert Problems’’, edited by Felix Brouder, American Mathematical Society, 1976), URL: http://aleph0.clarku.edu/~djoyce/hilbert/problems.html, Accessed: 2015/06/03.
  • Hilbert, D. (1905). Logische Principien des mathematischen Denkens. (Manuscript/Typescript of Hilbert Lecture Notes. Bibliothek des Mathematischen Instituts, Universität Göttingen, summer semester, 1905, annotated by E. Hellinger.)
  • Jevons, W S. (1890). Pure Logic and Other Minor Works, Robert Adamson and Harriet A. Jevons (eds), Lennox Hill Pub. & Dist. Co. [Reprinted 1971].
  • Ladd-Franklin, C. (1883). "On the algebra of logic," Studies in logic by the members of the Johns Hopkins University (C. S. Peirce, editor), Little, Brown, Boston, pp. 17-71.
  • Pasch, M., 1882. Vorlesungen über neueren Geometrie, Leipzig: Teubner.
  • Peacock, G. (1830). Treatise on Algebra.
  • Peano, G. (1889). Arithmetices principia nova methodo exposita. [English translation in Kennedy, H C. (1973). Selected Works of Giuseppe Peano, Allen & Unwin. pp. 101-134.]
  • Peirce, C S. (1881). “On the Logic of Number.” American Journal of Mathematics, Vol. 4, pp. 85-95, 1881.
  • Schröder, E. (1895). Algebra und Logik der Relativ.
  • Zermelo, I. (1908). “Investigations in the Foundations of Set Theory,” [English translation in van Heijenoort, J. (1967) From Frege to Godel, Harvard Univ. Press, pp. 199-215].

References

  • Anellis, I H. (2012b) “Peirce’s truth functional analysis and the origin of the truth table,” History and Philosophy of Logic, Vol. 33, No. 1, pp. 87–97, 2012, URL: http://arxiv.org/pdf/1108.2429.pdf, Accessed: 2015/08/07.
  • Bochenski, I M. (1956,[1961]) Formale Logik, North Holland, [English translation A History of Formal Logic, trans by Ivo Thomas, University of Notre Dame Press].
  • Boyer, C.B. (1939). The Concepts of the Calculus. A Critical and Historical Discussion of the Derivative and the Integral, Columbia University Press, vii + 346 pages, URL: http://catalog.hathitrust.org/Record/000165835 Accessed: 2015/06/29.
  • Chaitin, G. (2000). “A Century of Controversy Over the Foundations of Mathematics,“ Journal Complexity -- Special Issue: Limits in mathematics and physics, Vol. 5, No. 5, May-June 2000, pp. 12-21, (Originally published in Finite Versus Infinite: Contributions to an Eternal Dilemma, Calude, C. S.; Paun, G. (eds.); Springer-Verlag, London, 2000, pp. 75–100), URL: http://www-personal.umich.edu/~twod/sof/assignments/chaitin.pdf Accessed 2015/05/30.
  • Corry, L. (2006). “The Origin of Hilbert’s Axiomatic Method,” Jürgen Renn et al (eds.). The Genesis of General Relativity, Vol. 4 Theories of Gravitation in the Twilight of Classical Physics: The Promise of Mathematics and the Dream of a Unified Theory, Springer (2006), pp. 139-236. URL: http://www.tau.ac.il/~corry/publications/articles/pdf/Hilbert%20Kluwer.pdf, Accessed: 2015/08/16.
  • Dasgupta, A. (2014). Set Theory: With an Introduction to Real Point Sets, DOI 10.1007/978-1-4614-8854-5__2, © Springer Science+Business Media New York 2014, URL: http://www.springer.com/us/book/9781461488538, Accessed: 2015/06/19.
  • Ebbinghaus, H., et al. (1992: 3rd improved printing). Zahlen. Springer-Verlag.
  • Edwards, J.T. (editor) “Christine Ladd-Franklin,” Notable American women: A biographical dictionary 1607-1950, Vol. II, Belknap Press of Harvard University Press, Cambridge, MA, 1971.
  • Ewald, W B. (1996). From Kant to Hilbert: A source book in the foundations of mathematics, 2 vols., Oxford University Press.
  • Ewald, W B. (2002) Review of Grattan-Guinness, I. (2000) The Search for Mathematical Roots, 1870-1940, Princeton University Press. Bull. (New Series) Amer. Math. Soc., Vol. 40, No. 1, pp. 125–129.
  • Ferreirós, J. (2001). “The Road to Modern Logic -- An Interpretation,” ‘’The Bulletin of Symbolic Logic’’, Vol. 7, No. 4, Dec. 2001, URL: http://personal.us.es/josef/BSL0704-001.pdf, Accessed: 2015/07/13.
  • Grattan-Guinness, I. (1974). The rediscovery of the Cantor-Dedekind correspondence, Jahresbericht der Deutschen Mathematiker-Vereinigung 76 #2-3 (30 December 1974), 104-139, URL: http://catalog.hathitrust.org/Record/000165835 Accessed: 2015/06/30.
  • Grattan-Guinness, I. (1991). "Boole y su semi-seguidor jevons," ["Boole and his semi-follower Jevons"], in 2nd International Colloquium on Philosophy and History of Mathematics, Mexico City, Mathesis Mexico, Vol. 7. No. 3, (1991), pp. 351-362.
  • Joyce, D. (2005). The Dedekind/Peano Axioms, Clark University Press.
  • Kanamori, A. (2012). “In Praise of Replacement,” Bull. Symbolic Logic Vol. 18, No. 1 (2012), pp. 46-90.
  • Kanamori, A. (2007). “Set Theory from Cantor to Cohen,” Handbook of the Philosophy of Science, Volume: Philosophy of Mathematics, Vol. ed: Andrew Irvine, 2007, Elsevier BV, [A revision with significant changes of “The Mathematical Development of Set Theory from Cantor to Cohen,” The Bulletin of Symbolic Logic, Vol. 2, 1996, pp. 1–71], URL:http://math.bu.edu/people/aki/16.pdf, Accessed 2015/10/02.
  • Netz, R, Saito, K, and Tchernetska, N. (2001). “A new reading of Method Proposition 14 : preliminary evidence from the Archimedes palimpsest. I, SCIAMVS 2 (2001), 9-29.
  • Nidditch, P. (1963). “Peano and the Recognition of Frege,” Mind, Vol. 72 (1963) pp. 103-110.
  • Russell, B. (1945, [1972]) A History of Western Philosophy, Simon & Schuster, Inc.
  • Shen, E. (1927). “The Ladd-Franklin formula in logic: The antilogism,” Mind, Vol. 36, pp. 54-60.
  • Spalt, D.D. (1990). "Die Unendlichkeiten bei Bernard Bolzano," Konzepte des mathematisch Unendlichen im 19. Jahrhundert, Göttingen, 189-218.
  • Tarski, Alfred. (1941). “On the Calculus of Relations,” The Journal of Symbolic Logic, Vol. 6, No. 3 (Sep., 1941), pp. 73-89, Association for Symbolic Logic, URL: http://www.jstor.org/stable/2268577, Accessed: 2015/07/09.
  • Waterhouse, W.C. (1979). “Gauss on infinity,” Historia Math. Vol. 6, Issue 4, November 1979, pp. 430-436.
How to Cite This Entry:
Hilbert 2nd problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Hilbert_2nd_problem&oldid=37698