San Francisco, USA, April 8–11, 2020

The 2020 Winter Meeting of the Association for Symbolic Logic was to be held on April 8–11, 2020 at the Westin St. Francis on Union Square, San Francisco, in conjunction with the 2020 Pacific Division Meeting of the American Philosophical Association. Due to the global pandemic, the Pacific Division Meeting was cancelled.

The members of the Program Committee were Gillian Russell, Gil Sagi (chair), and Sean Walsh. The program was to include six invited speakers, listed below with their titles. These speakers were invited to give their talks at the 2021 ASL Winter Meeting instead and their abstracts will be included with the published meeting program for the 2021 Winter Meeting of the ASL. Following the list of invited speakers are the abstracts of the contributed talks by ASL members.

Andrew Bacon (University of Southern California), Substructural type theories and the metaphysics of propositions.

Eleonora Cresto (National Council for Scientific and Technical Research (CONICET)/IIF-SADAF, Argentina), The logic of reflective altruism.

Rohan French (University of California, Davis), Non-classical metatheory.

Melissa Fusco (Columbia University), A deontic logic for two-dimensional semantics.

Hanti Lin (University of California, Davis), Despite our death in the long run in inductive logic and data science.

Sanford Shieh (Wesleyan University), Form-series, predicativity & induction in Wittgenstein’s Tractatus.

For the Program Committee

Gil Sagi

Abstracts of contributed talks

▸ KATALIN BIMBÓ, Reverse computation in push-down automata,

Department of Philosophy, University of Alberta, 2–40 Assiniboia Hall, Edmonton, AB T6G 2E7, Canada.

E-mail: bimbo@ualberta.ca

URL: www.ualberta.ca/∼bimbo

Proofs in various logical systems can be linked to steps in one or another model of computation. Deterministic and non-deterministic push-down automata are models of computation in a restricted sense. In this talk, I will consider what reverse computation can mean in these machines, what sorts of machines can model the reverse computation, and what the result of the reverse computation is.

▸ MICHAŁ TOMASZ GODZISZEWSKI, Learnability, measurability, and applications of set theoretic independence in machine learning.

University of Warsaw, Poland and Munich Center for Mathematical Philosophy, LMU Munich, Germany.

E-mail: mtgodziszewski@gmail.com

In a recent paper Learnability can be undecidable by S. Ben-David et al. published in Nature Machine Intelligence the authors argue that certain abstract learnability questions are undecidable by ZFC axioms. The general learning problem considered there is to find a way of choosing a finite set that maximizes a particular expected value (within a certain range of error) with an obstacle that the probability distribution is unknown, or more formally: given a family of functions $\mathcal {F}$ from some fixed domain X to the real numbers and an unknown probability distribution $\mu $ over X, find, based on a finite sample generated by $\mu $ , a function in $\mathcal {F}$ whose expectation with respect to $\mu $ is $($ close to $)$ maximal.

The authors then provide a translation from this statistical framework to infinite combinatorics: namely, they prove that existence of certain learning functions corresponding to the problem above (the so-called estimating the maximum learners, or EMX-learners) translates into the existence of the so-called monotone compression schemes, which in turn is equivalent to a statement in cardinal arithmetic that is indeed independent of ZFC.

Specifically, let X be an infinite set, $Fin(X)$ be the family of its finite subsets, and let $m> k$ be natural numbers.

A monotone compression scheme for $(X, m, k)$ is a function $f\colon [X]^k \rightarrow Fin(X)$ such that

$$ \begin{align*} \forall A \in [X]^m \exists B \in [X]^k \, (B \subseteq A \subseteq f(B)). \end{align*} $$

The main result of the paper then is that there exists a monotone compression scheme for $([0,1], m+1, m)$ for some m if and only if $2^{\aleph }_0 < \aleph _{\omega }$ .

It is now well known that the results are related to Kuratowski’s theorem on decompositions of finite powers of sets and that the monotone compression functions on the unit interval cannot be Borel measurable. During the talk I will introduce the subject of the paper in question, present the set-theoretic aspects of the main results, including some remarks concerning the formulation of existence of the monotone compression schemes in terms of determinacy for certain collaborative compression–reconstruction games, and discuss what these theorems tell us about the nature of the way set theory (and set-theoretic independence in particular) is being applied in other fields of mathematics. Time permitting, I want also to elaborate on how the monotone compression schemes could be expressed in large cardinal terms.

