CyberSec Research

We prove a result concerning elementary embeddings of the set-theoretic universe into itself (Reinhardt embeddings) and functions on ordinals that "eventually dominate" such embeddings. We apply that result to show the existence of elementary embeddings satisfying some strict conditions and that are also reminiscent of extendibility in a more local setting. Building further on these concepts, we make precise the nature of some large cardinals whose existence under Reinhardt embeddings was proven by Gabriel Goldberg in his paper "Measurable Cardinals and Choiceless Axioms." Finally, these ideas are used to present another proof of the Kunen inconsistency.

We present a method for producing elementary embeddings from homomorphisms. This method is utilized in the study of the "strongly rigid relation principle" as defined by Hamkins and Palumbo in their paper "The Rigid Relation Principle, a New Weak Choice Principle." We establish that the strongly rigid relation principle is also a weak choice principle that is independent of ZF. Finally, we characterize proto Berkeley cardinals in terms of a strong failure of the strongly rigid relation principle.

Connections between structural graph theory and finite model theory recently gained a lot of attention. In this setting, many interesting question remain on the properties of hereditary dependent (NIP) classes of graphs, in particular related to first-order transductions. Motivated by Simon's decomposition theorem of dependent types into a stable part and a distal (order-like) part, we conjecture that every hereditary dependent class of graphs is transduction-equivalent to a hereditary dependent class of partially ordered graphs, where the cover graph of the partial order has bounded treewidth and the unordered graph is (edge) stable. In this paper, we consider the first non-trivial case (classes with bounded linear cliquewidth) and prove that the conjecture holds in a strong form, where the cover graph of the partial order has bounded pathwidth. Then, we extend our study to classes that admit bounded-size bounded linear cliquewidth covers, and prove that the conjecture holds for these classes, too.

We show that there is an additive $F_\sigma$ subgroup $A$ of $\mathbb{R}$ and $x \in \mathbb{R}$ such that $\mathrm{dim_H} (A) = \frac{1}{2}$ and $A + x A =\mathbb{R}$. However, if $A \subseteq \mathbb{R}$ is a subring of $\mathbb{R}$ and there is $x \in \mathbb{R}$ such that $A + x A =\mathbb{R}$, then $A =\mathbb{R}$. Moreover, assuming the continuum hypothesis (CH), there is a subgroup $A$ of $\mathbb{R}$ with $\mathrm{dim_H} (A) = 0$ such that $x \not\in \mathbb{Q}$ if and only if $A + x A =\mathbb{R}$ for all $x \in \mathbb{R}$. A key ingredient in the proof of this theorem consists of some techniques in recursion theory and algorithmic randomness. We believe it may lead to applications to other constructions of exotic sets of reals. Several other theorems on measurable, and especially Borel and analytic subgroups and subfields of the reals are presented. We also discuss some of these results in the $p$-adics.

The paper presents a solution to the long-standing question about the decidability of the two-variable fragment of the superintuitionistic predicate logic $\mathbf{QLC}$ defined by the class of linear Kripke frames, which is also the `superintuitionistic' fragment of the modal predicate logic $\mathbf{QS4.3}$, under the G\"odel translation. We prove that the fragment is undecidable ($\Sigma^0_1$-complete). The result remains true for the positive fragment, even with a single binary predicate letter and an infinite set of unary predicate letters. Also, we prove that the logic defined by ordinal $\omega$ as a Kripke frame is not recursively enumerable (even both $\Sigma^0_1$-hard and $\Pi^0_1$-hard) with the same restrictions on the language. The results remain true if we add also the constant domain condition. The proofs are based on two techniques: a modification of the method proposed by M.Marx and M.Reynolds, which allows us to describe tiling problems using natural numbers rather than pairs of numbers within an enumeration of Cantor's, and an idea of `double labeling' the elements from the domains, which allows us to use only two individual variables in the proof when applying the former method.

The paper considers algorithmic properties of classical and non-classical first-order logics and theories in bounded languages. The main idea is to prove the undecidability of various fragments of classical and non-classical first-order logics and theories indirectly, by extracting it as a consequence of the recursive inseparability of special problems associated with them. First, we propose a domino problem, which makes it possible to catch the recursive inseparability of two sets. Second, using this problem, we prove that the classical first-order logic of a binary predicate and the theory of its finite models where the predicate is symmetric and irreflexive are recursively inseparable in a language with a single binary predicate letter and three variables (without constants and equality). Third, we prove, for an infinite class of logics, that the monadic fragment of a modal predicate logic and the logic of the class of its finite Kripke frames are recursively inseparable in languages with a single unary predicate letter and two individual variables; the same result is obtained if we replace the condition of finiteness of frames with the condition of finiteness of domains allowed in frames. Forth, we expand the results to a wide class of superintuitionistic predicate logics. In particular, it is proved that the positive fragments of the intuitionistic predicate logic and the logic of the class of finite intuitionistic Kripke frames are recursively inseparable in the language with a single unary predicate letter and two individual variables. The technique used and the results obtained allow us to answer some additional questions about the decidability of special monadic fragments of some modal and superintuitionistic predicate logics.

