# Infinity

## Philosophy 20607 01 (32582)

### University of Notre Dame                                                                              Spring 2023

Instructor: Joel David Hamkins, O’Hara Professor of Philosophy and Mathematics
3:30-4:45 Tuesdays + Thursdays, DeBartolo Hall 208

Course Description. This course will be a mathematical and philosophical exploration of infinity, covering a wide selection of topics illustrating this rich, fascinating concept—the mathematics and philosophy of the infinite.

Along the way, we shall find paradox and fun—and all my favorite elementary logic conundrums and puzzles. It will be part of my intention to reveal what I can of the quirky side of mathematics and logic in its connection with infinity, but with a keen eye open for when issues happen to engage with philosophically deeper foundational matters.

The lectures will be based on the chapters of my forthcoming book, The Book of Infinity, currently in preparation, and currently being serialized and made available on the Substack website as I explain below.

Topics. Among the topics we shall aim to discuss will be:

• The Book of Numbers
• Largest number contest
• The googol plex chitty bang stack hierarchy
• Galileo’s Salviati on infinity
• Hilbert’s Grand Hotel
• The uncountable
• How to count (to infinity and beyond!)
• Slaying the Hydra
• Transfinite recursion
• The continuum hypothesis
• The axiom of choice
• Orders of infinity
• The lattice of subsets of ℕ
• Potential versus actual infinity
• Confounding puzzles of infinity
• Infinite liars
• Infinite utilitarianism
• Infinite computation
• Infinite games
• Indescribable numbers
• Extremely remote events of enormous consequence
• The sand reckoner
• The outer limits of reason
• Puzzles of epistemic logic and the problem of common knowledge

Mathematical background. The course will at times involve topics and concepts of a fundamentally mathematical nature, but no particular mathematical background or training will be assumed. Nevertheless, it is expected that students be open to mathematical thinking and ideas, and furthermore it is a core aim of the course to help develop the student’s mastery over various mathematical concepts connected with infinity.

Readings. The lectures will be based on readings from the topic list above that will be made available on my Substack web page, Infinitely More. Readings for the topic list above will be gradually released there during the semester. Each reading will consist of a chapter essay my book-in-progress, The Book of Infinity, which is being serialized on the Substack site specifically for this course. In some weeks, there will be supplemental readings from other sources.

Student access. I will issue subscription invitations to the Substack site for all registered ND students using their ND email, with free access to the site during the semester, so that students can freely access the readings.  Students are free to manage their subscriptions however they see fit. Please inform me of any access issues. There are some excellent free Substack apps available for Apple iOS and Android for reading Substack content on a phone or other device.

Discussion forum. Students are welcome to participate in the discussion forums provided with the readings to discuss the topics, the questions, to post answer ideas, or engage in the discussion there. I shall try to participate myself by posting comments or hints.

Homework essays. Students are expected to engage fully with every topic covered in the class. Every chapter concludes with several Questions for Further Thought, with which the students should engage. It will be expected that students complete approximately half of the Questions for Further thought. Each question that is answered should be answered essay-style with a mini-essay of about half a page or more.

Extended essays. A student may choose at any time to answer one of the Questions for Further Thought more fully with a more extended essay of two or three pages, and in this case, other questions on that particular topic need not be engaged. Every student should plan to exercise this option at least twice during the semester.

Final exam.  There will be a final exam consisting of questions similar to those in the Questions for Further Thought, covering every topic that was covered in the course. The final grade will be based on the final exam and on the submitted homework solutions.

Open Invitation. Students outside of Notre Dame are welcome to follow along with the Infinity course, readings, and online discussion. Simply subscribe at Infinitely More, keep up with the readings and participate in the discussions we shall be having in the forums there.

# Philosophy of Mathematics, Notre Dame Spring 2022

Philosophy of Mathematics
43906 01 (31349)

43906 02 (32481) – Reserved for Glynn Honors Program
Joel David Hamkins, Professor of Philosophy and Mathematics
3:30-4:45 TR, DeBartolo Hall 301
Cross-listed with MATH 40920 01

This series of self-contained seminar lectures on the philosophy of mathematics is intended for students in philosophy and mathematics. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light.

# Lectures on the Philosophy of Mathematics, Michaelmas term 2021, Oxford

Philosophy of Mathematics, Exam Paper 122, Oxford University

Wednesdays 12-1 during term, Radcliffe Humanities Lecture Room

Joel David Hamkins, Professor of Logic

This series of self-contained lectures on the philosophy of mathematics is intended for students preparing for Oxford Philosophy exam paper 122. All interested parties from the Oxford University community, however, are welcome to attend, whether or not they intend to sit the exam. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light. Lectures will loosely follow the instructor’s book Lectures on the Philosophy of Mathematics (MIT Press 2021), with supplemental suggested readings each week.

Previously recorded lectures from last year are available on the lecturer’s YouTube channel, below.

In light of the earlier lectures being available online, the plan for the lectures this year will be to feel somewhat more free occasionally to focus on narrower topics, and also to entertain at times a discussion format. Therefore kindly bring questions and well-thought-out opinions to the lecture.

The lectures this term will be held in person. The lecturer requests that students be vaccinated, wear masks, and observe social distancing as practicable. If this proves impossible or unsustainable, we shall regretably revert to online lectures on short notice.

Lecture 1. Numbers

Numbers are perhaps the essential mathematical idea, but what are numbers? There are many kinds of numbers—natural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and more—and these number systems provide a fruitful background for classical arguments on incommensurability and transcendentality, while setting the stage for discussions of platonism, logicism, the nature of abstraction, the significance of categoricity, and structuralism.

Lecture 2. Rigour

Let us consider the problem of mathematical rigor in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to the epsilon-delta limit concept, which secured a more rigorous foundation while also enlarging our conceptual vocabulary, enabling us to express more refined notions, such as uniform continuity, equicontinuity, and uniform convergence. Nonstandard analysis resurrected the infinitesimals on a more secure foundation, providing a parallel development of the subject. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devil’s staircase, space-filling curves, and the Conway base 13 function. Finally, does the indispensability of mathematics for science ground mathematical truth? Fictionalism puts this in question.

Lecture 3. Infinity

We shall follow the allegory of Hilbert’s hotel and the paradox of Galileo to the equinumerosity relation and the notion of countability. Cantor’s diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and nonconstructive proof. Zeno’s paradox highlights classical ideas on potential versus actual infinity. Furthermore, we shall count into the transfinite ordinals.

Lecture 4. Geometry

Classical Euclidean geometry is the archetype of a mathematical deductive process. Yet the impossibility of certain constructions by straightedge and compass, such as doubling the cube, trisecting the angle, or squaring the circle, hints at geometric realms beyond Euclid. The rise of non-Euclidean geometry, especially in light of scientific theories and observations suggesting that physical reality is not Euclidean, challenges previous accounts of what geometry is about. New formalizations, such as those of David Hilbert and Alfred Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarski’s decision procedure points to a tantalizing possibility of automation in geometrical reasoning.

Lecture 5. Proof

What is proof? What is the relation between proof and truth? Is every mathematical truth true for a reason? After clarifying the distinction between syntax and semantics and discussing various views on the nature of proof, including proof-as-dialogue, we shall consider the nature of formal proof. We shall highlight the importance of soundness, completeness, and verifiability in any formal proof system, outlining the central ideas used in proving the completeness theorem. The compactness property distills the finiteness of proofs into an independent, purely semantic consequence. Computer-verified proof promises increasing significance; its role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakening the logical rules.

Lecture 6. Computability

What is computability? Kurt Gödel defined a robust class of computable functions, the primitive recursive functions, and yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Alan Turing’s machine concept of computability, growing out of a careful philosophical analysis of the nature of human computability, proved robust and laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing had the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P versus NP problem standing in the background of nearly every serious issue in theoretical computer science.

Lecture 7. Incompleteness

David Hilbert sought to secure the consistency of higher mathematics by finitary reasoning about the formalism underlying it, but his program was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, self-reference, and definability, showing senses in which we cannot complete mathematics. After this, we shall discuss the second incompleteness theorem, the Rosser variation, and Tarski’s theorem on the nondefinability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength rising above every foundational mathematical theory.

Lecture 8. Set Theory

We shall discuss the emergence of set theory as a foundation of mathematics. Cantor founded the subject with key set-theoretic insights, but Frege’s formal theory was naive, refuted by the Russell paradox. Zermelo’s set theory, in contrast, grew ultimately into the successful contemporary theory, founded upon a cumulative conception of the set-theoretic universe. Set theory was simultaneously a new mathematical subject, with its own motivating questions and tools, but it also was a new foundational theory with a capacity to represent essentially arbitrary abstract mathematical structure. Sophisticated technical developments, including in particular, the forcing method and discoveries in the large cardinal hierarchy, led to a necessary engagement with deep philosophical concerns, such as the criteria by which one adopts new mathematical axioms and set-theoretic pluralism.

# Graduate Seminar in Philosophy of Logic, Oxford, Hilary Term 2021

This is a graduate seminar in the Philosophy of Logic at the University of Oxford, run jointly by myself and Volker Halbach in Hilary Term 2021.

