Transfinite epistemic logic puzzle challenge!

 

Can you solve my challenge puzzle?

 

Cheryl's numbers

Cheryl   Welcome, Albert and Bernard, to my birthday party, and I thank you for your gifts. To return the favor, as you entered my party, I privately made known to each of you a rational number of the form $$n-\frac{1}{2^k}-\frac{1}{2^{k+r}},$$ where $n$ and $k$ are positive integers and $r$ is a non-negative integer; please consider it my gift to each of you. Your numbers are different from each other, and you have received no other information about these numbers or anyone’s knowledge about them beyond what I am now telling you. Let me ask, who of you has the larger number?

Albert    I don’t know.

Bernard    Neither do I.

Albert    Indeed, I still do not know.

Bernard    And still neither do I.

Cheryl    Well, it is no use to continue that way! I can tell you that no matter how long you continue that back-and-forth, you shall not come to know who has the larger number.

Albert    What interesting new information! But alas, I still do not know whose number is larger.

Bernard    And still also I do not know.

Albert    I continue not to know.

Bernard    I regret that I also do not know.

Cheryl    Let me say once again that no matter how long you continue truthfully to tell each other in succession that you do not yet know, you will not know who has the larger number.

Albert    Well, thank you very much for saving us from that tiresome trouble! But unfortunately, I still do not know who has the larger number.

Bernard    And also I remain in ignorance. However shall we come to know?

Cheryl    Well, in fact, no matter how long we three continue from now in the pattern we have followed so far—namely, the pattern in which you two state back-and-forth that still you do not yet know whose number is larger and then I tell you yet again that no further amount of that back-and-forth will enable you to know—then still after as much repetition of that pattern as we can stand, you will not know whose number is larger! Furthermore, I could make that same statement a second time, even after now that I have said it to you once, and it would still be true. And a third and fourth as well! Indeed, I could make that same pronouncement a hundred times altogether in succession (counting my first time as amongst the one hundred), and it would be true every time. And furthermore, even after my having said it altogether one hundred times in succession, you would still not know who has the larger number!

Albert    Such powerful new information! But I am very sorry to say that still I do not know whose number is larger.

Bernard    And also I do not know.

Albert    But wait! It suddenly comes upon me after Bernard’s last remark, that finally I know who has the larger number!

Bernard    Really? In that case, then I also know, and what is more, I know both of our numbers!

Albert    Well, now I also know them!

 


Question. What numbers did Cheryl give to Albert and Bernard?

If you can determine the answer, make comments below or post a link to your solution. I shall post a solution in a few days time.

See my earlier transfinite epistemic logic puzzles, with solutions. These were inspired by Timothy Gowers’s example.

 

Now I know!

Inspired by Timothy Gowers’s example, here is my transfinite epistemic logic problem.

First, let’s begin with a simple finite example.

Cheryl   Hello Albert and Bernard! I have given you each a different natural number ($0, 1, 2, \ldots$). Who of you has the larger number?

Albert   I don’t know.

Bernard   I don’t know either.

Albert    Even though you say that, I still don’t know.

Bernard    And still neither do I.

Albert    Alas, I continue not to know.

Bernard   And also I do not know.

Albert     Yet, I still do not know.

Bernard     Aha! Now I know which of us has the larger number.

Albert      In that case, I know both our numbers.

Bernard.  And now I also know both numbers.

Question: What numbers do Albert and Bernard have?

Click for the solution.

infinity

 

Now, let us consider a transfinite instance. Consider the following conversation.

Cheryl     I have given you each a different ordinal number, possibly transfinite, but possibly finite. Who of you has the larger ordinal?

Albert     I don’t know.

Bernard     I don’t know, either.

Albert     Even though you say that, I still don’t know.

Bernard     And still neither do I.

Albert     Alas, I still don’t know.

Bernard     And yet, neither do I.

Cheryl     Well, this is becoming boring. Let me tell you that no matter how much longer you continue that back-and-forth, you still will not know the answer.

Albert      Well, thank you, Cheryl, for that new information. However, I still do not know who has the larger ordinal.

Bernard     And yet still neither do I.

Albert     Alas, even now I do not know!

Bernard      And neither do I!

Cheryl     Excuse me; you two can go back and forth like this again, but let me tell you that no matter how much longer you continue in that pattern, you will not know.

Albert      Well, ’tis a pity, since even with this further information, I still do not know.

Bernard     Aha! Now at last I know who of us has the larger ordinal.

Albert     In that case, I know both our ordinals.

Bernard. And now I also know both ordinals.

Question:   What ordinals do they have?

Click for a solution.

 

