Monadic theory of order and topology II

Assuming the Continuum Hypothesis we interpret the theory of the cardinal 2^ℵ ₀ with quantification over the constructible monadic, dyadic, etc. predicates in the monadic (second-order) theory of the real line, in the monadic theory of any other short non-modest chain, in monadic topology of Cantor’s Discontinuum and some other monadic theories. We build monadic sentences defining the real line up to isomorphism under some set-theoretic assumptions. There are some other results.     

Distributive lattices with a decidable monadic second order theory

A class of finite distributive lattices has a decidable monadic second order theory iff (a) the join irreducible elements of its members have a decidable monadic second order theory, and (b) the width of the lattices is bounded. Similar results are obtained for the monadic chain and the monadic antichain theory where quantification is restricted to chains and antichains, resp. Furthermore, there is no (up to finite difference) maximal set of finite distributive lattices with a decidable monadic (chain or antichain, resp.) theory. Received December 6, 2000; accepted in final form May 30, 2002.     

Random graphs in the monadic theory of order

We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line). Received: 18 July 1996     

Automaton transformations and monadic theories of infinite sequences

In this paper we prove that the set of degrees of asynchronously automaton transformations of infinite sequences with a solvable monadic theory forms an initial segment in the set of degrees of asynchronously automaton transformations. We prove a solvability criterion for a monadic theory of a complete sequence.     

Monadic dynamic algebras

The main purpose of this work is to introduce the class of the monadic dynamic algebras (dynamic algebras with one quantifier). Similarly to a theorem of Kozen we establish that every separable monadic dynamic algebra is isomorphic to a monadic (possibly non‐standard) Kripke structure. We also classify the simple (monadic) dynamic algebras. Moreover, in the dynamic duality theory, we analyze the conditions under which a hemimorphism of a dynamic algebra into itself defines a quantifier. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Notes on monadic logic. Part B: Complexity of linear orders in ZFC

In those notes we prove in ZFC: (a) that the monadic theory of linear order (syntactically) interprets and has the same Lowenheim number as second order logic (the interpretation is semantical but not in the “classical” way), (b) a parallel (weaker) result for the monadic logic for completely metrizable spaces. The main results are in §§5, 6. The author would like to thank the United States-Israel Binational Science Foundation for partially supporting this research, and Alice Leonhardt for the beautiful typing. Publication No. 284b.     

Automata transformations of prefix decidable and decidable by Buchi superwords

We show that the set of prefix decidable superwords is closed under finite automata and asynchronous automata transformations. We prove that structures of degrees of finite automata and asynchronous automata transformations contain an atom which consists of prefix decidable superwords with undecidable monadic theory (or undecidable by Buchi). Also we prove that the structure of degrees of asynchronous automata transformations contains an atom which consists of superwords with decidable monadic theory (decidable by Buchi).     

Monadic theory of order and topology, 1

We deal with the monadic theory of linearly ordered sets and topological spaces, disprove two of Shelah’s conjectures and prove some more results. In particular, if the Continuum Hypothesis holds, then there exist monadic formulae expressing the predicates “X is countable” and “X is meager” in the real line and in Cantor’s Discontinuum.     

Topological representation for monadic implication algebras

In this paper, every monadic implication algebra is represented as a union of a unique family of monadic filters of a suitable monadic Boolean algebra. Inspired by this representation, we introduce the notion of a monadic implication space, we give a topological representation for monadic implication algebras and we prove a dual equivalence between the category of monadic implication algebras and the category of monadic implication spaces.      

Monadic Algebras with finite degree

A monadic algebraA has finite degreen ifA/M has at most 2 ⁿ elements for every maximal idealM ofA and this bound is obtained for someM. Every countable monadic algebra with a finite degree is isomorphic to an algebra Γ(X, S) whereX is a Boolean space andS is a subsheaf of a constant sheaf with a finite simple stalk. This representation is used to prove that every proper equational class of monadic algebras has a decidable first-order theory.     

Fonctions généralisées et analyse non standard

We study some connections between Non-Standard Analysis and algebraical theories of generalized functions. More precisely, we point out the fact that the construction of these algebras can be interpreted in terms of Non Standard asymptotic properties. For example, we show that the construction of the J. F. Colombeau'Algebra is equivalent (in a certain sense) to a monadic property. Conversely, we show that a certain galactic property (being exponentially small with respect to a parameter) leads to a new algebra.

     

Free monadic Tarski algebras

A. Monteiro and L. Iturrioz [7], introduced the notion of monadic Tarski algebras as a generalization of the monadic Boolean algebras considered by P. Halmos [6]. They represent the algebraic version of a fragment of the functional monadic calculus. In this paper we determine the structure of the monadic Tarski algebras with a finite set of free generators.Presented by B. Jónsson.The author is grateful for many valuable comments and suggestions from the referee.     

Simple monadic theories and indiscernibles

Aiming for applications in monadic second‐order model theory, we study first‐order theories without definable pairing functions. Our main results concern forking‐properties of sequences of indiscernibles. These turn out to be very well‐behaved for the theories under consideration (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Functional monadic Heyting algebras

We show every monadic Heyting algebra is isomorphic to a functional monadic Heyting algebra. This solves a 1957 problem of Monteiro and Varsavsky [9]. Received May 18, 2001; accepted in final form October 18, 2001.     

INSTANCES AND RAMIFICATIONS OF THE SEMI-ADJOINT SITUATION II. THE COMPARISON FUNCTOR

Abstract

If a functor U has a left co-unadjoint then U can be factored through a category of semad algebras. An analogue of the Beck monadicity theory is obtained. If R is a ring without a left unit but satisfying R² = R then the category of unitary left R-modules need not be monadic over Set. The forgetful functor has, however, a left co-unadjoint for which a comparison functor is an equivalence of categories. Another example of a semadic functor is obtained by composing the forgetful functor from Abelian groups to Set with the doubling functor. The semi-adjoint situations in the senses of Medvedev and Davis are examined.     

Complete systems of monadic predicates for post classes

The problem of completeness of arbitrary systems of monadic predicates defined on finite sets is considered. Completeness criteria are obtained for an arbitrary system of monadic predicates over arbitrary set of Boolean functions.     

Monadic second-order model-checking on decomposable matroids

A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows one to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.     

Logical laws for existential monadic second-order sentences with infinite first-order parts

We consider existential monadic second-order sentences ?X φ(X) about undirected graphs, where ?X is a finite sequence of monadic quantifiers and φ(X) ∈ +_∞ω^ω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.     

Characterizations of Morita equivalent inverse semigroups

We prove that four different notions of Morita equivalence for inverse semigroups motivated by C^∗-algebra theory, topos theory, semigroup theory and the theory of ordered groupoids are equivalent. We also show that the category of unitary actions of an inverse semigroup is monadic over the category of étale actions. Consequently, the category of unitary actions of an inverse semigroup is equivalent to the category of presheaves on its Cauchy completion. More generally, we prove that the same is true for the category of closed actions, which is used to define the Morita theory in semigroup theory, of any semigroup with right local units.