CyberSec Research

We prove that if less than $\aleph_{\omega}$-many Cohen reals are added to a model of \textsf{CH}, then $\omega^{\ast}$ can not be covered by nowhere dense \textsf{P}-sets (equivalently, there is an ultrafilter on $\omega$ that does not contain a tower).

We study ultrafilters on regular uncountable cardinals, with a primary focus on $\omega_1$, and particularly in relation to the Tukey order on directed sets. Results include the independence from ZFC of the assertion that every uniform ultrafilter over $\omega_1$ is Tukey-equivalent to $[2^{\aleph_1}]^{<\omega}$, and for each cardinal $\kappa$ of uncountable cofinality, a new construction of a uniform ultrafilter over $\kappa$ which extends the club filter and is Tukey-equivalent to $[2^\kappa]^{<\omega}$. We also analyze Todorcevic's ultrafilter $\mathcal{U}(T)$ under PFA, proving that it is Tukey-equivalent to $[2^{\aleph_1}]^{<\omega}$ and that it is minimal in the Rudin-Keisler order with respect to being a uniform ultrafilter over $\omega_1$. We prove that, unlike PFA, $\text{MA}_{\omega_1}$ is consistent with the existence of a coherent Aronszajn tree $T$ for which $\mathcal{U}(T)$ extends the club filter. A number of other results are obtained concerning the Tukey order on uniform ultrafilters and on uncountable directed systems.

The game of cops and robbers is played on a fixed (finite or infinite) graph $G$. The cop chooses his starting position, then the robber chooses his. After that, they take turns and move to adjacent vertices, or stay at their current vertex, with the cop moving first. The game finishes if the cop lands on the robber's vertex. In that case we say that the cop wins, while if the robber is never caught then we say that the robber wins. The graph $G$ is called cop-win if the cop has a winning strategy. In this paper we construct an infinite cop-win graph in which, for any two given starting positions of the cop and the robber, we can name in advance a finite time in which the cop can capture the robber, but these finite times are not bounded above. This shows that this graph has maximum capture time (CR-ordinal) $\omega$, disproving a conjecture of Bonato, Gordinowicz and Hahn that no such graph should exist.

Let T be an algebraically bounded theory. We consider the $L(\bar\delta)$-expansions of T by a tuple $\bar \delta$ of derivations (which may be commuting or not). We investigate the model completion of either of the above theories, whose existence has been established in [FT:24], with particular attention to its model-theoretic properties, including $\omega$-stability, simplicity, open core, and elimination of imaginaries.

We study expansions of Hilbert spaces with a bounded normal operator $T$. We axiomatize this theory in a natural language and identify all of its completions. We prove the definability of the adjoint $T^*$ and prove quantifier elimination for every completion after adding $T^*$ to the language. We identify types with measures on the spectrum of the operator and show that the logic topology on the type space corresponds to the weak*-topology on the space of measures. We also give a precise formula for the metric on the space of $1$-types. We prove all completions are stable and characterize the stability spectrum of the theory in terms of the spectrum of the operator. We also show all completions, regardless of their spectrum, are $\omega$-stable up to perturbations.

Higman's lemma states that for any well partial order $X$, the partial order $X^*$ of finite sequences with members from $X$ is also well. By combining results due to Girard as well as Sch\"{u}tte and Simpson, one can show that Higman's lemma is equivalent to arithmetical comprehension over $\textsf{RCA}_0$, the usual base system of reverse mathematics. By incorporating Friedman's gap condition, Sch\"{u}tte and Simpson defined a slightly different order on finite number sequences with fewer comparisons. While it is still true that their definition yields a well partial order, it turns out that arithmetical comprehension is not enough to prove this fact. Gordeev considered a symmetric variation of this gap condition for sequences with members from arbitrary well orders. He could show, over $\textsf{RCA}_0$, that his partial order on sequences is well (for any underlying well order) if and only if arithmetical transfinite recursion is available. We present a new and simpler proof of this fact and extend Gordeev's results to weak and strong gap conditions as well as binary trees with weakly ascending labels. Moreover, we compute the maximal order types of all considered structures.

