Elementary theories of completely simple semigroups

The connections between first-order formulas over a completely simple semigroupC and corresponding formulas over its structure groupH are found in this paper. For the case of finite sandwich-matrix the criterion of decidability of the elementary theoryT(C) is established in terms of the elementary theory ofH in the enriched signature (Theorem 1). For the general case the criterion is established in terms of two-sorted algebraic systems (Theorem 2). Sufficient conditions in terms ofH for decidability and for undecidability ofT(C) are outlined. Corollaries and examples are presented, among them an example of a completely simple semigroup with a finite structure group and with undecidable elementary theory (Theorem 3).     

Extensions completes d'une theorie forcing complete

We give two examples of a universal theoryT such that the forcing companionT ^F (as defined by A. Robinson for infinite forcing) has some model which is not the elementary equivalent of a generic model ofT. Our examples answer in a negative way a question posed by E. Fisher and A. Robinson. In the first example, forT ^F, there is an extensionT′ which is complete and forcing comcomplete (that is, (T′) ^F=T′) not generated by a generic model ofT. In the second exampleT ^F has a complete extensionT′ which is not forcing complete.      

Definibility in normal theories

This paper initiates an investigation which seeks to explain elementary definability as the classical results of mathematicallogic (the completeness, compactness and Löwenheim-Skolem theorems) explain elementary logical consequence. The theorems of Beth and Svenonius are basic in this approach and introduce automorphism groups as a means of studying these problems. It is shown that for a complete theoryT, the definability relation of Beth (or Svenonius) yields an upper semi-lattice whose elements (concepts) are interdefinable formulas ofT (formulas having equal automorphism groups in all models ofT). It is shown that there are countable modelsA ofT such that two formulae are distinct (not interdefinable) inT if and only if they are distinct (have different automorphism groups) inA. The notion of a concepth being normal in a theoryT is introduced. Here the upper semi-lattice of all concepts which defineh is proved to be a finite lattice—anti-isomorphic to the lattice of subgroups of the corresponding automorphism group. Connections with the Galois theory of fields are discussed.     

Theories of linear order

LetT be a complete theory of linear order; the language ofT may contain a finite or a countable set of unary predicates. We prove the following results. (i) The number of nonisomorphic countable models ofT is either finite or 2^ω. (ii) If the language ofT is finite then the number of nonisomorphic countable models ofT is either 1 or 2^ω. (iii) IfS ₁(T) is countable then so isS _n(T) for everyn. (iv) In caseS ₁(T) is countable we find a relation between the Cantor Bendixon rank ofS ₁(T) and the Cantor Bendixon rank ofS _n(T). (v) We define a class of modelsL, and show thatS ₁(T) is finite iff the models ofT belong toL. We conclude that ifS ₁(T) is finite thenT is finitely axiomatizable. (vi) We prove some theorems concerning the existence and the structure of saturated models. Most of the results in this paper appeared in the author’s Master of Science thesis which was prepared at the Hebrew University under the supervision of Professor H. Gaifman.     

Finding model-companions via the skeleton

We present an analysis on the existentially closed (e.c.) structures for some theoryT in a rather complete categorical setting. The central notion of the skeleton ofT is defined. We formulate conditions on the skeleton which limit the number of e.c. structures forT, thereby ensuring the existence of a model-companion ofT. A new (purely categorical) proof of the uniqueness of the atomic structure is given for theories having the joint-embedding-property (JEP).As an application it is shown that a finitely generated universal Horn class possesses a model-companion — a resuilt that was proved earlier by a different method.Presented by Stanley Burris.     

On the number of homogeneous models of a given power

It is shown that, For each complete theoryT, the nomberh _T(m) of homogeneous models ofT of powerm is a non-increasing function of uncountabel cardinalsm Moreover, ifh _T(ℵ₀)≦ℵ₀, then the functionh _T is also non-increasing ℵ₀ to ℵ₁. This work was supported in part by NSF contracts GP 4257 and GP5913.     

On the eigenvalue problem for toeplitz matrices generated by rational functions

