$\omega$ $\aleph$ $\infty$
Mathematical Logic at Fudan

## Fudan Logic Seminar 2018

### April 6

Guozhen Shen 申国桢, Chinese Academy of Science

Time: 14:00 - 16:00. Location: HGW2403. Slides

#### On the Cardinality of Infinite Symmetric Groups in ZF

In ZFC, for all infinite sets $x$, the symmetric group on $x$ has the same cardinality of the power set of $x$. However, without AC, we cannot make any conclusion about the relationship between the two cardinalities for an arbitrary infinite set. In this talk, we shall show in ZF that for all sets $x$, the cardinality of $[x]^2$ is strictly less than that of the symmetric group on $x$; nevertheless, it is shown that it is consistent with ZF that there exists an infinite set $x$ such that the cardinality of the symmetric group on $x$ is strictly less than that of $[x]^3$

### April 25

Ruizhi Yang 杨睿之, Fudan University

Time: 14:00 - 16:00. Location: HGW2403.

#### Some natural reducets of models of set theory

Hamkins and Kikuchi (2016) have showed the set-theoretic mereology, namely, the theory of $(V, \subset)$ is decidable, hence cannot serve as a foundation of mathematics. We continue to look at other natural reducts of the models of set theory. We will show that the structure $(V,\bigcup)$, $(V,\bigcap)$, and even $(V,\bigcup, P)$ has a decidable theory, hence contains little information of a set theory structure, while $(V, \subset, \bigcap)$, $(V, \subset, \bigcup)$, and $(V, \bigcap, \bigcup)$ contains all the information to recover $(V, \in)$. We also find the structure of subset relation and power set operation $(V, \subset, P)$ is rigid, yet we do not know if $\in$ is definable in it or not. This is joint work with Joel David Hamkins.

### May 4

Zachiri McKenzie, University OF Michigan - Shanghai Jiao Tong University Joint Institute

Time: 14:00 - 16:00. Location: HGW2403. Slides

#### Automorphisms of Models of Set Theory

This talk will report on joint work that has been done in collaboration with Ali Enayat and Matt Kaufmann. Nontrivial automorphisms have revealed themselves as important devices in the study of models of arithmetic where they have been used, amongst other things, to find model-theoretic classifications of subsystems of $\mathrm{PA}$ and second order arithmetic. In the context of set theory, Jensen's consistency proof of the urelemented variant of Quine's New Foundations' Set Theory, $\mathrm{NFU}$, reveals that a model of this theory can be built from a model of a subsystem of $\mathrm{ZFC}$ that admits a nontrivial automorphism. In particular, if $\mathcal{M}$ is a model of set theory (a sufficiently strong subsystem of $\mathrm{ZFC}$) and $j$ is a nontrivial automorphism of $\mathcal{M}$ that yields a model of $\mathrm{NFU}$, then there is a connection between the largest initial segment of $\mathcal{M}$ that is pointwise fixed by $j$ and the canonical interpretation of well-founded set theory (s subsystem or extension of $\mathrm{ZFC}$) in the resulting model of $\mathrm{NFU}$. Let $\mathrm{MOST}$ be the subsystem of $\mathrm{ZFC}$ axiomatized by extensionality, pair, union, emptyset, powerset, infinity, set foundation, $\Sigma_1$-separation, $\Delta_0$-collection and the axiom of choice. If $\mathcal{M}$ is a model of $\mathrm{MOST}$ that is equipped with a non-trivial automorphism $j$, then let $\mathcal{I}_\mathrm{fix}(j)$ denote the submodel of $\mathcal{M}$ whose universe consists of points $m$ in $\mathcal{M}$ such that $j(x)=x$ for all $x$ in the transitive closure of $m$ (where the transitive closure of $m$ is computed in $\mathcal{M}$). In this talk I will discuss the class $\mathcal{C}$ of all structures in the form $\mathcal{I}_\mathrm{fix}(j)$ where $j$ is a nontrivial automorphism of a model $\mathcal{M}$ of $\mathrm{MOST}$ such that $j(n)=n$ for every $n$ that is a finite ordinal in the sense of $\mathcal{M}$. I will begin by showing that every structure in $\mathcal{C}$ is a model of the theory $\mathrm{MOST}+ \Delta_0^\mathcal{P}\textrm{-collection}$. I will then sketch an iterated ultrapower construction that yields a model-theoretic classification of the countable structures in $\mathcal{C}$. This classification can be used to show that the following conditions are sufficient for a countable structure $\mathcal{N}$ to be in $\mathcal{C}$:

1. $\mathcal{N}$ is a transitive model of $\mathrm{MOST}+\Delta_0^\mathcal{P}\textrm{-collection}$
2. $\mathcal{N}$ is a recursively saturated model of $\mathrm{MOST}+\Delta_0^\mathcal{P}\textrm{-collection}$
3. $\mathcal{N}$ is a model of $\mathrm{ZFC}$
I will conclude by discussing some open questions and, if time permits, discuss some applications and extensions of these results.

### May 18

Renling Jin 金人麟, College of Charleston

Time: 14:00 - 16:00. Location: HGW2403

#### Can nonstandard analysis produce new standard theorems?

The answer is yes. Nonstandard analysis which was created by A. Robinson in 1963 incorporates infinitely large numbers and infinitesimally small positive numbers consistently in our real number system. But the strength of nonstandard analysis in the research of standard mathematics has not seemed to be sufficiently appreciated by mathematical community. In the talk, we will introduce two parts of the work done by the speaker and his collaborators on the standard combinatorial number theory using nonstandard analysis. In each of these two parts new standard theorems that were proved by nonstandard methods will be presented. The audience are not assumed to have prior knowledge of nonstandard analysis.

### Jun 8

Yun Fan 范赟, Southeast University

Time: 14:00 - 16:00. Location: HGW2403.

#### A survey on the computable Lipschitz reducibility

Given two reals $\alpha, \beta$, recall that $\beta$ is $K$-reducible to $\alpha$, written as $\beta \leq_K \alpha$, if for all $n$, $K(\beta \upharpoonright_n) \leq K(\alpha\upharpoonright_n) + O(1)$. Similarly for $C$-complexity. However these loose (to mean any transitive and reflexive preorder on $2^{\omega}$) reducibilities are not real", both of them are the most basic measures of relative randomness based on the Kolmogorov complexity approach. Some stronger ` real" reducibilities, such as Solovay reducibility, computable Lipschitz reducibility, relative $K$-reducibility, were introduced to measure relative complexity, which imply $K$-reducibility (as well as $C$-reducibility). Computably Lipschitz (cl-) reduciblity is a Turing reducibilty, which use function on $x$ is bounded by $x + c$ for some constant $c$. In this talk, we make a survey on the properties of cl-degrees on c.e.sets and c.e. reals.