▸ MICHAŁ TOMASZ GODZISZEWSKI AND RAFAL URBANIAK, Potentialism, semantics, and ontology—a case study of Yablo’s Paradox.

University of Warsaw, Poland and Munich Center for Mathematical Philosophy, LMU Munich, Germany.

E-mail: mtgodziszewski@gmail.com

University of Gdańsk, Poland.

E-mail: rfl.urbaniak@gmail.com

When properly arithmetized, formal version of Yablo’s paradox results in a set of formulas which, if considered in first-order logic with the only assumptions about the notion of truth being local disquotation (i.e., when formalized without certain (strong) assumptions imposed either on logic behind our arithmetized theories or on the axioms governing the properties of the truth predicate involved in the formulas from the Yablo sequence) turns out consistent and only $\omega $ -inconsistent, contrary to natural-language interpretation of it. One has to add either uniform disquotation or the $\omega $ -rule to obtain an (expected) inconsistency. Since the paradox involves an infinite sequence of sentences, one might think that it also doesn’t arise in finitary contexts. We study whether it does. It turns out that the issue turns on how the finitistic approach is formalized.

On one of them, proposed by M. Mostowski, all paradoxical sentences simply fail to hold. This happens at a price: the underlying finitistic arithmetic itself is $\omega $ -inconsistent. Finally, when studied in the context of a finitistic approach which preserves the truth of standard arithmetic (developed by one of the authors), the paradox strikes back—it does so with double force, and for now inconsistency can be obtained without the use of uniform disquotation or the $\omega $ -rule.

Apart from a finitistic formalization of the Yablo paradox and giving out the modal semantics for potentially infinite domains of Mostowski, we conclude with a discussion of the difference between semantics and ontology of arithmetical potentialism. We claim that the difference is hidden in the choice of the order of logic used to determine arithmetical formulas. Although the modal first-order theory of potentially infinite domain of finite models approximating the natural numbers is simply (infinitistic) True Arithmetic, the finitary nature of the models serving as universes of potentialist discourse is revealed on the level of the second-order interpretations of quantifiers in this potentialist setting.

▸ JOACHIM MUELLER-THEYS, First-order concept logic.

Kurpfalzstr. 53, 69 226 Heidelberg, Germany.

E-mail: mueller-theys@gmx.de

We developed Basic Concept Logic, intentionally considering only juxtaposition (as with rational creature), thereby enabling a special intensional characterization of implication (cf. BSL 24 (2018), pp. 370–371). By adding conceptual negation, a level comparable to that of PL can be reached. However, concepts like prime cannot be further analyzed.

I. Let $ L $ be some first-order language, $ L _n : = \big \{ \phi \in L \! : { \rm fv } ( \phi ) = \{ x _1, \dots , x _n \} \big \} $ $ ( n \geq 0 ) $ . Any formula $ \phi ( x ) \in L _1 $ can be regarded a concept expression having the extension $ \phi ( x ) ^{\mathcal M }$ $ : = $ $ \{ a \in | {\mathcal M} | \! : {\mathcal M} \models \phi [ a ] \} $ with respect to the given L-model $ {\mathcal M }$ . There is a close relationship to definable sets $ A = \phi ( x ) ^{\mathcal M} $ , and the approach is in line with Buchholz’s determination: concepts are named sets.

In general, we consider predicate expressions $ \phi ( \vec {x} ) = \phi ( x _1 , \dots , x _n ) \in L _n $ , which we compare by extent as follows. Particularly: $ \phi ( \vec {x} ) \preceq _{\mathcal M} \psi ( \vec {x} ) $ :iff $ \phi ( \vec {x} ) ^{\mathcal M} \subseteq ( \leq ) \ \psi ( \vec {x} ) ^{\mathcal M} $ , and universally: $ \phi ( \vec {x} ) \preceq _{\Sigma } \psi ( \vec {x} ) $ :iff $ \phi ( \vec {x} ) \preceq _{\mathcal M} \psi ( \vec {x} ) $ for all $ {\mathcal M} \models \Sigma $ , where $ \Sigma \subseteq L _0 $ is some set of sentences (“axioms”). Notice that $ \phi ( \vec {x} ) \preceq _{\Sigma } \psi ( \vec {x} ) $ implies $ \phi ( \vec {x} ) \preceq _{{\mathcal M} _{\Sigma }} \psi ( \vec {x} ) $ , whereas the converse is not true obviously.