Formulas are given for the characteristic polynomials {p_n (λ)}and the eigenvectors of the family {T_n }of Toeplitz matrices generated by a formal Laurent series of rational function R(z). The formulas are in terms of the zeros of a certain fixed polynomial with coefficients which are simple functions of λ and the coefficients of R(z). The complexity of the formulas is independent ofn.     

All Finitely Axiomatizable Normal Extensions of K4.3 are Decidable

We use the apparatus of the canonical formulas introduced by Zakharyaschev [10] to prove that all finitely axiomatizable normal modal logics containing K4.3 are decidable, though possibly not characterized by classes of finite frames. Our method is purely frame-theoretic. Roughly, given a normal logic L above K4.3, we enumerate effectively a class of (possibly infinite) frames with respect to which L is complete, show how to check effectively whether a frame in the class validates a given formula, and then apply a Harropstyle argument to establish the decidability of L, provided of course that it has finitely many axioms.     

Topologically Complete Representations of Inverse Semigroups

A representation of an inverse semigroup by means of partial open homeomorphisms of a topological T ₀ -space is called topologically complete if the domains of these partial homeomorphisms form a base of the topology. It is shown how to construct topologically complete representations on the base of a ternary relation satisfying some elementary axioms. This result makes it possible to obtain a pseudo-elementary axiomatization for inverse semigroups that have faithful topologically complete representations in T ₁ ,T ₂ and T ₃ -spaces. A topology is introduced on any antigroup; this topology is a concomitant of the algebraic structure and every topologically complete representation is continuous with respect to this topology.     

Remark on Kreisel's conjecture

At the end of the 60's, Kreisel conjectured that formal arithmetics admit infinite induction rules if the lengths of proofs of their premises are uniformly bounded by the same number. By the length of a proof we mean the number of applications of axioms and rules of inference. In this article we construct a theory R ^* with a finite number of specific axioms. The language of R ^* contains a constant 0, a unary function symbol, equality, and ternary predicates for addition and multiplication. It is proved that for any consistent axiomatizable extensionR^* it is possible to find a formula A(a) that satisfies the following conditions: a) xA(x) cannot be derived in; b) for any n the length of the proof of the formula A(0⁽ⁿ⁾) is no greater than c₁[log₂ (n+1)]+c₂, where the constants c₁ and c₂ are independent of n. Here the expression 0⁽ⁿ⁾ indicates 0 with n primes.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institua im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 118–126, 1989.     

1-based theories — the main gap fora-models

We prove the Main Gap for the class ofa-models (sufficiently saturated models) of an arbitrary stable 1-based theoryT. We (i) prove a strong structure theorem fora-models, assuming NDOP, and (ii) roughly compute the number ofa-models ofT in any given cardinality.The analysis uses heavily group existence theorems in 1-based theories.Authors partially supported by the NSERC, and by NSF grants DMS90-06628 and DMS92-03399     

Funny rank-one weak mixing for nonsingular Abelian actions

We construct funny rank-one infinite measure preserving free actionsT of a countable Abelian groupG satisfying each of the following properties: (1)T _g1×…×T_gk is ergodic for each finite sequenceg ₁,…,g _k ofG-elements of infinite order, (2)T×T is nonconservative, (3)T×T is nonergodic but allk-fold Cartesian products are conservative, and theL ^∞-spectrum ofT is trivial, (4) for eachg of infinite order, allk-fold Cartesian products ofT _g are ergodic, butT _2g×T_g is nonconservative. A topological version of this theorem holds. Moreover, given an AT-flowW, we construct nonsingularG-actionsT with similar properties and such that the associated flow ofT isW. Orbit theory is used in an essential way here. The work was supported in part by INTAS 97-1843 and CRDF grant UM1-2092.     

Idealization of Some Weak Separation Axioms

An ideal is a nonempty collection of subsets closed under heredity and finite additivity. The aim of this paper is to unify some weak separation properties via topological ideals. We concentrate our attention on the separation axioms between T ₀ and T _1/2. We prove that if (X,,I) is a semi-Alexandroff T _I -space and I is a -boundary, then I is completely codense.     

Counting colorful multi-dimensional trees