The theme will be self-reference, truth, and the hierarchy of consistency strength.

A detailed schedule, including the list of topics and readings is available on Volker’s web site.

The seminar will be held Fridays 9-11 am during term, online via Zoom at 812 2300 3837.

The final two sessions of term will be specifically on the hierarchy of consistency strength, based on my current article in progress concerning the possibility of natural instances of incomparability and ill-foundedness in the hierarchy of large cardinal consistency strength.

# Lectures on the Philosophy of Mathematics, Oxford Michaelmas Term 2020

This series of self-contained lectures on the philosophy of mathematics, offered for Oxford Michaelmas Term 2020, is intended for students preparing for philosophy exam paper 122, although all interested parties are welcome to join. The lectures will be organized loosely around mathematical themes, in such a way that brings various philosophical issues naturally to light.

Lectures will follow my new book Lectures on the Philosophy of Mathematics (MIT Press), with supplemental readings suggested each week for further tutorial work. The book is available for pre-order, to be released 2 February 2021.

Lectures will be held online via Zoom every Wednesday 11-12 am during term at the following Zoom coordinates:

https://us02web.zoom.us/j/82822228760?pwd=UHU1cjVxSFpmd3haak5vYU51eFRrUT09

Meeting ID: 828 2222 8760

Passcode: 242081

All lectures will be recorded and made available at a later date.

## Lecture 1. Numbers

Numbers are perhaps the essential mathematical idea, but what are numbers? There are many kinds of numbers—natural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and more—and these number systems provide a fruitful background for classical arguments on incommensurability and transcendentality, while setting the stage for discussions of platonism, logicism, the nature of abstraction, the significance of categoricity, and structuralism.

## Lecture 2. Rigour

Let us consider the problem of mathematical rigour in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to the epsilon-delta limit concept, which secured a more rigourous foundation while also enlarging our conceptual vocabulary, enabling us to express more refined notions, such as uniform continuity, equicontinuity, and uniform convergence. Nonstandard analysis resurrected the infinitesimals on a more secure foundation, providing a parallel development of the subject. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devil’s staircase, space-filling curves, and the Conway base 13 function. Finally, does the indispensability of mathematics for science ground mathematical truth? Fictionalism puts this in question.

## Lecture 3. Infinity

We shall follow the allegory of Hilbert’s hotel and the paradox of Galileo to the equinumerosity relation and the notion of countability. Cantor’s diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and nonconstructive proof. Zeno’s paradox highlights classical ideas on potential versus actual infinity. Furthermore, we shall count into the transfinite ordinals.

## Lecture 4. Geometry

Classical Euclidean geometry is the archetype of a mathematical deductive process. Yet the impossibility of certain constructions by straightedge and compass, such as doubling the cube, trisecting the angle, or squaring the circle, hints at geometric realms beyond Euclid. The rise of non-Euclidean geometry, especially in light of scientific theories and observations suggesting that physical reality is not Euclidean, challenges previous accounts of what geometry is about. New formalizations, such as those of David Hilbert and Alfred Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarski’s decision procedure points to a tantalizing possibility of automation in geometrical reasoning.

## Lecture 5. Proof

What is proof? What is the relation between proof and truth? Is every mathematical truth true for a reason? After clarifying the distinction between syntax and semantics and discussing various views on the nature of proof, including proof-as-dialogue, we shall consider the nature of formal proof. We shall highlight the importance of soundness, completeness, and verifiability in any formal proof system, outlining the central ideas used in proving the completeness theorem. The compactness property distills the finiteness of proofs into an independent, purely semantic consequence. Computer-verified proof promises increasing significance; its role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakening the logical rules.

## Lecture 6. Computability

What is computability? Kurt Gödel defined a robust class of computable functions, the primitive recursive functions, and yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Alan Turing’s machine concept of computability, growing out of a careful philosophical analysis of the nature of human computability, proved robust and laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing had the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P versus NP problem standing in the background of nearly every serious issue in theoretical computer science.

## Lecture 7. Incompleteness

David Hilbert sought to secure the consistency of higher mathematics by finitary reasoning about the formalism underlying it, but his program was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, self-reference, and definability, showing senses in which we cannot complete mathematics. After this, we shall discuss the second incompleteness theorem, the Rosser variation, and Tarski’s theorem on the nondefinability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength rising above every foundational mathematical theory.

## Lecture 8. Set Theory

We shall discuss the emergence of set theory as a foundation of mathematics. Cantor founded the subject with key set-theoretic insights, but Frege’s formal theory was naive, refuted by the Russell paradox. Zermelo’s set theory, in contrast, grew ultimately into the successful contemporary theory, founded upon a cumulative conception of the set-theoretic universe. Set theory was simultaneously a new mathematical subject, with its own motivating questions and tools, but it also was a new foundational theory with a capacity to represent essentially arbitrary abstract mathematical structure. Sophisticated technical developments, including in particular, the forcing method and discoveries in the large cardinal hierarchy, led to a necessary engagement with deep philosophical concerns, such as the criteria by which one adopts new mathematical axioms and set-theoretic pluralism.

# Philosophy of Mathematics, graduate lecture seminar, Oxford, Trinity term 2020

This will be a graduate-level lecture seminar on the Philosophy of Mathematics held during Trinity term 2020 here at the University of Oxford, co-taught by Dr. Wesley Wrigley and myself.

The broad theme for the seminar will be incompleteness, referring both to the incompleteness of our mathematical theories, as exhibited in Gödel’s incompleteness theorems, and also to the incompleteness of our mathematical domains, as exhibited in mathematical potentialism.

All sessions will be held online using the Zoom meeting platform. Please contact Professor Wrigley for access to the seminar (wesley.wrigley@philosophy.ox.ac.uk). The Zoom meetings will not be recorded or posted online.

The basic plan will be that the first four sessions, in weeks 1-4, will be led by Dr. Wrigley and concentrate on his current research on the incompleteness of mathematics and the philosophy of Kurt Gödel, while weeks 5-8 will be led by Professor Hamkins, who will concentrate on topics in potentialism.

Weeks 1 & 2  (28 April, 5 May)
Kurt Gödel “Some basic theorems on the foundations of mathematics and their implications (*1951)”,  in: Feferman, S. et al.  (eds) Kurt Gödel: Collected Works Volume III, pp.304-323. OUP (1995). And Wrigley “Gödel’s Disjunctive Argument”. (Also available on Canvas).

Week 3 (12th May)
Donald Martin, “Gödel’s Conceptual Realism”, Bulletin of Symbolic Logic 11:2 (2005), 207- 224 https://www.jstor.org/stable/1556750. And Wrigley “Conceptual Platonism.”

Week 4 (19th May)
Bertrand Russell “The Regressive Method of Discovering the Premises of Mathematics (1907)”, in: Moore , G. (ed) The Collected Papers of Bertrand Russell, Volume 5, pp.571-580. Routledge (2014). And Wrigley “Quasi-Scientific Methods of Justification in Set Theory.”

Week 5 (26th May)
Øystein Linnebo & Stewart Shapiro, “Actual and potential infinity”, Noûs 53:1 (2019), 160-191, https://doi.org/10.1111/nous.12208. And Øystein Linnebo. “Putnam on Mathematics as Modal Logic,” In: Hellman G., Cook R. (eds) Hilary Putnam on Logic and Mathematics. Outstanding Contributions to Logic, vol 9. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96274-0_14

Week 6 (2nd June)
The topic this week is: tools for analyzing the modal logic of a potentialist system. This seminar will be based around the slides for my talk “Potentialism and implicit actualism in the foundations of mathematics,” given for the Jowett Society in Oxford last year. The slides are available at: http://jdh.hamkins.org/potentialism-and-implicit-actualism-in-the-foundations-of-mathematics-jowett-society-oxford-february-2019.  Interested readers may also wish to consult the more extensive slides for the three-lecture workshop I gave on potentialism at the Hejnice Winter School in 2018; the slides are available at http://jdh.hamkins.org/set-theoretic-potentialism-ws2018. My intent is to concentrate on the nature and significance of control statements, such as buttons, switches, ratchets and railyards, for determining the modal logic of a potentialist system.

Week 7 (9th June)
Joel David Hamkins and Øystein Linnebo. “The modal logic of set-theoretic potentialism and the potentialist maximality principles”. Review of Symbolic Logic (2019). https://doi.org/10.1017/S1755020318000242. arXiv:1708.01644. http://wp.me/p5M0LV-1zC. This week, we shall see how the control statements allow us to analyze precisely the modal logic of various conceptions of set-theoretic potentialism.

Week 8 (16th June)
Joel David Hamkins, “Arithmetic potentialism and the universal algorithm,” arxiv: 1801.04599, available at http://jdh.hamkins.org/arithmetic-potentialism-and-the-universal-algorithm. Please feel free to skip over the more technical parts of this paper. In the seminar discussion, we shall concentrate on the basic idea of arithmetic potentialism, including a full account of the universal algorithm and the significance of it for potentialism, as well as remarks of the final section of the paper.

# Lectures on the philosophy of mathematics, Oxford, Michaelmas term 2019

