Tag - Logic
"What can one describe by first-order formulas in a given group A?" is an old and interesting question. Of course, this depends on the group A. For example, in a free group only cyclic subgroups (and the group itself) are definable in the first-order logic, but in a free monoid of finite rank any finitely generated submonoid is definable. A group A is called rich if the first-order logic in A is equivalent to the weak second-order logic. Surprisingly, there are a lot of interesting groups, rings, semigroups, etc., which are rich. I will describe various algebraic, geometric, and algorithmic properties that are first-order definable in rich groups and apply these to some open problems. Weak second-order logic can be introduced into algebraic structures in different ways: via HF-logic, or list superstructures over A, or computably enumerable infinite disjunctions and conjunctions, or via finite binary predicates, etc. I will describe a particular form of this logic which is especially convenient to use in algebra and show how to effectively translate such weak second-order formulas into the equivalent first-order ones in the case of a rich group A.
We extend Bourke and Garner's idempotent adjunction between monads and pretheories to the framework of ∞-categories, and exploit this to prove many classical theorems about monads in the ∞-categorical setting. Among other things, we prove that the category of algebras for an accessible monad on a locally presentable ∞ category is locally presentable. We also apply the result to construct examples of ∞-categorical monads from pretheories.
In 1993 Brink and Howlett proved that finitely generated Coxeter groups are automatic. In particular, they constructed a finite state automaton recognizing the language of reduced words in the Coxeter group. This automaton is constructed in terms of the remarkable set of "elementary roots" in the associated root system.
In this talk we outline the construction of Brink and Howlett. We also describe the minimal automaton recognizing the language of reduced words, and prove necessary and sufficient conditions for the Brink-Howlett automaton to coincide with this minimal automaton. This resolves a conjecture of Hohlweg, Nadeau, and Williams, and is joint work with Yeeka Yau.
The family of high-rank arithmetic groups is a class of groups playing an important role in various areas of mathematics. It includes SLn(ℤ), for n ≥ 3, SLn(ℤ[1/p]) for n ≥ 2, their finite-index subgroups and many more. A number of remarkable results about them have been proven including: Weil local rigidity, Mostow strong rigidity, Margulis superrigidity and the Schwartz-Eskin-Farb Quasi-isometric rigidity. We will add a new type of rigidity: 'first order rigidity'. Namely if D is such a non-uniform characteristic zero arithmetic group and L a finitely generated group which is elementary equivalent to D then L is isomorphic to D. This stands in contrast with Zlil Sela's remarkable work which implies that the free groups, surface groups and hyperbolic groups (many of which are low-rank arithmetic groups) have many non-isomorphic finitely generated groups which are elementarily equivalent to them.
Vopěnka's principle has arisen as a model-theoretical statement, provably independent of ZFC set theory. However, there are a number of categorical ways of formulating it, preventing the existence of proper classes of objects with some conditions in presentable categories, and these are what our attention will be focused on. In particular, we will look at analogous statements in the context of ∞-categories and we will ask how these new statements interact with the older ones. Moreover, some of the consequences of Vopěnka's principle on classes of subcategories of presentable categories are investigated and to some extent generalized to ∞-categories. A parallel discussion is undertaken about the similar but weaker statement known as weak Vopěnka's principle.
The talk will survey a recent line of work, which takes a proof-theoretic approach to solving the coherence problem(s) for skew monoidal categories and related structures. I will begin by discussing the so-called Tamari order on fully-bracketed words induced by a semi-associative law (AB)C ¡= A(BC), and explain how a simple sequent calculus may account for some of its fascinating properties, such as the fact that the set of fully-bracketed words on n + 1 letters forms a lattice Yn under this order, as well as a remarkable formula counting the number of intervals in Yn. Then I will recall the definition of skew monoidal categories, and explain how a more refined sequent calculus may be used to solve two related coherence problems: deciding equality of maps and enumerating homsets in free skew monoidal categories. Closely related to recent work by Bourke and Lack, this sequent calculus may be considered as a canonical construction of the free left representable skew multicategory over a set of atoms. Finally, I will briefly discuss variations of the sequent calculus capturing ”partially skew” monoidal categories with different normality conditions.
There have traditionally been two ways to reason about universal algebraic structure categorically: via algebraic theories, and via monads. It is well known that the two are tightly related: in particular, there is a correspondence between algebraic theories and a class of monads on the category of sets.
Motivated by the study of simple type theories, Fiore and Mahmoud introduced second-order algebraic theories, which extend classical (first-order) algebraic theories by variable-binding operators, such as the existential quantifier ∃x of first-order logic; the differential operators d/dx of analysis; and the λ-abstraction operator of the unityped λ-calculus. Fiore and Mahmoud established a correspondence between second-order algebraic theories and a second-order equational logic, but did not pursue a general understanding of the categorical structure of second-order algebraic theories. In particular, the possibility of a monad–theory correspondence for second-order algebraic theories was left as an open question.
In this talk, I will present a generalization of algebraic theories to higher-order structure, in particular subsuming the second-order algebraic theories of Fiore and Mahmoud, and describe a universal property of the category of nth-order algebraic theories. The central result is a correspondence between (n+1)th-order algebraic theories and a class of relative monads on the category of nth-order algebraic theories, which extends to a monad correspondence subsuming that of the classical setting. Finally, I will discuss how the perspective lent by higher-order algebraic theories sheds new light on the classical monad-theory correspondence.
In a series of papers the above authors examined the relationship between the universal and elementary theory of a group ring R[G] and the corresponding universal and elementary theory of the associated group G and ring R. Here we assume that R is a commutative ring with identity 1 ≠ 0. Of course, these are relative to an appropriate logical language L0, L1, L2 for groups, rings and group rings respectively. Axiom systems for these were provided. Kharlampovich and Myasnikov, as part of the proof of the Tarskii theorems, prove that the elementary theory of free groups is decidable. For a group ring they have proved that the first-order theory (in the language of ring theory) is not decidable and have studied equations over group rings, especially for torsion-free hyperbolic groups. We examined and survey extensions of Tarksi-like results to the collection of group rings and examine relationships between the universal and elementary theories of the corresponding groups and rings and the corresponding universal theory of the formed group ring. To accomplish this we introduce different first-order languages with equality whose model classes are respectively groups, rings and group rings. We prove that if R[G] is elementarily equivalent to S[H] then simultaneously the group G is elementarily equivalent to the group H and the ring R is elementarily equivalent to the ring S with respect to the appropriate languages. Further if G is universally equivalent to a nonabelian free group F and R is universally equivalent to the integers ℤ then R[G] is universally equivalent to ℤ[F] again with respect to an appropriate language. It was proved that if R[G] is elementarily equivalent to S[H] with respect to L2, then simultaneously the group G is elementarily equivalent to the group H with respect to L0, and the ring R is elementarily equivalent to the ring S with respect to L1.
The structure of group rings is related to the Kaplansky zero-divisor conjecture. A Kaplansky group is a torsion-free gorup which satisfies the Kaplansky conjecture. We next show that each of the classes of left-orderable groups and orderable groups is a quasivariety with undecidable theory. In the case of orderable groups, we find an explicit set of universal axioms. We have that 𝒦 the class of Kaplansky groups is the model class of a set of universal sentences in the language of group theory. We also give a characterization of when two groups in 𝒦 or more generally two torsion-free groups are universally equivalent.
Finally we consider F to be a rank 2 free group and ℤ be the ring of integers. we call ℤ[F] a free group ring. Examining the universal theory of the free group ring ℤ[F] the hazy conjecture was made that the universal sentences true in ℤ[F] are precisely the universal sentences true in F modified appropriately for group ring theory and the converse that the universal sentences true in F are the universal sentences true in ℤ[F] modified appropriately for group theory. We prove that this conjecture is true in terms of axiom systems for ℤ[F].
This is a 22-lecture course, with each lecture being about 45 minutes or so, given online by Piotr Kowalski. It gives an introduction to model theory.
We state several classical results about fields (Ax’s theorem, Hilbert's Nullstellensatz), which have easy model-theoretic proofs and then introduce the necessary basic model-theoretic tools to describe those proofs. In this way we motivate and present basic definitions and results from model theory. We will also sketch at the end of the lecture some recent applications of model theory regarding non-existence of classical solutions of some differential equations, which was a problem considered by Painlevé in 1895 and an argument was found only recently.
You must be logged in to post a comment.