Where are we at?

• Galileo provided an example of both the dawning power of formal reason (geometry as the foundation of two new sciences), but also the conundrums that remained concerning some kinds of reasoning (e.g., about infinity)
• Cantor formalized what Galileo said could not be understood
• But, Cantor's system has an antinomy!
• Other prominent concerns include the development of non-Euclidean geometry. If we learn about geometry from our intuitions of space, and these led us to see the necessary truths of Euclidean geometry, then why do we also see the necessary truths of non-Euclidean geometry?
• Consensus developed that we need to step back, return to the basics
• Next: foundationalisms, the algorithm, and paradoxes and limits.

---

Review of Cantor's Antinomy

• Two things contradict: each set has a smaller cardinality than its power set, but there is a set of all sets (which we can prove has a cardinality greater than or equal to that of its powerset).
• Some smart folks in class made two suggestions:

  1. Could we keep unrestricted set formation but rule out just the universal set? There are systems like this, but this move alone will not work: as we'll see with our discussion of Frege, antinomies can still be created.
  
  2. Can we rule out self-reference? This is interesting, and we need to consider if this is possible. Approaches like this include Russell's theory of types.

• What is done in set theory today? Briefly, pure set theory requires that someone prove a set "exists" by "constructing" it (by describing a procedure that gets you to that object out of arrangements of other objects previously proven to exist or assumed to exist). To foreshadow: such an approach rules out the ability to just derive many mathematical objects -- rather, with such an approach, one must explicitly posit them as "axioms" (an axiom is a principle or law that one starts with, and does not derive.)

---

Foundations

• Issues like the invention of non-Euclidean geometry, the controversies over infinity, and concern about calculus and real numbers, led to a deep concern about the foundations of reason.
• Since our intuitions about what one can and cannot reason about conflict (e.g., Kronecker versus Cantor), can we get rid of intuition?
• Three different approaches to exploring foundations arose:

  1. Logicism: sound mathematical reasoning, and the admissible entities of mathematics, will be reducible to logic.
  
  2. Formalism: sound mathematical reasoning is either reducible to logic or is a description of the manipulation of real world objects (symbols).
  
  3. Intuitionism: sound mathematical reasoning, and the admissible entities of mathematics, do not need justification, but are given in a special intuition (and through constructions based upon those intuitions).

• (To this list, we are going to add before the end of the semester another kind of reasoning about reasoning, a semi-empirical approach.)
  
  

---

Frege and Logicism: Frege background

• Born 1848 in Wismar, Germany
• Both his parents were educators
• Studied at Universities in Jena and Gottingen
• Received doctorate in 1873
• Begriffsschrift (Concept Script) published 1879
• Grundgesetze der Arithmetik (Basic Laws of Arithmetic), Volume 1 published 1893; volume 2 published 1903.
• Russell communicates the paradox in 1902.
• Later volumes of the Basic Laws attempt to avoid the paradox, but fail.
• Frege died, believing that his program had failed, in 1925

Frege's Logicism

• Frege's goal is to expunge reference to intuitions from logic, by reducing all of mathematics to logic (which means at least, very general and uncontroversial propositions)
• In his Foundations of Arithmetic, Frege attacks psychologism (the view that mathematics can be explained via psychology), and asks "what is a number?" His answer is a good first step towards his logicism.
  • Frege argues that we can understand the number of things falling under a concept F by way of the more general concept of being equinumerous.
  • Thus, we use the idea that (1) the extension of the concept F is equinumerous with the extension of the concept G, to make sense of the idea that (2) the number of Fs is the same as the number of Gs.
  • Frege says, "The Number that belongs to the concept F is the extension of the concept 'equinumerous to the concept F'"
  • Here is then how he defines zero: The number 0 is the Number which belongs to the concept not identical with itself
  • The number 1 is the Number that belongs to the concept identical with 0.
  • The number 2 is the Number that belongs to the concept identical with 0 or 1.
  • The number n+1 is the Number which belongs to the concept member of the natural number series ending with n.
• In his Begriffsschrift, Frege developed single-handedly the system which underlies modern logic. His many achievements include the invention of the quantifier.
• In the Basic Laws of Arithmetic, Frege sought to apply and extend the system of the Begriffsschrift, and show that from this he could derive arithmetic.
• In this system, one basic principle is that a concept has a referent (or, as Frege would say, it has an extension) if it is constructed out of other concepts using basic logical principles, and we know those other concepts have a referent.
• Frege did not note, however, that his system has at least one necessary exception to this principle, "Law V" (the fifth law posited in Basic Laws of Arithmetic). Roughly, in English, this law says:

  Whatever satisfies a concept F also satisfies the concept G, and vice versa, if and only if the concepts F and G have the same extension.

• Law V is an instance of what logicians now call "second order logic"

The Axioms
It is helpful to see the axioms of his system. Roughly, in contemporary formulation, and followed by both an english "translation" and also a very rough example, are the axioms. Let "A" stand for the universal quantifier, all. Let P, Q be sentences (these are each either true or false, but not both and not neither). Let F and G be predicates (these label properties). Let a be some particular thing.

