next day
all days

View: session overviewtalk overview

09:00-09:15 Session 1: Opening

– Welcome speech by Professor Astrid Söderbergh Widding, Vice Chancellor of Stockholm University

– Opening of the scientific programme by Mirna Dzamonja, chairman of the programme committee for Logic Colloquium 2017

Location: Hörsal 2 (A2)
09:15-10:15 Session 2: Plenary talk
Location: Hörsal 2 (A2)
Assertion and request

ABSTRACT. Think of the content of an assertion as something that is to be done: let us call it a task. Peirce's explanation of the speech act of assertion as the assuming of responsibility then takes the form: by making an assertion, you assume the responsibility, or duty, of performing the task which constitutes the content of the assertion, when requested to do so by the hearer. Thus a duty on the part of the speaker appears as a right on the part of the hearer to request the speaker to perform his duty: this is an instance of what is called the correlativity of rights and duties, a fundamental principle of deontological ethics which can be traced back to Bentham. In logic, it appears as the correlativity of assertions and requests. Since nothing but assertions appear in the usual inference rules of logic, there arises the question of what the rules are that govern the correlative requests. In the case of constructive type theory, they turn out to be the rules which bring the meaning explanations for the various forms of assertion to formal expression. Thus, in analogy with Gentzen's dictum that the propositional operations, the connectives and the quantifiers, are defined by their introduction rules, we may say that the forms of assertion are defined by their associated request rules.

10:45-11:45 Session 3: Plenary talk
Location: Hörsal 2 (A2)
Stone duality and applications in computer science (1/3)
SPEAKER: Mai Gehrke

ABSTRACT. This will be a three part tutorial: 1. General introduction to Stone duality 2. Applications in semantics 3. Applications in formal languages: automata and beyond

11:45-12:45 Session 4: Plenary talk
Location: Hörsal 2 (A2)
Generic absoluteness for Chang models
SPEAKER: David Aspero

ABSTRACT. The main focus of the talk will be on extensions of Woodin's classical result that, in the presence of a proper class of Woodin cardinals, $\mathcal C_\omega^V$ and $\mathcal C_\omega^{V^P}$ are elementally equivalent for every set--forcing $P$ (where $\mathcal C_\kappa$ denotes the $\kappa$--Chang model).

1. In the first part of the talk I will present joint work with Asaf Karagila in which we derive generic absoluteness for $\mathcal C_\omega$ over the base theory $\mbox{ZF}+\mbox{DC}$.

2. Matteo Viale has defined a strengthening $MM^{+++}$ of Martin's Maximum which, in the presence of a proper class of sufficiently strong large cardinals, completely decides the theory of $\mathcal C_{\omega_1}$ modulo forcing in the class $\Gamma$ of set--forcing notions preserving stationary subsets of $\omega_1$; this means that if $MM^{+++}$ holds, $P\in \Gamma$, and $P$ forces $MM^{+++}$, then $\mathcal C_{\omega_1}^V$ and $\mathcal C_{\omega_1}^{V^P}$ are elementarily equivalent. $MM^{+++}$ is the first example of a ``category forcing axiom.''

In the second part of the talk I will present some recent joint work with Viale in which we extend his machinery to deal with other classes $\Gamma$ of forcing notions, thereby proving the existence of several mutually incompatible category forcing axioms, each one of which is complete for the theory of $\mathcal C_{\omega_1}$, in the appropriate sense, modulo forcing in $\Gamma$.

14:00-15:30 Session 5A: Computability
Location: Hörsal 11 (F11)
Irrationality Exponents and Effective Hausdorff Dimension

ABSTRACT. We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension. Let a be any real number greater than or equal to 2 and let b be any non-negative real less than or equal to 2/a. We show that there is a Cantor-like set with Hausdorff dimension equal to b such that, with respect to its uniform measure, almost all real numbers have irrationality exponent equal to a. We give an analogous result relating the irrationality exponent and the effective Hausdorff dimension of individual real numbers. We prove that there is a Cantor-like set such that, with respect to its uniform measure, almost all elements in the set have effective Hausdorff dimension equal to b and irrationality exponent equal to a. In each case, we obtain the desired set as a distinguished path in a tree of Cantor sets.​​

Characterizing the continuous degrees

ABSTRACT. The continuous degrees were introduced by J. Miller as a way to capture the effective content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are difficult to construct: every proof we know invokes a nontrivial topological theorem.

In 2014 Cai, Lempp, Miller and Soskova discovered an unusual structural property of the continuous degrees: if we join a continuous degree with a total degree that is not below it then the result is always a total degree. We call degrees with this curious property almost total. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of the enumeration degrees, this implies that the continuous degrees are also definable. Applying earlier work of J. Miller on the continuous degrees, this shows that the relation "PA above" on the total degrees is definable in the enumeration degrees.

In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. Like them, we identify our almost total degree as the degree of a point in a computably regular space with a computable dense sequence, and then we apply the effective version of Urysohn's metrization theorem to reveal our space as a computable metric space.

This is joint work with Uri Andrews, Greg Igusa, and Joseph Miller.

On the first-order strength of Ramsey's theorem in reverse mathematics

ABSTRACT. Deciding the first-order part of Ramsey's theorem for pairs is one of the important problems in reverse mathematics. In this talk, I will overview the recent developments of this study.

14:00-15:30 Session 5B: Proof theory
Location: Hörsal 4 (B4)
A herbrandized functional interpretation of classical first-order logic

ABSTRACT. We define a (cumulative) functional interpretation of first-order classical logic and show that each theorem of first-order logic is naturally associated with a certain scheme of tautologies. Herbrand's theorem is obtained as a special case. The schemes are given through formulas of a language of finite-type logic defined with the help of an extended typed combinatory calculus that associates to each given type the type of its nonempty finite subsets. New combinators and reductions are defined, the properties of strong normalization and confluence still hold and, in reality, they play a crucial role in defining the above mentioned schemes. The functional interpretation is dubbed "cumulative" because it enjoys a monotonicity property now so characteristic of many recently defined functional interpretations.

(Joint work with Gilda Ferreira in [1].)

[1] Fernando Ferreira and Gilda Ferreira, A herbrandized functional interpretation of classical first-order logic, Archive for Mathematical Logic, published online on 19 May 2017.

Strong Normalization for Simply Typed Lambda Calculus

ABSTRACT. A solution is proposed to Gödel's Koan as the problem is stated in the TLCA list of open problems. As the problem is formulated it contains an element of vagueness as it is presented as the problem of finding a simple or easy ordinal assignment for strong normalization of the beta-reduction of simply typed lambda calculus. Whether a proof is sufficiently easy to categorize as a solution is thus a matter of opinion.

The solution is based on (Howard, 1970) and its improved notation in (Schütte, 1977). These normalization proofs also work for a system with a recursor. However, when the recursor is absent, as in our case, a further simplification is possible. The delta-operation becomes redundant (or at least highly simplified), as does the use of ordinal and vector variables, while the crucial Howard's permutation lemma 2.6 is preserved with some alterations in the vector assigned to the abstracted term.

The proof also gives a unique ordinal assignment for strong normalization as opposed to the non-unique assignment of Howard. The limit ordinal of the assignment is epsilon_0. That this is possible is more or less noted by Howard when he explains that the delta-operation is the point where the strong normalization proof breaks down for his unique assignment. The reason being that the division into cases in the definition of the delta-operation makes some vectors incomparable and it becomes impossible to prove that the inequalities are preserved when the delta-operator is applied. Therefore, Howard's unique assignment is limited to a weak normalization (however with the recursor included). As mentioned the presented result gives a unique assignment for strong normalization though the recursor is not included in order to fit the problem description of the Koan that was first proposed by Gödel.

The extended predicative Mahlo Universe in Explicit Mathematics - model construction
SPEAKER: Anton Setzer

ABSTRACT. Extending Martin-Löf Type Theory by one Mahlo-Universe

The extended predicative Mahlo Universe in Explicit Mathematics -- model construction

This is joint work with Reinhard Kahle, Lisbon. In [3] Setzer introduced the Mahlo universe V in type theory and determined its proof theoretic strength. This universe has a constructor, which depends on the totality of functions from families of sets in the universe into itself. Essentially for every such function f a subuniverse U_f of V was introduced, which is closed under f and represented in V. Because of the dependency on the totality of functions, not all type theoretists agree that this is a valid principle, if one takes Martin-Löf Type Theory as a foundation of mathematics.

Feferman's theory of Explicit Mathematics [1] is a different framework for constructive mathematics, in which we have direct access to the set of partial functions. In such a setting, we can avoid the reference to the totality of functions on V. Instead, we can take arbitrary partial functions f, and try to form a subuniverse U_f closed under f. If f is total on U_f, then we add a code for it to V. In [2] we developed a universe based on this idea (using mahlo as a name for V and sub as a name for U), and showed that we can embed the axiomatic Mahlo universe, an adaption of the Mahlo construction as in [3] to Explicit Mathematics, into this universe. We added as well an induction principle, expressing that the Mahlo universe is the least one. Since the addition of U_f to V depends only on elements of V present before U_f was added to V, it can be regarded as being predicative, and we called it therefore the extended predicative Mahlo universe.

