# Mathematical Logic

This page contains a list of ideas for DRP projects, but is by no means exhaustive.

**Topic**: Transfinite Numbers: Ordinals and Cardinals

**Suggseted** **Text**: *Introduction to Set Theory*, Karel Hrbacek & Thomas Jech

**Suggested Background**: Any course that has used sets (e.g. MATH 3100 (Introduction to Analysis), MATH 3200 (Introduction to Topology), MATH 3300 (Abstract Algebra), MATH 3310 (Introduction to Mathematical Logic), etc)

**Description**: The ordinal numbers are canonical representatives of the well-ordered sets. Using the Axiom of Choice, and its equivalent characterization the Well-Ordering Theorem, such ordinal numbers can be used to measure the ‘sizes’ of sets via *cardinal*. Natural operations on and between sets induce notions of ‘addition’, ‘multiplication’, and ‘exponentiation’ for these cardinals. Famously, exponentiation in particular is a very wild operation, with the Continuum Hypothesis being independent of the standard axiomatization of set theory. How is the Continuum Hypothesis shown to be independent? In general, what properties does cardinal exponentiation necessarily satisfy? What role does the Axiom of Choice play?

**Topic**: Gödel’s Incompleteness Theorems

**Suggested Text**: *Gödel’s Theorem: **An Incomplete Guide to Its Use and Abuse*, Torkel Fránzen or *An Introduction to Gödel’s Theorems*, Peter Smith

**Suggested Background**: MATH 4310 (Set Theory) might be useful, but not required

**Description**: A major program in the early 1900s was to place mathematics on a firm foundation, influenced by a growing feeling of the need for rigor in mathematics. Popularly, this meant reducing all of mathematics to arithmetic, and then showing that arithmetic was consistent and complete. The, in 1931, Kurt Gödel dealt a massive blow against that program when he published his First and Second Incompleteness Theorems, the first of which showed that any ‘sufficiently nice’ theory which expressed a minimal amount of arithmetical facts was not complete (i.e., there were claims that could neither be proven nor disproven) and the second of which showed that even if such a ‘sufficently nice’ theory which expressed a minimal amount of arithmetical facts *was* consistent, it would not be able to *prove* its consistency.

**Topic**: P =? NP

**Suggested** **Text**: *P =? NP*, Scott Aaronson

**Suggested ****Background**: soft recommendation for MATH 3700 (Discrete Mathematics) or related subject

**Description**: The question “P =? NP” can be phrased in the following way: “Is every problem whose solution can be verified quickly also able to be solved quickly?” Here, ‘problem’ means ‘decision problem’, i.e. yes-or-no questions; ‘quickly’ means ‘polynomial-time’ under some fixed model of computation. What exactly are P and NP? How is computation modeled mathematically? What is the current community opinion on whether P = NP or not.

**Topic**: Infinitesimals and Hyperreals

**Suggested** **Text**: *Foundations of Infinitesimal Calculus*, H. Jerome Keisler

**Suggested Background**: MATH 3100 (Introduction to Analysis)

**Description**: In its infancy, calculus was described in terms of ‘infinitesimals’, which were non-zero quantities which were smaller in magnitude than any real number. Using this intuition, limits, continuity, differentiation, and integration were developed and studied. As time wore on, a distrust of such notions grew and eventually was replaced with the modern approach ushered in by Weierstrass and Cauchy. In the mid 1900s, however, Abraham Robinson showed that infinitesimals *could** be placed on a rigorous foundation*, bringing back the old motivations in the form of non-standard analysis.