CUNY Graduate Center
Virtual
Organized by Athar Abdul-Quader and Roman Kossak
Spring 2023
May 9
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Mateusz Łełyk
University of Warsaw
Pathologies in Satisfaction Classes: part II
Abstract
This is the second part of the talk given by Athar Abdul-Quader (Pathologically definable subsets of models of CT-), however we will make sure to make it self-contained.
The talk is centered around the following problem: when a subset of a countable and recursively saturated model M can be characterized as the set of the lengths of disjunctions on which a satisfaction class behaves correctly? More precisely: let DC(x) denote a sentence in a language of PA with a fresh binary predicate S which says 'For every disjunction d with at most x disjuncts and every assignment a, S(d,a) iff there is a disjunct d' in d such that S(d',a).' We say that X is a DC-set in (M,S) iff X is precisely the set of those numbers a such that (M,S) satisfies DC(a). We ask: given a countable and recursively saturated model M for which subsets X of M we can find a satisfaction class S such that X is a DC-set in (M,S)?
In the talk we study this problem for idempotent disjunctions, that is: disjunctions which repeat the same sentence. Let IDC(x) be DC(x) restricted to such 'idempotent' disjunctions of length x. The following is one of our core results:
Theorem: For an arbitrary countable and recursively saturated model M of PA the following conditions are equivalent:
(a) M is arithmetically saturated
(b) For every cut I in M there is a satisfaction class S such that I is an IDC-set in (M,S).
We study how this result generalizes to other propositional constructions in the place of disjunctions. The talk is based on a joint work with Athar Abdul-Quader presented in this paper from arxiv: arXiv:2303.18069v1 [math.LO] 31 Mar 2023.
Video
April 25
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Mateusz Łełyk
University of Warsaw
Pathologies in Satisfaction Classes
Abstract
This is the second part of the talk given by Athar Abdul-Quader (Pathologically definable subsets of models of CT-), however we will make sure to make it self-contained.
The talk is centered around the following problem: when a subset of a countable and recursively saturated model M can be characterized as the set of the lengths of disjunctions on which a satisfaction class behaves correctly? More precisely: let DC(x) denote a sentence in a language of PA with a fresh binary predicate S which says 'For every disjunction d with at most x disjuncts and every assignment a, S(d,a) iff there is a disjunct d' in d such that S(d',a).' We say that X is a DC-set in (M,S) iff X is precisely the set of those numbers a such that (M,S) satisfies DC(a). We ask: given a countable and recursively saturated model M for which subsets X of M we can find a satisfaction class S such that X is a DC-set in (M,S)?
In the talk we study this problem for idempotent disjunctions, that is: disjunctions which repeat the same sentence. Let IDC(x) be DC(x) restricted to such 'idempotent' disjunctions of length x. The following is one of our core results:
Theorem: For an arbitrary countable and recursively saturated model M of PA the following conditions are equivalent:
(a) M is arithmetically saturated
(b) For every cut I in M there is a satisfaction class S such that I is an IDC-set in (M,S).
We study how this result generalizes to other propositional constructions in the place of disjunctions. The talk is based on a joint work with Athar Abdul-Quader presented in this paper from arxiv: arXiv:2303.18069v1 [math.LO] 31 Mar 2023.
Video
April 18
1:30pm NY time
Virtual (email Victoria Gitman for meeting id)
Katarzyna W. Kowalik
University of Warsaw
The chain-antichain principle and proof size
Abstract
The chain-antichain principle $\mathsf{CAC}$ is a well-known consequence of Ramsey's theorem for pairs and two colours $\mathsf{RT}^2_2$. It says that for every partial order on $\mathbb{N}$ there exists an infinite chain or antichain with respect to this order. Both of these principles are $\Pi^0_3$-conservative over the weak base theory $\mathsf{RCA}^*_0$. Such conservation results usually prompt to ask about lengths of proofs. Kołodziejczyk, Wong and Yokoyama proved that $\mathsf{RT}^2_2$ has a non-elementary speedup over $\mathsf{RCA}^*_0$ for proofs of $\Sigma_1$ sentences. We show that the behaviour of $\mathsf{CAC}$ is the opposite: it can be polynomially simulated by $\mathsf{RCA}^*_0$ with respect to $\Pi^0_3$ sentences. Our argument uses a technique of forcing interpretation developed by Avigad. In the first step we syntactically simulate a construction of a generic computable ultrapower of a model of $\mathsf{RCA}^*_0$. Then we find a generic cut satisfying $\mathsf{CAC}$ inside the ultrapower.
Video
March 21
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Bartosz Wcisło
University of Gdańsk
Satisfaction classes with the full collection scheme: Part II
Abstract
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.
Video
March 14
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Bartosz Wcisło
University of Gdańsk
Satisfaction classes with the full collection scheme
Abstract
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.
Video
March 7
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Bellaouar Djamel
University 08 Mai 1945 Guelma
Some generalizations on the representation of unlimited natural numbers
Abstract
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 $W_1$ and $W_2$ with integer entries, that is, $A = S + W_1 \cdot W_2$. 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.
Video
February 28
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Zuzana Hanikova
Czech Academy of Sciences
Vopěnka's Alternative Set Theory and its mathematical context
Abstract
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.
Slides
Video
February 21
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Alexei Miasnikov
Stevens Institute of Technology
First-order classification and non-standard models
Abstract
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.
Video
February 14
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Vladimir Kanovei
Institute for Information Transmission Problems
On the significance of parameters in the choice and сomprehension schemata in the 2nd-order Peano arithmetic
Abstract
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
[...] if one is convinced of the significance of something like a given axiom schema, it is natural to study details, such as the effect of parameters.
This talk is devoted to the effect of parameters in the schemata of Comprehension and Choice in second-order arithmetic.
Video
February 7
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Mikhail Katz
Bar Ilan University
Effective infinitesimals in R
Abstract
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.
Video
January 31
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Lorenzo Galeotti
Amsterdam University College
Order types of models of arithmetic without induction
Abstract
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?
Friedman’s question is very complex and still wide open. In this talk we will go in the opposite direction and consider a version of Friedman’s question for syntactic fragments of PA. We will present results from a joint work with Benedikt Löwe on order types of non-standard models of syntactic subsystems of arithmetic obtained by restricting the language to subsets of the operations. We will put particular emphasis on models of syntactic subsystems of Peano Arithmetic obtained by dropping the schema of induction.
Video
January 24
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Karel Hrbacek
CUNY
Representation of unlimited integers
Abstract
Nonstandard methods have been successfully applied to standard problems in number theory by R. Jin, T. Tao and others. A. Boudaoud and D. Bellaouar are pursuing the opposite direction: they are formulating number-theoretic problems in the language of nonstandard analysis and solving them by standard methods. Two examples of the kind of questions they consider are:
(1) Can every unlimited natural number n be represented in the form n = s + w_1w_2 where s is a limited integer and w_1, w_2 are unlimited?
(2) Can every unlimited natural number n be represented in the form n = w_1w_2 + w_3w_4 so that each ratio w_i / w_j is appreciable (ie, neither infinitesimal nor unlimited)?
I give a negative answer to question (1) (assuming Dickson’s Conjecture) and a positive answer to question (2).
A. Boudaoud, D. Bellaouar, Representation of integers: A nonclassical point of view, Journal of Logic & Analysis. 12:4 (2020) 1{31; K. Hrbacek, Journal of Logic & Analysis 12:5 (2020) 1–6.
Video
January 10
1:00pm NY time
Virtual (email Victoria Gitman for meeting id)
Arseniy Sheydvasser
Technion
Are higher-rank arithmetic groups uniformly bi-interpretable with arithmetic?
Abstract
Given a model M of an axiomatic theory A, and a model N of an axiomatic theory B, we say that they are bi-interpretable if, roughly speaking, they have the same definable sets: that is, there are definable maps that move definable sets in one to definable sets in the other. One interesting question we might ask, given an axiomatic theory A, is which of its models are bi-interpretable with the integers (seen as a model of the first-order theory of rings)? As self-interpretations of the integers are particularly simple, this gives a lot of information about properties of the model. In this talk, we will consider arithmetic groups like SL(n, Z) and discuss recent progress in understanding when such groups are bi-interpretable with arithmetic and what consequences this has when it occurs.
Video