LetV be a disjoint union ofr finite setsV ₁,...,V _r (colors). A collectionT of subsets ofV iscolorful if each member ifT contains at most one point of each color. Ak-dimensional colorful tree is a colorful collectionT of subsets ofV, each of sizek+1, such that if we add toT all the colorful subsets ofV of sizek or less, we get aQ-acyclic simplicial complex _T We count (using the Binet-Cauchy theorem) thek-dimensional colorful trees onV (for allk), where each treeT is counted with weight . The result confirms, in a way, a formula suggested by Bolker. (fork-r–1). It extends, on one hand, a result of Kalai on weighted counting ofk-dimensional trees and, on the other hand, enumeration formulas for multi-partite (1-dimensional) trees. All these results are extensions of Cayley's celebrated treecounting formula, now 100 years old.     

Nearly Model Complete Theories

A theory T of a language L is 1-model complete (nearly model complete) iff for every formula ρ of L there is a formula ? (χ) of L which is a ??-formula (a Boolean combination of universal formulas) such that T ? ?x [??θ]. The main results of the paper give characterizations of nearly model complete theories and of 1-model complete theories. As a consequence we obtain that a theory T is nearly model complete iff whenever ?? is a model of T and ???₁??, then T ∪ Δ¹_?? is a complete L(A)-theory, where Δ¹_?? is the 1-diagram of ??. We also point out that our main results extend to (n + l)-model complete and nearly ra-model complete theories for all n > 0.     

Invariants forω-categorical,ω-stable theories

In this paper we give a complete solution to the classification problem forω-categorical,ω-stable theories. More explicitly, supposeT isω-categorical,ω-stable with fewer than the maximum number of models in some uncountable power. We associate with each modelM ofT a “simple” invariantI(M), not unlike a vector of dimensions, such thatI(M)=I(N) if and only ifM≅N. The spectrum function,I(−,T), for a first-order theoryT is such that for all infinite cardinals λ,I(λ,T) is the number of nonisomorphic models ofT of cardinality λ. As an application of our “structure theorem” we determine the possible spectrum functions forω-categorical,ω-stable theories.     

Almost stable spectra and limits of similarities

Suppose that {D _n } is a sequence of invertible operators on a Hilbert space, andD _n T D _n ^–1 converges in norm toT ₀. Recently, H. Bercovici, C. Foias, and A. Tannenbaum have shown that if {D _n ^±1 n=1, 2,...} is contained in a finite dimensional subspace of operators, thenT andT ₀ must have the same spectral radius. Using this result, R. Teodorescu proved that the resolvents ofT andT ₀ have the same unbounded component. We show that in fact the spectra differ only by certain eigenvalues ofT ₀, and the spectrum ofT ₀ is obtained by filling in holes in the spectrum ofT; i.e., by adjoining (all, some, or none of the) bounded components of the resolvent ofT to the spectrum ofT.     

Approximation du spectre d'un operateur lineaire; application aux operateurs differentiels elliptiques non autoadjoints

To be computed, the eigenvalues of a closed linear operatorT in a Banach space are usually approximated by the eigenvalues ofT h, a linear operator approximatingT in a finite dimensional space (for example, finite difference method, Galerkin method),h is a parameter which tends to 0. This approximation is studied in [2]; stability ofT h implies the continuity of the spectrum ofT h, whenh tends to 0.We present here a new kind of sufficient condition. For that purpose, we disconnect the continuity of the spectrum ofT h into lower and upper semicontinuities. And we give two different criteria for these semi-continuities. Applications to the approximation of nonselfadjoint elliptic operators by finite difference schemes, are given.     

A minimax theorem for irreducible compact operators inL p-spaces

Let (X, Σ, μ) be a σ-finite measure space,T a compact irreducible (positive, linear) operator onL ^p (μ) (1≦p<+∞). It is shown that the spectral radiusr ofT is characterized by the minimax property {fx196-1} where ∑₀ denotes the ring of sets of finite measure and whereQ denotes the set of all, almost everywhere positive functions inL ^p. Moreover, ifr>0 then equality on either side is assumed ifff is the (essentially unique) positive eigenfunction ofT. Various refinements are given in terms of corresponding relations for irreducible finite rank operators approximatingT. Dedicated to H. G. Tillmann on his 60th birthday