Axiom 1 a and b:
a. (P → (Q → P))
b. (P → P)
"Translation": If sentence P is true, then if sentence Q is true, P is true.
Example: If the streets are wet, then if it rains then the streets are wet. It's not obvious at first why such a principle is useful, but it allows you to do many important things, like prove a conditional.

Axiom 2:
a. (∀xFx → Fa)
"Translation": If everything has property F, then some particular a has property F.
Example (assume we're talking only about numbers): If every number is divisible by 1, then 15 is divisible by 1.

b. (∀F(Fa) → Ga)
"Translation": If a has every property, then a has particular property G.

Axiom 3:
∀x∀y(x=y → ∀F(Fx → Fy))

"Translation": If x and y are the same, then any property x has is also had by y.
Example: If number x is the same as number y, then if x is divisible by 4, y is divisible by 4.

Axiom 4:
¬(P ↔ ¬Q) → (P ↔ Q)

"Translation": if it is not the case that sentence P is true just in case Q is false, then P is true just in case Q is true. Basically, this says that if it is not the case that P and Q have different truth values, then they have the same truth value.

Axiom 5
((x'Fx = x'Gx) ↔ ∀x(Fx ↔ Gx))

"Translation": the collection of things that F is true of is the same collection of things that G is true of, just in case for any thing x, x has property F if and only if x has property G. For example, the collections of humans is the same as the collection of rational animals, just in case if all and only humans are rational animals.

Axiom 6
a = ie'(a = e) "Translation": object a is the thing with property e such that a is the sole extension of e. This basically means that each object will have a unique description true only of it. Thus, suppose a stands for Abraham Lincoln. Then: a = the thing of the extension e where e is the property of being the 16th President of the United States and a is e.

The Problem

Frege needs Axiom 5 to develop the elements of mathematics that he aims to develop. However, he assumes that every concept is defined over every object. Axiom 5 also allows that the extension of a concept is an "object" -- it is a thing that we can quantify over and treat the way we treat other objects, like numbers, of our theory. Finally, Axiom 5 has as a consequence that once we formulate a concept it has an extension. These facts allow as concepts with extensions things like "the concept of being a concept that is not satisfied by itself."

The Paradox

• Frege received from Bertrand Russell a letter of June 16, 1902, which said in part:

  .... I have known your Grundgesetze der Arithmetik for a year and a half, but only now have I been able to find the time for the thorough study I intend to devote to your writings. I find myself in full accord with you on all main points, especially in your rejection of any psychological element in logic and in the value you attach to a Begriffsschrift for the foundations of mathematics and of formal logic, which, incidentally, can hardly be distinguished. On many questions of detail, I find discussions, distinctions and definitions in your writings for which one looks in vain in other logicians. On functions in particular (Section 9 of your Begriffsschrift) I have been led independently to the same views even in detail. I have encountered a difficulty only on one point. You assert (p. 17) that a function could also constitute the indefinite element. This is what I used to believe, but this view now seems to me dubious because of the following contradiction: Let w be the predicate of being a predicate which cannot be predicated of itself. Can w be predicated of itself? From either answer follows its contradictory. We must therefore conclude that w is not a predicate. Likewise, there is no class (as a whole) of those classes which, as wholes, are not members of themselves. From this I conclude that under certain circumstances a definable set does not form a whole. (Quoted in Beaney 1997: 253)

• Frege's reply, written likely the day he received Russell's note (June 22 June 1902):

  .... Your discovery of the contradiction has surprised me beyond words and, I should almost like to say, left me thunderstruck, because it has rocked the ground on which I meant to build arithmetic. It seems accordinly that the transformation of the generality of an equality into an equality of value ranges (set 9 of my Grundgesetze) is not always permissible, that my law V (section 20, p. 36) is false, and that my explanations in section 31 do not suffice to secure a Bedeutung for my combinations of signs in all cases. I must give some further thought to the matter. It is all the more serious as the collapse of my law V seems to undermine not only the foundations of my arithmetic but the only possible foundations of arithmetic as such. And yet, I should think, it must be possible to set up conditions for the transformation of the generality of an equality into an equality of value-ranges so as to retain the essentials of my proofs. Your discovery is at any rate a very remarkable one, and it may perhaps lead to a great advance in logic, undesirable as it may seem at first. (Quoted in Beaney 1997: 254)

• Russell's paradox is very general (it does not refer, for example, to the biggest Cardinal, or other such weird things). Frege was unimpressed by the Cantorian antinomy, but considered Russell's paradox devastating.
• Frege himself abandoned logicism, but Russell continued the program.

---

Refences
I've quoted Frege from the Foundations of Arithmetic, translated by J. L. Austin, and quoted here out of The Frege Reader, Michael Beaney (ed.), 1997, Oxford: Blackwell publishers.