In this paper we study elimination of imaginaries in some classes of henselian valued fields of equicharacteristic zero and residue field algebraically closed. The results are sensitive to the complexity of the value group. We focus first in the case
where the ordered abelian group has finite spines, and then prove a better result for the dp-minimal case. An ordered abelian with finite spines weakly eliminates imaginaries once we add sorts for the quotient groups $Gamma/ Delta$ for each definable convex subgroup $Delta$, and sorts for the quotient groups $Gamma/ Delta+ lGamma$ where $Delta$ is a definable convex subgroup and $l in mathbb{N}_{geq 2}$. We refer to these sorts as the quotient sorts. We prove the following two theorems: Theorem: Let $K$ be a valued field of equicharacteristic zero, residue field algebraically closed and value group with finite spines. Then $K$ admits weak elimination of imaginaries once we add codes for all the definable $mathcal{O}$-submodules of $K^{n}$ for each $n in mathbb{N}$, and the quotient sorts for the value group. Theorem: Let $K$ be a henselian valued field of equicharacteristic zero, residue field algebraically closed and dp-minimal value group. Then $K$ eliminates imaginaries once we add codes for all the definable $mathcal{O}$-submodules of $K^{n}$ for each $n in mathbb{N}$, the quotient sorts for the value group and constants to distinguish representatives of the cosets of $Delta+lGamma$ in $Gamma$, where $Delta$ is a convex definable subgroup and $l in mathbb{N}_{geq 2}$.
Fix a countable nonstandard model $mathcal M$ of Peano Arithmetic. Even with some rather severe restrictions placed on the types of minimal cofinal extensions $mathcal N succ mathcal M$ that are allowed, we still find that there are $2^{aleph_0}$ pos
sible theories of $(mathcal N,M)$ for such $mathcal N$s.
Godels Dialectica interpretation was designed to obtain a relative consistency proof for Heyting arithmetic, to be used in conjunction with the double negation interpretation to obtain the consistency of Peano arithmetic. In recent years, proof theor
etic transformations (so-called proof interpretations) that are based on Godels Dialectica interpretation have been used systematically to extract new content from proofs and so the interpretation has found relevant applications in several areas of mathematics and computer science. Following our previous work on Godel fibrations, we present a (hyper)doctrine characterisation of the Dialectica which corresponds exactly to the logical description of the interpretation. To show that we derive in the category theory the soundness of the interpretation of the implication connective, as expounded on by Spector and Troelstra. This requires extra logical principles, going beyond intuitionistic logic, Markovs Principle (MP) and the Independence of Premise (IP) principle, as well as some choice. We show how these principles are satisfied in the categorical setting, establishing a tight (internal language) correspondence between the logical system and the categorical framework. This tight correspondence should come handy not only when discussing the applications of the Dialectica already known, like its use to extract computational content from (some) classical theorems (proof mining), its use to help to model specific abstract machines, etc. but also to help devise new applications.
We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several othe
r problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.
In [5], Hjorth proved that for every countable ordinal $alpha$, there exists a complete $mathcal{L}_{omega_1,omega}$-sentence $phi_alpha$ that has models of all cardinalities less than or equal to $aleph_alpha$, but no models of cardinality $aleph_{a
lpha+1}$. Unfortunately, his solution does not yield a single $mathcal{L}_{omega_1,omega}$-sentence $phi_alpha$, but a set of $mathcal{L}_{omega_1,omega}$-sentences, one of which is guaranteed to work. It was conjectured in [9] that it is independent of the axioms of ZFC which of these sentences has the desired property. In the present paper, we prove that this conjecture is true. More specifically, we isolate a diagonalization principle for functions from $omega_1$ to $omega_1$ which is a consequence of the Bounded Proper Forcing Axiom (BPFA) and then we use this principle to prove that Hjorths solution to characterizing $aleph_2$ in models of BPFA is different than in models of CH. In addition, we show that large cardinals are not needed to obtain this independence result by proving that our diagonalization principle can be forced over models of CH.
We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents information databases. The static base of our logics is obtained by adding to standard epistemic log
ic comparative epistemic assertions, that can express epistemic superiority between groups or individuals, as well as a common distributed knowledge operator (that combines features of both common knowledge and distributed knowledge). On the dynamic side, we introduce actions by which epistemic superiority can be acquired: sharing all one knows (by e.g. giving access to ones information database to all or some of the other agents), as well as more complex informational events, such as hacking. We completely axiomatize several such logics and prove their decidability.
This note draws conclusions that arise by combining two recent papers, by Anuj Dawar, Erich Gradel, and Wied Pakusa, published at ICALP 2019 and by Moritz Lichter, published at LICS 2021. In both papers, the main technical results rely on the combina
torial and algebraic analysis of the invertible-map equivalences $equiv^text{IM}_{k,Q}$ on certain variants of Cai-Furer-Immerman (CFI) structures. These $equiv^text{IM}_{k,Q}$-equivalences, for a natural number $k$ and a set of primes $Q$, refine the well-known Weisfeiler-Leman equivalences used in algorithms for graph isomorphism. The intuition is that two graphs $G equiv^text{IM}_{k,Q} H$ cannot be distinguished by iterative refinements of equivalences on $k$-tuples defined via linear operators on vector spaces over fields of characteristic $p in Q$. In the first paper it has been shown that for a prime $q otin Q$, the $equiv^text{IM}_{k,Q}$ equivalences are not strong enough to distinguish between non-isomorphic CFI-structures over the field $mathbb{F}_q$. In the second paper, a similar but not identical construction for CFI-structures over the rings $mathbb{Z}_{2^i}$ has been shown to be indistinguishable with respect to $equiv^text{IM}_{k,{2}}$. Together with earlier work on rank logic, this second result suffices to separate rank logic from polynomial time. We show here that the two approaches can be unified to prove that CFI-structures over the rings $mathbb{Z}_{2^i}$ are indistinguishable with respect to $equiv^text{IM}_{k,mathbb{P}}$, for the set $mathbb{P}$ of all primes. This implies the following two results. 1. There is no fixed $k$ such that the invertible-map equivalence $equiv^text{IM}_{k,mathbb{P}}$ coincides with isomorphism on all finite graphs. 2. No extension of fixed-point logic by linear-algebraic operators over fields can capture polynomial time.
We investigate the mathematics of a model of the human mind which has been proposed by the psychologist Jens Mammen. Mathematical realizations of this model consist of so-called emph{Mammen spaces}, where a Mammen space is a triple $(U,mathcal S,math
cal C)$, where $U$ is a non-empty set (the universe), $mathcal S$ is a perfect Hausdorff topology on $U$, and $mathcal Csubseteqmathcal P(U)$ together with $mathcal S$ satisfy certain axioms. We refute a conjecture put forward by J. Hoffmann-J{o}rgensen, who conjectured that the existence of a complete Mammen space implies the Axiom of Choice, by showing that in the first Cohen model, in which ZF holds but AC fails, there is a complete Mammen space. We obtain this by proving that in the first Cohen model, every perfect topology can be extended to a maximal perfect topology. On the other hand, we also show that if all sets are Lebesgue measurable, or all sets are Baire measurable, then there are no complete Mammen spaces with a countable universe. Finally, we investigate two new cardinal invariants $mathfrak u_M$ and $mathfrak u_T$ associated with complete Mammen spaces and maximal perfect topologies, and establish some basic inequalities that are provable in ZFC. We show $mathfrak u_M=mathfrak u_T=2^{aleph_0}$ follows from Martins Axiom, and, contrastingly, we show that $aleph_1=mathfrak u_M=mathfrak u_T<2^{aleph_0}=aleph_2$ in the Baumgartner-Laver model.
We present a new approach to ternary Boolean algebras in which negation is derived from the ternary operation. The key aspect is the replacement of complete commutativity by other axioms that do not require the ternary operation to be symmetric.
These are the lecture notes of an introductory course on ordinal analysis. Our selection of topics is guided by the aim to give a complete and direct proof of a mathematical independence result: Kruskals theorem for binary trees is unprovable in cons
ervative extensions of Peano arithmetic (note that much stronger results of this type are due to Harvey Friedman). Concerning prerequisites, we assume a solid introduction to mathematical logic but no specialized knowledge of proof theory. The material in these notes is intended for 14 lectures and 7 exercise sessions of 90 minutes each.