See my next transfinite epistemic logic puzzle challenge!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Solutions.

  1. For the first problem, with natural numbers, let us call the numbers $a$ and $b$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $a\neq 0$, and so $a$ is at least $1$. And since Bernard can make this conclusion, when he announces that he doesn’t know, it must mean that $b$ is not $0$ or $1$, for otherwise he would know, and so $b\geq 2$. On the next round, since Albert still doesn’t know, it follows that $a$ must be at least $3$, for otherwise he would know; and then, because Bernard still doesn’t know, it follows that $b$ is at least $4$. The next round similarly yields that $a$ is at least $5$ and then that $b$ is at least $6$. Because Albert can undertake all this reasoning, it follows that $a$ is at least $7$ on account of Albert’s penultimate remark. Since Bernard announces at this point that he knows who has the larger number, it must be that Bernard has $6$ or $7$ and that Albert has the larger number. And since Albert now announces that he knows the numbers, it must be because Albert has $7$ and Bernard has $6$.
  2. For the transfinite problem, let us call the ordinal numbers $\alpha$ and $\beta$, respectively, for Albert and Bernard. Since Albert doesn’t know at the first step, it means that $\alpha\neq 0$ and so $\alpha\geq 1$. Similarly, $\beta\geq 2$ after Bernard’s remark, and then $\alpha\geq 3$ and $\beta\geq 4$ and this would continue for some time. Because Cheryl says that no matter how long they continue, they will not know, it follows that both $\alpha$ and $\beta$ are infinite ordinals, at least $\omega$. But since Albert does not know at this stage, it means $\alpha\geq\omega+1$, and then $\beta\geq \omega+2$. Since Cheryl says again that no matter how long they continue that, they will not know, it means that $\alpha$ and $\beta$ must both exceed $\omega+k$ for every finite $k$, and so $\alpha$ and $\beta$ are both at least $\omega\cdot 2$. Since Albert still doesn’t know after that remark, it means $\alpha\geq\omega\cdot 2+1$. But now, since Bernard knows at this point, it must be that $\beta=\omega\cdot 2$ or $\omega\cdot 2+1$, since otherwise he couldn’t know. So Albert’s ordinal is larger. Since at this point Albert knows both the ordinals, it must be because Albert has $\omega\cdot 2+1$ and Bernard has $\omega\cdot 2$.

It is clear that one may continue in this way through larger transfinite ordinals. When the ordinals become appreciable in size, then it will get harder to turn it into a totally finite conversation, by means of Cheryl’s remarks, but one may succeed at this for quite some way with suitably obscure pronouncements by Cheryl describing various limiting processes of the ordinals. To handle any given (possibly uncountable) ordinal, it seems best that we should consider conversations of transfinite length.

Math for eight-year-olds: graph theory for kids!

This morning I had the pleasure to be a mathematical guest in my daughter’s third-grade class, full of inquisitive eight- and nine-year-old girls, and we had a wonderful interaction. Following up on my visit last year (math for seven-year-olds), I wanted to explore with them some elementary ideas in graph theory, which I view as mathematically rich, yet accessible to children. Cover

My specific aim was for them to discover on their own the delightful surprise of the Euler characteristic for connected planar graphs.

Page 1

 

We began with a simple example, counting together the number of vertices, edges and regions. For counting the regions, I emphasized that we count the “outside” region as one of the regions.

 

Then, I injected a little mystery by mentioning that Euler had discovered something peculiar about calculating $V-E+R$.  Could they find out what it was that he had noticed?

Page 2+3

Each student had her own booklet and calculated the Euler characteristic for various small graphs, as I moved about the room helping out.Page 5Page 4

 

 

 

 

 

 

 

Eventually, the girls noticed the peculiar thing — they kept getting the number two as the outcome!  I heard them exclaim, why do we keep getting two?  They had found Euler’s delightful surprise!

Page 6+7

The teachers also were very curious about it, and one of them said to me in amazement, “I really want to know why we always get two!”

Page 8

 

With the students, I suggested that we try a few somewhat more unusual cases, to see how robust the always-two situation really was. But in these cases, we still got two as the result.

 

The girls made their own graphs and tested the hypothesis.Page 9Page 10+11

 

Eventually, of course, I managed to suggest some examples that do in fact test the always-two phenomenon, first by looking at disconnected graphs, and then by considering graphs drawn with crossing edges.Page 13Page 12

 

 

 

 

 

 

 

In this way, we were led to refine the $V-E+R=2$ hypothesis to the case of connected planar graphs.

Now, it was time for proof.  I was initially unsure whether I should actually give a proof, since these were just third-graders, after all, and I thought it might be too difficult for the students. But when the teachers had expressed their desire to know why, they had specifically encouraged me to give the argument, saying that even if some students didn’t follow it, there was still value merely in seeing that one can mount an argument like that.  Excellent teachers!