We prove several results on the model theory of Artin groups, focusing on Artin groups which are ``far from right-angled Artin groups''. The first result is that if $\mathcal{C}$ is a class of Artin groups whose irreducible components are acylindrically hyperbolic and torsion-free, then the model theory of Artin groups of type $\mathcal{C}$ reduces to the model theory of its irreducible components. The second result is that the problem of superstability of a given non-abelian Artin group $A$ reduces to certain dihedral parabolic subgroups of $A$ being $n$-pure in $A$, for certain large enough primes $n \in \mathbb{N}$. The third result is that two spherical Artin groups are elementary equivalent if and only if they are isomorphic. Finally, we prove that the affine Artin groups of type $\tilde{A}_n$, for $n \geq 4$, can be distinguished from the other simply laced affine Artin groups using existential sentences; this uses homology results of independent interest relying on the recent proof of the $K(\pi, 1)$ conjecture for affine Artin groups.

We give a combinatorial consistency-inconsistency configuration that is equivalent to the failure of the following form of Kim's lemma for a given $k$: $(\star)$ For any set of parameters $A$, formula $\varphi(x,b)$, and $A$-bi-invariant types $p$ and $q$ extending $\mathrm{tp}(b/A)$, if $\varphi(x,b)$ $k$-divides along $p$, then it divides along $q$. We then give an equivalent technical variant of $(\star)$ that is non-trivial over arbitrary invariance bases. We also show that the failure of weaker versions of $(\star)$ entails the existence of stronger combinatorial configurations, the strongest of which can be phrased in terms of families of parameters indexed by arbitrary cographs (i.e., $P_4$-free graphs). Finally, we show that if there is an array $(b_{i,j} : i,j < \omega)$ of parameters such that $\{\varphi(x,b_{i,j}) : (i,j) \in C\}$ is consistent whenever $C \subseteq \omega^2$ is a chain (in the product partial order) and $k$-inconsistent whenever $C$ is an antichain, then there is a model $M$, parameter $b$, and $M$-coheirs $p,q \supset \mathrm{tp}(b/M)$ such that $q^{\otimes \omega}$ is an $M$-heir-coheir and $\varphi(x,b)$ $k$-divides along $p$ but does not divide along $q$. In doing so, we also show that this configuration entails the failure of generic stationary local character under the assumption of $\mathsf{GCH}$.

We show that, contrary to the commonly held view, there is a natural and optimal compactness theorem for $\mathrm{L}_{\infty\infty}$ which generalizes the usual compactness theorem for first order logic. The key to this result is the switch from Tarski semantics to Boolean valued semantics. On the way to prove it, we also show that the latter is a (the?) natural semantics both for $\mathrm{L}_{\infty\infty}$ and for $\mathrm{L}_{\infty\omega}$.

Cyclic proof systems for Heyting and Peano arithmetic eschew induction axioms by accepting proofs which are finite graphs rather than trees. Proving that such a cyclic proof system coincides with its more conventional variants is often difficult: Previous proofs in the literature rely on intricate arithmetisations of the metamathematics of the cyclic proof systems. In this article, we present a simple and direct embedding of cyclic proofs for Heyting and Peano arithmetic into purely inductive, i.e. 'finitary', proofs by adapting a translation introduced by Sprenger and Dam for a cyclic proof system of $\mu\text{FOL}$ with explicit ordinal approximations. We extend their method to recover Das' result of $\text{C}\Pi_n \subseteq \text{I}\Pi_{n + 1}$ for Peano arithmetic. As part of the embedding we present a novel representation of cyclic proofs as a labelled sequent calculus.