In this talk we construct a model of the extended predicative Mahlo universe in a suitable extension of Kripke-Platek set theory, in order to determine an upper bound for its proof theoretic strength. The model construction adds only elements to the Mahlo universe which are justified by its introduction rules. The model makes use of a new monotonicity condition on family sets, the notion of a monotone operator for defining universes, and a special condition for closure operators. This is an alternative to Richter's [Gamma,Gamma'] operator for defining closure operators.

14:00-15:30 Session 5C: Set theory
Location: Hörsal 8 (D8)
The hereditarily ordinal definable sets in inner models with finitely many Woodin cardinals

ABSTRACT. An essential question regarding the theory of inner models is the analysis of the class of all hereditarily ordinal definable sets $\operatorname{HOD}$ inside various inner models $M$ of the set theoretic universe $V$ under appropriate determinacy hypotheses. Examples for such inner models $M$ are $L(\mathbb{R})$, $L[x]$ and $M_n(x)$. Woodin showed that under determinacy hypotheses these models of the form $\operatorname{HOD}^M$ contain large cardinals, which motivates the question whether they are fine-structural as for example the models $L(\mathbb{R})$, $L[x]$ and $M_n(x)$ are. A positive answer to this question would yield that they are models of $\operatorname{CH}, \Diamond$, and other combinatorial principles.

The first model which was analyzed in this sense was $\operatorname{HOD}^{L(\mathbb{R})}$ under the assumption that every set of reals in $L(\mathbb{R})$ is determined. In the 1990's Steel and Woodin were able to show that $\operatorname{HOD}^{L(\mathbb{R})} = L[M_\infty, \Lambda]$, where $M_\infty$ is a direct limit of iterates of the canonical mouse $M_\omega$ and $\Lambda$ is a partial iteration strategy for $M_\infty$. Moreover Woodin obtained a similar result for the model $\operatorname{HOD}^{L[x,G]}$ assuming $\Delta^1_2$ determinacy, where $x$ is a real of sufficiently high Turing degree, $G$ is $\operatorname{Col}(\omega, {<}\kappa_x)$-generic over $L[x]$ and $\kappa_x$ is the least inaccessible cardinal in $L[x]$.

In this talk I will give an overview of these results and outline how they can be extended to the model $\operatorname{HOD}^{M_n(x,g)}$ assuming $\boldsymbol\Pi^1_{n+2}$ determinacy, where $x$ again is a real of sufficiently high Turing degree, $g$ is $\operatorname{Col}(\omega, {<}\kappa_x)$-generic over $M_n(x)$ and $\kappa_x$ is the least inaccessible cutpoint in $M_n(x)$ which is a limit of cutpoints in $M_n(x)$.

This is joint work with Grigor Sargsyan.

Transversal of full outer measure

ABSTRACT. For every partition of a set of reals into countable sets there is a transversal of full outer measure. Joint work with S. Shelah.

Infinite utility streams and irregular sets

ABSTRACT. Utility streams for infinite horizon have been widely investigated in economical theory in the last decades. From the set-theoretical view point, infinite utility streams are nothing more than infinite sequences on certain topological spaces, and so they can be analyzed and studied with the usual methods coming from forcing and descriptive set theory. In particular, Zame \cite{Z07} and Lauwers \cite{Lau09} showed that the existence of Paretian social welfare relations satisfying intergenerational equity imply the existence of non-constructible objects, such as non-Ramsey and non-measurable sets.

In this talk I prove some connection also with another well-known regularity property, namely the Baire property, and I use Shelah's amalgamation (\cite{JR93} for a very detailed and complete introduction) in order to show that the two above implications do not reverse. Moreover I also investigate other types of egalitarian pre-orders, such as pre-orders satisfying Pigou-Dalton's principle and Hammond's principle.

I thank Adrian Mathias to suggest me the reading of \cite{Lau09} and more generally to show me this connection between set theory and theoretical economics.

16:00-17:40 Session 6A: Contributed talks
Location: D289
Propositional sequent systems of two valued classical logic and many valued logics are no monotonous.

ABSTRACT. We introduce the notion of minimal sequent (two or many valued) and show that well known propositional sequent systems of two valued classical logic (with and without cat rule) as well as the sequent systems, which are constructed by us for some versions of many valued logic are monotonous neither by lines nor by sizes of proofs, that is the results of substitution into minimal sequent can be derived more easier, than corresponding minimal sequent.

Computable bi-embeddable categoricity of equivalence relations

ABSTRACT. We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. To do this, we use the notions of $\Delta^0_\alpha$ \emph{bi-embeddable categoricity} and \emph{relative $\Delta^0_\alpha$ bi-embeddable categoricity} defined analogously to the standard concepts of $\Delta^0_\alpha$ categoricity and relative $\Delta^0_\alpha$ categoricity.

We give a characterization of $\Delta^0_1$ bi-embeddably categorical equivalence structures, completely characterize $\Delta^0_2$ bi-embeddably categorical and relatively $\Delta^0_2$ bi-embeddably categorical equivalence structures, and show that all equivalence structures are relatively $\Delta^0_3$ bi-embeddably categorical.

Furthermore, let the \emph{degree of bi-embeddable categoricity} of a computable structure $\mathcal{A}$ be the least Turing degree that, if it exists, computes embeddings between any computable bi-embeddable copies of $\mathcal{A}$. Then every computable equivalence structure has a degree of bi-embeddable categoricity, and the only possible degrees of bi-embeddable categoricity for equivalence structures are $\mathbf{0}, \mathbf{0}'$ and $\mathbf{0}''$.

Tomographs for Substructural Display Logic
SPEAKER: Michael Arndt

ABSTRACT. The central feature of Belnap's Display Logic [1] is the possibility of displaying every formula occuring in any given sequent as the only formula in either the antecedent or succedent. This is accomplished by means of structural connectives that retain the positional information of the contextual formulae as they are moved aside. Goré [2] accomodates substructural, intuitionistic and dual intuitionistic logic families by building upon a basic display calculus for Bi-Lambek logic. His version uses two nullary, two unary, and three binary structural connectives. The meaning of each of these varies depending on whether it occurs in an antecendent part or in a succedent part of a sequent. Since the structural connectives are not independent of one another, display equivalences are required to mediate between the binary structural connectives.

I propose an alternative approach in which two graph-like ternary structural connectives express one set of three structural connectives each. Each of these new connectives represents all three sequents making up one of the two display equivalences. The notion of sequent disappears and is replaced by that of a structure graph consisting of systems of ternary connectives in which occurrence variables or nodes mark the linking of the connectives and of formulae to those connectives. This manner of linking yields tomographs, graphs that have the property that disconnecting a structure graph at an occurrence variable yields two unconnected subgraphs. The turnstile of a sequent is represented by the highlighting of a single one of the occurrence variables linking connectives.

I will demonstrate that the highlight can be moved freely within the tomograph in accordance to the display equivalences. Specifically, every outmost occurrence variable can be highlighted, and this corresponds to displaying the formula connected to that occurrence. Furthermore, one of the two nullary connectives can be shown to arise as a special case for empty positions of the ternary connective, and the unary negation connectives can be shown to be definable through the ternary ones with the help of that nullary connective. The result is a tomographical framework for Goré's Substructural Display Logic.

[1] N.D.Belnap. Display Logic. Journal of Philosophical Logic 11:375-417, 1982 [2] R. Goré. Substructural Logics on Display. Logic Journal of the IGPL 6(3):451-504, 1998

(Dynamic) epistemic interpretation for erotetic search scenarios
SPEAKER: Michal Pelis

ABSTRACT. As a point of departure in this paper we take the ideas from Inferential Erotetic Logic (IEL), however we relay on epistemic erotetic logic. Such an approach allows us to discuss problem-solving and strategic questioning in the context of agents' interaction. We do this by the means of providing an epistemic interpretation of erotetic search scenarios (a tool from IEL). We introduce concepts of askability and epistemic erotetic implication. Finally we discuss epistemic erotetic search scenarios for the one-agent setting and suggest the multi-agent setting.

A Decision Procedure Model for Finding the Missing Premise in Automated Reasoning

ABSTRACT. Missing premise is an unstated premise that is required to make an incomplete argument valid. Discovering a missing premise in an argument is crucial for both commonsense reasoning and scientific reasoning (Chesnevar et. al., 2000; Besnard and Hunter, 2001). In natural sciences, there are lots of data sets used for supporting scientific hypotheses. There may be some cases in which these data sets cannot support the hypotheses. The technique, which is developed to discover the missing premise, can help to find the required information in order to build a bridge between the data set and hypotheses. Our method aims to provide a decision procedure in order to reason with uncertainty and inconsistency, which will ease the formal reasoning.