This will be a series of self-contained lectures on the philosophy of mathematics, given at Oxford University in Michaelmas term 2019. We will be meeting in the Radcliffe Humanities Lecture Room at the Faculty of Philosophy every Friday 12-1 during term.

All interested parties are welcome. The lectures are intended principally for students preparing for philosophy exam paper 122 at the University of Oxford.

The lectures will be organized loosely around mathematical themes, in such a way I hope that brings various philosophical issues naturally to light. The lectures will be based on my new book, forthcoming with MIT Press.

There are tentative plans to make the lectures available by video. I shall post further details concerning this later.

Lecture 1. Numbers. Numbers are perhaps the essential mathematical idea, but what are numbers? We have many kinds of numbers—natural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and more—and these number systems provide a fruitful background for classical arguments on incommensurability and transcendentality, while setting the stage for discussions of platonism, logicism, the nature of abstraction, the significance of categoricity, and structuralism.

Lecture 2. Rigour. Let us consider the problem of mathematical rigour in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to formal epsilon-delta limit concepts, which provided a capacity for refined notions, such as uniform continuity, equicontinuity and uniform convergence. Nonstandard analysis resurrected the infinitesimal concept on a more secure foundation, providing a parallel development of the subject, which can be understood from various sweeping perspectives. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devil’s staircase, space-filling curves and the Conway base 13 function. Whether the indispensibility of mathematics for science grounds mathematical truth is put in question on the view known as fictionalism.

Lecture 3. Infinity. We shall follow the allegory of Hilbert’s hotel and the paradox of Galileo to the equinumerosity relation and the notion of countability. Cantor’s diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and non-constructive proof. Zeno’s paradox highlights classical ideas on potential versus actual infinity. Time permitting, we shall count into the transfinite ordinals.

Lecture 4. Geometry. Classical Euclidean geometry, accompanied by its ideal of straightedge and compass construction and the Euclidean concept of proof, is an ageless paragon of deductive mathematical reasoning. Yet, the impossibility of certain constructions, such as doubling the cube, trisecting the angle or squaring the circle, hints at geometric realms beyond Euclid, and leads one to the concept of constructible and non-constructible numbers. The rise of non-Euclidean geometry, especially in light of scientific observations and theories suggesting that physical reality may not be Euclidean, challenges previous accounts of what geometry is about and changes our understanding of the nature of geometric and indeed mathematical ontology. New formalizations, such as those of Hilbert and Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarski’s decision procedure hints at the tantalizing possibility of automation in our geometrical reasoning.

Lecture 5. Proof. What is proof? What is the relation between proof and truth? Is every mathematical truth, true for a reason? After clarifying the distinction between syntax and semantics, we shall discuss new views on the dialogical nature of proof. With formal proof systems, we shall highlight the importance of soundness, completeness and verifiability in any such system, outlining the central ideas used in proving the completeness theorem. The compactness theorem distills the finiteness of proofs into an independent purely semantic consequence. Computer-verified proof promises increasing significance; it’s role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakenings of the logical rules.

Lecture 6. Computability. What is computability? Gödel defined the primitive recursive functions, a robust class of computable functions, yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Turing’s machine concept, growing out of a careful philosophical analysis of computability, laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing has the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P vs. NP problem standing in the background of nearly every serious issue in theoretical computer science.

Lecture 7. Incompleteness. The Hilbert program, seeking to secure the consistency of higher mathematics by finitary reasoning about the formal system underlying it, was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, via self-reference, and via definability. After this, we’ll discuss the second incompleteness theorem, the Rosser variation, and Tarski on the non-definability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength underlying all mathematical theories.

Lecture 8. Set theory. We shall discuss the emergence of set theory as a foundation of mathematics. Cantor founded the subject with key set-theoretic insights, but Frege’s formal theory was naive, refuted by the Russell paradox. Zermelo’s set theory, in contrast, grew ultimately into the successful contemporary theory, founded upon the cumulative conception. Set theory was simultaneously a new mathematical subject, with its own motivating questions and tools, but also a new foundational theory, with a capacity to represent essentially arbitrary abstract mathematical structure. Sophisticated technical developments, including especially the forcing method and discoveries in the large cardinal hierarchy, led to a necessary engagement with deep philosophical concerns, such as the criteria by which one adopts new mathematical axioms and set-theoretic pluralism.

# Philosophy of Mathematics, graduate lecture seminar, Oxford, Trinity term 2019

This will be a graduate-level lecture seminar on the Philosophy of Mathematics, run jointly by Professor Timothy Williamson and myself, held during Trinity term 2019 at Oxford University. We shall meet every Tuesday 2-4 pm during term in the Ryle Room at the Radcliffe Humanities building.

We shall discuss a selection of topics in the philosophy of mathematics, based on the readings set for each week, as set out below. Discussion will be led each week either by Professor Williamson or myself.

In the classes led by Williamson, we shall discuss issues concerning the ontology of mathematics and what is involved in its application. In the classes led by me, we shall focus on the philosophy of set theory, covering set theory as a foundation of mathematics; determinateness in set theory; the status of the continuum hypothesis; and set-theoretic pluralism.

Week 1 (30 April)
Discussion led by Williamson. Reading: Robert Brandom, ‘The significance of complex numbers for Frege’s philosophy of mathematics’, Proceedings of the Aristotelian Society (1996): 293-315 https://www.jstor.org/stable/pdf/4545241.pdf

Week 2 (7 May)
Discussion led by Hamkins. Reading: Penelope Maddy, Defending the Axioms: On the Philosophical Foundations of Set Theory, OUP (2011), 150 pp.

Week 3 (14 May)
Discussion led by Hamkins. Reading: Donald Martin, ‘Multiple universes of sets and indeterminate truth values’, Topoi (2001): 5-16. https://link.springer.com/article/10.1023%2FA%3A1010600724850

Week 4 (21 May)
Discussion led by Hamkins. Reading: Chris Freiling, ‘Axioms of symmetry: throwing darts at the real number line’, Journal of Symbolic Logic (1986) https://www.jstor.org/stable/pdf/2273955.pdf. And: Solomon Feferman, ‘The Continuum Hypothesis is neither a definite mathematical problem nor a definite logical problem’, https://math.stanford.edu/~feferman/papers/CH_is_Indefinite.pdf

Week 5 (28 May)
Discussion led by Hamkins. Reading: his ‘The set-theoretic multiverse’, Review of Symbolic Logic (2012): 416-449

Week 6 (4 June)
Discussion led by Williamson. Reading: Cian Dorr, ‘Of numbers and electrons’, Proceedings of the Aristotelian Society (2010): 133-181. https://onlinelibrary.wiley.com/doi/epdf/10.1111/j.1467-9264.2010.00282.x

Week 7 (11 June)
Discussion led by Williamson. Reading: Otávio Bueno and Mark Colyvan, ‘An inferential conception of the application of mathematics’, Noûs (2011): 345-374. https://onlinelibrary.wiley.com/doi/epdf/10.1111/j.1468-0068.2010.00772.x

Week 8 (18 June)
Discussion led by Williamson. Reading: his ‘Alternative logics and applied mathematics’, Philosophical Issues (2018): 399-424. https://onlinelibrary.wiley.com/doi/epdf/10.1111/phis.12131

# Lectures on the Philosophy of Mathematics, Oxford, Michaelmas 2018

This will be a series of lectures on the philosophy of mathematics, given at Oxford University, Michaelmas term 2018. The lectures are mainly intended for undergraduate students preparing for exam paper 122, although all interested parties are welcome.

My approach to the philosophy of mathematics tends to be grounded in mathematical arguments and ideas, treating philosophical issues as they arise organically. The lectures will accordingly be organized around mathematical themes, in such a way that naturally brings various philosophical issues to light.

Here is a tentative list of topics, which may be updated as the term approaches.

Lecture 1. Numbers. Numbers are perhaps the essential mathematical idea, but what are numbers? We have many kinds of numbers—natural numbers, integers, rational numbers, real numbers, complex numbers, hyperreal numbers, surreal numbers, ordinal numbers, and more—and these number systems provide a fruitful background for classical arguments on incommensurability, the irrationality of $\sqrt{2}$, transcendental numbers, the infinitude of primes, and lead naturally to discussions of platonism, Frege’s number concept, Peano’s numbers, Dedekind’s categoricity arguments, and the philosophy of structuralism.

Lecture 2. Rigour. Let us consider the problem of mathematical rigour in the development of the calculus. Informal continuity concepts and the use of infinitesimals ultimately gave way to formal epsilon-delta limit concepts, which provided a capacity for refined notions, such as uniform continuity, equicontinuity and uniform convergence. Nonstandard analysis resurrected the infinitesimal concept on a more secure foundation, providing a parallel development of the subject, which can be understood from various sweeping perspectives. Meanwhile, increasing abstraction emerged in the function concept, which we shall illustrate with the Devil’s staircase, space-filling curves and the Conway base 13 function.

Lecture 3. Infinity. We shall follow the allegory of Hilbert’s hotel and the paradox of Galileo to the equinumerosity relation and the notion of countability. Cantor’s diagonal arguments, meanwhile, reveal uncountability and a vast hierarchy of different orders of infinity; some arguments give rise to the distinction between constructive and non-constructive proof. Zeno’s paradox highlights classical ideas on potential versus actual infinity. Time permitting, we shall count into the transfinite ordinals.

