ABSTRACT. Ever since the compilers of Euclid's Elements gave the "definitions" that "a point is that which has no part" and "a line is breadthless length", philosophers and mathematicians have worried that the the basic concepts of geometry are too abstract and too idealized. In the 20th century writers such as Husserl, Lesniewski, Whitehead, Tarski, Blumenthal, and von Neumann have proposed "pointless" approaches.

A problem more recent authors have emphasized it that there are difficulties in having a rich theory of a part-whole relationship without atoms and providing both size and geometric dimension as part of the theory.

A solution will be proposed using the Boolean algebra of measurable sets modulo null sets along with relations derived from the group of rigid motions in Euclidean n-space.

(This is a preliminary report on on-going joint work with Tamar Lando, Columbia University.)

ABSTRACT. A recent approach by Beklemishev uses provability logics to represent reflection principles in formal theories and, in turn, uses said principles to callibrate a theory's consistency strength. There are several benefits to this approach, including semi-finitary consistency proofs and independent combinatorial statements.

A key ingredient is Japaridze's polymodal provability logic GLP_ω. In order to study stronger theories one needs to go beyond GLP_ω to the logics GLP_Λ, where Λ is an arbitrary ordinal. These logics have for each ordinal ξ<Λ a modality [ξ]. As it turns out, proof theoretic ordinals below Γ₀ may be represented in the closed fragment of GLP_Λ (i.e., where no propositional variables occur) and 'worms' therein. Worms are iterated consistency statements of the form ‹ξ₀›...‹ξ_n›T and are well-ordered by their consistency strength.

We will present a calculus for computing the order types of worms and compare the resulting ordinal representation system with standard systems based on Veblen functions. We will also discuss how larger ordinals arising from impredicative proof theory may be represented within provability logics, by interpreting infinitary inference rules which are stronger than the ω-rule.

ABSTRACT. As it is well known, Craig Interpolation fails for the Guarded Fragment GF. In this paper we show that we can recuperate even a stronger form of it, the Uniform Interpolation Property, by considering the Modal character of GF more seriously.

ABSTRACT. There is a close parallel between classical computability and the effective definability on abstract structures. For example, the $\Sigma^0_{n+1}$ sets correspond to the sets definable by means of computable infinitary $\Sigma_{n+1}$ formulae on a structure A. In his last paper, Soskov gives an analogue for abstract structures of Ash's reducibilities between sets of natural numbers and sequences of sets of natural numbers. He shows that for every sequence of structures A, there exists a structure M such that the sequences that are omega-enumeration reducible to A coincide with the c.e. in M sequences. He generalizes the method of Marker's extensions for a sequence of structures. Soskov demonstrates that for any sequence of structures its Marker's extension codes the elements of the sequence so that the n-th structure of the sequence appears positively at the n-th level of the definability hierarchy. The results provide a general method given a sequence of structures to construct a structure with n-th jump spectrum contained in the spectrum of the n-th member of the sequence. As an application a structure with spectrum consisting of the Turing degrees which are non-low_n for all n is obtained. Soskov shows also an embedding of the omega-enumeration degrees into the Muchnik degrees generated by spectra of structures.

We apply these results and generalize the notion of degree spectrum with respect to an infinite sequence of structures A in two ways as Joint spectra of A and Relative spectra of A. We study the set of all lower bounds of the generalized notions in terms of enumeration and omega-enumeration reducibility.

ABSTRACT. In this talk we will explore connections between computable structure theory and generic extensions of the set-theoretic universe, $V$. Recall the definition of {\em Muchnik reducibility} for countable structures: $\mathcal{A}\le_w\mathcal{B}$ if every copy of $\mathcal{B}$ computes a copy of $\mathcal{A}$. We will begin by introducing the notion of {\em generic Muchnik reducibility}, $\le_w^*$: we say $\mathcal{A}\le_w^*\mathcal{B}$ for uncountable structures $\mathcal{A}, \mathcal{B}$ if $\mathcal{A}\le_w\mathcal{B}$ in some (=every) generic extension $V[G]$ in which $\mathcal{A}$ and $\mathcal{B}$ are both countable. We will discuss the basic properties and give some examples of generic Muchnik (non-)reducibilities among natural uncountable structures.