We extend logical categories with fiberwise interior and closure operators so as to obtain an embedding theorem into powers of the category of topological spaces. The required axioms, besides the Kuratowski closure axioms, are a `product independence' and a `loop contraction' principle.

We review principal results on axiomatizability of classes of lattices of equivalences

We present a new version of the Friedman-Magidor theorem: for every measurable cardinal $\kappa$ and $\tau\leq\kappa^{++}$, there exists a forcing extension $V\subseteq V[G]$ such that any normal measure $U\in V$ on $\kappa$ has exactly $\tau$ distinct lifts in $V[G]$, and every normal measure on $\kappa$ in $V[G]$ arises as such a lift. This version differs from the original Friedman-Magidor theorem in several notable ways. First, the new technique does not involve forcing over canonical inner models or rely on any fine-structural tools or assumptions, allowing it to be applied in the realm of large cardinals beyond the current reach of the inner model program. Second, in the case where $\tau\leq \kappa^+$, all lifts of a normal measure $U\in V$ on $\kappa$ to $V[G]$ have the same ultrapower. Finally, the technique generalizes to a version of the Friedman-Magidor theorem for extenders. An additional advantage is that the forcing used is notably simple, relying only on nonstationary support product forcing.

We call an infinite structure $\mathcal{M}$ sunflowerable if whenever $\mathcal{M}'$ is isomorphic to $\mathcal{M}$ with underlying set $M'$, consisting of finite sets of bounded size, there is an $M_0 \subseteq M'$ such that $M_0$ is a sunflower and $\mathcal{M}'\!\!\upharpoonright[M_0]$ is isomorphic to $\mathcal{M}$. We give sufficient conditions on $\mathcal{M}$ to show that $\mathcal{M}$ is sunflowerable. These conditions allow us to show that several well-known structures are sunflowerable and give a complete characterization of the countable linear orderings which are sunflowerable. We show that a sunflowerable structure must be indivisible. This allows us to show that any Fra\"iss\'e limit which has the 3-disjoint amalgamation property and a single unary type must be indivisible. In addition to studying sunflowerability of infinite structures, we also consider an analogous property of an age which we call the sunflower property. We show that any sunflowerable structure must have an age with the sunflower property. We also give concrete bounds in the case that the age has the hereditary property, the 3-disjoint amalgamation property, and is indivisible.

In this paper, we study definably compact semigroups in o-minimal structures, aiming to extend the theory of definable groups to a broader algebraic setting. We show that any definably compact semigroup contains idempotents and admits a unique minimal ideal as well as minimal left and right ideals, all of which are definable and definably compact. We prove that cancellativity characterizes definable groups among definably compact semigroups, and that any definably compact subsemigroup of a definable group is itself a subgroup. In the completely simple case, we classify definable subsemigroups via a definable Rees matrix decomposition and analyse when results from the theory of definable groups extend to this setting.

We introduce an axiomatisation of when a model of the form $L(V_{\kappa+1})^M$ can be considered a ``$\kappa$-Solovay model''; we show a characterisation of $\kappa$-Solovay models; and we prove elementary equivalences between $\kappa$-Solovay models.

We bring an abstract model theory perspective to interpolation. We ask, what is the role of interpolation in the study of extensions of first order logic, such as infinitary logics, generalized quantifiers and higher order logics? The abstract model theory approach reveals the basic connections between various interpolation properties in isolation, on their own, as well as with respect to other model theoretic properties, such as compactness.

We analyze the effective content of countable, second countable topological spaces by directly calculating the complexity of several topologically defined index sets. We focus on the separation principles, calibrating an arithmetic completeness result for each of the Tychonoff separation axioms. Beyond this, we prove completeness results for various other topological properties, such as being Polish and having a particular Cantor-Bendixson rank, using tools from computable structure theory. This work contrasts with previous work analyzing countable, second countable spaces which used the framework of reverse mathematics, as reverse mathematics generally lacks the precision to pin down exact arithmetic complexity levels for properties of interest.