The idea of the proof is that $V-E+R=2$ is true at the start, in the case of a graph consisting of one vertex and no edges. Furthermore, it remains true when one adds one new vertex connected by one new edge, since the new vertex and new edge cancel out.  Also, it remains true when one carves out a new region from part of an old region with the addition of a single new edge, since in this case there is one new edge and one new region, and these also balance each other. Since any connected planar graph can be built up in this way by gradually adding new vertices and edges, this argument shows $V-E+R=2$ for any connected planar graph. This is a proof by mathematical induction on the size of the graph.

Page 14+15

Page 16

 

Next, we moved on to consider some three-dimensional solids and their surfaces.  With various polyhedra, and the girls were able to verify further instances of $V-E+R=2$.

Page 17

Page 18+19

 

The girls then drew their own solids and calculated the Euler characteristic.  I taught them how to draw a cube and several other solids pictured here; when the shape is more than just a simple cube, this can be a challenge for a child, but some of the children made some lovely solids:Page 21Page 20

 

 

 

 

 

 

 

In the end, each child had a nice little booklet to take home. The images above are taken from one of the students in the class.

Graph Booklet
What a great day!

You can find a kit of the booklet here: Math for eight-year-olds: graph theory for kids!

See also the account of my previous visit:  Math for seven-year-olds: graph coloring and Eulerian paths.

 

My new book:

A Mathematician's Year in Japan, by Joel David Hamkins, available on Amazon Kindle Books