Lecture 4. Geometry. Classical Euclidean geometry, accompanied by its ideal of straightedge and compass construction and the Euclidean concept of proof, is an ageless paragon of deductive mathematical reasoning. Yet, the impossibility of certain constructions, such as doubling the cube, trisecting the angle or squaring the circle, hints at geometric realms beyond Euclid, and leads one to the concept of constructible and non-constructible numbers. The rise of non-Euclidean geometry, especially in light of scientific observations and theories suggesting that physical reality may not be Euclidean, challenges previous accounts of what geometry is about and changes our understanding of the nature of geometric and indeed mathematical ontology. New formalizations, such as those of Hilbert and Tarski, replace the old axiomatizations, augmenting and correcting Euclid with axioms on completeness and betweenness. Ultimately, Tarski’s decision procedure hints at the tantalizing possibility of automation in our geometrical reasoning.

Lecture 5. Proof. What is proof? What is the relation between proof and truth? Is every mathematical truth, true for a reason? After clarifying the distinction between syntax and semantics, we shall discuss formal proof systems and highlight the importance of soundness, completeness and verifiability in any such system, outlining the central ideas used in proving the completeness theorem. The compactness theorem distills the finiteness of proofs into an independent purely semantic consequence. Computer-verified proof promises increasing significance; it’s role is well illustrated by the history of the four-color theorem. Nonclassical logics, such as intuitionistic logic, arise naturally from formal systems by weakenings of the logical rules.

Lecture 6. Computability. What is computability? Gödel’s primitive recursive functions were a robust class, yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Turing’s machine concept, growing out of his careful philosophical analysis of computability, laid a foundation for the contemporary computer era, and the widely accepted Church-Turing thesis asserts that Turing has the right notion. Meanwhile, the distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses this on the realm of feasible computation, with the still-unsolved P vs. NP problem standing in the background of nearly every serious issue in theoretical computer science.

Lecture 7. Incompleteness. The Hilbert program, seeking to secure the consistency of higher mathematics by finitary reasoning about the formal system underlying it, was dashed by Gödel’s incompleteness theorems, which show that no consistent formal system can prove even its own consistency, let alone the consistency of a higher system. We shall describe several proofs of the first incompleteness theorem, via the halting problem, via self-reference, and via definability. After this, we’ll discuss the Rosser variation, the second incompleteness theorem, and Tarski on the non-definability of truth. Ultimately, one is led to the inherent hierarchy of consistency strength underlying all mathematical theories.

Lecture 8. Set theory. We shall discuss the emergence of set theory as a foundation of mathematics. An initially naive theory, challenged fundamentally by the Russell paradox, grew into Zermelo’s formal set theory, founded on the idea of a cumulative universe of sets and providing a robust general context in which to undertake mathematics, while also enabling the clarification of fundamentally set-theoretic issues surrounding the axiom of choice, the continuum hypothesis and an increasingly diverse hierarchy of large cardinal concepts. The development of forcing solved many stubborn questions and illuminated a ubiquitous independence phenomenon, feeding into philosophical issues concerning the criteria by which one should add new axioms to mathematics and the question of pluralism in mathematical foundations.

# Introduction to proofs, CSI Math 505, Spring 2017

I shall be teaching a new course Introduction to Proofs at the CUNY College of Staten Island this semester.

The course is intended for aspiring mathematics students who are learning—perhaps for the first time in a serious way—how to write mathematical proofs. I think of it as a kind of mathematical coming-of-age course, for students on the cusp, maturing into mathematicians, who aspire to communicate mathematical truths to other mathematicians in the currency of mathematics, which is: proof.

I hope to help them learn how a mathematician makes an argument in order to establish a mathematical truth.

I have written a new book specifically for the course, Proof and the art of mathematical reasoning, which I hope will be available before too long. The text will be suitable for any kind of introduction-to-proofs or transition-to-proofs course at the undergraduate level, with a variety of elementary proofs from a broad swath of mathematical topics. I shall post some excerpts later, to give you an idea of the nature of the book, but for now let me simply list the current table of contents. The book begins in chapter one with the proof that $\sqrt{2}$ is irrational. The epilogue contains a variety of logic puzzles in epistemic logic.

Preface 5
A note to the instructor 11
Chapter 1. Begin with a classic 13
Chapter 2. Multiple proofs 21
Chapter 3. Number theory and the primes 27
Chapter 4. Mathematical Induction 37
Chapter 5. Discrete mathematics and finite combinatorics 45
Chapter 6. Pick’s theorem: a case study in Pólya’s advice 57
Chapter 7. Visual proofs 67
Chapter 8. Geometry and lattice-point regular polygons 77
Chapter 9. Relations 85
Chapter 10. Graph theory 95
Chapter 11. Order theory 105
Chapter 12. Theory of games 111
Chapter 13. Set theory 129
Chapter 14. Real analysis 139
Epilogue 153
Bibliography 171

# Mathematical logic, GC Math 712, Spring 2017

I shall be teaching Mathematical Logic, Math 712 at the CUNY Graduate Center in Spring 2017. The course is 4.5 credits, and it will meet Tuesdays and Thursdays, 2:00 pm – 3:30 pm.  There are no official pre-requisites, other than a willingness to engage with graduate-level mathematics. Students will benefit from having taken the first semester logic course, Math 711.

Course Description. This course is a graduate introduction to mathematical logic, in which we shall cover a variety of topics united by the theme of Gödel’s incompleteness theorem. In particular, during the semester we shall give several independent proofs of that theorem and its generalizations from different perspectives. We shall do so in the context of our studies of computability theory, decidability, strongly undecidable structures, the arithmetic hierarchy, arithmetization, definability and selected topics in proof theory, model theory and set theory, including the hierarchy of consistency strength. Students will complete weekly problem sets and write a term paper.

Check back here later for further information about the course.

# Survey of Logic for Philosophers, CUNY GC PHIL 76500, Spring 2016

Survey of Logic for Philosophers
PHIL 76500
Program in Philosophy
Spring semester 2016
4 credits
Weds. 11:45-1:45
Room 5417

This seminar will be a graduate-level survey of topics in logic for philosophers, including propositional logic, modal logic, predicate logic, model theory, completeness, incompleteness, computability theory, set theory and the higher infinite. The material will thus be a mixture of philosophical logic and mathematical logic, and a goal of the course will be to develop the student’s ability to treat the main ideas of logic with clarity and precision.

Students will solve weekly problem sets and write a final paper on a topic chosen in consultation with me.

Students talks on their research projects. The students will give brief talks on their research paper topics on May 25, 2016, 11:45-1:45 in GC 5417. I will post titles and abstracts here when I get them. Among the topics will be the following and others:

• The problem of aggregating individual preferences to a group preference relation
• The logic of missing information
• The hierarchy of expressive power of sets of classical connectives
• Recovering the accessibility relation from the modal theories of the worlds in a Kripke model
• The fundamental theorem of finite games of perfect information
• Multi-valued modal logic
• Definability via category theory
• Discernibility and indiscernibility in a language without equality
• Modal predicate logic and the Barcan formula

# Logic for Philosophers, NYU, Spring 2015, graduate seminar PHIL-GA 1003

This seminar will be a graduate-level survey of topics in logic for philosophers, including propositional logic, modal logic, predicate logic, model theory, completeness, incompleteness, computability theory, set theory and the higher infinite. The material will thus be a mixture of philosophical logic and mathematical logic, and a goal of the course will be to develop the student’s ability to consider these ideas with clarity and precision.

The lectures will be largely self-contained, and some course materials will be distributed during the semester.  On some topics, material will be drawn from:

More Precisely, The Math You Need to do Philosophy, Eric Steinhart, Broadview.

On other topics, students may wish to supplement the lecture notes with other sources, and there are dozens of suitable texts for this purpose, as well as on-line information.

For focused help, students are also directed to the following excellent on-line resources:

1. Math.StackExchange.com, an on-line question/answer forum for mathematics questions, which welcomes questions on logic, and most questions get high quality answers very quickly.
2. MathOverflow.net, a similar site for research-level mathematics questions.

Weekly exercises.  Exercises will be assigned in connection with each lecture, and these are due by the following lecture.  It is fine and even advisable for you to work in groups, but kindly submit only solutions that you yourself have thoroughly mastered.

Final paper.  Students will write a final paper (about 8 pages) on an approved topic chosen in consultation with the instructor.  The instructor’s goal in assigning this paper is to give the students experience both in conducting research on a technical topic, as well as in writing on such a topic.  Suitable topics will be suggested, but they will generally consist not of giving a summary account or criticism of an advanced topic from the literature (this will be discouraged), but rather of considering a modest but novel topic or context—perhaps a variation of a better known theory—and then discovering and working out some interesting aspect of it. The idea is that the paper topic should be a little like undertaking research in logic.  The paper is due by the last day of the semester, and late work will not be accepted.

