# 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.

# Philosophy of set theory, Fall 2011, NYU PH GA 1180

I taught a course in Fall 2011 at NYU entitled Topics in Logic: set theory and the philosophy of set theory, aimed at graduate students in philosophy and others who want to gain greater understanding of some of the set-theoretic topics central to work in the philosophy of set theory.  The course began with a review of the mathematical ideas, including a presentation of large cardinals, strong axioms of infinity and their associated elementary embeddings of the universe, and forcing, emphasizing the connection with the Boolean ultrapower and Boolean-valued models, but discussing the alternative formalizations. The second part of the course covers some of the philosophical literature, including what it means to accept or believe mathematical axioms, whether mathematics needs new axioms, the criteria one might use when adopting new axioms, and the question of pluralism and categoricity in set theory.

Here is a partial list of our readings:

1. Mathematical background.

2.  Penelope Maddy, “Believing the axioms”, in two parts.  JSL vols. 52 and 53. Part 1Part 2

3. Chris Freiling, “Axioms of Symmetry: throwing darts at the real number line,”
JSL, vol. 51.   http://www.jstor.org/stable/2273955

4. W. N. Reinhardt, “Remarks on reflection principles, large cardinals, and elementary embeddings,” Proceedings of Symposia in Pure Mathematics, Vol 13, Part II, 1974, pp. 189-205.

5. Donald Martin, “Multiple universes of sets and indeterminate truth values,” Topoi 20, 5–16, 2001.

6. Hartry Field, “Which undecidable mathematical sentences have determinate truth values,” as reprinted in his book Truth and the Absence of Fact, Oxford University Press, 2001.

7. A brief selection from Marc Balaguer, Platonism and Anti-Platonism in Mathematics, Oxford University Press, 1998, describing the plenitudinous Platonism position.

8. Daniel Isaacson, “The reality of mathematics and the case of set theory,” 2007.

9. J. D. Hamkins, “The set-theoretic multiverse,” to appear in the Review of Symbolic Logic.

10.  Solomon Feferman, Does mathematics need new axioms? Text of an invited AMS-MAA joint meeting, San Diego, January, 1997.

11. Solomon Feferman, Is the continuum hypothesis a definite mathematical problem? Draft article for the Exploring the Frontiers of Independence lecture series at Harvard University, October, 2011.

12. Peter Koellner, Feferman On the Indefiniteness of CH, a commentary on Feferman’s EFI article.

13. Interpretability of theories, the interpretability degrees and Orey sentences in set theory and arithmetic.  Some of the basic material is found in Per Lindström’s book Aspects of Incompleteness, available at  http://projecteuclid.org/euclid.lnl/1235416274, particularly chapter 6, and some later chapters.

14. Haim Gaifman, “On ontology and realism in mathematics,” to appear in the Review of Symbolic Logic (special issue connected with the NYU philosophy of mathematics conference 2009).

15. Saharon Shelah, “Logical dreams,”  Bulletin of the AMS, 40(20):203–228, 2003. (Pre-publication version available at:http://arxiv.org/abs/math.LO/0211398)

16.  For mathematical/philosophical amusement, Philip Welch and Leon Horsten, “The aftermath.”

It’s been a great semester!