We have formulated and proved the Universally Less-Extent Implication Theorem: $ \phi ( \vec {x} ) \preceq _{\Sigma } \psi ( \vec {x} ) $ if and only if $ \phi ( \vec {x} ) \Rightarrow _{\Sigma } \psi ( \vec {x} ) $ , where $ \phi \Rightarrow _{\Sigma } \psi $ :iff $ \Sigma \models \phi \rightarrow \psi $ .

II. Odd is an attribute of $ \mathrm {prime}> \! 2 $ , since $ \mathrm {prime}> \! 2 $ implies uneven. In general, we call $ \phi ( \vec {x} ) $ $ \Sigma $ -attribute of $ \psi ( \vec {x} ) $ :iff $ \psi ( \vec {x} ) \Rightarrow _{\Sigma } \phi ( \vec {x} ) $ . Traditionally, conceptual content has been considered the “sum” of attributes: $ \big ( \phi ( \vec {x} ) \big ) _{\Sigma } : = \big \{ \psi ( \vec {x} ) \in L _n \! : \psi ( \vec {x} ) \ \mathrm {attr} _{\Sigma } \ \phi ( \vec {x} ) \big \} $ . For $ n = 0 $ , $ ( \sigma ) _{\Sigma } $ amazingly becomes propositional content, which we have considered the set of implicates $ \{ \tau \! : \sigma \, \Rightarrow _{\Sigma } \tau \} $ evidently.

We can now compare by content: $ \phi ( \vec {x} ) = ) _{\Sigma } \ \psi ( \vec {x} ) $ :iff $ \big ( \phi ( \vec {x} ) \big ) _{\Sigma } \supseteq \big ( \psi ( \vec {x} ) \big ) _{\Sigma } \, $ , and we get the More-Content Implication Theorem: $ \phi ( \vec {x} ) = ) _{\Sigma } \ \psi ( \vec {x} ) $ if and only if $ \phi ( \vec {x} ) \Rightarrow _{\Sigma } \psi ( \vec {x} ) $ , which we can reconstruct in any quasi-ordering.

III. Traditional logic has claimed that more content corresponds to less extent. The More-Content Implication and the Universally Less-Extent Implication Theorem yield the Logical Reciprocity Theorem: $ \phi ( \vec {x} ) = ) _{\Sigma } \ \psi ( \vec {x} ) $ if and only if $ \phi ( \vec {x} ) \preceq _{\Sigma } \psi ( \vec {x} ) $ . The concrete Reciprocity Theorem follows: $ \phi ( \vec {x} ) = ) _{\Sigma } \ \psi ( \vec {x} ) $ implies $ \phi ( \vec {x} ) \preceq _{{\mathcal M}_{\Sigma }} \psi ( \vec {x} ) $ , but, on the other hand, we have Failure of Converse Reciprocity—as with BCL.

Acknowledgments. Many of my original ideas were resolved by Wilfried Buchholz. My work has been closely connected to “Peana Pesen”.

▸ IAROSLAV PETIK, Abstract complexity algebra for first order predicate logic.

Independent Scholar, Ukraine.

E-mail: iaroslav.petik@gmail.com

This thesis proposes to modify the model of first order predicate theory so as to present the levels of abstract complexity to any given statement of the logic which is useful for purposes of studying the complexity properties of a variety of formal systems.

The signature of a first order predicate logic is $\Sigma = (\Omega , \Pi )$ where $\Omega $ is a set of function symbols and $\Pi $ is a set of predicate symbols. The next symbols are added $\{ A,D \}$ where A is a set of abstract complexity indicators, and D is a graph of which nodes represent individual terms of FOPL and lines represent logical operators. Thus the growth of graph D represents the semantics for A-indicators.

Examples. $P(X)$ is a term which will have the basic abstract complexity represented by $P(X)[^*1]$ . Complex formula $P(X) \wedge Q(X)$ will be calculated basing on the complexities of its nodes and their algebraic sum $(P(X)[^*1] \wedge Q(X)[^*1])[^*2]$ .

Complexity in this case is abstract because it gives the opportunity to view FOPL without being bounded to existing technical hierarchies of decision problems. In most of the cases, the abstract complexity can be translated to time or memory complexity hierarchies (being in direct ratio to it). Exceptions include “hard” places of decisions problem theory like problems with evaluations differs in time and memory systems.