Grading. Grades will be based on the weekly exercises and the final paper (with a class participation element).  All work for this class, including the final paper, must be submitted by the last day of the semester.  No Incomplete grades will be given—no exceptions.

My intention is to post the weekly problem sets here, by updating this post.  I will make Google+ posts pointing to this page when it is updated, for a circle of subscribed members; send me a message on G+ to join the circle (or you can alternatively just subscribe to this blog, but then you’ll get notified of all my posts).

Lecture 1.  A picture of logic.  Propositional logic. Truth tables; tautologies; logical equivalence; well-formed formulas; induction on formulas; complete sets of connectives; every truth function is represented by a formula in disjunctive normal form; satisfiability; connections with P vs. NP.

Lecture 1 notes by a student

Exercises:$\newcommand\iff{\leftrightarrow}$

1. Make truth tables for $$(p\wedge q\wedge r)\vee((p\wedge q)\to r)$$ $$(p\wedge(t\to q))\wedge((q\iff r)\vee p)$$ $$(((p\vee q)\vee r)\vee(r\to(\neg q\to r)))\to r$$

2. Argue that every well-formed formula of propositional logic has the same number of left as right parentheses.  (According to the rules we gave in class for the formula-building operations.)

3. Argue that every well-formed formula of propositional logic has twice as many parentheses as binary logical connectives.

4. Argue that the collection of tautologies is closed under conjunction, disjunction, implication and biconditional. In other words, if $\varphi$ and $\psi$ are tautologies, then so are $\varphi\wedge\psi$, $\varphi\vee\psi$, $\varphi\to\psi$ and $\varphi\iff\psi$.

5. Which of the converses of these are true? In other words, which of the following are correct:

• If $A\to B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\iff B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\wedge B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\vee B$ is a tautology, then $A$ and $B$ are tautologies.

6. Argue that every propositional assertion is logically equivalent to an assertion in conjunctive normal form (a conjunction of disjunction clauses, each of which is a disjunction of literals).  (Hint:  in class we proved that every propositional assertion is logically equivalent to an assertion in disjunction normal form.  Given $\varphi$, consider $\neg\varphi$ in light of what we did in class.)

7. Determine which of the following sets of logical connectives are complete: $\{\neg,\to\}$,  $\{\neg,\iff\}$.  (The second one is a bit harder, and we’ll cover it in class next time.)

8.  Show that Nand and Nor are the only binary connectives that, by themselves individually, are complete.  (Hint:  if you have a binary connective $A\star B$ that is complete, then consider what the truth table of $\star$ must be. What must it be on the top row? On the bottom row? How many possibilities remain?)

Possible paper topic connected with the Satisfiability problem and P vs. NP.  For example, you could write a paper explaining how the general satisfiability problem reduces to the 3-Sat problem.  (This is a classical result, but one that can be easily rediscovered independently.)

Lecture 2. Discussion of homework problems from last time, including a simple account of the disjunctive normal form theorem and the conjunctive normal form theorem.

New topic:  multi-valued logic; Lukasiewicz/Kleene logic.  Basic truth tables for 3-valued logic.  Discussion of various motivations, such as logic of missing information, logic of possible worlds, logic of unknown truth values, neither true nor false, both true and false; most of these stories are flawed and do not actually capture the logic. Tautologies and complete sets of connectives in 3-valued logic.  Notions of logical equivalence. No strict tautologies. Disjunctive normal form still works.  Weak tautologies are the same as classical tautologies.

Lecture 2 notes by a student

Exercises.

1. If $\varphi$ is a propositional assertion in the language with $\neg,\wedge,\vee,\to,\leftrightarrow$, and $\varphi(\vec p)=U$. Does there always exist a crispification of $\vec p$ to $\vec p^*$ with $\varphi(\vec p^*)=T$ and another crispification $\vec p^{**}$ with $\varphi(\vec p^{**})=F$? In other words, does the truth value $U$ mean that it could have been $T$ and it could have been $F$, depending on what way the input $U$ values are made crisp?
2. Define a natural analogue of NAND and of NOR for Kleene logic. Does it obey the expected identities? Does it continue to be complete in Kleene logic in the narrow sense? In the wide sense?
3. Verify the De Morgan laws in Lukasiewicz logic, namely, that $\neg(A\vee B)\equiv\neg A\wedge\neg B$ and $\neg(A\wedge B)\equiv\neg A\vee\neg B$, using $\equiv$ to mean logically equivalent in the sense of having the same truth table.
4. Verify the distributivity laws $$P\wedge(Q\vee R)= (P\wedge Q)\vee(P\wedge R)$$ $$P\vee (Q\wedge R) = (P\vee Q)\wedge (P\vee R)$$ in Lukasiewicz logic.  (You probably don’t want to compute the truth table, since it has 27 rows; rather, reason about what must happen if $P$ is true; if $P$ is false; and if $P$ is $U$.)
5. Find an expression in $P$, $Q$ and $R$ that has value $U$, if any of them is $U$, and otherwise has value $F$.
6. Is the truth table of every expression in Lukasiewicz logic determined (as it is in classical logic) by the location of the $T$’s? That is, if you know where the $T$’s are, can you determined whether the others are $F$ or $U$, just from knowing that the expression came from $\wedge,\vee,\neg,\to,\leftrightarrow$?

Possible paper topics.

• Develop the logic of missing information.  The context would be that there is a genuine classical logic world, but we do not know some of the truth values of the atomic facts.  What is a sensible way to develop a logic for this situation? Is it truth-functional? Can we assign truth values to every statement in a sensible multi-valued logic? What are the notions of tautology, validity, completeness, and so on?
• Explore the notion of complete sets of logical connectives in Lukasiewicz logic.  We know the standard set of connectives $\neg,\wedge,\vee,\to,\leftrightarrow$ is not complete, but can we augment it with another connective to make it complete? Is there a single connective in the 3-valued logic that is complete? (I have some good references for research on this topic.)

Lecture 3.  Fuzzy logic. Definitions of the logic. Disjunctive normal form theorem. Traditional connectives are not complete. No finite set  (nor even any countably infinite set, nor even any set of size continuum) is complete for fuzzy logic. Tautologies in fuzzy logic; weak tautologies (truth value $\geq\frac12$); positive assertions (truth value is never $0$). For assertions in traditional logical language, weak tautologies, positive and classical tautologies are the same. The proof uses logical homomorphisms, translating fuzzy logic to Lukasiewicz logic. We discussed various kinds of logical homomorphisms. General treatment of truth-functional logic: a space $\cal L$ of truth values, with logical functions $\neg,\wedge,\vee$ on that space.  Concepts of extensions ${\cal L}_0\subset{\cal L}_1$ and logical homomorphisms $\pi:{\cal L}_1\to {\cal L}_0$. Boolean algebras. Axioms of Boolean algebras. A few examples, including power sets.

Exercises.

1. Verify in fuzzy logic that $$p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q).$$
2. Verify that the de Morgan laws continue to hold in fuzzy logic.$$\neg(A\vee B)\equiv (\neg A)\wedge(\neg B)$$$$\neg(A\wedge B)\equiv(\neg A)\vee(\neg B)$$
3. Verify that the distributivity laws continue to hold in fuzzy logic.$$A\wedge(B\vee C)\equiv (A\wedge B)\vee(A\wedge C)$$$$A\vee(B\wedge C)\equiv(A\vee B)\wedge(A\vee C)$$
4. Argue that in fuzzy logic, just as in Lukasiewicz logic, there are no tautologies in the language having only the traditional five connectives: $\neg,\wedge,\vee,\to,\iff$.
5. Consider the translation from fuzzy logic to Lukasiewicz logic, which takes the center interval $(\frac13,\frac23)$ of fuzzy truth values to the truth value U; the numbers in the interval $[0,\frac13]$ to $F$ and numbers in $[\frac23,1]$ to $T$. Show that this is a logical homomorphism of fuzzy logic to Lukasiewicz logic.
6. Show that there is no logical homomorphism of fuzzy logic to classical logic.
7. Discuss the question of whether fuzzy logic is the logic of probabilistic reasoning. Suppose that we are in a probability space, where the underlying propositional variables are given a probability. Does fuzzy logic then give sensible probabilities for compound logical expressions using those variables? That is, if we know the probabilities of $p$, $q$ and $r$, then does fuzzy logic tell us the probability of compound expressions like $p\to(q\vee r)$?

Suggested Paper topics.

1. Investigate the nature of the fuzzy truth functions that one may define using the standard five connectives. Can one recognize or characterize them? How many binary connectives are realized?
2. Investigate and discuss the issue of continuity of truth functions in fuzzy logic. Under what kind of semantics would one want to make use of or consider discontinuous truth functions?
3. Discuss the issue or ordinal comparision versus cardinal comparison in fuzzy logic truth values.  One might consider logical homomorphisms of fuzzy logic to itself, which preserve the order of truth values, but which greatly magnify small differences or diminish large ones.

Lecture 4.  Relational logic; the theory of relations. Reflexivity, symmetry, transitivity; irreflexivity; asymmetry; anti-symmetry; anti-transitivity; equivalence relations; equivalence classes; partitions; every equivalence relation determines a partition and vice versa. Refinement of equivalence relations. Partial orders; strict orders; converse order; pre-order; comparability.

