Delta Workshops on Logic aim to bring together logicians from Math, Philosophy, and CS.
Delta 13 will be held online on May 16 and 17 2020, due to the pandemic.
Day 1
Time: May 16, 2020 09:00 AM Beijing, Shanghai
Join Zoom Meeting
https://zoom.us/j/94155202359?pwd=Q0ZaRStBaGR4R0szVi81QjBlOTlEZz09
Meeting ID: 941 5520 2359
Password: 054754
Day 2
Time: May 17, 2020 09:00 AM Beijing, Shanghai
Join Zoom Meeting
https://zoom.us/j/92867771543?pwd=SUhjSDFvSklSVWhFV1hwa3UyaWY1UT09
Meeting ID: 928 6777 1543
Password: 567357
Invited speakers:
Eddy Keming Chen (UC San Diego, US)
Yifeng Ding (UC Berkeley, US)
Sicun Gao (UC San Diego, US)
Renlin Jin (College of Charleston, US)
Mingyang Li (Pennsylvania State University, US)
Tingxiang Zou (Hebrew University of Jerusalem, IL)
Schedule (Beijing time below):
Day 1 (16 May)
9:00-9:50 Renlin Jin: Szemeredi 定理证明的非标准化和简化.
Abstract: Szemeredi 定理是组合数论半个世纪来的热点之一。1975年Szemeredi 证明了由 Erdos-Turan 在 1936年提出一个猜想：一个有正稠度的自然数集一定含有长度为任意自然数 k 的等差数列。自那以来又出现基于历遍理论的证明和基于调和分析的证明，而这两种证明又成了各自领域中的重要研究方向。然而由于 Szemeredi 的最初的初等证明艰涩难懂，少有人去探索其潜能。2017年 Terence Tao 在 San Jose 的一个非标准分析工作坊中给了一系列讲座，介绍 Szemeredi 的原始思想，并指出非标准分析可能是最合适简化Szemeredi 原始思想的工具。他还提到自己试了非标准分析方法但未能实现本质上的简化，同时挑战听众能否证实他的直觉。基于Tao 的讲义，本人作了一些工作，完成了Szemeredi 定理在 k = 4 时的非标准证明，而对于任意长度 k 的证明也正在进行中。此证明的主要贡献是避免了使用矢量指标，和用简单归纳法替代了 Szemeredi 的汉诺塔式的归纳发，从而使得证明变得简单透明。
10:00-10:50 Yifeng Ding: The logic of comparative cardinality.
Abstract: For any field of sets, there is a natural binary relation on it: Rab if and only if the cardinality of a is at least as large as that of b. Just as the laws of intersection, union, and complementation of sets in a field of sets are captured by the laws of Boolean algebras, we ask what are the laws one must add when we also want to compare cardinalities of sets. Specifically, we consider the (quantifier-free) language of Boolean algebras with an extra binary predicate ``|s| is no smaller than |t|'' expressing that there is an injection from the set t to the set s.
Then the question of what laws to add becomes how to completely axiomatize the valid formulas in this language. Previously, axiomatizations of formulas that are valid only for finite sets or only for infinite sets are given, though usually interpreted not as comparing the cardinalities but as comparing probabilities or possibilities. We will bridge the divide here by showing that we can almost define finiteness and infiniteness in this language, and then treat sets differently according to which defining formulas they satisfy. Another feature of our system is that it avoids the complex finite cancellation axioms. Instead, we use de Finetti's axiom together with the so-called polarizability rule, which intuitively states that to prove a formula, we can always choose a set and assume that it is divided into two parts of the same cardinality.
Finally, we also consider the effect of allowing the addition of cardinals in the language. We show that there is an increase in expressivity, and a more perspicuous axiomatization can be obtained.
This is joint work with Matthew Harrison-Trainor and Wesley Holliday.
15:30-16:20 Tingxiang Zou: Pseudofinite counting dimensions
Abstract: In this talk we will discuss a family of dimensions based on counting. They are introduced by E. Hrushovski around 2010. These dimensions are important tools to study asymptotic behaviours of finite sets or finite substructures. They also connect model theory with other areas of mathematics, such as group theory and additive combinations. We will discuss some examples of these connections, such as the Larsen-Pink inequality and the Erdös-Hajnal conjecture. If time permitted, we will also talk about a family of ultraproducts of finite difference fields, of which one of the counting dimensions behaves well.
Day 2 (17 May)
9:00-9:50 Mingyang Li: Algorithmic Randomness and complexity for continuous measures
Abstract: Algorithmic randomness is the study of random objects through computability theoretic means. In contrast to the traditional approach via probability theory, one of its core features is the possibility to define and investigate individual random objects (e.g. a random binary sequence). We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a new notion of randomness tests parameterized by a natural number that generalizes Solovay tests. We use this new notion to prove the existence of NCR elements in certain Turing degrees. We also discuss some algorithmic complexity properties of NCR reals.
10:00-10:50 Eddy Keming Chen: Nomic Vagueness
If there are fundamental laws of nature, can they fail to be exact? In this talk, I consider the possibility that some fundamental laws are vague. I call this phenomenon 'nomic vagueness.' I propose to characterize nomic vagueness as the existence of (apparent) borderline lawful worlds. I also discuss the issue of higher-order nomic vagueness. The existence of nomic vagueness would likely present a challenge to the mathematical expressibility of fundamental laws and add new wrinkles to the debate of Humeanism vs. anti-Humeanism. For a case study, we turn to the Past Hypothesis, a postulate that aims to explain the direction of time. We have reasons to take it seriously as a candidate fundamental law of nature. Yet it is vague as it admits borderline (nomologically) possible worlds. An exact version would lead to untraceable arbitrariness absent in any other fundamental laws. However, the dilemma between vagueness and untraceability is dissolved in a new quantum theory of time's arrow.
11:00-11:50 Sicun Gao: Polynomial Hierarchy in the Real World
Abstract: I will discuss some work along the following lines. 1. Understand the computational complexity of controlling nonlinear and hybrid physical systems. Such problems are commonly considered to be wildly undecidable because of the involvement of nonlinear real functions, differential equations, and so on. I show how reasonable upper bounds can be obtained through a new formulation that suits practical needs. 2. Enhance automation in the design and implementation of control systems through automated reasoning. These engines are designed to cope with NP-hard problems, matching the complexity of the problems to be solved. The key is to engineer exponential algorithms that perform well in practice by combining the full power of combinatorial, numerical, and statistical methods. 3. Certify reliability of control systems through formal proofs. All algorithms that are used for the design and analysis of these systems should produce mathematical proofs that are machine-checkable. Making good progress in these directions is crucial for building computing systems that can physically engage us in safety-critical ways.
Organizers:
§ Shichang Song (BJTU)
§ Yanjing Wang (Peking University)
§ Liang Yu (Nanjing University)