A mathematician’s year in Japan

  • J. D. Hamkins, A Mathematician’s Year in Japan, author-published, via Amazon Kindle Direct Publishing, 2015. (ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2)  
    @BOOK{Hamkins2015:AMathematiciansYearInJapan,
    author = {Joel David Hamkins},
    title = {A {Mathematician's} {Year} in {Japan}},
    publisher = {author-published, via Amazon Kindle Direct Publishing},
    year = {2015},
    month = {March},
    url = {http://www.amazon.com/dp/B00U618LM2},
    note = {ASIN:B00U618LM2, 156 pages, http://www.amazon.com/dp/B00U618LM2},
    }

Years ago, when I was still a junior professor, I had the pleasure to live for a year in Japan, working as a research fellow at Kobe University. During that formative year, I recorded brief moments of my Japanese experience, and every two weeks or so—this was well before the current blogging era—I sent my descriptive missives by email to friends back home. I have now collected together those vignettes of my life in Japan, each a morsel of my experience. The book is now out!


A Mathematician's Year in Japan, by Joel David Hamkins, available on Amazon Kindle BooksA Mathematician’s Year in Japan
Joel David Hamkins

Glimpse into the life of a professor of logic as he fumbles his way through Japan.

A Mathematician’s Year in Japan is a lighthearted, though at times emotional account of how one mathematician finds himself in a place where everything seems unfamiliar, except his beloved research on the nature of infinity, yet even with that he experiences a crisis.

Available on Amazon $4.49.

Please be so kind as to write a review there.
jo eh ru

Embeddings of the universe into the constructible universe, current state of knowledge, CUNY Set Theory Seminar, March 2015

This will be a talk for the CUNY Set Theory Seminar, March 6, 2015.

I shall describe the current state of knowledge concerning the question of whether there can be an embedding of the set-theoretic universe into the constructible universe.

V to L

Question.(Hamkins) Can there be an embedding $j:V\to L$ of the set-theoretic universe $V$ into the constructible universe $L$, when $V\neq L$?

The notion of embedding here is merely that $$x\in y\iff j(x)\in j(y),$$ and such a map need not be elementary nor even $\Delta_0$-elementary. It is not difficult to see that there can generally be no $\Delta_0$-elementary embedding $j:V\to L$, when $V\neq L$.

Nevertheless, the question arises very naturally in the context of my previous work on the embeddability phenomenon, Every countable model of set theory embeds into its own constructible universe, where the title theorem is the following.

Theorem.(Hamkins) Every countable model of set theory $\langle M,\in^M\rangle$, including every countable transitive model of set theory, has an embedding $j:\langle M,\in^M\rangle\to\langle L^M,\in^M\rangle$ into its own constructible universe.

The methods of proof also established that the countable models of set theory are linearly pre-ordered by embeddability: given any two models, one of them embeds into the other; or equivalently, one of them is isomorphic to a submodel of the other. Indeed, one model $\langle M,\in^M\rangle$ embeds into another $\langle N,\in^N\rangle$ just in case the ordinals of the first $\text{Ord}^M$ order-embed into the ordinals of the second $\text{Ord}^N$. (And this implies the theorem above.)

In the proof of that theorem, the embeddings $j:M\to L^M$ are defined completely externally to $M$, and so it was natural to wonder to what extent such an embedding might be accessible inside $M$. And I realized that I could not generally refute the possibility that such a $j$ might even be a class in $M$.

Currently, the question remains open, but we have some partial progress, and have settled it in a number of cases, including the following, on which I’ll speak:

  • If there is an embedding $j:V\to L$, then for a proper class club of cardinals $\lambda$, we have $(2^\lambda)^V=(\lambda^+)^L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$.
  • If $0^\sharp$ exists, then there is no embedding $j:V\to L$ and indeed no embedding $j:P(\omega)\to L$.
  • If there is an embedding $j:V\to L$, then the GCH holds above $\aleph_0$.
  • In the forcing extension $V[G]$ obtained by adding $\omega_1$ many Cohen reals (or more), there is no embedding $j:V[G]\to L$, and indeed, no $j:P(\omega)^{V[G]}\to V$. More generally, after adding $\kappa^+$ many Cohen subsets to $\kappa$, for any regular cardinal $\kappa$, then in $V[G]$ there is no $j:P(\kappa)\to V$.
  • If $V$ is a nontrivial set-forcing extension of an inner model $M$, then there is no embedding $j:V\to M$. Indeed, there is no embedding $j:P(\kappa^+)\to M$, if the forcing has size $\kappa$. In particular, if $V$ is a nontrivial forcing extension, then there is no embedding $j:V\to L$.
  • Every countable set $A$ has an embedding $j:A\to L$.

This is joint work of myself, W. Hugh Woodin, Menachem Magidor, with contributions also by David Aspero, Ralf Schindler and Yair Hayut.

See my related MathOverflow question: Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?

Talk Abstract

A conference in honor of W. Hugh Woodin’s 60th birthday, March 2015

I am pleased to announce the upcoming conference at Harvard celebrating the 60th birthday of W. Hugh Woodin.  See the conference web site for more information. Click on the image below for a large-format poster.

woodin_conference_poster

Moved to a new server, new WordPress installation

I’ve recently moved my site to a new server and apologize for the brief disruption in service. Many thanks to Sam Coskey and Peter Krautzberger for all the help with the move, and for all their help over the years with getting me started on WordPress at Boolesrings.  They really opened my eyes to the possibilities.

I am currently still fixing various technical issues with the new installation, but please post a comment if you see any issue that needs attention. My intention is that all links to jdh.hamkins.org will still work as before.

– Joel David Hamkins

 

 

A picture of logic, between mathematics and philosophy

A picture of logic between math and philosophyYears ago, when I was a student and young professor in Berkeley, one often heard it said that the subject of logic or at least metamathematics, according to the Tarski school, could be divided into four subjects: model theory, set theory, computability theory (then called recursion theory) and proof theory.

I have long felt that this taxonomy has become increasingly inadequate as a description, and so at the start of my course Logic for Philosophers yesterday, I tried to draw a somewhat fuller picture on the whiteboard.  You can see my diagram above, showing the main parts of logic, occupying regions both within mathematics, within philosophy and within computer science, as well as filling out regions that might be considered between these subjects.

OK, this picture is a first attempt, and I’ll try to improve it.  Please post comments and criticisms below.

It would certainly be possible to flesh out subareas of nearly all the subjects mentioned. We may imagine set theory, for example, broken into descriptive set theory, Borel equivalence relation theory, large cardinals, forcing, cardinal characteristics, and so on; and similarly we may break up the huge subjects of model theory, computability theory and proof theory. In particular, most subjects don’t fit neatly into a small region, since almost all the subjects have parts that touch areas very far away.  Computability theory, for example, touches not only complexity theory and computer science, but also model theory in computable model theory, as well as reverse mathematics, foundations of mathematics, proof theory and so on.  Category theory is a kind of diffuse superposition onto the entire diagram, with comparatively less direct interaction with these other areas.  Proof theory should be closer to reverse mathematics and to model theory, and probably closer to mathematics.

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

NYU PhilosophyThis 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.  Exercise_graphs

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. Two partial orders
  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.

$\newcommand\necessary\square\newcommand\possible\Diamond$
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)$$Kripke model 1
  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.

$\newcommand\Mod{\text{Mod}}\newcommand\Th{\text{Th}}$

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.

Ehrenfeucht's lemma in set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Ehrenfeucht’s lemma in set theory.” (manuscript under review)  
    @ARTICLE{FuchsGitmanHamkins:EhrenfeuchtsLemmaInSetTheory,
    author = {Gunter Fuchs and Victoria Gitman and Joel David Hamkins},
    title = {Ehrenfeucht's lemma in set theory},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    eprint = {1501.01918},
    note = {manuscript under review},
    url = {\url{http://jdh.hamkins.org/ehrenfeuchts-lemma-in-set-theory}},
    abstract = {},
    keywords = {},
    source = {},
    }

This is joint work with Gunter Fuchs and Victoria Gitman. $\newcommand\HOD{\text{HOD}}\newcommand\Ehrenfeucht{\text{EL}}$

Abstract. Ehrenfeucht’s lemma asserts that whenever one element of a model of Peano arithmetic is definable from another, then they satisfy different types. We consider here the analogue of Ehrenfeucht’s lemma for models of set theory. The original argument applies directly to the ordinal-definable elements of any model of set theory, and in particular, Ehrenfeucht’s lemma holds fully for models of set theory satisfying $V=\HOD$. We show that the lemma can fail, however, in models of set theory with $V\neq\HOD$, and it necessarily fails in the forcing extension to add a generic Cohen real. We go on to formulate a scheme of natural parametric generalizations of Ehrenfeucht’s lemma, namely, the principles of the form $\Ehrenfeucht(A,P,Q)$, which asserts that whenever an object $b$ is definable in $M$ from some $a\in A$ using parameters in $P$, with $b\neq a$, then the types of $a$ and $b$ over $Q$ in $M$ are different. We also consider various analogues of Ehrenfeucht’s lemma obtained by using algebraicity in place of definability, where a set $b$ is \emph{algebraic} in $a$ if it is a member of a finite set definable from $a$ (as in J. D. Hamkins and C. Leahy, Algebraicity and implicit definability in set theory). Ehrenfeucht’s lemma holds for the ordinal-algebraic sets, we prove, if and only if the ordinal-algebraic and ordinal-definable sets coincide. Using similar analysis, we answer two open questions posed in my paper with Leahy, by showing that (i) algebraicity and definability need not coincide in models of set theory and (ii) the internal and external notions of being ordinal algebraic need not coincide.

Incomparable $\omega_1$-like models of set theory

  • G. Fuchs, V. Gitman, and J. D. Hamkins, “Incomparable $\omega_1$-like models of set theory.” (manuscript under review)  
    @ARTICLE{FuchsGitmanHamkins:IncomparableOmega1-likeModelsOfSetTheory,
    author = {Gunter Fuchs and Victoria Gitman and Joel David Hamkins},
    title = {Incomparable $\omega_1$-like models of set theory},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    eprint = {1501.01022},
    note = {manuscript under review},
    url = {\url{http://jdh.hamkins.org/incomparable-omega-one-like-models-of-set-theory}},
    abstract = {},
    keywords = {},
    source = {},
    }

This is joint work with Gunter Fuchs and Victoria Gitman.

Abstract. We show that the analogues of the Hamkins embedding theorems, proved for the countable models of set theory, do not hold when extended to the uncountable realm of $\omega_1$-like models of set theory. Specifically, under the $\diamondsuit$ hypothesis and suitable consistency assumptions, we show that there is a family of $2^{\omega_1}$ many $\omega_1$-like models of $\text{ZFC}$, all with the same ordinals, that are pairwise incomparable under embeddability; there can be a transitive $\omega_1$-like model of ZFC that does not embed into its own constructible universe; and there can be an $\omega_1$-like model of PA whose structure of hereditarily finite sets is not universal for the $\omega_1$-like models of set theory.

In this article, we consider the question of whether the embedding theorems of my article, Every countable model of set theory embeds into its own constructible universe, which concern the countable models of set theory, might extend to the realm of uncountable models. Specifically, in that paper I had proved that (1) any two countable models of set theory are comparable by embeddability; indeed, (2) one countable model of set theory embeds into another just in case the ordinals of the first order-embed into the ordinals of the second; consequently, (3) every countable model of set theory embeds into its own constructible universe; and furthermore, (4) every countable model of set theory embeds into the hereditarily finite sets $\langle\text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. The question we consider here is, do the analogous results hold for uncountable models? Our answer is that they do not. Indeed, we shall prove that the corresponding statements do not hold even in the special case of $\omega_1$-like models of set theory, which otherwise among uncountable models often exhibit a special affinity with the countable models. Specifically, we shall construct large families of pairwise incomparable $\omega_1$-like models of set theory, even though they all have the same ordinals; we shall construct $\omega_1$-like models of set theory that do not embed into their own $L$; and we shall construct $\omega_1$-like models of \PA\ that are not universal for all $\omega_1$-like models of set theory.

The embedding theorems are expressed collectively in the theorem below. An embedding of one model $\langle M,{\in^M}\rangle$ of set theory into another $\langle N,{\in^N}\rangle$ is simply a function $j:M\to N$ for which $x\in^My\longleftrightarrow j(x)\in^Nj(y)$, for all $x,y\in M$, and in this case we say that $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$; note by extensionality that every embedding is injective. Thus, an embedding is simply an isomorphism of $\langle M,{\in^M}\rangle$ with its range, which is a submodel of $\langle N,{\in^N}\rangle$. Although this is the usual model-theoretic embedding concept for relational structures, the reader should note that it is a considerably weaker embedding concept than commonly encountered in set theory, because this kind of embedding need not be elementary nor even $\Delta_0$-elementary, although clearly every embedding as just defined is elementary at least for quantifier-free assertions. So we caution the reader not to assume a greater degree of elementarity beyond quantifier-free elementarity for the embeddings appearing in this paper.

Theorem.

1. For any two countable models of set theory $\langle M,\in^M\rangle$ and $\langle N,\in^N\rangle$, one of them embeds into the other.

2. Indeed, such an $\langle M,{\in^M}\rangle$ embeds into $\langle N,{\in^N}\rangle$ if and only if the ordinals of $M$ order-embed into the ordinals of $N$.

3. Consequently, every countable model $\langle M,\in^M\rangle$ of set theory embeds into its own constructible universe $\langle L^M,\in^M\rangle$.

4. Furthermore, every countable model of set theory embeds into the hereditary finite sets $\langle \text{HF},{\in}\rangle^M$ of any nonstandard model of arithmetic $M\models\text{PA}$. Indeed, $\text{HF}^M$ is universal for all countable acyclic binary relations.

One can begin to get an appreciation for the difference in embedding concepts by observing that ZFC proves that there is a nontrivial embedding $j:V\to V$, namely, the embedding recursively defined as follows $$j(y)=\bigl\{\ j(x)\ \mid\ x\in y\ \bigr\}\cup\bigl\{\{\emptyset,y\}\bigr\}.$$

We leave it as a fun exercise to verify that $x\in y\longleftrightarrow j(x)\in j(y)$ for the embedding $j$ defined by this recursion. (See my paper Every countable model of set theory embeds into its own constructible universe; but to give a hint here for the impatient, note that every $j(y)$ is nonempty and also $\emptyset\notin j(y)$; it follows that inside $j(y)$ we may identify the pair $\{\emptyset,y\}\in j(y)$; it follows that $j$ is injective and furthermore, the only way to have $j(x)\in j(y)$ is from $x\in y$.} Contrast this situation with the well-known Kunen inconsistency, which asserts that there can be no nontrivial $\Sigma_1$-elementary embedding $j:V\to V$. Similarly, the same recursive definition applied in $L$ leads to nontrivial embeddings $j:L\to L$, regardless of whether $0^\sharp$ exists. But again, the point is that embeddings are not necessarily even $\Delta_0$-elementary, and the familiar equivalence of the existence of $0^\sharp$ with a nontrivial “embedding” $j:L\to L$ actually requires a $\Delta_0$-elementary embedding.)

We find it interesting to note in contrast to the theorem above that there is no such embedding phenomenon in the the context of the countable models of Peano arithmetic (where an embedding of models of arithmetic is a function preserving all atomic formulas in the language of arithmetic). Perhaps the main reason for this is that embeddings between models of PA are automatically $\Delta_0$-elementary, as a consequence of the MRDP theorem, whereas this is not true for models of set theory, as the example above of the recursively defined embedding $j:V\to V$ shows, since this is an embedding, but it is not $\Delta_0$-elementary, in light of $j(\emptyset)\neq\emptyset$. For countable models of arithmetic $M,N\models\text{PA}$, one can show that there is an embedding $j:M\to N$ if and only if $N$ satisfies the $\Sigma_1$-theory of $M$ and the standard system of $M$ is contained in the standard system of $N$. It follows that there are many instances of incomparability. Meanwhile, it is a consequence of statement (4) that the embedding phenomenon recurs with the countable models of finite set theory $\text{ZFC}^{\neg\infty}$, that is, with $\langle\text{HF},{\in}\rangle^M$ for $M\models\text{PA}$, since all nonstandard such models are universal for all countable acyclic binary relations, and so in the context of countable models of $\text{ZFC}^{\neg\infty}$ there are precisely two bi-embeddability classes, namely, the standard model, which is initial, and the nonstandard countable models, which are universal.

Our main theorems are as follows.

Theorem.

1. If $\diamondsuit$ holds and ZFC is consistent, then there is a family $\mathcal C$ of $2^{\omega_1}$ many pairwise incomparable $\omega_1$-like models of ZFC, meaning that there is no embedding between any two distinct models in $\mathcal C$.

2. The models in statement (1) can be constructed so that their ordinals order-embed into each other and indeed, so that the ordinals of each model is a universal $\omega_1$-like linear order. If ZFC has an $\omega$-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.

3. If $\diamondsuit$ holds and ZFC is consistent, then there is an $\omega_1$-like model $M\models\text{ZFC}$ and an $\omega_1$-like model $N\models\text{PA}$ such that $M$ does not embed into $\langle\text{HF},{\in}\rangle^N$.

4. If there is a Mahlo cardinal, then in a forcing extension of $L$, there is a transitive $\omega_1$-like model $M\models\text{ZFC}$ that does not embed into its own constructible universe $L^M$.

Note that the size of the family $\mathcal C$ in statement (1) is as large as it could possibly be, given that any two elements in a pairwise incomparable family of structures must be non-isomorphic and there are at most $2^{\omega_1}$ many isomorphism types of $\omega_1$-like models of set theory or indeed of structures of size $\omega_1$ in any first-order finite language. Statement (2) shows that the models of the family $\mathcal C$ serve as $\omega_1$-like counterexamples to the assertion that one model of set theory embeds into another whenever the ordinals of the first order-embed into the ordinals of the second.

The global choice principle in Gödel-Bernays set theory

$\newcommand\Ord{\text{Ord}}
\newcommand\R{\mathbb{R}}
\newcommand\HOD{\text{HOD}}$

I’d like to follow up on several posts I made recently on MathOverflow (see here, here and here), which engaged several questions of Gérard Lang that I found interesting. Specifically, I’d like to discuss a number of equivalent formulations of the global choice principle in Gödel-Bernays set theory. Let us adopt the following abbreviations for the usually considered theories:

  • GB is the usual Gödel-Bernays set theory without any choice principle.
  • GB+AC is GB plus the axiom of choice for sets.
  • GBC is GB plus the global choice principle.

The global choice principle has a number of equivalent characterizations, as proved in the theorem below, but for definiteness let us take it as the assertion that there is a global choice function, that is, a class $F$ which is a function such that $F(x)\in x$ for every nonempty set $x$.

Note in particular that I do not use the set version of choice AC in the equivalences, since most of the statements imply AC for sets outright (except in the case of statement 7, where it is stated specifically in order to make the equivalence).

Theorem. The following are equivalent over GB.

  1. The global choice principle. That is, there is a class function $F$ such that $F(x)\in x$ for every nonempty set $x$.
  2. There is a bijection between $V$ and $\Ord$.
  3. There is a global well-ordering of $V$. That is, there is a class relation $\triangleleft$ on $V$ that is a linear order, such that every nonempty set has a $\triangleleft$-least member.
  4. There is a global set-like well-ordering of $V$. There is a class well-ordering $\triangleleft$ as above, such that all $\triangleleft$-initial segments are sets.
  5. Every proper class is bijective with $\Ord$.
  6. Every class injects into $\Ord$.
  7. AC holds for sets and $\Ord$ injects into every proper class.
  8. $\Ord$ surjects onto every class.
  9. Every class is comparable with $\Ord$ by injectivity; that is, one injects into the other.
  10. Any two classes are comparable by injectivity.

Proof. 

($1\to 2$) Assume that $F$ is a global choice class function. Using the axiom of replacement, we may recursively define a class sequence of sets $\langle x_\alpha\mid\alpha\in\Ord\rangle$, where $x_\alpha=F(X_\alpha)$, where $X_\alpha$ is the set of minimal-rank sets $x$ not among $\{x_\beta\mid\beta<\alpha\}$. That is, we use $F$ to choose the next element among the minimal-rank sets not yet chosen. Thus, we have an injection of $V$ into $\Ord$. If a set $x$ does not appear as some $x_\alpha$ on this sequence, then no set of that rank or higher can appear, since we always add sets of the minimal rank not yet having appeared; thus, in this case we will have injected $\Ord$ into some $V_\beta$. But this is impossible by Hartog’s theorem, and so in fact we have bijection between $\Ord$ and $V$.

($2\to 3$) If there is a bijection between $\Ord$ and $V$, then we may define a global well-ordering by $x<y$ if $x$ appears before $y$ in that enumeration.

($3\to 1$) Let $F(x)$ be the least element of $x$ with respect to a fixed global well-ordering.

($3\to 4$) If there is a global well-ordering $<$, then we may refine it to a set-like well-ordering, by defining $x\triangleleft y$ just in case the rank of $x$ is less than the rank of $y$, or they have the same rank and $x<y$. This relation is still a well-order, since the least member of any nonempty set $X$ will be the $\triangleleft$-least member of the set of members of $X$ having minimal rank. The relation $\triangleleft$ is set-like, because the $\triangleleft$-predecessors of any set $x$ are amongst the sets having rank no larger than $x$, and this is a set.

($4\to 5$) If there is a global set-like well-ordering $<$ of $V$ and $X$ is a proper class, then $<$ on $X$ is a well-ordering of $X$, and we may map any ordinal $\alpha$ to the $\alpha^{th}$ member of $X$. This will be a bijection of $\Ord$ with $X$.

($5\to 6$) If every proper class is bijective with $\Ord$, then $V$ is bijective with $\Ord$, and so every set injects into $\Ord$ by restriction.

($6\to 7$) If every class injects into $\Ord$, then in particular, $V$ injects into $\Ord$. The image of this injection is a proper class subclass of $\Ord$, and all such classes are bijective with $\Ord$ by mapping $\alpha$ to the $\alpha^{th}$ member of the class, and so every proper class is bijective with $\Ord$. So $\Ord$ injects the other way, and also AC holds.

($7\to 3$) Suppose that AC holds and $\Ord$ injects into every proper class. Let $W$ be the class of all well-orderings of some rank-initial segment $V_\alpha$ of the set-theoretic universe $V$. Since for each $\alpha$ there are only a set number of such well-orderings of $V_\alpha$, if we inject $\Ord$ into $W$, then there must be well-orderings of unboundedly many $V_\alpha$ in the range of the injection. From this, we may easily construct a global well-ordering of $V$, by defining $x<y$ just in case $x$ has lower rank than $y$, or they have the same rank and $x<y$ in the first well-ordering of a sufficiently large $V_\alpha$ to appear in the range of the injection.

($5\to 8$) Immediate.

($8\to 3$) If $\Ord$ surjects onto $V$, then there is a global well-ordering, defined by $x<y$ if the earliest appearance of $x$ in the surjection is earlier than that of $y$.

($6\to 9$) Immediate.

($9\to 3$) Assume every class is comparable with $\Ord$ via injectivity. It follows that AC holds for sets, since $\Ord$ cannot inject into a set, and if a set injects into $\Ord$ then it is well-orderable. Now, if $\Ord$ injects into the class $W$ used above, consisting of all well-orderings of a $V_\alpha$, then we saw before that we can build a well-ordering of $V$. And if $W$ injects into $\Ord$, then $W$ is well-orderable and we can also in this case build a well-ordering of $V$.

($5\to 10$) If $V$ is bijective with $\Ord$, then every class is bijective with $\Ord$ or with an ordinal, and these are comparable by injections. So any two classes are comparable by injections.

($10\to 9$) Immediate.

QED

Let’s notice a few things.

First, we cannot omit the AC assertion in statement 7. To see this, consider the model $V=L(\R)$, in a case where it does not satisfy AC. I claim that in this model, $\Ord$ injects into every proper class that is definable from parameters. The reason is that every object in $L(\R)$ is definable from ordinal and real parameters, and indeed, definable in some $V_\alpha^{L(\R)}$ by some real and ordinal parameters. Indeed, one needs only one ordinal and real parameter. If $W$ is any proper class, then there
must be a proper subclass $W_0\subset W$ whose elements are all defined by the same definition in this way. And by partitioning further, we may find a single real that works with various ordinal parameters using that definition to define a proper class of
elements of $W$. Thus, we may inject $\Ord$ into $W$, even though AC fails in $L(\R)$.

Second, the surjectivity analogues of a few of the statements are not equivalent to global choice. Indeed, ZF proves that every proper class surjects onto $\Ord$, with no choice at all, since if $W$ is a proper class, then there are unboundedly many ordinals
arising as the rank of an element of $W$, and so we may map each element $x\in W$ to $\alpha$, if the rank of $x$ is the $\alpha^{th}$ ordinal that is the rank of any element of $W$.

An introduction to the theory of infinite games, with examples from infinite chess, University of Connecticut, December 2014


This will be a talk for the interdisciplinary Group in Philosophical and Mathematical Logic at the University of Connecticut in Storrs, on December 5, 2014.

Value omega cubedAbstract. I shall give a general introduction to the theory of infinite games, with a focus on the theory of transfinite ordinal game values. These ordinal game values can be used to show that every open game — a game that, when won for a particular player, is won after finitely many moves — has a winning strategy for one of the players. By means of various example games, I hope to convey the extremely concrete game-theoretic meaning of these game values for various particular small infinite ordinals. Some of the examples will be drawn from infinite chess, which is chess played on a chessboard stretching infinitely without boundary in every direction, and the talk will include animations of infinite chess positions having large numbers of pieces (or infinitely many) with hundreds of pieces making coordinated attacks on the chessboard. Meanwhile, the exact value of the omega one of chess, denoted $\omega_1^{\mathfrak{Ch}_{\!\!\!\!\sim}}$, is not currently known.

Slides | Transfinite game values in infinite chess | The mate-in-n problem of infinite chess is decidable