Lecture 4 student notes

Exercises.

1. Are all eight combinations of the properties of reflexivity, symmetry and transitivity possible? Provide instances of relations exhibiting each combination that can occur.
2. Criticize the following argument that every relation that is symmetric and transitive is also reflexive: If $E$ is symmetric, then $a\mathrel{E} b$ implies $b\mathrel{E} a$, and so if it is also transitive, it follows that $a\mathrel{E} a$, and so it is reflexive. Is this argument correct? If not, what is a correct statement that a similar argument establishes?
3. How are the concepts of asymmetric, anti-symmetric and “not symmetric” connected to each other? Which imply which others? Which of the eight conceivable combinations actually arise? Provide relations exhibiting each possible combination.
4. How many equivalence relations are there on a 4 element set? It is possible easily to draw a small picture of each one. Organize this chart into the refinement hierarchy.
5. Consider the claim that the living-in-the-same-city-as relation refines the living-in-the-same-country-as relation, on the set of all people.  Discuss the various problematic assumptions underlying this example. For example, if there were a person who lives in more than one country, or no country, or a person who lives in more than one city, or no city; or suppose that there is a city with parts in more than one country. For each of these situations and others you may think of, precisely which parts of the claims that these relations are both equivalence relations on the set of all people and that the first relation refines the second would be affected?
6. Consider the relation of comparability for elements in a partial order.  Is it an equivalence relation? Consider each of the properties of relations that we have considered (reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, etc.) and argue that comparability always has that property or give an example partial order showing that the comparability relation need not have that property.

Lecture 5. Order theory. Mathematical and natural examples. Reflexive closure of a relation. Symmetric closure. Transitive closure. The reflexive/transitive closure of a relation is the same as the reachability relation. Strict partial orders. Defining $<$ from $\leq$ and vice versa. Pre-orders (quasi-orders). With pre-orders, the interdefinability of $<$ with $\leq$ breaks down. Example of distinct preference pre-orders with same strict preferences. Maximal and greatest elements. Minimal and least elements. Example of a partial order with a unique maximal element that is not greatest. Upper bounds; lower bounds; least upper bounds; greatest lower bounds. Lattices. Linear orders. Linearly graded partial orders.

Lecture 5 student notes

Exercises.

1. Give an example of an anti-symmetric relation, whose reflexive/transitive closure is not anti-symmetric.
2. Give a relation on five elements, using as few relational instances as possible, whose reflexive/transitive closure is the full relation (for which each of the five elements stands in the relation to all five elements). How many relational edges did you use? Can you make a general claim and argument for a domain with $n$ elements?
3. Suppose that $\leq$ is a partial pre-order. Define $a\sim b$ just in case $a\leq b$ and $b\leq a$. Argue that $\sim$ is an equivalence relation on the same domain.
4. Does the interdefinability of $\leq$ and $<$ succeed with pre-orders? Suppose that $\leq$ is a transitive reflexive relation (that is, a pre-order). Define $a<b$ if $a\leq b$ and $a\neq b$. Will this necessarily be a partial order? If not, what is a better way to define a strict partial order $a<b$ in terms of $\leq$ for a pre-order $\leq$?
5. Suppose that an author (mistakenly, in my view) defines that we are {\it indifferent} between $a$ and $b$ if neither $a$ nor $b$ is better than the other. That is, $a\approx b\iff a\not<b\wedge b\not< a$. Provide a preference relation for which this is not an equivalence relation. Specifically, we’d want the person to be indifferent between $a$ and $b$, and indifferent between $b$ and $c$, but not indifferent between $a$ and $c$.
6. True or false: if $\leq$ is a partial ordering on a set, then $a\leq b$ if and only if $b\not <a$.
7. Give an example of a partial order that admits more than one linear grading order. In other words, provide a partial order that can be divided into levels in more than one way.

Suggested paper topics.

1. The connection between preference relations and group preferences. For example, if you try to define a group preference by using majority rule on the individual preferences, then you don’t necessarily get a partial order.
2. The algebra of partial orders. If $\mathbb{A}$ and $\mathbb{B}$ are partial orderings, there is a notion of $\mathbb{A}+\mathbb{B}$, which is the order placing a copy of $\mathbb{B}$ on top of a copy of $\mathbb{A}$; and $\mathbb{A}\times\mathbb{B}$ is the order consisting of $\mathbb{B}$ many copies of $\mathbb{A}$. There are numerous easy but interesting questions to ask about how features are preserved or not by these constructions, such as: if $\mathbb{A}$ and $\mathbb{B}$ are dense orders, then are $\mathbb{A}+\mathbb{B}$ also dense? $\mathbb{A}\times\mathbb{B}$? And what of discrete orders?

Lecture 6. First-order predicate logic. Formal language of a relational structure. Well-formed formulas. Induction on formulas. Parse trees. Unique readability. Free and bound variables. Scope. Sentences. Definition of satisfaction. Truth in a model.

Lecture 6 student notes

Exercises.

1. In the language of the structure $\langle\mathbb{N},\leq\rangle$, construct a formula with two free occurrences each of the variable symbols $x$, $y$ and $z$, and with two bound occurrences of $x$ and $y$, but where the bound appearances of $x$ fall under the scope of different quantifications over $x$. Next, construct a second formula with variables $w,x,y,z$ each with one free occurrence and three bound occurrences, but make the bound occurrences of $w,x$, respectively, fall under the scope of different quantifiers of these variables.
2. Distinguish the structure $\langle\mathbb{Z}^+,\mid\rangle$, where $\mathbb{Z}^+$ denotes the positive integers and $n\mid m$ just in case $n$ divides $m$, from the structure $\langle F,\subseteq\rangle$, where $F$ is the collection of finite subsets of the natural numbers $\mathbb{N}$. That is, find a statement in the first-order language with one binary relation, which is true in $\langle\mathbb{Z}^+,\mid\rangle$ and false in $\langle F,\subseteq\rangle$.
3. For each of the following pairs or triples of structures, distinguish them by finding a sentence that is true in the first, but false in the second.

Lecture 7. Signatures in first-order logic, with constants, functions and relations. terms. Models. Satisfaction. Distinguishing various structures by sentences. (Aside on the irrationality of $\sqrt{2}$.) The type of an element. Submodels. Reducts. Expansions. Elementary submodels. Leibniz principle on identity of indiscernibles. Leibnizian models. Isomorphisms. Elementary embeddings.

Lecture 7 students notes

Exercises.

1. Kindly do the rest of problem 3 from lecture 6 above; some of those instances were not mentioned in the previous lecture.
2. Distinguish the following structures in the first-order language having only multiplication, by finding for each structure a sentence true only in that structure:
$$\langle \mathbb{N},\cdot\rangle\qquad\langle \mathbb{Z},\cdot\rangle\qquad\langle \mathbb{Q},\cdot\rangle$$
3. Show that $\sqrt{3}$ is irrational. (Hint: follow the argument for $\sqrt{2}$ given in lecture, but replace talk of even/odd with talk involving divisibility-by-$3$. After all, a number is even just in case it is divisible by $2$.) What do you think is the general fact concerning whether $\sqrt{n}$ is irrational for natural numbers $n$?
4. Consider the chain of submodels $$\langle\mathbb{Z}^+,\lt\rangle\subset\langle \mathbb{N},\lt\rangle\subset\langle\mathbb{Z},\lt\rangle\subset\langle\mathbb{Q},\lt\rangle$$Are any of these submodels elementary submodels?
5. Argue that $\langle\mathbb{N},<\rangle$ is Leibnizian (any two elements are discernible, that is, they have different types).
6. Let $\langle A,\sim\rangle$ be a relational structure in which $\sim$ is an equivalence relation. Show that if $a\sim b$, then $a$ and $b$ are indiscernible in this structure.
7. Give an example of an infinite pre-order, which is not a partial order, in which any two elements are indiscernible.
8. Using some of the examples from the other exercises, find a structure $\cal M$ and a submodel ${\cal N}\subset {\cal M}$ such that ${\cal N}\equiv{\cal M}$ but ${\cal N}\not\prec{\cal M}$.
9. In the integers, is less-than fundamentally different from greater-than? Compare $\langle\mathbb{Z},<\rangle$ with $\langle\mathbb{Z},>\rangle$. Are there any statements that can tell apart $<$ from $>$? Specifically, argue that the structures $\langle \mathbb{Z},<\rangle$ and $\langle \mathbb{Z},>\rangle$ satisfy exactly the same truths. Conclusion: no first-order assertion can tell apart $<$ from $>$. That is, $\langle \mathbb{Z},<\rangle\equiv \langle \mathbb{Z},>\rangle$.

Paper topics.

1. Indiscernibility and identity.  Objects in a model are indiscernible with respect to a given formal language, if they satisfy all the same formulas in that language. There are numerous examples of structures having indiscernible non-identical elements, or in which all elements are indiscernible or none are, and it would be an interesting project to find examples illustrating the range of possibility.
2. Is every structure characterized by the collection of first-order truths in it? Is this true for finite structures? This is actually a deep topic, and there are many interesting examples and ideas.

