75 papers
This paper establishes that the explorability of a finitely generated group's Cayley graph by finite automata systems depends on the group's periodicity: periodic groups confine automata to finite areas, groups with non-periodic elements are explorable by automata with three pebbles, and aperiodic groups cannot be explored by any finite automata system.
This paper compares three fixed-dimension satisfiability semantics for quantum logic—standard Hilbert-lattice, global commuting-projector, and local partial-Boolean—proving a strict hierarchy where the standard semantics is strictly more expressive than the others, as demonstrated by an explicit formula that is satisfiable in the standard semantics but unsatisfiable under the other two for all dimensions .
This paper demonstrates that while inquisitive team logic is expressively equivalent to first-order logic for sentences, its open formulas possess strictly greater expressive power, a finding that extends to standard inquisitive first-order logic where certain sentences can express non-first-order properties.
Assuming Schanuel's conjecture, this paper proves that the complete theory of the real exponential field is axiomatized by definably complete exponential fields satisfying , thereby establishing its decidability and relying on the unconditional model completeness of the exponential function restricted to .
This paper investigates the relationship between degrees of categoricity and their punctual (primitive recursive) analogues for functional structures, demonstrating that these notions coincide for non--categorical injection structures but diverge for certain -categorical ones, while also establishing the existence of specific PR-degrees with distinct properties in every non-zero c.e. Turing degree.
This paper investigates the primitive recursive analogue of computable categoricity spectra, demonstrating that these notions coincide for several natural classes of structures, including relatively -categorical equivalence structures and linear orders, relatively -categorical Boolean algebras, and computably categorical trees as partial orders.
This paper answers a question posed by Ben Yaacov, Ibarlucía, and Tsankov by demonstrating an explicit construction of an affine formula using quantifier alternations to calculate distances between -tuples in -valued -structures.
This paper presents new methods for constructing external subsets of nonstandard arithmetic models to demonstrate that while copies of the real numbers cannot be formed within an ultraproduct of finite fields using these techniques, such constructions can yield copies of the algebraic reals, hyperreal fields, or algebraically closed fields of continuum cardinality.
This paper extends A. Miller's -forcing framework to regular uncountable cardinals to construct models with diverse lengths for the -Borel hierarchy on subspaces of the generalized Baire space and to determine the exact -Borel complexity of certain well-founded tree classes.
This paper establishes that nontrivial automorphisms of the Boolean algebra exist in Cohen extensions of a model for any number of added reals , and extends this result to under additional hypotheses involving sage Davies trees.
This paper establishes that the theory of lovely pairs of any complete strongly geometric field theory with quantifier elimination admits quantifier elimination when expanded with predicates for linear independence and corresponding coordinate functions, thereby generalizing Delon's results to include dense pairs of real closed and -adically closed fields.
This paper serves as a corrigendum and addendum to the authors' 2024 work on categoricity-like properties in first-order logic, providing necessary corrections and supplementary insights to the original study.
This paper introduces a novel logical framework featuring four distinct negations by generalizing spectral presheaves to arbitrary complete orthocomplemented lattices, thereby constructing Akchurin algebras that model a product of biquasiintuitionistic and biintuitionistic logics while demonstrating the impossibility of interpreting the spectral presheaf as a model for relevance logic.
This paper proves that determining whether a computable strategy guarantees a win in the Yu-Gi-Oh! Trading Card Game is an undecidable problem that is actually -complete, demonstrating this by constructing legal decks capable of reducing the Halting Problem and the set of countable well orders to the game's winning condition.
This paper establishes the decidability of the word problem for various classes of just infinite groups with recursively enumerable relations using direct methods independent of the Wilson–Grigorchuk classification, while also constructing specific counterexamples of locally finite groups where the problem is undecidable for certain presentations.
This paper generalizes the theory of stable canonical rules and formulas to pre-transitive logics by introducing definable filtration, thereby establishing axiomatization, the finite model property, and structural characterizations for extensions of while demonstrating the existence of continuum many such logics that are neither -stable nor subframe logics.
This paper establishes a cohomological criterion for decomposing Borel graphs, analogous to Dunwoody's work on group accessibility, and applies it to prove that Borel graphs with uniformly bounded degrees and cohomological dimension one are Lipschitz equivalent to acyclic graphs, thereby providing a new proof of a result by Chen et al. regarding graphs with tree-like components.
This paper presents a formalization of Cornelius Castoriadis' concept of "magmas" within a strengthened ZFA set theory by modeling them as nonempty open subsets of a pre-ordered set of atoms, thereby constructing a hierarchical "magmatic universe" where elements depend on one another in a manner distinct from standard Cantorian sets.
This paper presents a constructive formalization of Abstract Rewriting Systems in Agda that eliminates classical logic from standard proofs, refines termination and confluence criteria, and demonstrates its applicability through a formalization of the lambda calculus.
This paper argues that the Gelfand–Naimark duality between compact Hausdorff spaces and unital commutative C*-algebras offers profound insights into the structure of compact Hausdorff spaces, particularly regarding Čech–Stone remainders and their autohomeomorphisms.