We will then turn our attention to {\em generic presentability}. Roughly speaking, an object $\mathcal{X}$ is generically presentable if a ``copy" of $\mathcal{X}$, up to the appropriate equivalence relation, exists in every generic extension of the universe by some fixed forcing notion. Solovay \cite{Sol70} showed that all generically presentable {\em sets} (up to equality) already exist in the ground model; we will investigate the situation for {\em countable structures} (up to isomorphism) and {\em infinitary formulas} (up to semantic equivalence). We will present two Solovay-type results (and some consequences): (1) any structure generically presentable by a forcing not making $\omega_2$ countable has a copy in $V$, and (2) (under $CH$) any structure generically presentable by a forcing not collapsing $\omega_1$ has a {\em countable} copy in $V$. Time permitting, we will discuss a contrasting result coming from work by Laskowski and Shelah \cite{SL93}.

This is joint work with Julia Knight and Antonio Montalban \cite{KMS14}.

ABSTRACT. In the last years there has been a second boom of the technique of forcing with side conditions (see for instance the recent works of Aspero-Mota, Krueger and Neeman describing three different perspectives of this technique). The first boom took place in the 1980s when Todorcevic discovered a method of forcing in which elementary substructures are included in the conditions of a forcing poset to ensure that the forcing poset preserves cardinals. More than twenty years later, Friedman and Mitchell independently took the first step in generalizing the method from adding small (of size at most the first uncountable cardinal) generic objects to adding larger objects by defining forcing posets with finite conditions for adding a club subset on the second uncountable cardinal. However, neither of these results show how to force (with side conditions together with another finite set of objects) the existence of such a large object together with the continuum being small. In this talk we will discuss new results in this area.

ABSTRACT. Let $G=\langle V, \mathcal{E} \rangle$ be a simple graph, that is, $V$ is a non-empty set of vertexes and $\mathcal E \subseteq [V]^2$ is a set of edges. The \emph{list chromatic number of $G$}, $\mathrm{List}(G)$, is the minimal (finite or infinite) cardinal $\kappa$ such that for every function $F$ on $V$ with $|F(x)|=\kappa$ for $x \in V$, there is a function $f$ on $V$ satisfying that $f(x) \in F(x)$ and if $x \mathcal E y$ then $f(x) \neq f(y)$. The \emph{coloring number of $G$}, $\mathrm{Col}(G)$, is the minimal (finite or infinite) cardinal $\kappa$ such that there is a well-ordering $\triangleleft$ on $V$ such that $|\{y \in V:y \triangleleft x, y \mathcal E x\}|<\kappa$ for every $x \in V$. It is known that $\mathrm{List}(G) \le \mathrm{Col}(G) \le |V|$.

The \emph{reflection principle of coloring number of graphs}, $\mathrm{RP(Col)}$, is the assertion that every graph with uncountable coloring number has a subgraph of size $\aleph_1$ with uncountable coloring number. This principle wad studied in \cite{F1} and \cite{F2}, and it was appeared that this principle is a very strong large cardinal property. On the other hand, Komj\'ath \cite{K} showed the consistency of the statement that $\mathrm{Col}(G)=\mathrm{List}(G)$ for every graph $G$ with infinite coloring number. Using his result, Fuchino and Sakai \cite{FS} proved that the standard model with $\mathrm{RP(Col)}$ also satisfies the \emph{reflection principle of list-chromatic number of graphs}, $\mathrm{RP(List)}$, which assets that every graph with uncountable list-chromatic number has a subgraph of size $\aleph_1$ with uncountable list-chromatic number. They also constructed a model in which $\mathrm{RP(Col)}$ holds but $\mathrm{RP(List)}$ fails. These results suggest the natural question: Does $\mathrm{RP(List)}$ imply $\mathrm{RP(Col)}$?