Lecture 8. Definability. Definable elements, definable subsets. Examples with small finite partial orders. Every element of $\langle\mathbb{N},<\rangle$ is definable. No element of $\langle\mathbb{Z},<\rangle$ is definable. Homomorphisms, isomorphisms, automorphisms. If every object is definable, then the structure is Leibnizian. Is the converse true? No. Example of a Leibnizian structure with non-definable elements. $<$ is definable in $\langle\mathbb{N},<\rangle$, but not in $\langle\mathbb{Z},<\rangle$. The Peano structure $\langle\mathbb{N},S,0\rangle$. This structure admits elimination of quantifiers, by an argument proceeding via induction on formulas.

Exercises.

1. Which are the definable elements of the following partial orders? For each definable element, provide a definition; if an element is not definable, explain how you know that.
2. Consider the case of an equivalence relation $\sim$ having exactly one class of size one, exactly one class of size two, exactly one class of size three, etc. Are there any definable elements? What are the definable subsets?
3. Show that every element is definable in $\langle\mathbb{N},+\rangle$. (Hint: it is easy to define $0$; to define $1$, note that $1$ cannot be written as the sum of two other numbers, neither of which are $1$; now use $1$ to define all other numbers.)
4. Show that multiplication is not definable from addition in $\langle\mathbb{Z},+\rangle$. (Hint: If it were, then $1$ would be definable. But argue that $1$ is not definable in $\langle\mathbb{Z},+\rangle$.)
5. Show that “$x$ is even” and “$x$ is odd” are definable in $\langle\mathbb{N},+\rangle$. Using the elimination of quantifiers result from lecture, conclude that $+$ is not definable in the Peano structure $\langle\mathbb{N},S,0\rangle$.
6. Show that “$x$ is prime” is definable in $\langle\mathbb{N},\cdot\rangle$.

Suggested Paper topics.

1. Additional instances of elimination of quantifiers. For example, in $\langle\mathbb{Q},<\rangle$, which is an interesting argument.
2. Argue that in a finite structure, Leibnitzian is the same as every-object-is-definable.
3. Discuss the Leibnitizian axiom of set theory: every two objects are discernible over the ordinals.
4. On the significance of Tarski’s theorem that $\langle\mathbb{R},+,\cdot,0,1,<\rangle$ admits elimination of quantifiers. Discuss significance of having a decision procedure for Cartesian plane geometry.

Lecture 9. Continuation of quantifier elimination. Discussion of Tarski’s theorem on quantifier elimination for $\langle\mathbb{R},+,\cdot,0,1,<\rangle$, and consequent decidability of Cartesian geometry.  Modal logic. Examples of natural modalities. Kripke semantics. Kripke models for propositional modal logic. Kripke frames. Axiom K $\necessary(\varphi\to\psi)\to(\necessary\varphi\to\necessary\psi)$ and axiom Dual $\neg\possible\varphi\leftrightarrow\necessary\neg\varphi$ are true in all Kripke models. Axiom S $\necessary\varphi\to \varphi$ is valid on a frame just in case the frame is reflexive. Seriality D $\necessary\varphi\to\possible\varphi$ is valid on a frame just in case the frame has no terminal worlds, accessing no other worlds. Axiom 4 $\necessary\varphi\to\necessary\necessary\varphi$ is valid on a frame just in case the frame transitive. Axiom 5 $\possible\necessary\varphi\to \varphi$ is valid on a frame just in case the frame is symmetric. Axiom (.2) $\possible\necessary\varphi\to\necessary\possible\varphi$ expresses that the frame is directed. Axiom (.3) $\possible\varphi\wedge\possible\psi\implies(\possible(\varphi\wedge\possible\psi) \vee\possible(\varphi\wedge\psi)\vee\possible(\psi\wedge\possible\varphi))$ expresses that the frame is linear.  Predicate modal logic. The Barcan formula $\forall x\necessary\varphi(x)\to\necessary\forall x\varphi(x)$ and the converse Barcan $\necessary\forall x\varphi(x)\to\forall x\necessary\varphi(x)$, and the connection with growing vs. shrinking worlds.

Exercises.

1. Determine the truth of the following assertions at the various worlds in the following Kripke model. $$\necessary(p\to\necessary p),\quad\qquad \possible\necessary p,\quad\qquad \possible\necessary\neg p,\quad\qquad \necessary p\to\necessary\necessary p,\quad\qquad\possible\necessary(p\iff\neg\possible p)$$
2. Prove that every assertion of propositional modal
logic is equivalent under the Kripke semantics to an assertion using only
$\necessary,\wedge,\neg$.
3. Show that $[(\possible\necessary\varphi)\wedge(\possible\necessary\psi)]\implies\possible\necessary(\varphi\wedge\psi)$ is valid on a partial pre-order frame just in case the frame is directed.

Paper topics. We have fewer exercises because it is time to be working on your papers.  Please make an appointment to discuss your topic with me, if you have not done so already.

1. Combine modal logic Kripke semantics with multivalued logic.
2. Investigate predicate modal logic, such as conditions for the Barcan formula and for its converse.
3. Bimodalities obtained by using the accessibility relation and its inverse.
4. Analyze various conceptions of temporal logic using modal logic, and investigate how one’s conception of the nature of possibility through time (such as linear, tree branching, others) arise in the resulting modal logic.


