Set Theory Talks

Melvin Fitting (CUNY)
Title: On Kripke’s proof of Kripke completeness

Abstract: Saul Kripke announced his possible world semantics in 1959, and `published his proof of axiomatic completeness for the standard modal logics of the time in 1963.  It is very unlike the standard completeness proof used today, which involves a Lindenbaum/Henkin construction and produces canonical models.  Kripke’s proof involved tableaus, in a format that is difficult to follow, and uses tableau construction algorithms that are complex and somewhat error prone to describe. I will first discuss Kripke’s proof, then the historical origins of the modern version.  Then I will show that completeness, proved Kripke style, could actually have been done in the Lindenbaum/Henkin way, thus simplifying things considerably.  None of this is new but, with the parts collected together it is an interesting story. “In my end is my beginning”.

Bartosz Wcisło, University of Gdańsk
Satisfaction classes with the full collection scheme

Satisfaction classes are subsets of models of Peano arithmetic which satisfy Tarski's compositional clauses. Alternatively, we can view satisfaction or truth classes as the extension of a fresh predicate T(x) (the theory in which compositional clauses are viewed as axioms is called CT^-).

It is easy to see that CT^- extended with a full induction scheme is not conservative over PA, since it can prove, for instance, the uniform reflection over arithmetic. By a nontrivial argument of Kotlarski, Krajewski, and Lachlan, the sole compositional axioms of CT^- in fact form a conservative extension of PA. Moreover, in order to obtain non-conservativity it is enough to add induction axioms for the Delta_0 formulae containing the truth predicate.

Answering a question of Kaye, we will show that the theory of compositional truth, CT^- with the full collection scheme is a conservative extension of Peano Arithmetic. Following the initial suggestion of Kaye, we will in fact show that any countable recursively saturated model M of PA has an elementary omega_1-like end extension M' such that M' carries a full satisfaction class.

Title: Lewis on accommodation and representation de re

Abstract: Recall Lumpl, the lump of clay out of which the statue Goliath is fashioned. While (1) ‘Lumpl could have survived a squashing’ is true, (2) ‘Goliath could have survived a squashing’ is false, it being after all essential to Goliath, but not to Lumpl, that it be a statue. We have here an example of what David Lewis (1986) called “the inconstancy of representation de re”. For Lewis, the inconstancy does not amount to inconsistency, but rather points to the context-sensitivity of de re modal predication: (1) and (2) make implicit, context-sensitive reference to different counterpart relations. Once we recognize this, Lewisians argue, it becomes clear how our intuitive truth-conditional judgments are fully consistent. As I show, however, the conversational rule that triggers the implicit reference not only fails to license the reference shift, it effectively prohibits it. The upshot is that counterpart theory is deprived of a central motivation.

Bellaouar Djamel, University 08 Mai 1945 Guelma
Some generalizations on the representation of unlimited natural numbers

Based on permanence principles of nonstandard analysis and as a continuation of the papers [1-3], we present some notes and questions on the representation of unlimited natural numbers. As a natural generalization, let A be an unlimited m by n matrix with integer entries (i.e one of its integer entries is unlimited). Here we prove that every unlimited matrix A with integer entries can be written as the sum of a limited matrix S with integer entries and the product of two unlimited matrices W1 and W2 with integer entries, that is, A=S+W1⋅W2. For further research, we propose several matrix representation forms.

Finally, we consider the numbers of the form z=a+bi where a,b are integers, which are called Gaussian integers. In the case when a or b is unlimited, the number z=a+bi is said to be unlimited. Also, some notes on the representation of unlimited Gaussian integers are given.

[1] A. Boudaoud, La conjecture de Dickson et classes particulière d'entiers, Ann. Math. Blaise Pascal. 13 (2006), 103-109.
[2] A. Boudaoud and D. Bellaouar, Representation of integers: A nonclassical point of view, J. Log. Anal. 12:4 (2020) 1-31.
[3] K. Hrbacek, On Factoring of unlimited integers, J. Log. Anal. 12:5 (2020) 1-6.

Melvin Fitting (CUNY)
Title: On Kripke’s proof of Kripke completeness

Abstract: Saul Kripke announced his possible world semantics in 1959, and `published his proof of axiomatic completeness for the standard modal logics of the time in 1963.  It is very unlike the standard completeness proof used today, which involves a Lindenbaum/Henkin construction and produces canonical models.  Kripke’s proof involved tableaus, in a format that is difficult to follow, and uses tableau construction algorithms that are complex and somewhat error prone to describe. I will first discuss Kripke’s proof, then the historical origins of the modern version.  Then I will show that completeness, proved Kripke style, could actually have been done in the Lindenbaum/Henkin way, thus simplifying things considerably.  None of this is new but, with the parts collected together it is an interesting story. “In my end is my beginning”.