In this talk, we prove the following consistency results, which show that $\mathrm{RP(List)}$ does not imply $\mathrm{RP(Col)}$, and the bounded version of $\mathrm{RP(List)}$ is not a large cardinal property: \begin{enumerate} \item Suppose GCH. Let $\lambda$ be a cardinal $>\omega_1$. Then there is a poset which preserves all cardinals, and forces that ``$\mathrm{RP(List)}$ restricted to graphs of size $\le \lambda$ holds''. \item Relative to a certain large cardinal assumption, it is consistent that $\mathrm{RP(List)}$ holds but $\mathrm{RP(Col)}$ fails. \end{enumerate}

\begin{thebibliography}{10} \bibitem{F1} {\scshape S.~Fuchino}, {\itshape Remarks on the coloring number of graphs}, {\bfseries\itshape RIMS K\^oky\^uroku}, vol.~1754 (2011), pp.~6--16.

\bibitem{F2} {\scshape S.~Fuchino, H.~Sakai, L.~Soukop, T.~Usuba}, {\itshape More about the Fodor-type reflection principle}, {\bfseries\itshape preprint},

\bibitem{FS} {\scshape S.~Fuchino, H.~Sakai}, {\itshape On reflection and non-reflection of countable list-chromatic number of graphs}, {\bfseries\itshape RIMS K\^oky\^uroku}, vol.1790 (2012), pp.~31--44.