We define and study an infinitary operation on countable sequences of ordinals which is strictly monotone in many significant cases and has both an order-theoretical characterization and a characterization in terms of combinatorial games.

In 1984, Ditor asked two questions: (1) For each $n\in\omega$ and infinite cardinal $\kappa$, is there a join-semilattice of breadth $n+1$ and cardinality $\kappa^{+n}$ whose principal ideals have cardinality $< \kappa$? (2) For each $n \in \omega$, is there a lower-finite lattice of cardinality $\aleph_{n}$ whose elements have at most $n+1$ lower covers? We show that both questions have positive answers under the axiom of constructibility, and hence consistently with $\mathsf{ZFC}$. More specifically, we derive the positive answers from assuming that $\square_\kappa$ holds for enough $\kappa$'s.

This article deals with the description and recognition of fiber bundles, in particular nerves, in medical images, based on the anatomical description of the fiber trajectories. To this end, we propose a logical formalization of this anatomical knowledge. The intrinsically imprecise description of nerves, as found in anatomical textbooks, leads us to propose fuzzy semantics combined with first-order logic. We define a language representing spatial entities, relations between these entities and quantifiers. A formula in this language is then a formalization of the natural language description. The semantics are given by fuzzy representations in a concrete domain and satisfaction degrees of relations. Based on this formalization, a spatial reasoning algorithm is proposed for segmentation and recognition of nerves from anatomical and diffusion magnetic resonance images, which is illustrated on pelvic nerves in pediatric imaging, enabling surgeons to plan surgery.

Substructural logics are formal logical systems that omit familiar structural rules of classical and intuitionistic logic such as contraction, weakening, exchange (commutativity), and associativity. This leads to a resource-sensitive logical framework that has proven influential beyond mathematical logic and its algebraic semantics, across theoretical computer science, linguistics, and philosophical logic. The set of theorems of a substructural logic is recursively enumerable and, in many cases, recursive. These logics also possess an intricate mathematical structure that has been the subject of research for over six decades. We undertake a comprehensive study of substructural logics possessing an underlying well-quasi-order (wqo), using established ordinal-indexed fast-growing complexity classes to classify the complexity of their deducibility (quasiequational) and provability (equational) problems. This includes substructural logics with weak variants of contraction and weakening, and logics with weak or even no exchange. We further consider infinitely many axiomatic extensions over the base systems. We establish a host of decidability and complexity bounds, many of them tight, by developing new techniques in proof theory, well-quasi-order theory (contributing new length theorems), the algebraic semantics of substructural logics via residuated lattices, algebraic proof theory, and novel encodings of counter machines. Classifying the computational complexity of substructural logics (and the complexity of the word problem and of the equational theory of their algebraic semantics) reveals how subtle variations in their design influence their algorithmic behavior, with the decision problems often reaching Ackermannian or even hyper-Ackermannian complexity.

In this work, we develop a formal system of inductive logic. It uses an infinitary language that allows for countable conjunctions and disjunctions. It is based on a set of nine syntactic rules of inductive inference, and contains classical first-order logic as a special case. We also provide natural, probabilistic semantics, and prove both $\sigma$-compactness and completeness. We show that the whole of measure-theoretic probability theory is embedded in this system of inductive logic. The semantic models of inductive logic are probability measures on sets of structures. (Structures are the semantic models of finitary, deductive logic.) Moreover, any probability space, together with a set of its random variables, can be mapped to such a model in a way that gives each outcome, event, and random variable a logical interpretation. This embedding, however, is proper. There are scenarios that are expressible in this system of logic which cannot be formulated in a measure-theoretic probability model. The principle of indifference is an idea originating with Laplace. It says, roughly, that if we are "equally ignorant" about two possibilities, then we should assign them the same probability. The principle of indifference has no rigorous formulation in probability. It exists only as a heuristic. Moreover, its use has a problematic history and is prone to apparent paradoxes. Within inductive logic, however, we formulate it rigorously and illustrate its use through a number of examples. Many of the ideas in inductive logic have counterparts in measure theory. The principle of indifference, however, does not. Its formulation requires the structure of inductive logic, both its syntactic structure and the semantic structures embedded in its models. As such, it exemplifies the fact that inductive logic is a strictly broader theory of probability than any that is based on measure theory alone.

