Formal Systems of Mathematics

by Hannah Sarver

Readings

Wikipedia – Formal Logical Systems - http://en.wikipedia.org/wiki/Formal_logical_system

Wikipedia – Peano Arithmetic: http://en.wikipedia.org/wiki/Peano_axioms

University of Waterloo – Principia Mathematica: http://www.math.uwaterloo.ca/~snburris/htdocs/scav/principia/principia.html

Skim the following:

Wikipedia – Euclid’s Elements: http://en.wikipedia.org/wiki/Euclid%27s_elements

Wikipedia – Axiomatic Set Theory: http://en.wikipedia.org/wiki/Axiomatic_set_theory#Axiomatic_set_theory

Reading Questions

On Formal Systems:

1. What is a formal system?

2. What is considered to be the first example of such a system?

3. List the four elements of a formal system in mathematics.

4. What is an axiom?

5. Name the two elements of a formal language. How is a formal language different from a formal system? How is it different from a formal grammar?

On PA:

1. Who were some of the predecessors of Peano in axiomatizing natural-number arithmetic?

2. List and briefly describe the three types of statements in the Peano axioms. (Hint: wait to answer this question until you get to the ‘The axioms’ section of the Wikipedia article)

3. Why is S(n) = 0 false?

4. Describe the two statements of the induction axiom shown in the article.

5. How are the Peano axioms augmented to give us Peano arithmetic?

6. What is the recursive definition of addition given in PA?

7. Give an overview of how PA can be derived from set theory.

8. Is PA consistent?

On PM:

1. What was the primary innovation of PM as compared with previous formalizations of mathematics?

2. What sort of problems did this innovation solve?

3. Summarize the summaries of the contents of each of the three books of PM.

4. Are there topics listed that you don’t recognize? If so, pick one and find out what it is.

5. Is PM consistent?

Lecture Notes

Road Map

Formal Systems

- Recall from Lecture 16: Philosophy of Mathematics, Formalism, and Hilbert’s Challenge

- A formal system has a formal language composed of symbols that combine into formulas based on certain rules of formation from a set of axioms.

- Remember the MIU System, with its symbols, axiom, and rules:

Formal Mathematical Systems

- Attempt to describe all of mathematics

- We talked about the lambda calculus, and briefly about PM and PA in class

- Other examples of formal systems include predicate, propositional, and pi calculus(es)

- First example of a formal system commonly considered to be Euclid’s Elements

Euclid’s Elements

- Written in 300 BC

- Over 1000 editions published, second only to the Bible

- Comprised of 13 books containing definitions, postulates, propositions, and proofs

- Covers plane and spatial geometry and number theory

- Also ratios and proportions (for example the parallel postulate, Pythagorean theorem, prime numbers)

Peano Axioms and Arithmetic

- Axioms compiled by Peano in 1889

- Preceded by work of Grassmann, Pierce, Dedekind

- Includes arithmetical properties of natural numbers

- Axioms describe 0, equality relationships (reflexive, symmetric, transitive, closed), arithmetic properties (ie successor, induction)

- Arithmetic augments axioms with addition and multiplication

Principia Mathematica

- First published in 1910, primarily motivated by Frege’s work and Peano Arithmetic

- Avoids paradoxes with elaborate type system

- Covers set theory, cardinal and ordinal numbers, real numbers

- Planned fourth volume on geometry, not written due to “intellectual exhaustion”

- Primitive ideas include elementary propositions, assertion, negation, and disjunction; all structured with variables, propositions, and equivalence relationships

Extension of Topic: Set Theory and New Foundations of Mathematics

- New Foundations simplifies the typing theory found in PM

- NF is consistent relative to PA when urelements are allowed (objects that are elements of sets but cannot be sets themselves)

- See also: Zermelo-Fraenkel Set Theory (includes the axiom of choice)

Class Activity

In your reading on Peano Arithmetic, you saw the recursive model of addition given by the system:

a + 0 = a, a + S(b) = S(a + b). Thus we can show that a + 1 = a + S(0) = S(a + 0) = S(a), where we could substitute in, for example, 1 for the variable a to get 1 + 1 = S(1) = 2 (or more accurately S(0)+S(0)=S(S(0)) ).

Given your understanding of this method of construction of arithmetical statements, derive the following in Peano Arithmetic, keeping track of all recursive steps:

1. 2 + 2 = 4

2. 0 + 0 = 0

3. 1 * 1 = 1

4. 2 * 5 = 10

5. 2 + (1 * 5) = 8

6. 2 * (1 + 5) = 12

Quiz Questions

1. Can the string ‘AHA!’ be derived in the following formal axiomatic system? Show or explain why or why not.

Symbols: A, B, H, !, ?

Axioms: ABA, A!, BAH

Rules:

1. xA -> xAA!

2. Hx -> AHx?

3. xAx -> xHAx

4. x? -> x

2. Derive the following statements in Peano Arithmetic (you don’t have to write out integers in successor notation from 0, just deal with + and x operations):

a. 2 + 3 = 5

b. 1 x (2 + 3) = 5

c. 1 + (2 x 2) = 5

3. What is an urelement and how does it relate to set theory and type theory?

Homework Assignment

Choose one of the formal axiomatic systems from this list (http://en.wikipedia.org/wiki/List_of_formal_systems) other than Peano Arithmetic or the Lambda Calculus, or any other formal system that interests you. Find the primary axioms, or at least the first few needed to begin constructing logical statements or formulas (these may be difficult to find). Choose at least three appropriate statements and derive them using the axioms of the system you chose to research. (see example solution on Tuple Calculus)