\bibitem{K} {\scshape P.~Komj\'ath}, {\itshape The list-chromatic number of infinite graphs}, {\bfseries\itshape Israel Journal of Mathemathics}, vol.~196 (2013), no.~1, pp.~67--94. \end{thebibliography}

ABSTRACT. It can be argued that by accepting the axioms of a theory as formally expressing our intuitive grasp of a mathematical structure—e.g. PA for arithmetic—we thereby implicitly commit ourselves to accepting certain other statements that are not formally provable from the axioms because of the incompleteness phenomena—such as the statement expressing the soundness of the axioms—and therefore to a fundamentally stronger theory. It follows that any formal theory that aims at capturing our pre-theoretic understanding of the natural numbers structure must admit of extensions; the question then arises as to how the axioms of arithmetic should be extended in order to construct a formal system that allows us to talk rigorously about the scope and limits of our arithmetical knowledge.

The process of recognising the soundness of the axioms is conceived of as a process of reflection on the given theory and the kinds of methods of proof that we recognise as correct. For this reason, the addition of proof-theoretic reflection principles as new axioms can be thought of as representing a natural way of extending PA in order to capture arithmetical knowledge.

I will distinguish two main strategies to justify the addition of reflection principles to be found in the literature (via transfinite induction, and via our truth-theoretic commitments), and I will argue that, contrary to these approaches, proof-theoretic reflection should be justified on the same fundamental grounds as our acceptance of the axioms of the initial system (see e.g. Feferman [1962] and [1988]). Furthermore, I will argue that on these grounds only uniform reflection is justified.

ABSTRACT. Post's paper [2] from 1921 contains the first published proof of the completeness of the propositional subsystem of Principia Mathematica and a decision procedure for it. His unsuccessful attempts in the following years to extend his results to the whole of Principia Mathematica lead him to anticipate the Incompleteness and Undecidability results of Godel and Turing [3]. Being deeply influenced by Lewis' 'Heterodox view' [1], Post considered logical systems as "purely formal developments" to "reach the highest generality possible." This "preoccupation with the outward forms of symbolic expressions" allowed, according to Post, for "greater freedom of method and technique." It made his developments recognizably different from the others, but it was in part "perhaps responsible for the fragmentary nature of [his] development." Moreover, Post views the logical process as "Essentially Creative"; that makes "the mathematician much more than a kind of clever being who can do quickly what a machine could." Post interprets this conclusion as being contrary to Lewis' view. In my talk I will summarize Lewis' 'Heterodox view' and make transparent his influence on Post's early work. At the end I will show that Post's interpretation of his conclusion is not in conflict with Lewis' views as expressed in [1].

[1] C. I. Lewis, A Survey of Symbolic Logic, University of California Press, 1918.

[2] E. Post, Introduction to a General Theory of Elementary Propositions, American Journal of Mathematics, vol.43 (1921), no.3, pp. 163-185.

[3] E. Post, Absolutely Unsolvable Problems and Relatively Undecidable Propositions - Account of an Anticipation, The Undecidable (Martin Davis, editor), Raven Press, Hewlett, 1965, pp. 340-433.

ABSTRACT. We present a new proof of the existence of Morley sequences in simple theories. We avoid using the Erd\H{o}s-Rado theorem and instead use Ramsey's theorem. The proof shows that the basic theory of forking in simple theories can be developed inside $\left< H ((2^{2^{|T|}})^+), \in \right>$ without using the axiom of replacement, answering a question of Grossberg, Iovino and Lessmann, as well as a question of Baldwin.

ABSTRACT. A Polish group G has ample generics if the diagonal action of G on G^n by conjugation has a comeager orbit for every natural n. The existence of ample generics has very strong consequences. Every Polish group $G$ with ample generics has the small index property (that is, every subgroup H of G with [G:H]<2^\omega is open), the automatic continuity property (that is, every homomorphism from G into a separable group is continuous), and uncountable cofinality for non-open subgroups (that is, every countable exhaustive chain of non-open subgroups of G is finite.)

What is surprising is that all known examples of groups with ample generics are isomorphic to the automorphism group of some countable structure, and the question of whether there exists a Polish group with ample generics which is not of this form, is still open. In particular, the isometry group of the Urysohn space Iso(U), the automorphism group of the measure algebra Aut(MA), and the unitary group U(l_2) have meager conjugacy classes. On the other hand, it is known that these groups share some of the consequence of the existence of ample generics. For example, U(l_2) has the automatic continuity property, while Aut(MA) has the automatic continuity property, and the small index property.

Very recently, M.Sabok proposed a model theoretic approach that sheds new light on the structure of these groups, and more generally, automorphism groups of certain classes of homogeneous metric structures. In particular, he formulated a general criterion for a homogeneous metric structure $X$ that implies that Aut(X) has the automatic continuity property, and he verified it for U, MALG, and l_2.

We propose a criterion that implies all the main consequences of the existence of ample generics: the small index property, the automatic continuity property, and uncountable cofinality for non-open subgroups, which suggests that it may be regarded as a counterpart of the notion of ample generics in the realm of homogeneous metric structures. We also verify it for U, MALG, and l_2, thus proving that the groups Iso(U), Aut(MA), U(l_2) satisfy these properties.

ABSTRACT. In constructive mathematics we often consider implications between non-constructive reasoning principles. For instance, it is well known that the Limited principle of omniscience implies that equality of real numbers is decidable. Most such reductions proceed by reducing an instance of the consequent to an instance of the antecedent. We may therefore define a notion of \emph{instance reducibility}, which turns out to have a very rich structure. Even better, under Kleene's function realizability interpretation instance reducibility corresponds to Weihrauch reducibility, while Kleene's number realizability relates it to truth-table reducibility. We may also ask about a constructive treatment of other reducibilities in computability theory. I shall discuss how one can tackle Turing reducibility constructively via Kleene's number realizability. One can then ask whether the constructive formulation of Turing degrees relates them to standard mathematical concepts.

ABSTRACT. A theory is *restricted* if there is a fixed bound on the complexity of its axioms. Kenneth McAloon proved that every restricted arithmetical theory that is consistent with Peano Arithmetic has a model in which the standard natural numbers are definable. In slogan, one could say that McAloon shows that one needs the full language to exclude the standard numbers in principle.

In this talk we discuss the idea of generalizing McAloon's result to the class of consistent restricted sequential theories. We only obtain a weaker statement for the more general case. Whether the stronger statement holds remains open.

Sequential theories are, as a first approximation, theories with sufficient coding machinery for the construction of partial satisfaction predicates of a certain sort. Specifically, we have satisfaction for classes of formulas with complexity below $n$ for a complexity measure like *depth of quantifier alternations*. There are several salient general results concerning sequential theories. For example the degrees of interpretability of sequential theories have many good properties. Examples of sequential theories are PA^-, S^1_2, I\Sigma_1, PA, ACA_0, ZF, GB.

To any sequential model M we can uniquely assign an arithmetical model J_M. This is, roughly, the intersection of all definable cuts of an internal model N of a weak arithmetic like S^1_2. We can show that J_M is independent of the specific choice of N. Our theorem says that any consistent restricted sequential theory U has a model M such that J_M is isomorphic to the standard model.

In the talk, we will briefly indicate how McAloon's proof works and discuss some immediate generalizations. Then, we will outline the basic ideas behind the proof of the result concerning consistent restricted sequential theories.

ABSTRACT. IΔ₀ is the fragment of first-order arithmetic obtained by restricting the induction scheme to bounded formulas. BΣ₁ extends IΔ₀ by the collection scheme for bounded formulas, that is by the axioms [∀x<v∃y ψ(x,y)] ⇒ [∃w ∀x<v ∃y<w ψ(x,y)], where ψ(x,y) is bounded (and may contain additional parameters).

It has been known since the seminal work of Parsons and of Paris and Kirby in the 1970s that BΣ₁ does not follow from IΔ₀, even though it is Π⁰_2-conservative over IΔ₀. However, all constructions of a model of IΔ₀ not satisfying BΣ₁ make use of the axiom Exp, which asserts that 2^x is a total function. From the perspective of IΔ₀, which does not prove the totality of any function of superpolynomial growth, the totality of exponentiation is a very strong unprovable statement. This led Wilkie and Paris [1] to ask whether IΔ₀ + ¬Exp proves BΣ₁.

It is generally believed that the answer to Wilkie and Paris's question is negative, and there are various statements from computational complexity theory, in some cases mutually contradictory, known to imply a negative answer. However, an unconditional proof of a negative answer remains elusive.

I plan to survey some facts related to Wilkie and Paris's question, focusing on two recent groups of theorems:

• the results of the paper [1], which seem to suggest that we are a ``small step'' away from building a model of IΔ<sub>0</sub> + ¬Exp without collection, 
• some new results suggesting that the ``small step'' will be very hard to take, because there is a complexity-theoretic statement, almost certainly false but possibly not disprovable using present-day methods, which implies that $B\Sigma_1$ does follow from ¬Exp.

References:

[1] A. Wilkie and J. Paris, On the existence of end extensions of models of bounded induction, Logic, Methodology, and Philosophy of Science VIII (Moscow 1987), J.E. Fenstad, I.T. Frolov, and R. Hilpinen (eds.), North-Holland, 1989, pp. 143-162.

[2] Z. Adamowicz, L. A. Kołodziejczyk, and J. Paris, Truth definitions without exponentiation and the Σ₁ collection scheme, Journal of Symbolic Logic, vol. 77 (2012), no. 2, pp. 649-655.

ABSTRACT. In computable structure theory, we ask questions about complexity of structures and classes of structures. For a particular countable structure $\mathcal{M}$, how hard is it to build a copy? Can we do it effectively? How hard is it to describe $\mathcal{M}$, up to isomorphism, distinguishing it from other countable structures? For a class $K$, how hard is it to characterize the class, distinguishing members from non-members? How hard is it to classify the elements of $K$, up to isomorphism. In the lecture, I will describe some results on these questions, obtained by combining ideas from computability, model theory, and descriptive set theory. Of special importance are formulas of special forms.