Title: Lewis on accommodation and representation de re

Abstract: Recall Lumpl, the lump of clay out of which the statue Goliath is fashioned. While (1) ‘Lumpl could have survived a squashing’ is true, (2) ‘Goliath could have survived a squashing’ is false, it being after all essential to Goliath, but not to Lumpl, that it be a statue. We have here an example of what David Lewis (1986) called “the inconstancy of representation de re”. For Lewis, the inconstancy does not amount to inconsistency, but rather points to the context-sensitivity of de re modal predication: (1) and (2) make implicit, context-sensitive reference to different counterpart relations. Once we recognize this, Lewisians argue, it becomes clear how our intuitive truth-conditional judgments are fully consistent. As I show, however, the conversational rule that triggers the implicit reference not only fails to license the reference shift, it effectively prohibits it. The upshot is that counterpart theory is deprived of a central motivation.

Bellaouar Djamel, University 08 Mai 1945 Guelma
Some generalizations on the representation of unlimited natural numbers

Based on permanence principles of nonstandard analysis and as a continuation of the papers [1-3], we present some notes and questions on the representation of unlimited natural numbers. As a natural generalization, let A be an unlimited m by n matrix with integer entries (i.e one of its integer entries is unlimited). Here we prove that every unlimited matrix A with integer entries can be written as the sum of a limited matrix S with integer entries and the product of two unlimited matrices W1 and W2 with integer entries, that is, A=S+W1⋅W2. For further research, we propose several matrix representation forms.

Finally, we consider the numbers of the form z=a+bi where a,b are integers, which are called Gaussian integers. In the case when a or b is unlimited, the number z=a+bi is said to be unlimited. Also, some notes on the representation of unlimited Gaussian integers are given.

[1] A. Boudaoud, La conjecture de Dickson et classes particulière d'entiers, Ann. Math. Blaise Pascal. 13 (2006), 103-109.
[2] A. Boudaoud and D. Bellaouar, Representation of integers: A nonclassical point of view, J. Log. Anal. 12:4 (2020) 1-31.
[3] K. Hrbacek, On Factoring of unlimited integers, J. Log. Anal. 12:5 (2020) 1-6.

Melvin Fitting (CUNY)
Title: On Kripke’s proof of Kripke completeness