Lecture 10. Theory theory. $T\models\varphi$. Deduction theorem for logical consequence: $\Gamma+\varphi\models\psi\iff\Gamma\models\varphi\to\psi$. The set of models of a theory, $\Mod(T)$. The theory of a model $\Th(M)$. The theory of a set of models, $\Th(\Gamma)$. $\Gamma_0\subset\Gamma_1\to\Th(\Gamma_1)\subset\Th(\Gamma_0)$. $T_0\subset T_1\to\Mod(T_1)\subset\Mod(T_0)$. $\Gamma\subset\Mod(\Th(\Gamma))$. $T\subset\Th(\Mod(T))$. $\Mod(\Th(\Mod(T))=\Mod(T)$. Consequences of a theory. Complete theory. Satisfiable theory. Finitely satisfiable theory. Compactness theorem: A theory $T$ is finitely satisfiable if and only if it is satisfiable. Direct proof of compactness using Henkin constants. Every finitely satisfiable theory $T$ is contained in a finitely satisfiable complete Henkin theory. Every such theory has a model, built from the Henkin constants. Consequences of compactness. Finiteness is not first-order expressible. Every theory with arbitrarily large finite models has an infinite model. Upward Löwenheim-Skolem theorem. Elementary extensions of $\langle\mathbb{R},+,\cdot,0,1,<\rangle$. Nonstandard analysis. Infinitesimals. Historical significance of nonstandard analysis for calculus.Lecture 10 student notes

Exercises.

1. Show that $\Th(\Mod(\Th(\Gamma)))=\Th(\Gamma)$, if $\Gamma$ is any set of models.
2. Let $\text{Conseq}(T)=\{\ \varphi\mid T\models\varphi\ \}$, the set of consequences of a theory $T$. Show that $T\models\psi$ if and only if $\text{Conseq}(T)\models\psi$.
3. Show that a theory $T$ is closed under consequences (that is, $T\models\sigma$ implies $\sigma\in T$) if and only if $T=\Th(\Mod(T))$. (Edit: an earlier version of this exercise was not correct.)
4. Show that if $T\models\varphi$, then there is a finite subtheory $S\subset T$ such that $S\models\varphi$. In another words, if a statement $\varphi$ is a consequence of a theory $T$, then there is a finite part of the theory that is responsible for this.

Suggested paper topics.

1. Nonstandard analysis. There are many topics here that would be suitable; please come and discuss with me. Using the compactness theorem, one could establish that various kinds of nonstandard natural exist.
2. Undertake some theory theory in infinitary logic. Prove that compactness can fail; finiteness is expressible and so on.

Lecture 11. Proof theory. What is a proof? Various formal proof systems. Logical axioms, rules of inference, formal proof. Automated theorem proving. Importance of (1) soundness $T\vdash\varphi$ implies $T\models\varphi$; (2) completeness $T\models\varphi$ implies $T\vdash\varphi$; (3) decidability: we should be able to recognize whether something is a proof. The MM proof system (A. Miller) is sound and complete. Another more satisfactory proof system, with examples. Gödel’s completeness theorem, using Henkin’s proof. Every consistent theory can be extended to a complete consistent Henkin theory, and every such theory is satisfiable.

Lecture 11 students notes

Exercises.

1. Construct a formal proof system that is sound, but not complete.
2. Construct a formal proof system that is complete, but not sound.
3. Construct a formal proof system that is sound and complete, but not decidable. (These first three exercises are meant to be very easy, and there is no need for the systems to be complicated at all. Think along the lines of having a system with no logical axioms or with every statement being an axiom or with having lots of rules of inference, or none. The right combinations will make the examples work.)
4. Show that a theory $T$ is inconsistent (proves a contradiction $\varphi\wedge\neg\varphi$ for some $\varphi$) just in case $T\vdash\psi$ for every $\psi$.
5. Extra: Show that every formal proof system is equivalent to a formal proof system having no logical axioms. (Hint: add extra rules of inference with empty hypotheses.)
6. Extra: Show that any formal proof system having no logical axioms and having rules of inference only with nonempty hypotheses, is not complete. (Hint: consider the proofs arising from the empty theory.)
7. Extra: Show that no sound formal proof system having only logical axioms and no rules of inference is complete.

Suggested paper topics.

1. Design your own formal proof system and prove the completeness theorem for it.
2. Translating proofs from one system to another.
3. Automated reasoning. Learn one of the standard proof-checker automated theorem proving systems and carry out a nontrivial formal proof in it.

Lecture 12. Computability theory. Primitive recursive functions; composition; primitive recursion, with examples. Turing machines. Sample programs. Other computational models: register machines, flowchart machines, recursive functions, idealized programming languages. Hierarchy vision of computability vs. threshold vision. Church-Turing thesis (weak and strong). Undecidability of the halting problem.

Lecture 12 student notes

Exercises

1. Write a Turing machine program to compute the function $d(n)=0$, when $n$ is even; otherwise, $d(n)=1$, when $n$ is odd.
2. Extra: Explain how the the class of Turing computable functions avoids the diagonalization argument of Gödel given for the primitive recursive functions. That is, we may still effectively enumerate $f_n$ all computable functions, and still attempt to define $g(n)=f_n(n)+1$. Does this argument show that there are intuitively computable functions that are not Turing computable? Why does it work with primitive recursive functions and not with computable functions?

Paper topics

1. Develop a new model of computability and prove that it is Turing complete.
2. Topics in oracle computation and the Turing degrees.
3. Topics in infinitary computability, such as Blum-Shub-Smale machines, or infinite time Turing machines.

Next week:  Gödel’s incompleteness theorems!

Lecture 13. Gödel’s incompleteness theorems. Hilbert program. Proof of first incompleteness via halting problem (due to Kleene). For any true computably axiomatizable theory $T$, there is a Turing machine program $p$ and input $k$ such that $p$ does not halt on input $k$, but $T$ does not prove this. MRDP theorem. Arithmetization of syntax. Gödel codes. Carnap’s fixed-point lemma. Gödel sentence, “I am not provable.” First incompleteness theorem. Second incompleteness theorem. Derivability conditions. Rosser’s theorem. Tarski’s theorem. Löb’s theorem. Independence phenomenon. Goodstein’s theorem. Kirby-Paris Hydra theorem.

Lecture 13 student notes

Exercises.

1. Show that if $T$ is a computably axiomatizable theory extending PA, then $T$ is inconsistent just in case $T$ proves $\text{Con}_T$.

All students should be working on their final papers, with the topic chosen in consultation with me.  The papers are due by the end of finals week; no late work will be accepted. Please come to my office with drafts for comments and suggestions.

Lecture 14. Set theory and the higher infinite. The googol plex bang stack hierarchy. Hilbert’s hotel. Countable sets. Cantor’s theorem on the uncountability of the reals. Equinumerosity. Cantor-Schröder-Bernstein theorem. Ordinals. How to count. Cantor’s theorem that $X<P(X)$. General Comprehension principle. Russell’s paradox. Rise of ZFC. The continuum hypothesis. Gödel’s theorem on the constructible universe; Cohen’s development of forcing. The independence phenomenon. The singularist/pluralist debate in the philosophy of set theory.

Lecture 14 student notes

This was the last lecture; it was a great time! Final papers are due by the end of finals week. Please drop by my office for comments on a draft version of your paper.

Final Papers The students all wrote final papers on various topics connected with the seminar, and many of them were quite interesting. Let me summarize here several of the resulting titles and topics.

Mala Chatterjee, Łukasiewicz Logic & Strong Completeness.  Mala investigates complete sets of connectives for Łukasiewicz logic, introducing several novel connectives, denoted by $+$, $\Cup$ and $\oplus$, which she shows can form various small complete sets of connectives for this logic.

Hugo Dumoulin, Logic Gates and the Turing Machine. Hugo constructs a subtractor using only logic gates and explains how logic gates can be used be used to simulate Turing machines.

Arden Koehler, Definability and distinguishability in finite and infinite structures.  Arden investigates the difference between Leibnizian structures (where any two objects have different types) and pointwise-definable structures (where every individual is definable) in first-order logic. In finite structures, the concepts are equivalent, but there are infinite structures, even in a finite language, which are Leibnizian, yet have no definable elements.

Annette Martin, A brief look at nonstandard models of true arithmetic. Annette develops the theory of nonstandard models of true arithmetic, establishing the overspill principle, determining the order type of every countable nonstandard model of arithmetic, proving that every nonstandard model of arithmetic has entire $\mathbb{Z}$ chains consisting of composite nonstandard numbers, and proving that there are uncountably many pairwise non-isomorphic countable nonstandard models of true arithmetic.

Nathan Pensler, What is the Logic of Missing Information?  Abstract: Is there a logic of missing information? In this paper, I’ll survey several logics and determine
whether any of them provide an adequate analysis of the concept. I first discuss Kleene and Łukasiewicz Logics. I argue that both systems fail as logics of missing information, due to counterexamples involving classical tautologies. I then discuss several new logics of missing information, all of which assign truth values to formulae relative to an informational background. I define what it is for a logic to be truth functional and prove that several logics of this type are truth functional just in case the informational background is severely restricted. I then explore a truth-functional logic of missing information. I conclude by exploring whether there is reason to prefer the truth functional logic of missing information to the non-truth functional logics.

David Storrs-Fox, The modal logic of a knight in chess.  David investigates the modal logic of a knight’s move, by considering the frame consisting of the squares on a chessboard (in both the finite and infinite cases) as the possible worlds and the knight’s move as the accessibility relation. After settling a large number of validities and invalidities for this chessboard interpretation, David proves that the squares on the 8×8 chessboard are distinguished by their modal validities, unless they are in rotational or reflective symmetry.

Casey Tirschfield, Select limitations of infinitary logic.   In this paper, Casey develops the basic syntax and semantics of the infinitary logics $L_{\kappa,\mu}$ and proved that the compactness theorem and the upward Löwenheim-Skolem theorems can both fail in the infinitary context.

Kameryn J Williams, Complete sets of connectives for generalized Łukasiewicz logics. Abstract: While $\wedge$, $\vee$, $\neg$ form  complete set of connectives for classical propositional logic, this does not hold for Łukasiewicz’s three-valued propositional logic, nor its generalization to $n$-valued logic. We define a unary connective $\frak{c}$ so that $\wedge$, $\vee$, $\neg$, $\frak{c}$ form a complete set of connectives for $n$-valued Lukasiewicz logic. We discuss generalizations of this to infinitary logics. If we allow infinite conjunctions and disjunctions of arbitrary size, this provides a complete set of connectives for real-valued Łukasiewicz logic. Restricting to countable conjunctions and disjunctions, the truth functions expressible with these connectives are precisely the Borel functions.

Jake Zuehl, What group preferences can arise by majority vote?  It is known by the Condorcet paradox that the group preferences determined by majority vote can be non-transitive, even when all individuals have linearly ordered preference relations. But exactly which relations can arise? In this paper, Jake proves that it is all and only the asymmetric irreflexive relations that arise as the majority-vote group preference relation by a group of individuals with linear preferences. He then proceeds to investigate bounds on the minimum number of voters required to realize a given relation.

# Student talks on infinitary computability

Students in my Infinitary Computability course will give talks on their term papers.  Talks will be held at the CUNY Graduate Center, Room 3307, 9:30-11:30.

Monday, December 3rd

• Miha Habič will speak on “Cardinal-Recognizing Infinite Time Turing Machines”, in which he develops the theory of infinite time Turing machines that are given information about when they have reached cardinal time.
• Erin Carmody will speak on “Non-deterministic infinite time Turing machines”, in which she develops the theory of non-deterministic ITTM computation.
• Alexy Nikolaev will speak on “Equivalence of ITTMs, and their simultation on a finite time computer,” in which we proves the equivalence of various formalizations of ITTMs.

Monday, December 10th

• Manuel Alves will speak on infinite time computable model theory.
• Syed Ali Ahmed will speak on the relation between Büchi automata and infinite time Turing machines, including $\omega$-regular languages and generalizations to longer transfinite strings.

# A course in infinitary computability, Fall 2012, CUNY Graduate Center, CSC 85020

In Fall 2012 I will teach a graduate course on infinitary computability theory in the Computer Science program at the CUNY Graduate Center.   This course will be aimed at graduate students in computer science and mathematics who are interested in infinitary computational processes.

Infinitary computability, CSC 85020, Mondays, 9:30 – 11:30 am
CS course listings | this listing

This course will explore all the various infinitary theories of computability, including infinite time Turing machines, Blum-Shub-Smale computability, Büchi automata, ordinal register machines and others. The focus will be on introducing the computability models and comparing them to each other and to standard concepts of computability. In the early part of the course, we shall review the standard finitary computational models, before investigating the infinitary supertask analogues.

Students wishing to prepare for the course should review their understanding of Turing machines and the other theoretical machine models of computation.