We build a proof theoretical model to provide a decision procedure for finding the missing premise. A model for decision procedure consists of finite number of steps for proving the validity of arguments (Macagno & Walton, 2009; Dupin de Saint-Cyr , 2011). For this purpose, we construe a decision procedure by means of formal techniques, i.e. definitions and set of rules, including an automated reasoning computer program, to find the missing premise in the domain of first order monadic predicate logic without identity. In our study we are running a modified version of ”Tree Proof Generator” developed by Wolfgang Schwarz which is based on the analytic tableaux method. We use eligible problems from (Pelletier, 1986) for testing the decision procedure model. We first introduce a notation then using this notation we formulate the basic rules that will be used in our project.


Besnard, P. and Hunter, A. (2001). A logic-based theory of deductive arguments. Articial Intelligence, 128(1-2):203-235.

Chesnevar, C.; Marguitman, A.; Loui, R. (2000). Logical models of argument. ACM Comp. Surveys, 32:337-383.

Dupin de Saint-Cry, F. (2011). Handling Enthymemes in Time-Limited Persuasion Dialogs. In Scalable Uncertainty Management, Benferhat S. & Grant J. (eds.), 149- 162. Springer.

Macagno F. and Walton D. (2009). Enthymemes, argumentation schemes, and topics. Logique et Analyse, 205:39-56.

Pelletier, F. J. (1986). Seventy-five problems for testing automatic theorem provers. Journal of Automated Reasoning, 2:191-216.

Tree Proof Generator. v2.09 (2015-03-04)

16:00-18:00 Session 6B: Contributed talks
Location: D299
On algebras of distributions for binary formulas of quite o-minimal theories with non-maximum many countable models

ABSTRACT. \documentclass[bsl,meeting]{asl} \AbstractsOn \pagestyle{plain} \def\urladdr#1{\endgraf\noindent{\it URL Address}: {\tt #1}.} \newcommand{\NP}{}

\begin{document} \thispagestyle{empty}

\NP \absauth{Dmitry Emelyanov, Beibut Kulpeshov, Sergey Sudoplatov} \meettitle{On algebras of distributions for binary formulas of quite o-minimal theories with non-maximum many countable models}

\affil{Novosibirsk State University, Novosibirsk, Russia; Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan} \meetemail{}

\affil{International Information Technology University, Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan} \meetemail{}

\affil{Sobolev Institute of Mathematics, Novosibirsk State Technical University, Novosibirsk State University, Novosibirsk, Russia; Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan} \meetemail{} %\urladdr{$\sim$sudoplatov/}


We apply a general approach for distributions of binary formulas \cite{EKScite1} to the class of quite o-minimal theories with non-maximum many countable models \cite{EKScite2}. Using Cayley tables for countably categorical weakly o-minimal theories \cite{EKScite3} we explicitly define the classes of commutative monoids $\mathfrak{A}_n$, respectively, $\mathfrak{A}^{\rm QR}_n$, $\mathfrak{A}^{\rm QL}_n$, $\mathfrak{A}^{I}_n$, of isolating formulas for isolated, respectively, quasirational to the right, quasirational to the left, irrational, $1$-types $p$ of quite $o$-minimal theories with non-maximum many countable models, with convexity rank ${\rm RC}(p)=n$. For an algebra $\mathfrak{P}_{\nu(p)}$ of binary isolating formulas of $1$-type~$p$, we have

\begin{theorem} Let $T$ be a quite $o$-minimal theory with non-maximum many countable models, $p\in S_1(\emptyset)$ be a non-algebraic type. Then there exists $n<\omega$ such that:

$(1)$ if $p$ is isolated then $\mathfrak{P}_{\nu(p)}\simeq\mathfrak{A}_n$;

$(2)$ if $p$ is quasirational to the right {\rm (}left{\rm )} then $\mathfrak{P}_{\nu(p)}\simeq\mathfrak{A}^{\rm QR}_n$ {\rm (}$\mathfrak{P}_{\nu(p)}\simeq\mathfrak{A}^{\rm QL}_n${\rm )};

$(3)$ if $p$ is irrational then $\mathfrak{P}_{\nu(p)}\simeq\mathfrak{A}^I_n$. \end{theorem}

\begin{corollary} Let $T$ be a quite $o$-minimal theory with non-maximum many countable models, $p,q\in S_1(\emptyset)$ be non-algebraic types. Then $\mathfrak{P}_{\nu(p)}\simeq\mathfrak{P}_{\nu(q)}$ if and only if ${\rm RC}(p)={\rm RC}(q)$ and the types $p$ and $q$ are simultaneously either isolated, or quasirational, or irrational. \end{corollary}

\begin{definition} {\rm \cite{EKScite3} We say that an algebra $\mathfrak{P}_{\nu(\{p,q\})}$ is {\it generalized commutative} if there is a bijection $\pi{\rm :\ }\rho_{\nu(p)}\to\rho_{\nu(q)}$ witnessing that the algebras $\mathfrak{P}_{\nu(p)}$ and $\mathfrak{P}_{\nu(q)}$ are isomorphic (i.e., that their Cayley tables are equal up to $\pi$) and for any labels $l\in\rho_{\nu(p,q)}$, $m\in\rho_{\nu(q,p)}$, we have $\pi(l\cdot m)=m\cdot l$.} \end{definition}

\begin{theorem} Let $T$ be a quite $o$-minimal theory with non-maximum many countable models, $p,q\in S_1(\emptyset)$ be non-algebraic non-weakly orthogonal types. Then the algebra $\mathfrak{P}_{\nu(\{p,q\})}$ is a generalized commutative monoid. \end{theorem}