Abstract: Saul Kripke announced his possible world semantics in 1959, and `published his proof of axiomatic completeness for the standard modal logics of the time in 1963.  It is very unlike the standard completeness proof used today, which involves a Lindenbaum/Henkin construction and produces canonical models.  Kripke’s proof involved tableaus, in a format that is difficult to follow, and uses tableau construction algorithms that are complex and somewhat error prone to describe. I will first discuss Kripke’s proof, then the historical origins of the modern version.  Then I will show that completeness, proved Kripke style, could actually have been done in the Lindenbaum/Henkin way, thus simplifying things considerably.  None of this is new but, with the parts collected together it is an interesting story. “In my end is my beginning”.

Zuzana Hanikova, Czech Academy of Sciences
Vopěnka's Alternative Set Theory and its mathematical context

Vopěnka first presented his Alternative Set Theory (AST) in the monograph 'Mathematics in the Alternative Set Theory' published by Teubner, Leipzig in 1979. Another book presenting the theory, 'Introduction to Mathematics in the Alternative Set Theory', was published in 1989 in Slovak by Alfa, Bratislava. In addition there are numerous journal papers on the AST by members of the research group established by Vopěnka, and the proceedings of a conference dedicated to the AST, also from 1989. In several essays, Vopěnka sought to lay out the motivation and philosophical import of the AST and some of his subsequent work. As one consequence of the emphasis on his philosophy, the mathematical inspiration for the AST has been somewhat obliterated. The aim of the talk is to discuss the design choices Vopěnka made for the AST in relation to pertinent mathematical developments of the 20th century, such as Skolem's work on nonstandard models of arithmetic, Robinson's nonstandard analysis, Rieger's nonstandard models of arithmetic, Vopěnka's nonstandard model of set theory, Vopěnka and Hájek's theory of semisets, or Parikh's almost consistent theories. The presentation will include an outline of the AST following the works of Vopěnka and Sochor. This is a historical talk; no new mathematical results on the AST will be presented.

Title: Lewis on accommodation and representation de re

Abstract: Recall Lumpl, the lump of clay out of which the statue Goliath is fashioned. While (1) ‘Lumpl could have survived a squashing’ is true, (2) ‘Goliath could have survived a squashing’ is false, it being after all essential to Goliath, but not to Lumpl, that it be a statue. We have here an example of what David Lewis (1986) called “the inconstancy of representation de re”. For Lewis, the inconstancy does not amount to inconsistency, but rather points to the context-sensitivity of de re modal predication: (1) and (2) make implicit, context-sensitive reference to different counterpart relations. Once we recognize this, Lewisians argue, it becomes clear how our intuitive truth-conditional judgments are fully consistent. As I show, however, the conversational rule that triggers the implicit reference not only fails to license the reference shift, it effectively prohibits it. The upshot is that counterpart theory is deprived of a central motivation.

Bellaouar Djamel, University 08 Mai 1945 Guelma
Some generalizations on the representation of unlimited natural numbers

Based on permanence principles of nonstandard analysis and as a continuation of the papers [1-3], we present some notes and questions on the representation of unlimited natural numbers. As a natural generalization, let A be an unlimited m by n matrix with integer entries (i.e one of its integer entries is unlimited). Here we prove that every unlimited matrix A with integer entries can be written as the sum of a limited matrix S with integer entries and the product of two unlimited matrices W1 and W2 with integer entries, that is, A=S+W1⋅W2. For further research, we propose several matrix representation forms.

Finally, we consider the numbers of the form z=a+bi where a,b are integers, which are called Gaussian integers. In the case when a or b is unlimited, the number z=a+bi is said to be unlimited. Also, some notes on the representation of unlimited Gaussian integers are given.

[1] A. Boudaoud, La conjecture de Dickson et classes particulière d'entiers, Ann. Math. Blaise Pascal. 13 (2006), 103-109.
[2] A. Boudaoud and D. Bellaouar, Representation of integers: A nonclassical point of view, J. Log. Anal. 12:4 (2020) 1-31.
[3] K. Hrbacek, On Factoring of unlimited integers, J. Log. Anal. 12:5 (2020) 1-6.

Vladimir Kanovei, Institute for Information Transmission Problems
On the significance of parameters in the choice and сomprehension schemata in the 2nd-order Peano arithmetic

Parameters are free variables in various axiom schemata in PA, ZFC, and other similar theories. Given an axiom schema S, we let S* be the parameter-free sub-schema.

Kreisel (A survey of proof theory, JSL 1968) was one of those who paid attention to the comparison of some schemata in second-order PA and their parameter-free versions. In particular, Kreisel noted that

This talk is devoted to the effect of parameters in the schemata of Comprehension and Choice in second-order arithmetic.

Russell Miller, CUNY
Computability and the Absolute Galois Group of Q

Fix a computable presentation ¯¯¯¯Q of the algebraic closure of the rational numbers. The absolute Galois group of the rational numbers, which is precisely the automorphism group of the field ¯¯¯¯Q, may then be viewed as a collection of paths through a finite-branching tree. Each individual automorphism has a Turing degree. We will use known results in computability to try to build natural countable elementary subgroups of the absolute Galois group. Several intriguing questions in number theory will appear as we measure the extent to which we succeed in doing so.

Alexei Miasnikov, Stevens Institute of Technology
First-order classification and non-standard models

In this talk I will discuss some recent advances in the first-order classification problem. I will touch on first-order rigidity and quasi finite axiomatization. However, the main point of the presentation is on how, in principle, one can describe all structures which are first-order equivalent to a given one. This leads to non-standard models of algebraic structures (aka non-standard analysis or non-standard arithmetic), which are interesting in their own right.

When Gromov asked 'What is a typical group?', he was thinking of finitely presented groups, and he proposed an approach involving limiting density. Here, we reframe this question in the context of universal algebra and discuss some examples illustrating the behaviors of some of these algebraic varieties and then general conditions that imply some of these behaviors. Our primary general result states that for a commutative generalized bijective variety and presentations with a single generator and single identity, the zero-one law holds and, furthermore, that the sentences with density 1 are those true in the free structure. The proof of this result requires a specialized version of Gaifman's Locality Theorem that enables us to get a better bound on the complexity of the formulas of interest to us.

This work is joint with Meng-Che 'Turbo' Ho and Julia Knight.

Zuzana Hanikova, Czech Academy of Sciences
Vopěnka's Alternative Set Theory and its mathematical context

Vopěnka first presented his Alternative Set Theory (AST) in the monograph 'Mathematics in the Alternative Set Theory' published by Teubner, Leipzig in 1979. Another book presenting the theory, 'Introduction to Mathematics in the Alternative Set Theory', was published in 1989 in Slovak by Alfa, Bratislava. In addition there are numerous journal papers on the AST by members of the research group established by Vopěnka, and the proceedings of a conference dedicated to the AST, also from 1989. In several essays, Vopěnka sought to lay out the motivation and philosophical import of the AST and some of his subsequent work. As one consequence of the emphasis on his philosophy, the mathematical inspiration for the AST has been somewhat obliterated. The aim of the talk is to discuss the design choices Vopěnka made for the AST in relation to pertinent mathematical developments of the 20th century, such as Skolem's work on nonstandard models of arithmetic, Robinson's nonstandard analysis, Rieger's nonstandard models of arithmetic, Vopěnka's nonstandard model of set theory, Vopěnka and Hájek's theory of semisets, or Parikh's almost consistent theories. The presentation will include an outline of the AST following the works of Vopěnka and Sochor. This is a historical talk; no new mathematical results on the AST will be presented.

Vladimir Kanovei, Institute for Information Transmission Problems
On the significance of parameters in the choice and сomprehension schemata in the 2nd-order Peano arithmetic

Parameters are free variables in various axiom schemata in PA, ZFC, and other similar theories. Given an axiom schema S, we let S* be the parameter-free sub-schema.

Kreisel (A survey of proof theory, JSL 1968) was one of those who paid attention to the comparison of some schemata in second-order PA and their parameter-free versions. In particular, Kreisel noted that

This talk is devoted to the effect of parameters in the schemata of Comprehension and Choice in second-order arithmetic.

Russell Miller, CUNY
Computability and the Absolute Galois Group of Q

Fix a computable presentation ¯¯¯¯Q of the algebraic closure of the rational numbers. The absolute Galois group of the rational numbers, which is precisely the automorphism group of the field ¯¯¯¯Q, may then be viewed as a collection of paths through a finite-branching tree. Each individual automorphism has a Turing degree. We will use known results in computability to try to build natural countable elementary subgroups of the absolute Galois group. Several intriguing questions in number theory will appear as we measure the extent to which we succeed in doing so.

Alexei Miasnikov, Stevens Institute of Technology
First-order classification and non-standard models

In this talk I will discuss some recent advances in the first-order classification problem. I will touch on first-order rigidity and quasi finite axiomatization. However, the main point of the presentation is on how, in principle, one can describe all structures which are first-order equivalent to a given one. This leads to non-standard models of algebraic structures (aka non-standard analysis or non-standard arithmetic), which are interesting in their own right.

Mikhail Katz, Bar Ilan University
Effective infinitesimals in R

We survey the effective foundations for analysis with infinitesimals recently developed by Hrbacek and Katz, and detail some applications. Theories SPOT and SCOT illustrate the fact that analysis with infinitesimals requires no more choice than traditional analysis. The theory SCOT incorporates in particular all the axioms of Nelson's Radically Elementary Probability Theory, which is therefore conservative over ZF+ADC.

Strategy and determinacy in infinite Hex

The popular game of Hex can be extended to the infinite hexagonal lattice, defining a winning condition which formalises the idea of a chain of colored stones stretching towards infinity. The descriptive-set-theoretic complexity of the set of winning positions is unknown, although it is at most Σ^1_1, and it is conjectured to be Borel; this has implications on whether games of infinite Hex are determined from all initial positions as either first-player wins or draws.

I will show that, unlike the finite game, infinite Hex with an initially empty board is a draw. But is the game still a draw when starting from a non-empty board? This open question can be partially answered in the positive by assuming the existence of certain local strategies, and in the negative by giving the advantage of placing two stones at each turn to one of the players. This is joint work with Joel David Hamkins.

Athar Abdul-Quader, Purchase College
Satisfaction and saturation

It is well known that a countable model of PA has a truth predicate if and only if it is recursively saturated. It is also well known that not all countable recursively saturated models of PA have *inductive* or even Δ0-inductive truth predicates: indeed, such models must satisfy Con(PA), for example. Recent work by Enayat-Pakhomov and Cieśliński-Łełyk-Wcisło explored the principle of 'disjunctive correctness', asserting that every disjunction is true if and only if it has a true disjunct. In particular, one can show that every countable model of PA has a 'disjunctively trivial' elementary extension: that is, an elementary extension with a truth predicate in which all nonstandard length disjunctions are evaluated as true. In this talk, we will see that such 'disjunctively trivial' models are necessarily arithmetically saturated; indeed, we will see that a countable model of PA is arithmetically saturated if and only if it has a disjunctively trivial truth predicate. We will explore related pathologies in truth predicates, and classify the sets which can be defined using such pathologies. We find other surprising connections between arithmetic saturation and these questions of definability. This is joint work with Mateusz Łełyk, based heavily on unpublished work by Jim Schmerl.

Vladimir Kanovei, Institute for Information Transmission Problems
On the significance of parameters in the choice and сomprehension schemata in the 2nd-order Peano arithmetic

Parameters are free variables in various axiom schemata in PA, ZFC, and other similar theories. Given an axiom schema S, we let S* be the parameter-free sub-schema.

Kreisel (A survey of proof theory, JSL 1968) was one of those who paid attention to the comparison of some schemata in second-order PA and their parameter-free versions. In particular, Kreisel noted that

This talk is devoted to the effect of parameters in the schemata of Comprehension and Choice in second-order arithmetic.

Russell Miller, CUNY
Computability and the Absolute Galois Group of Q

Fix a computable presentation ¯¯¯¯Q of the algebraic closure of the rational numbers. The absolute Galois group of the rational numbers, which is precisely the automorphism group of the field ¯¯¯¯Q, may then be viewed as a collection of paths through a finite-branching tree. Each individual automorphism has a Turing degree. We will use known results in computability to try to build natural countable elementary subgroups of the absolute Galois group. Several intriguing questions in number theory will appear as we measure the extent to which we succeed in doing so.

Lorenzo Galeotti, Amsterdam University College
Order types of models of arithmetic without induction

It is a well-known fact that non-standard models of Peano Arithmetic (PA) have order type N + Z · D, where D is a dense linear order. The question of which dense linear orders D can occur in such order types is non-trivial and widely studied. In this context Friedman asked the following question:

Are there consistent extensions of Peano Arithmetic T and T′ such that the class of order types of models of T and the class of order types of models of T′ differ?

Marko Malink (NYU) and Anubav Vasudevan (University of Chicago).
Title: The origins of conditional logic: Theophrastus on hypothetical syllogisms

Abstract: Łukasiewicz maintained that “the first system of propositional logic was invented about half a century after Aristotle: it was the logic of the Stoics”. In this talk, we argue that the first system of propositional logic was, in fact, developed by Aristotle’s pupil Theophrastus. Theophrastus sought to establish the priority of categorical over propositional logic by reducing various modes of propositional reasoning to categorical form. To this end, he interpreted the conditional “If φ then ψ” as a categorical proposition “A holds of all B”, in which B corresponds to the antecedent φ, and A to the consequent ψ. Under this interpretation, Aristotle’s law of subalternation (A holds of all B, therefore A holds of some B) corresponds to a version of Boethius’ Thesis (If φ then ψ, therefore not: If φ then not-ψ). Jonathan Barnes has argued that this consequence renders Theophrastus’ program of reducing propositional to categorical logic inconsistent. In this paper, we show that Barnes’s objection is inconclusive. We argue that the system developed by Theophrastus is both non-trivial and consistent, and that the propositional logic generated by Theophrastus’ system is exactly the connexive variant of the first-degree fragment of intensional linear logic. 

Speaker:     Saeed Salehi, University of Tabriz.

Date and Time:     Wednesday November 23, 2022, Zoom Talk SPECIAL TIME 9:30AM-11:00AM.

Title:     Self-Reference and Diagonalization: their difference and a short history.

Abstract: What is now called the Diagonal (or the Self-Reference) Lemma, is the statement that for every formula F(x), with the only free variable x, there exists a sentence σ such that σ is equivalent to the F of the Gödel code of σ, i.e., σ ≡ F(#σ); and this equivalence is provable in certain weak arithmetics. This lemma is credited to Gödel (1931), in the special case when F is the unprovability predicate, and to Carnap (1934) in the more general case.

In this talk, we will argue that Gödel-Carnap's original Diagonal Lemma is not the modern formulation and was more similar to, but not exactly identical with, the Strong Diagonal (or Direct Self-Reference) Lemma. This lemma, so-called recently, says that for every formula F(x), in a sufficiently expressive language, there exists a sentence σ such that σ is equal to the F of the Gödel code of σ, i.e., σ = F(#σ); and this equality is provable in sufficiently strong theories. We will attempt at tracking down the first appearance of the modern formulation of the Diagonal Lemma in the equivalent form, also in the strong direct form of equality.

Dima Sinapova, Rutgers University
Prikry sequences and square properties at ℵω

It is well known that if an inaccessible cardinal κ is singularized to countable cofinality while preserving cardinals, then □κω holds in the outer model. Moreover, this remains true even when relaxing the cardinal preservation assumption a bit. In this talk we focus on when Prikry forcing adds weaker forms of square in a more general setting. We prove abstract theorems about when Prikry forcing with interleaved collapses to bring down the singularized cardinal to ℵω will add a weak square sequence. This can be viewed as a partial positive result to a question of Woodin about whether the failure of SCH at ℵω implies weak square.

Marko Malink (NYU) and Anubav Vasudevan (University of Chicago).
Title: The origins of conditional logic: Theophrastus on hypothetical syllogisms

Abstract: Łukasiewicz maintained that “the first system of propositional logic was invented about half a century after Aristotle: it was the logic of the Stoics”. In this talk, we argue that the first system of propositional logic was, in fact, developed by Aristotle’s pupil Theophrastus. Theophrastus sought to establish the priority of categorical over propositional logic by reducing various modes of propositional reasoning to categorical form. To this end, he interpreted the conditional “If φ then ψ” as a categorical proposition “A holds of all B”, in which B corresponds to the antecedent φ, and A to the consequent ψ. Under this interpretation, Aristotle’s law of subalternation (A holds of all B, therefore A holds of some B) corresponds to a version of Boethius’ Thesis (If φ then ψ, therefore not: If φ then not-ψ). Jonathan Barnes has argued that this consequence renders Theophrastus’ program of reducing propositional to categorical logic inconsistent. In this paper, we show that Barnes’s objection is inconclusive. We argue that the system developed by Theophrastus is both non-trivial and consistent, and that the propositional logic generated by Theophrastus’ system is exactly the connexive variant of the first-degree fragment of intensional linear logic. 

Speaker:     Saeed Salehi, University of Tabriz.

Date and Time:     Wednesday November 23, 2022, TIME TBA.

Title:     Self-Reference and Diagonalization: their difference and a short history.

Abstract: What is now called the Diagonal (or the Self-Reference) Lemma, is the statement that for every formula F(x), with the only free variable x, there exists a sentence σ such that σ is equivalent to the F of the Gödel code of σ, i.e., σ ≡ F(#σ); and this equivalence is provable in certain weak arithmetics. This lemma is credited to Gödel (1931), in the special case when F is the unprovability predicate, and to Carnap (1934) in the more general case.

In this talk, we will argue that Gödel-Carnap's original Diagonal Lemma is not the modern formulation and was more similar to, but not exactly identical with, the Strong Diagonal (or Direct Self-Reference) Lemma. This lemma, so-called recently, says that for every formula F(x), in a sufficiently expressive language, there exists a sentence σ such that σ is equal to the F of the Gödel code of σ, i.e., σ = F(#σ); and this equality is provable in sufficiently strong theories. We will attempt at tracking down the first appearance of the modern formulation of the Diagonal Lemma in the equivalent form, also in the strong direct form of equality.