We introduce a simple yet powerful invariant relation connecting four successive terms of a class of exponentially decaying alternating functions. Specifically, for the sequence defined by f(n) = ((1/2)^n + (-1)^n) / n, we prove that the combination [(n-2)f(n-2) + (n-3)f(n-3)] / [n f(n) + (n-1)f(n-1)] is universally equal to 4 for all integers n >= 4. This invariant bridge across four points opens new possibilities for predictive coding, data compression, and error detection. We demonstrate how the relation can be used to reconstruct missing data, verify data integrity, and reduce redundancy in data streams with minimal computational overhead. The simplicity and universality of this invariant make it a promising tool for a wide range of applications in information theory and coding systems.

For a given group $G$, it is natural to ask whether one can classify all isometric $G$-actions on Gromov hyperbolic spaces. We propose a formalization of this problem utilizing the complexity theory of Borel equivalence relations. In this paper, we focus on actions of general type, i.e., non-elementary actions without fixed points at infinity. Our main result is the following dichotomy: for every countable group $G$, either all general type actions of $G$ on hyperbolic spaces can be classified by an explicit invariant ranging in an infinite dimensional projective space or they are unclassifiable in a very strong sense. In terms of Borel complexity theory, we show that the equivalence relation associated with the classification problem is either smooth or $K_\sigma$ complete. Special linear groups $SL_2(F)$, where $F$ is a countable field of characteristic $0$, satisfy the former alternative, while non-elementary hyperbolic (and, more generally, acylindrically hyperbolic) groups satisfy the latter. In the course of proving our main theorem, we also obtain results of independent interest that offer new insights into algebraic and geometric properties of groups admitting general type actions on hyperbolic spaces.

BSS RAMs over first-order structures help to characterize algorithms for processing objects by means of useful operations and relations. They are the result of a generalization of several types of abstract machines. We want to discuss whether this concept that allows a machine-oriented characterization of algorithms is sufficiently general for describing also other models of computation. Yiannis N. Moschovakis introduced a concept of abstract computability of functions on the basis of recursive definability over first-order structures. Moschovakis' search operator is the counterpart to the operator introduced by Stephen C. Kleene and suitable for structures without computable minima. To compare our concept with Moschovakis' generalization of the theory of recursive functions, we extend the abilities of BSS RAMs by an operator that makes it possible to provide information about computable functions and their inverses in a non-deterministic way. In Part IIb, we compare several non-determinisms, summarize effects resulting from the restriction of guesses to constants, and take into account properties such as the semi-decidability of oracle sets, the semi-decidability of the identity relation, and the recognizability of constants.

Johnstone demonstrated that Heyting semilattices form a semi-abelian category via a specific triple of terms. Inspired by this work, we introduce \emph{Johnstone algebras} or J-algebras. The algebraic $(*,\to,e)$-theory $J$ of arities $(2,2,0)$ consists of three axioms carefully chosen to ensure protomodularity in alignment with Johnstone's terms. Johnstone algebras generalize well-known structures such as groups (division) and Heyting semilattices (implication) providing a unified framework within the well-behaved setting of semi-abelian categories. We present two primary contributions. First, we identify the M-axiom, \[ (t(x,y)\to x)\to (t(x,y)\to z) \approx x\to z, \text{ where }t(x,y) = (x\to y)\to y. \] The M-axiom is satisfied by residuated Johnstone algebras, and it can be considered a weakening of the H-axiom to comparable elements. We show that $t(x,y)$ defines a \emph{relative closure term} in MBC-algebras, and it implies that MBC-algebras form a variety of algebras, thereby generalizing the corresponding theorem related to HBCK-algebras. Second, we prove several no-go results, demonstrating that balanced theories or theories admitting non-discrete monotone or inflationary algebras cannot possess Malcev terms. Together, these results establish Johnstone algebras as significant structures that achieve desirable categorical properties by carefully integrating both logical and symmetric features, while closely avoiding the constraints imposed by our no-go results.

We formulate and discuss a general axiomatic theory of arbitrary objects. This theory is expressed in a simple first-order language without modal operators, and it is governed by classical logic.

The theory of recursive functions is related in a well-known way to the notion of *least fixed points*, by endowing a set of partial functions with an ordering in terms of their domain of definition. When terms in the pure lambda-calculus are considered as partial functions on the set of reduced lambda-terms, they inherit such a partial order. We prove that Curry's well-known fixed point combinator Y produces least fixed points with respect to this partial order.

Building on the correspondence between finitely axiomatised theories in {\L}ukasieiwcz logic and rational polyhedra, we prove that the unification type of the fragment of {\L}ukasiewicz logic with $n\geq 2$ variables is nullary. This solves a problem left open in [V. Marra and L. Spada. Ann. Pure Appl. Logic 164 2013, p. 192-210]. Furthermore, we refine the study of unification with bounds on the number of variables. Our proposal distinguishes the number $m$ of variables allowed in the problem and the number $n$ in the solution. We prove that the unification type of {\L}ukasiewicz logic for all $m,n \geq 2$ is nullary.