\bibitem{EKScite1} {\scshape I.V.~Shulepov, S.V.~Sudoplatov}, {\itshape Algebras of distributions for isolating formulas of a complete theory}, {\bfseries\itshape Siberian Electronic Mathematical Reports}, vol.11 (2014), pp.~362--389. \bibitem{EKScite2} {\scshape B.Sh.~Kulpeshov, S.V.~Sudoplatov}, {\itshape Vaught's conjecture for quite o-minimal theories}, {\bfseries\itshape Annals of Pure and Applied Logic}, vol.~168, issue~1 (2017), pp.~129--149. \bibitem{EKScite3} {\scshape D.Yu.~Emelyanov, B.Sh.~Kulpeshov, S.V.~Sudoplatov}, {\itshape Algebras for distributions of binary isolating formulas in countably categorical weakly o-minimal structures}, {\bfseries\itshape Algebra and Logic}, vol.~56, issue~1 (2017), pp.~13--36.




On preserving properties under expanding models of quite o-minimal theories

ABSTRACT. Here we discuss properties that are preserved under expanding models of an $\aleph_0$-categorical quite o-minimal theory by a convex unary predicate. We prove that the following properties as quite o-minimality \cite{KScite1}, $\aleph_0$-categoricity and convexity rank \cite{KScite2} are preserved under such expansions.

Let $M$ be a weakly o-minimal structure, $A, B\subseteq M$, $M$ be $|A|^+$-saturated, and let $p, q\in S_1(A)$ be non-algebraic types. \begin{definition}\rm \cite{bbs1} We say that $p$ is not {\it weakly orthogonal} to $q$ if there are an $A$-definable formula $H(x,y)$, $\alpha \in p(M)$, and $\beta_1, \beta_2 \in q(M)$ such that $\beta_1 \in H(M,\alpha)$ and $\beta_2 \not\in H(M,\alpha)$. \end{definition} \begin{definition}\rm \cite{KScite1} We say that $p$ is not {\it quite orthogonal} to $q$ if there is an $A$-definable bijection $f: p(M)\to q(M)$. We say that a weakly o-minimal theory is {\it quite o-minimal} if the relations of weak and quite orthogonality for 1-types coincide. \end{definition}

Quite o-minimal theories form a subclass of the class of weakly o-minimal theories preserving a series of properties of o-minimal theories. For instance, in \cite{jms}, $\aleph_0$-categorical quite o-minimal theories were completely described. This description implies their binarity (the similar result holds for $\aleph_0$-categorical o-minimal theories).

\begin{theorem} Let $M$ be a model of an $\aleph_0$-categorical quite o-minimal theory, $M'$ be an expansion of $M$ by an arbitrary finite family of convex unary predicates. Then $M'$ is a model of an $\aleph_0$-categorical quite o-minimal theory of the same convexity rank. \end{theorem}

\begin{thebibliography}{10} \bibitem{KScite1} {\scshape B.Sh.~Kulpeshov}, {\itshape Convexity rank and orthogonality in weakly o-minimal theories}, {\bfseries\itshape News of the National Academy of Sciences of the Republic of Kazakhstan}, Physical and Mathematical Series, vol.~227 (2003), pp.~26--31. \bibitem{KScite2} {\scshape B.Sh.~Kulpeshov}, {\itshape Weakly o-minimal structures and some of their pro\-per\-ties}, {\bfseries\itshape The Journal of Symbolic Logic}, vol.~63, issue~4 (1998), pp.~1511--1528. \bibitem{bbs1} {\scshape B.S.~Baizhanov}, {\itshape Expansion of a model of a weakly o-minimal theory by a family of unary predicates}, {\bfseries\itshape The Journal of Symbolic Logic}, vol.~66, issue~3 (2001), pp.~1382--1414. \bibitem{jms} {\scshape B.Sh.~Kulpeshov}, {\itshape Countably categorical quite o-minimal theories}, {\bfseries\itshape Journal of Ma\-the\-ma\-ti\-cal Sciences}, vol.~188, issue~4 (2013), pp.~387--397.

Easy and hard homogenizable structures
SPEAKER: Ove Ahlman

ABSTRACT. For any natural number $k$, a structure $\mathcal{M}$ is called $>$$k$$-$homogeneous if for any $\mathcal{A}\subseteq \mathcal{M}$ with $|A|>k$ if $f:\mathcal{A}\to\mathcal{M}$ is an embedding, then $f$ may be extended into an automorphism of $\mathcal{M}$. A structure is called homogeneous (sometimes called ultrahomogeneous) if it is both $>$$k$$-$homogeneous and $\leq$$ k$$-$homogeneous. The random graph is a typical example of a homogeneous structure while the random $t-$partite graph is not. However the random $t-$partite graph can be forced into being homogeneous by adding a definable binary predicate $\xi$ as a new relational symbol such that $\xi(a,b)$ hold if and only if $a$ and $b$ are in the same part. We say that a structure is homogenizable if there exists a finite amount of definable new relations which may be added to the signature in order to make the structure homogeneous. \\\indent Since the homogeneous structures have many nice properties, it is a natural question to ask which structures are the closest to being homogeneous. In this talk I will give you a tour of the homogenizable structures, pointing out especially how close (or not) the structures are to being homogeneous. We will take special care with the $>$$k-$homogeneous graphs for which I will also provide an explicit classification.

Universal theories and compactly expandable models

ABSTRACT. Our aim is to solve a quite old question on the difference between expandability and compact expandability, showing that there are compactly expandable models which are not expandable. Toward this, we further investigate the logic of countable cofinality and we prove the existence of universal theories.

On distributions for countable models of quite o-minimal theories with non-maximum many countable models

ABSTRACT. \documentclass[bsl,meeting]{asl} \AbstractsOn \pagestyle{plain} \def\urladdr#1{\endgraf\noindent{\it URL Address}: {\tt #1}.} \newcommand{\NP}{}

\begin{document} \thispagestyle{empty}

\NP \absauth{Beibut Kulpeshov, Sergey Sudoplatov} \meettitle{On distributions for countable models of quite o-minimal theories with non-maximum many countable models}

\affil{International Information Technology University, Almaty, Kazakhstan; Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan} \meetemail{}

\affil{Sobolev Institute of Mathematics, Novosibirsk, Russia; Novosibirsk State Technical University, Novosibirsk, Russia; Novosibirsk State University, Novosibirsk, Russia; Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan} \meetemail{} %\urladdr{$\sim$sudoplatov/}


Quite o-minimal theories (which were introduced in \cite{KScite1}) form a subclass of the class of weakly o-minimal theories preserving a series of properties of o-minimal theories. Using structural results on quite o-minimal Ehrenfeucht theories and solving the Vaught's conjecture \cite{KScite2} similar to \cite{KScite3}, a general approach to the classification of countable models of complete theories \cite{KScite4} is applied to the class of quite o-minimal theories with non-maximum many countable models.

We use the following theorem and the general decomposition formula \cite{KScite4} for the number $I(T,\omega)$ of countable models of theory $T$, the finite Rudin--Keisler preorder ${\rm RK}(T)$ of almost prime models of $T$, and the distribution function ${\rm IL}$ of limit models with respect to ${\rm RK}(T)$: \begin{equation}\label{eqmain1} I(T,\omega)=|{\rm RK}(T)|+\sum_{i=0}^{|{\rm RK}(T)/\sim_{\rm RK}|-1} {\rm IL}(\widetilde{{\bf M}_i}). \end{equation}

\begin{theorem}\label{th_basic} {\rm \cite{KScite2}} Let $T$ be a quite o-minimal theory in a countable language. Then either $T$ has $2^{\omega}$ countable models or $T$ has exactly $3^k\cdot 6^s$ countable models, where $k$ and $s$ are natural numbers. Moreover, for any $k,s\in\omega$ there is a quite o-minimal theory $T$ with exactly $3^k\cdot 6^s$ countable models. \end{theorem}

The Rudin--Keisler preorders ${\rm RK}(T)$ as well as the distribution functions ${\rm IL}$ are described for quite o-minimal theories $T$ with non-maximum many countable models. The decomposition formula (\ref{eqmain1}) is represented in the following form: $$ 3^k\cdot 6^s=2^k\cdot 3^s+\sum\limits_{t=0}^k\sum\limits_{m=0}^s 2^{s-m}\cdot(2^t\cdot 4^m-1)\cdot C^t_k\cdot C^m_s. $$

\begin{thebibliography}{10} \bibitem{KScite1} {\scshape B.Sh.~Kulpeshov}, {\itshape Convexity rank and orthogonality in weakly o-minimal theories}, {\bfseries\itshape News of the National Academy of Sciences of the Republic of Kazakhstan}, Physical and Mathematical Series, 227 (2003), pp.~26--31. \bibitem{KScite2} {\scshape B.Sh.~Kulpeshov, S.V.~Sudoplatov}, {\itshape Vaught's conjecture for quite o-minimal theories}, {\bfseries\itshape Annals of Pure and Applied Logic}, vol.~168, issue~1 (2017), pp.~129--149. \bibitem{KScite3} {\scshape L.L.~Mayer}, {\itshape Vaught's conjecture for o-minimal theories}, {\bfseries\itshape The Journal of Symbolic Logic}, vol.~53, issue~1 (1988), pp.~146--159. \bibitem{KScite4} {\scshape S.V.~Sudoplatov}, {\bfseries\itshape Classification of countable models of complete theories}, Novosibirsk, Edition of NSTU, 2014.


\vspace*{-0.5\baselineskip} \end{document}

Some VC-combinatorial aspects of definable set systems

ABSTRACT. Several aspects of interactions between combinatorial features of definable set systems and model theoretic properties of them have been explored in different works in recent years such as [1], [2], [3], [4], etc. For example many connections between notions of VC-dimension, VC-density, (p,q)-theorems and compression schemes from combinatorial sides and NIP, forking and UDTFS from model theoretic side has been studied. Also some VC-combinatorial invariants are defined in [5]. We will talk about some further developments in these directions. We consider several new combinatorial assumptions on definable set systems, in particular some properties with an extremal combinatorial nature, and then explore their model theoretic impacts for example on complexities in stability hierarchy, spaces of types, etc. We also give several examples in each case. Meanwhile, we give characterizations of some stability theoretic dividing lines in terms of such combinatorial properties.

[1] M. Aschenbrenner, A. Dolich, D. Haskell, D. Macpherson, and S. Starchenko, Vapnik-Chervonenkis Density in some Theories without the Independence Property I, Trans. Amer. Math. Soc, 368 (2016), no. 8, 5889-5949.

[2] A. Chernikov, P. Simon, Externally definable sets and dependent pairs II, Trans. Amer. Math. Soc, vol.367 (2015), pp.52175235.

[3] V. Guingona1, C. Hill, On Vapnik-Chervonenkis density over indiscernible sequences, Math. Log. Quart, No. 12, (2014), pp.5965.

[4] H. Johnson, Vapnik-Chervonenkis Density on Indiscernible Sequences, Stability, and the Maximum Property, Notre Dame J. Formal Logic, vol 56, Number 4 (2015), 583-593.

[5] A. Mofidi, On some dynamical aspects of NIP theories, Arch. Math. Logic, to appear.

16:00-18:00 Session 6C: Contributed talks
Location: E306
The full basis theorem does not imply analytic wellordering

ABSTRACT. In a suitable ccc generic extension of L, the constructible universe, it is true that every non-empty analytically definable set of reals contains an analytically definable real (the full basis theorem), but there is no analytically definable wellordering of the continuum.

Caristi's fixed point theorem and strong systems of arithmetic

ABSTRACT. Caristi's theorem states that if X is a complete metric space and f:X->X is a possibly discontinuous function that is "controlled" by a lower semi-continuous function V, then f has a fixed point. We analyze Caristi's theorem, its natural restrictions, and some lemmas used in its proofs in the context of reverse mathematics, obtaining equivalents for theories ranging from weak König's lemma to the inflationary fixed point scheme.

Nonstandard methods and construction of models of arithmetics

ABSTRACT. We show how to use nonstandard methods of set theory to obtain various models of weak arithmetics. The nonstandard methodology provides us with class mapping ${}^{*}$ defined on $\textbf{V}$, the class of all sets. To construct models of arithmetics, we start with the structure $({}^{\cdot}{\mathbb{N}},{}^{\cdot}{+},{}^{\cdot}{\cdot})$, which is obtained as the limit of the elementary chain $(\mathbb{N},+,\cdot) \preccurlyeq ({}^{*}{\mathbb{N}}, {}^{*}{+},{}^{*}{\cdot}) \preccurlyeq ({}^{**}{\mathbb{N}}, {}^{**}{+},{}^{**}{\cdot}) \preccurlyeq \cdots \preccurlyeq ({}^{n*}{\mathbb{N}}, {}^{n*}{+},{}^{n*}{\cdot}) \preccurlyeq \cdots$. The structure $({}^{\cdot}{\mathbb{N}},{}^{\cdot}{+},{}^{\cdot}{\cdot})$ and its basic properties are due to work by Josef Ml\v{c}ek and Petr Glivick\'{y}. For every $a \in {}^{\cdot}{\mathbb{N}}$, its rank is defined by $r(a) = \min\{n \in \mathbb{N}; a \in {}^{n*}{\mathbb{N}} \}$.

Graded arithmetical structures arise when functions ${}^{\cdot}{+}$ and ${}^{\cdot}{\cdot}$ are replaced by their so called graded versions. Given $g_0,g_1$, functions from $\mathbb{N}^{2}$ to $\mathbb{N}$, the graded version of $f(x,y)$ with respect to $g_0,g_1$ is defined as $f({}^{g_0(r(x),r(y))*}x,{}^{g_1(r(x),r(y))*}y)$.

We study basic properties of graded functions and explore how various choices of $g_0,g_1$ result in very different graded arithmetical structures. An important tool in analyzing the behavior of graded functions is the so called depth function.

We are especially interested in how grading influences prime numbers. By Chen's theorem, there are infinitely many primes $p$ such that $p+2$ is a product of at most two prime numbers. In graded arithmetical structures it is possible to enforce that some composite numbers become primes with respect to the new multiplication (such numbers are called graded primes.) Using Chen's theorem, we show how to obtain a structure that is a model of Robinson (and Presburger) arithmetic and in which the twin prime conjecture holds for graded primes.

Constructing and classifying stability-preserving substructures

ABSTRACT. See paper above

Reflection principles, bounded induction and axiomatic truth theories.

ABSTRACT. We study the arithmetical strength of extensions a non-classically compositional axiomatic theory of truth PT^- with various reflection principles. PT^- does not admit a global axiom for the negation, saying that "the negation of A is true if and only if A is not true" (which is an axiom of a classically compositional CT^-), but instead of it a group of axioms saying when negated compound sentences are true. For example the sentence "negation of a disjunction of two sentences is true if and only if negations of both sentences are true" is an axiom of PT^-(similarly for negation of atomic sentences, negation of existential quntifier and double negation). We ask how strong are extensions of PT^- with reflection principles of the form:

(TPA) "All theorems of PA are true" (TL) "All theorems of logic are true" (REF) "Every first-order consequence of true sentences is true"

It was already known that CT^- extended with every of the above sentences yields the same theory, which is equivalent to CT^- extended with induction for \Delta_0 formulae with T (CT_0). We show that

(1) PT^- extended with (TPA) is conservative over the uniform reflection over PA, hence strictly weaker than the respective extension of CT^-. (2) PT^- extended with (TL) is conservative over PA. (3) PT^- extended with (REF) is equivalent to the analogous extension of CT^-. (4) PT^- extended with induction for \Delta_0 formulae with T is equivalent to CT_0 (and hence to theories mentioned in (3).

On local induction rules: collapse and conservation properties

ABSTRACT. Local induction schemes are variations of the classical induction schemes axiomatizing Peano arithmetic ($\Sigma_n$--induction or $\Pi_n$--induction). Usually, these local schemes are obtained by restricting the conclusion of the induction axioms to some class of definable elements. Given $n,m\geq 1$, the scheme $I(\Sigma_n,{\mathcal K}_m)$ is defined in this way, when the conclusion of the classical $\Sigma_n$--induction scheme is restricted to $\Sigma_m$--definable elements.

For $m=n$, the schemes $I(\Sigma_n,\mathcal{K}_n)$ and the corresponding induction rules associated to them, $(\Sigma_n,\mathcal{K}_n)\mbox{--IR}$, have showed to be useful tools in the analysis of the conservation properties of parameter free $\Pi_n$--induction schemes and local reflection principles (see [CL1] and [CL2]). A specially interesting feature of $(\Sigma_n,\mathcal{K}_n)\mbox{--IR}$ is the ``collapse'' property (i.e. reduction of nested applications of the rule to unnested applications) that distinguishes this rule from the classical $\Sigma_n\mbox{--IR}$.

In this work we extend our previous work in [CL1] and focus on collapse and conservation properties of the rules $(\Sigma_n,\mathcal{K}_m)\mbox{--IR}$ and their parameter free counterparts. Namely:

1. For n=m, we discuss general collapse results for $(\Sigma_n,\mathcal{K}_n)\mbox{--IR}$.

2. For $n>m\geq 1$, we discuss results á la Kreisel--Levy relating (parameter free) local induction rules and local reflection principles.

3.For $1 \leq n

(Work partially supported by grant MTM2014-59178-P, Ministerio de Economía y Competitividad, Spanish Government)


[CL1] Cordón-Franco, A.; Lara-Martín F. F. Local induction and provably total computable functions. Annals of Pure and Applied Logic, 165 (2014), no. 9, 1429--1444.

[CL2] Cordón-Franco, A.; Lara-Martín F. F. On the optimality of conservation results for local reflection in arithmetic. The Journal of Symbolic Logic, 78 (2013) no. 4, 1025--1035.

16:00-17:20 Session 6D: Contributed talks
Location: E497
Systems of propositions referring to each other: a model-theoretic view

ABSTRACT. We investigate arbitrary sets of propositions such that some of them state that some of them (possibly, themselves) are wrong, and criterions of paradoxicality or non-paradoxicality of such systems. For this, we propose a finitely axiomatized first-order theory with one unary and one binary predicates, $T$ and $U$. An heuristic meaning of the theory is as follows: variables mean propositions, $Tx$ means that $x$ is true, $Uxy$ means that $x$ states that $y$ is wrong, and the axioms express natural relationships of propositions and their truth values. A model $(X,U)$ is called non-paradoxical iff it can be enriched to some model $(X,T,U)$ of this theory, and paradoxical otherwise. E.g. a model corresponding to the Liar paradox consists of one reflexive point, a model for the Yablo paradox is isomorphic to natural numbers with their usual ordering, and both these models are paradoxical.

We show that the theory belongs to the class $\Pi^{0}_{2}$ but not $\Sigma^{0}_{2}$. We propose a natural classification of models of the theory based on a concept of a collapse of models. Further, we show that the theory of non-paradoxical models, and hence, the theory of paradoxical models, belongs to the class $\Delta^{1}_{1}$ but is not elementary. We consider also various special classes of models and establish their paradoxicality or non-paradoxicality. In particular, we show that models with reflexive relations, as well as models with transitive relations without maximal elements, are paradoxical; this general observation includes the instances of Liar and Yablo. On the other hand, models with well-founded relations, and more generally, models with relations that are winning in sense of a certain membership game non-paradoxical. Finally, we propose a natural classification of non-paradoxical models based on the above-mentioned classification of models of our theory.

This work was supported by grant 16-11-10252 of the Russian Science Foundation.

Revealing the 4D vector space within disquotational truth theory for self-reference statements

ABSTRACT. The dynamic model of sentences generates of 16-valued logic. Restriction of complete language for it (equivalence, negation)—fragment describes 8-valued logic. The positive fragment of this 8-valued logic and the Klein four group coincide. This group describes the 4D vector space by hypercomplex numbers. We formalize the specified matrix as the partial systems of propositional calculus based on equivalence and negation by [Church, 1956]

A computable solution to Partee's puzzle
SPEAKER: Sam Sanders

ABSTRACT. We present an application of computability theory to formal semantics, a sub-discipline of linguistics. In particular, we discuss a computable solution to Partee's temperature puzzle. Our solution improves upon the standard Montagovian solution to Partee's puzzle (i) by providing computable natural language interpretations for this solution, (ii) by lowering the complexity of the types in the puzzle's interpretation, and (iii) by acknowledging the role of linguistic and communicative context in this interpretation. These improvements are made possible by interpreting natural language in a model that is inspired by the Kleene-Kreisel model of countable-continuous functionals. In this model, continuous functionals are represented by lower-type objects, called the associates of these functionals, analogous to the representation via codes in Reverse Mathematics.

G\"odel's second incompleteness theorem cannot be used as an argument against Hilbert's program

ABSTRACT. We look at argumentation against realizability of Hilbert's finitistic program based on G\"odel's second incompleteness theorem. It is proved that such argumentation is incorrect, since it leads to absurd conclusions. This implies that the second theorem can not be thought of as a decisive argument against feasibility of Hilbert's program in its original form.

16:00-18:00 Session 6E: Contributed talks
Location: F289
Definability between temporal relations in dynamic mereology

ABSTRACT. This paper explores definability dependencies between temporal and spatio-temporal relations in some dynamic mereological systems. These systems are part of a point-free approach to spatial and temporal theories. The approach in question describes space and time in terms of "regions", which are tangible and/or regular parts of space or time ("periods" or "epochs" may be used for parts of time). The point-free theories forgo standard Euclidean notions like "point" or "line", arguing that such objects are abstract and do not exist in reality. Space and time are built, instead, on regions, while points and lines are complex constructs of specific sets of regions(see [1] and [2] for recent works in this area).

The current studies compare three types of systems, which are different types of dynamic spatio-temporal structures. The first two types are mereological reducts of dynamic structures from [2]: Dynamic Mereological Algebras (DMAs) are algebraic structures that use products of Boolean algebras to track changes in space and time, while rich Dynamic Mereological Algebras are a specific kind of DMAs that include special spatio-temporal regions, called "time representatives". The third type of structures is the relational variants of DMAs from [1] that have much weaker language and conditions on their domains. All of these systems include the following four dynamic relations: unstable part-of (a dynamic region is sometimes part of another dynamic region), stable overlap (a dynamic region always overlaps with another), stable underlap (a pair of regions always do not exhaust the whole space) and temporal contact (a pair of regions exist simultaneously at some point).

The results in this paper show that in rich DMAs all of the four relations are equivalent (each of them can define the other three), in general DMAs the first three are equivalent, while the temporal contact is independent, and in relational DMAs all four relations are completely independent from each other.

Teaching universalized-conditionals and Hazen’s Theorem.
SPEAKER: unknown

ABSTRACT. Where S(x) and P(x) are predicates in the sense of [1] and [2], the predicate [S(x) → P(x)] is called the conditional [predicate] with antecedent S(x) and consequent P(x). The sentence ∀x [S(x) → P(x)], which is the universalization of the conditional [S(x) → P(x)], is said to be the universalized-conditional [sentence] with antecedent S(x) and consequent P(x). Students should note that universalized-conditionals are universals; no universalized-conditional is a conditional. The universalized-conditional ∀x [(S(x) &∼ P(x)) → P(x)] is the negated-consequent-qualification [NCQ] of the universalized-conditional ∀x [S(x) → P(x)]. It is easy to see that the NCQ of a universalized-conditional is logically-equivalent to the universalized-conditional itself. Moreover, the existentialized-conjunction corresponding to an NCQ, say, ∃x [(S(x) &∼ P(x)) & P(x)], is evidently inconsistent and thus not implied by its NCQ unless the latter is inconsistent. This shows that no consistent negated-consequent-qualification has existential import in the sense of [1] and [2]. But since every universalized-conditional is logically equivalent to its NCQ, we have the Hazen Lemma: every consistent universalized-conditional is logically-equivalent to a universalized-conditional without existential import. One important question—answered definitively by Allen Hazen in correspondence with Corcoran and Masoud—concerns which universalized-conditionals with existential-import are logically-equivalent to universalized-conditionals without existential-import. Hazen’s Theorem: A universalized-conditional with existential-import is logically equivalent to some universalized-conditional without existential-import iff it is consistent. Hazen’s contributions nicely complement our results in [1] and [2]. They use none of our previously published conclusions: they are entirely new. [1] JOHN CORCORAN AND HASSAN MASOUD, Existential-import today, History and Philosophy of Logic, vol. 36 (2015), pp. 39–61. [2] JOHN CORCORAN AND HASSAN MASOUD, Existential-import mathematics, Bulletin of Symbolic Logic, vol. 21 (2015), pp. 1–14.

A modal operator in multi-modal mu-calculus and induced semiring structure

ABSTRACT. The meanings of formulas in multi-modal mu-calculus (as an extended version of Hennesy-Milner logic) have been discussed by the author, where the states for interactive communication and function application are monitored (conditioned) by formulas: The syntax of the formulas includes the truth, propositions, two kinds of negation, the disjunction operator, the least fixed point operator, and prefix/postfix modal operators.

This contribution is concerned with the case that the postfix modal operator is provided with (another type of) logical formulas. The modal operator might be related to and motivated by declarative programming, originating from: (i) a conjunction of propositional formulas which are all of the expression "a conjunction of literals implies a (single) literal", and (ii) their models over a 3-valued domain (containing truth, falsehood and the undefined). Regarding the model, an extended version of fixed point (of A. Van Gelder et al.) is available so that we may have the pair of positive and negative sets assigned to truth and to falsehood, respectively.

As a next step to the modal operator, the model pair (as a model) is abstracted into the form for sequential and alternative effects. In this contribution, the sequential effect is restricted only to the positive set, such that the pair of a sequence set and a negative set is aimed at, where the sequence set is a subset of the set containing all the finite proposition sequences (formed by concatenation from the set of propositions). Taking the alternation (for concatenation formation) into consideration, we would have a direct sum of such pairs. The set of the direct sums might be finally constructed into a semiring structure, with the operations (addition and multiplication) in accordance to the alternation and the concatenation, respectively.

Interpolation for modal mu-calculus

ABSTRACT. Modal logics are known to widely enjoy interpolation and so does modal mu-calculus, the extension of modal logic by propositional fixed point quantifiers. D'Agostino and Hollenberg [2] utilise automata theory to show that bisimulation quantifiers are expressible in modal mu-calculus and can be used to define interpolants. I will present a constructive and purely syntactic proof of Lyndon (and hence also Craig) interpolation via a finitary sequent calculus of circular proofs introduced in [1].

[1] Bahareh Afshari and Graham E. Leigh, Cut-free completeness for modal mu-calculus, Proceeding of Thirty-Second Annual ACM/IEEE Symposium on Logic in Computer Science (Reykjavik, Iceland), 2017, to appear.

[2] Giovanna D’Agostino and Marco Hollenberg, Logical questions concerning the mu-calculus, Journal of Symbolic Logic, vol. 65 (2000), no. 1, pp. 310–332.

On the Decidability of Mereological Theories with Local Complementation

ABSTRACT. The signature of the formal language of mereology has only one binary predicate P whose intended meaning is “being a part of”. In the literature, quite a few mereological axioms have been formulated and mereological theories can be generated by using those axioms. The so-called axiom of local complementation, which has been formulated by the present writer recently, says that if x is not the greatest member, then for any proper part y of x, there is another proper part z of x such that y does not overlap z and x is composed of y and z. It has been shown that any first-order mereological theory generated by using the traditional axioms must be undecidable if that theory has atomic models but cannot prove the axiom of local complementation. On the other hand, some first-order mereological theories each of which has the axiom of local complementation have been proven to be decidable. This talk will look into the decidability issue of mereological theories with local complementation in a more systematic way. More precisely, we will try to extend each first-order mereological theory known to be undecidable by adding the axiom of local complementation and see whether such an extension is decidable or not.

On the Admissibility of the Structural Rules in Kanger's Calculus with Restricted Equality Rules

ABSTRACT. Kanger's sequent calculus for first order logic with equality, introduced in the classic \cite{K63}, is a sequent calculus for classical first order logic with equality, free of structural rules, based on the following equality rules:

\[ \ba{clcl} \Gamma_1\{v/r\}, s=r,\Gamma\{v/r\}\seq \Delta\{v/r\} & \vbox to 0pt{\hbox{$P_3$}}&\Gamma_1\{v/r\}, r=s,\Gamma\{v/r\}\seq \Delta\{v/r\} & \vbox to 0pt{\hbox{$P_4$}}\\ \cline{1-1}\cline{3-3} \Gamma_1\{v/s\}, s=r,\Gamma\{v/s\}\seq \Delta\{v/s\} &&\Gamma_1\{v/s\},r=s, \Gamma\{v/s\}\seq \Delta\{v/s\} & \ea \] where $\Gamma_1,\Gamma_2, \Delta$ are sequences and $\Gamma\{v/t\}$ denotes the result of substituting all the free occurrences of $v$ in $\Gamma$ by $t$. {\cite{K63} restricts the applications of $P_3$ by the requirement that $rank(r)\leq rank(s)$ and those of $P_4$ by the requirement that $rank(r)< rank(s)$, and the applications of the $\gamma$-rules:

\[ \ba{clcl} \Gamma_1,F\{x/t\}, \forall x F,\Gamma_2 \seq \Delta& &\Gamma\seq \Delta_1, F\{x/t\}, \exists x F \Delta_2& \\ \cline{1-1}\cline{3-3} \Gamma_1, \forall x F,\Gamma_2 \seq \Delta& &\Gamma\seq \Delta_1, \exists x F \Delta_2& \\ \ea \] by the requirement that the term $t$ be present free in the endsequent or be a fresh variable in case there are no free terms in the endsequent. If such restrictions on the equality and $\gamma$-rules are dropped, a syntactic proof of the admissibility of all the structural rules, including the cut rule, over the resulting calculus, as well as over its intuitionistic version, is known from \cite{MP15}. We address that admissibility issue in case the restriction on the equality rules is maintained, and give a syntactic proof that the unrestricted equality rules are admissible over the restricted ones, from which it follows that cut elimination still holds. The proof is based on the admissibility of the contraction rule for equalities in the restricted calculus, for which a syntactic proof remains to be given. The result is obtained through a strengthening of Orevkov's claim in \cite{O69} concerning the existence of nonlentghening derivations, that by itself would fall short of establishing the desired result, since nonlengthening in the specific case ensures only that we have the same restriction $rank(r)\leq rank(s)$ in both $P_3$ and $P_4$ (see also \cite{PP16}).

\bibitem{K63} {\scshape S. Kanger}, {\itshape A Simplified Proof Method for Elementary Logic}, {\itshape In: P. Braffort, D. Hirshberg (eds)}, {\itshape Computer Programming and Formal Systems, pp. 87-94}, North-Holland, Amsterdam (1963)

\bibitem{MP15} {\scshape F. Munini, F.Parlamento}, {\itshape Admissibility of the Structural Rules in Kanger's Sequent Calculus for First Order Logic with Equality}, {\itshape Logic Colloquium 2015- Abstract of Contributed Talks}, {\bfseries\itshape The Bulletin of Symbolic Logic }, vol.~22(2016), no.~3, p.414

\bibitem{PP16} {\scshape F.Parlamento, F.Previale}, {\itshape The Cut Elimination and Nonlengthening Property for the Sequent Calculus with Equality.}, {\itshape Logic Colloquium 2016- Contributed Talk} {\bfseries\itshape ArXiv 1705.00693 }

\bibitem{O69} V. P. Orevkov, {\scshape On Nonlengthening Applications of Equality Rules (in Russian)} {\bfseries\itshape Zapiski Nauchnyh Seminarov LOMI}, 16:152-156, 1969

{\itshape English translation in: A.O. Slisenko (ed) {\em Studies in Constructive Logic}, Seminars in Mathematics: Steklov Math. Inst. 16, Consultants Bureau, NY-London 77-79 (1971)}

16:00-17:40 Session 6F: Contributed talks
Location: F299
Boolean-valued models of ZFC and forcing in geometry and physics

ABSTRACT. To every complex separable Hilbert space $\mathcal{H}$ of quantum-mechanical (QM) states one can assign orthomodular lattice of projections $\mathbb{L}(\mathcal{H})$. Given a maximal complete Boolean algebra of projections $B\subset\mathbb{L}(\mathcal{H})$, it determines a Boolean-valued ZFC model $V^B$ with real numbers corresponding bijectively to self-adjoint operators with spectral projections in $B$ [1]. We provide the conditions for $B$ to be atomless and the QM-meaning of the non-trivial forcing in $V^B$. For a generic ultrafilter $G$ in $V^B$, the change of the real line $R$ in 2-valued model $V$ into $R[G]$ in $V^B/G$ helps to solve some problems in cosmology.

Another change of the real line concerns the level of the formal language, i.e. $R[G]\to\mathbb{R}$ where $R[G]$ is the 1st order set of real numbers and $\mathbb{R}$ is the unique (up to isomorphism) model of the 2nd order theory of Dedekind-complete ordered field. This shift is expected to take place in the cosmological model of expanding Universe [2]. We show that this shift is derivable from $\mathbb{L}(\mathcal{H})$ and leads to a change in smoothness structure of spacetime manifold which must be an exotic $R^4$. The embedding into the standard smooth $\mathbb{R}^4$ allows prediction of the cosmological constant value purely topologically.

[1] Gaisi Takeuti, Two Applications of Logic to Mathematics, Publications of the Mathematical Society of Japan, Princeton University Press, 1978. [2] Jerzy Król, Torsten Asselmeyer-Maluga, Krzysztof Bielas, Paweł Klimasara, From Quantum to Cosmological Regime. The Role of Forcing and Exotic 4-Smoothness, Universe, vol. 3 (2017), no. 2, article number: 31.

Keisler's order via Boolean ultrapowers

ABSTRACT. In this talk, we shall present some applications of the Boolean ultrapower construction to Keisler's order.

Over the last decade, Malliaris and Shelah proved a striking sequence of results in the intersection between model theory and set theory, solved a long-lasting problem, and developed surprising connections between classification theory and cardinal characteristics of the continuum. The main motivation of their work is the study of Keisler's order, introduced originally in 1967 as a device to compare the complexity of complete theories by looking at saturated ultrapowers of their models.

Although the definition of Keisler's order makes use of regular ultrafilters on power-set algebras, recently there has been a shift towards building ultrafilters on complete Boolean algebras. In particular, moral ultrafilters have emerged as the main tool to find dividing lines among unstable theories.

Motivated by this new Boolean-algebraic framework, in this talk we shall address the following question: what kind of classification can arise when we compare theories according to the saturation of Boolean ultrapowers of their models?

We shall show that most model-theoretic properties of $\kappa$-regular ultrafilters can be generalized smoothly to the context of $\kappa$-distributive Boolean algebras. On the other hand, we shall prove the existence of regular ultrafilters on the Cohen algebra $\mathbb{C}_\kappa$ with unexpected model-theoretic features.

On Approximations and Eigenvectors - looking at Quantum Physics via Metric Ultraproducts
SPEAKER: Åsa Hirvonen

ABSTRACT. There is a tradition of using finite dimensional Hilbert spaces to approximate the standard L_2(R) model of quantum mechanics. I present a model theoretic way of looking at such approximations, based on ultraproducts of metric structures.

The ultraproduct allows one to define and calculate the Feynman propagator as the inner product , where |x_i> are eigenvectors of the position operator and K^t is the time evolution operator. The calculations use Gauss sums which, however, causes a discretising effect, giving the wrong value at the limit. This can be remedied by instead of the propagator looking at the kernel of the time evolution operator. Mathematically the propagator and the kernel are different things, but they are used the same way in calculating the movement of a particle and thus should have the same value. Calculating the limit of the kernels allows one to avoid the discretising effect and still use the benefits of finite Gauss sums.

The talk is based on joint work with Tapani Hyttinen.

A plausibility model for regret games

ABSTRACT. In this paper we develop a plausibility game model by defining a new notion of rationality based on the assumption that a player believes that she doesn't play a weakly regret dominated strategy. Especially, we show that the interactive epistemic outcomes from the common belief of this type of rationality are in line with the solutions of the Iterated Regret Minimization (IRM) algorithm. So, we state that one can achieve a characterization of the IRM algorithm in light of common belief of this type of rationality. A benefit of our characterization is that it provides the epistemic foundation to the IRM algorithm. Meanwhile, we also link solutions of the IRM algorithm to modal mu-calculus to deepen our understanding of the epistemic characterization.

Dathematics: a meta-isomorphic version of classic mathematics based on proper classes

ABSTRACT. An implicit working principle in von Newmann-Bernays-Goedel Set Theory (NBG) is that small classes (or `sets') are more suitable objects to start and work with for developing a general foundational framework for standard mathematics. On the other hand, proper classes are just `too big' and formally `too dangerous' in order to be able to ground any classic mathematical theory.

In this paper, we will mainly show that these classic quantitative considerations about proper and small classes are just tangential facts regarding the consistency of ZFC set theory. Effectively, we will construct a first-order logic theory D-ZFC (Dual theory of ZFC set theory) strictly based on (a particular sub-collection of) proper classes with a corresponding special membership relation, such that ZFC and D-ZFC are meta-isomorphic frameworks. More specifically, for any standard formal definition, axiom and theorem that can be described and deduced in ZFC set theory, there exists a corresponding `dual' version in D-ZFC and vice versa. In particular ZFC set theory is consistent if and only if D-ZFC is consistent.

In addition, let us call modern Mathematics for all formal mathematical theories which are grounded in ZFC set theory, for instance, Real and Complex Analysis, Geometry, Algebra, Number theory, Topology and Category Theory. So, we will name Dathematics for the family of all dual versions of the (former) modern theories, where all the subsequent concepts and theorems describing properties among them are expressed and grounded by D-ZFC. Finally, we prove the meta-fact that (classic) mathematics and dathematics are meta-isomorphic, i.e., for any concept, theory and conjecture in (classic) mathematics there exists a symmetric d-concept, d-theory and d-conjecture in dathematics with equivalent formal properties, and vice versa; e.g., a mathematical conjecture C is true (resp. provable) if and only if the dual `dathematical' conjecture C^+ is true (resp. provable). So, (standard) Mathematics and Dathematics are equiconsistent and the last meta-framework has, strictly speaking, proper classes as fundamental objects.

16:00-18:00 Session 6G: Contributed talks
Location: E487
The Semanticist's Guide to Ramification

ABSTRACT. I outline an account of intensional paradoxes in Ramified Higher Order Logic (RHOL). These paradoxes are intensional versions of the paradoxes derived by a syntactic truth predicate. One reason why the intensional paradoxes are especially interesting is that they arise from reasoning about domains of propositions. Thus, they are especially relevant for our understanding of the foundations of Semantic Theory.

In his work on intensional paradoxes, Kaplan (1995) sketches a version of RHOL. Ramification is one way of articulating a consistent metalanguage for Semantic Theory in which the rules for the logical operators are classical. Thus the resulting theory is compatible with standard Montague Grammar.

There’s several different ways of ramifying, and there’s different interpretations of the metaphysical underpinnings of ramification. Here I discuss a simple and user-friendly version of RHOL (in fact, so simple that it could be taught in undergraduate textbooks, I’d say) in which predicative restrictions on the level of formulas are introduced only by generalization over propositional domains. In effect, on my favorite version, a Ramified Logic is one in which the inference from ∀pSp to Sq sometimes fails. I compare my preferred version of RHOL to Kaplan’s version, and argue that the former is better. The argument relies on the fact that on my version, unlike Kaplan’s, it is possible to derive a Fixed Point Theorem over propositions and attitude operators in the standard Tarski fashion. This fact has important positive consequences for the resulting Semantic Theory, in particular it secures the existence of a Stalnakerian Common Ground for arbitrary classes of propositions.

Negative Properties in First-Degree Entailment with Constructible Negation and an Extensional Semantics

ABSTRACT. Classical logic assumes for arbitrary properties F and individuals c that c has F, exactly if c does not have the negative property non-F. Based on the definition of truth and falsehood in classical logic, this implies that any characterization in terms of positive properties can be expressed in terms of negative properties, and vice versa. There is, however, ample evidence that a characterization in terms of positive in contrast to negative properties matters. Positive properties are often assumed to be more homogenous (e.g., ‘x is a bird’) than negative properties (e.g., ‘x is not a bird’) and are argued to be privileged from a metaphysical perspective. In non-classical logics a number of semantics have been developed that allow for the differential treatment of positive and negative properties. This paper uses such a semantics and provides a soundness and completeness proof with respect to an extension of first-order Hilbert axiomatization of first-degree entailment. The logic differs from alternative ones, insofar as first-degree entailments are described in the object language and allow for Boolean combinations of entailments as well as quantification across entailments and within their scopes. The axiomatization is paraconsistent and extends previous accounts of first degree entailments, based on constructible negation and an extensional four-valued semantics that allows for an independent evaluation of positive and negative properties as expressed by negated and non-negated predicates, respectively. In contrast to Anderson and Belnap, both modus ponens and modus tollens inferences with entailments are characterized by valid rules rather than rules which are only admissible. In the semantics an entailment A>B true iff (a) given A is true, so is B and (b) given B is false, so is A. In contrast, semantic consequence is defined to be only truth preserving.

Volutionary deliberations

ABSTRACT. We depart from a classical arithmetical system T strong enough to contains its own coding so that Gödel's incompleteness argument goes though, and we assume T is omega consistent. We presuppose an axiomatization of T that only has modus ponens as a primitive inference rule; such approaches were suggested already in the sixties in the work of Tarski, and a key idea is to have all sentential generalizations of the axiom schemas as presupposed axiom schemas. One consequence of the axiomatization of T is that only sentences of its formal language are theorems. The volutionary turn shifts attention to the set of sentences whose negations are not theses of T. As a consequence undecidable sentences of T become textbook paradoxical sentences, and volutionism offers a deviant resolution of the paradoxes so that e.g. the incompleteness sentence G of Gödel as well as its negation are volutionary theses as neither of these sentences are theses of T. The volutionary points of view are distinct from paraconsistent points of view as volutionist systems as we develop them contain classical logical theses and do not contradict them even in the presence of the volutionary truth predicate which is taken to hold of the negation of a sentence just if the standard provability predicate does not hold of the sentence. In the more technical abstract we relate how we can minimally justify a volutionary style comprehension principle, and this might in light of the weak completeness of RCA(0) in combination with other assumptions possibly provide possibly peculiar volutionary arithmetical models of stronger systems of particular interest.

Relation algebras, representability and relevant logics

ABSTRACT. This talk is an introduction to the problems concerning certain relevant logics and relation algebras.

Maddux (2010) has shown how to obtain sound and complete semantics for RM , the implicational fragment R → of R with the axiom mingle of the form A → (A → A). He also demonstrated how one can obtain a sound but not complete interpretation of R by replacing sets with commuting dense binary relations. However, RM does not have a variable-sharing property (V SP ) which R has. A modal restriction of RM in case of which the V SP is preserved was given in Robles et al. (2010) together with the argument that from an intuitive semantical point of view, this modal restriction of RM is an alternative to Anderson and Belnap’s logic of entailment E (Anderson and Belnap, 1990).

Meyer (2004) has studied a version of positive minimal relevant logic B and Kowalski (2007) demonstrated that B is fully interpretable in the variety of weakly-associative relation algebras which are not representable. Kowalski (2014) went on to show that if representability is dropped, one can obtain a complete interpretation of of certain relevant logics in the language of relational algebras.

We will examine the mentioned results in order to clarify the connection between certain relation algebras and relevant logics like R and RM and see (i.) whether such connection entails full interpretability of relevant logics in terms of relational algebras and (ii.) what are the consequences of achieving this interpretability for representability and completeness.

References Anderson, A. R. and Belnap, N. J. (1990). Entailment: The Logic of Relevance and Necessity, volume I. Princeton Univ Pr. Kowalski, T. (2007). Weakly associative relation algebras hold the key to the universe. Bulletin of the Section of Logic, 36(3/4):145–157. Kowalski, T. (2014). Relevant logic and relation algebras. In Galatos, N., Kurz, A., and Tsinakis, C., editors, TACL 2013. Sixth International Conference on Topology, Algebra and Categories in Logic, volume 25 of EPiC Series in Computing, pages 125–128. EasyChair. Maddux, R. D. (2010). Relevance logic and the calculus of relations. Review of Symbolic Logic, 3(1):41–70. Meyer, R. K. (2004). Ternary relations and relevant semantics. Annals of Pure and Applied Logic, 127(1-3):195–217. Robles, G., Salto, F., and Méndez, J. M. (2010). A modal restriction of r-mingle with the variable-sharing property. Logic and Logical Philosophy, 19(4):341–351.

Meanings of contradicts.
SPEAKER: unknown

ABSTRACT. The ambiguous verb ‘contradicts’ and its cognates play important roles in logic and logic-related literature. We study their uses. We build on [1]: a treatment of the verb ‘implies’ and its cognates. We exploit similarities with ‘implies’ as studied in [3], which observes that the verb ‘implies’ as a relation verb can express relations of various semantic categories: for example, person-to-proposition relations as well as proposition-to-proposition relations: as in ‘Cantor implies that omega exists’ and ‘Zorn’s Lemma implies the Choice Axiom’, respectively. The verb ‘contradicts’ expresses person-to-person relations ([4], pp.52 et al.), person-to-proposition relations ([4], pp.68, 108, et al.), and proposition-to-proposition relations ([4], p. xxvii et al.) (to mention only three): as in “Cantor contradicts Brouwer”, ‘Brouwer contradicts Bivalence’ and ‘Bivalence contradicts Trivalence’. Of course there are several more, e.g., the set-to-proposition relation: a given set of propositions contradicts a given proposition iff the set implies the negation of the given proposition: ‘Lobachevskian Geometry contradicts Euclid’s Parallel Postulate’. The noun ‘contradiction’—besides being used as a proper name of various relations including the one that holds from a set to a proposition iff the former contradicts the latter—has various uses as a common noun applying to propositions, for example, to those whose negations are tautological. It also serves as a part of ambiguous expressions such as ‘the principle of contradiction’[2]. The string ‘contradicting’ is found in different grammatical categories; [4] uses it in three categories on a single page, p. xxviii. [1] JOHN CORCORAN, Meanings of implication, Diálogos, vol. 9 (1973), pp. 59–76. [2] JOHN CORCORAN AND JUSTIN LEGAULT, Aristotle, Boole, and Tarski on contradiction, this BULLETIN, vol. 19 (2013), p. 515. [3] JOHN CORCORAN AND KENNETH BARBER, Agent and Premise Implication, this BULLETIN, vol. 15 (2009), p. 235. [4] MORRIS COHEN AND ERNEST NAGEL, Introduction to Logic, second edition, John Corcoran (editor), Hackett, 1993.

Truth as a Logical Property

ABSTRACT. Numerous deflationists claim that truth is a logical property, similar to conjunction or quantification. This claim can be analysed by using Tarski's criterion of logicality - the logical notions are those which are invariant under any permutation of the world \cite{Tarski}. Considering a materially adequate truth property over arithmetic, I prove the existence of permutations $\pi$ for which the truth property is not invariant. I take this to show that truth is not a logical property.

One can offer a refinement on this thesis: Horsten \cite{Horsten} has argued that truth is not purely logical, but a logico-linguistic property. Can Tarski's criterion be modified to support this claim? I propose suggestions, but show that ultimately they fail, proving that in general it is impossible to have a truth predicate invariant under non-trivial permutation and materially adequate in the permuted model.

McGee's theorem \cite{McGee} provides an alternative statement of Tarski's criterion: a notion is invariant if and only if it is definable in $L(\infty\infty)$, the infinitary language of first order logic. Whilst a truth predicate is not definable in this language, an arithmetical truth predicate is definable in infinitary arithmetical languages, in particular $L_A(\omega_1\omega)$. This results in interesting formal consequences on the expressive utility of a truth predicate and, I argue, shows one can understand truth as a quasi-logical property.

19:00-21:00 Session : City Hall reception

Welcome reception in the City Hall, hosted by Stockholm City