We study classes of graded structures satisfying the properties of amalgamation, joint embedding and hereditariness. Given appropriate conditions, we can build a graded analogue of the Fraïssé limit. Some examples such as the class of all finite weighted graphs or the class of all finite fuzzy orders (evaluated on a particular countable algebra) will be examined.

A general method for constructing a new class of topological Ramsey spaces is presented. Members of such spaces are infinite sequences of products of Fraïssé classes of finite relational structures satisfying the Ramsey property. The Product Ramsey Theorem of Sokič is extended to equivalence relations for finite products of structures from Fraïssé classes of finite relational structures satisfying the Ramsey property and the Order-Prescribed Free Amalgamation Property. This is essential to proving Ramsey-classification theorems for equivalence relations on (...) fronts, generalizing the Pudlák–Rödl Theorem to this class of topological Ramsey spaces. To each topological Ramsey space in this framework corresponds an associated ultrafilter satisfying some weak partition property. By using the correct Fraïssé classes, we construct topological Ramsey spaces which are dense in the partial orders of Baumgartner and Taylor generating p-points which are k-arrow but not \-arrow, and in a partial order of Blass producing a diamond shape in the Rudin-Keisler structure of p-points. Any space in our framework in which blocks are products of n many structures produces ultrafilters with initial Tukey structure exactly the Boolean algebra \\). If the number of Fraïssé classes on each block grows without bound, then the Tukey types of the p-points below the space’s associated ultrafilter have the structure exactly \. In contrast, the set of isomorphism types of any product of finitely many Fraïssé classes of finite relational structures satisfying the Ramsey property and the OPFAP, partially ordered by embedding, is realized as the initial Rudin-Keisler structure of some p-point generated by a space constructed from our template. (shrink)

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in Ehrenfeucht- (...) class='Hi'>Fraïssé type games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (shrink)

In this paper, we introduce the notion of $${\textbf{K}} $$ -rank, where $${\textbf{K}} $$ is a strong amalgamation Fraïssé class. Roughly speaking, the $${\textbf{K}} $$ -rank of a partial type is the number “copies” of $${\textbf{K}} $$ that can be “independently coded” inside of the type. We study $${\textbf{K}} $$ -rank for specific examples of $${\textbf{K}} $$, including linear orders, equivalence relations, and graphs. We discuss the relationship of $${\textbf{K}} $$ -rank to other ranks in model theory, including (...) dp-rank and op-dimension (a notion coined by the first author and C. D. Hill in previous work). (shrink)

We show that every two-dimensional class of topological similarity, and hence every diagonal conjugacy class of pairs, is meager in the group of order preserving bijections of the rationale and in the group of automorphisms of the ordered rational Urysohn space.

Two structures A and B are n-equivalent if Player II has a winning strategy in the n-move Ehrenfeucht-Fraïssé game on A and B. In earlier articles we studied n-equivalence classes of ordinals and coloured ordinals. In this article we similarly treat a class of scattered order-types, focussing on monomials and sums of monomials in ω and its reverse ω*.

The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.

We realize the Jiang-Su algebra, all UHF algebras, and the hyperfinite II1factor as Fraïssé limits of suitable classes of structures. Moreover by means of Fraïssé theory we provide new examples of AF algebras with strong homogeneity properties. As a consequence of our analysis we deduce Ramsey-theoretic results about the class of full-matrix algebras.

We say that a linear ordering is extendible if every partial ordering that does not embed can be extended to a linear ordering which does not embed either. Jullien’s theorem is a complete classification of the countable extendible linear orderings. Fraïssé’s conjecture, which is actually a theorem, is the statement that says that the class of countable linear ordering, quasiordered by the relation of embeddability, contains no infinite descending chain and no infinite antichain. In this paper we study (...) the strength of these two theorems from the viewpoint of Reverse Mathematics and Effective Mathematics. As a result of our analysis we get that they are equivalent over the basic system of .We also prove that Fraïssé’s conjecture is equivalent, over , to two other interesting statements. One that says that the class of well founded labeled trees, with labels from {+,−}, and with a very natural order relation, is well quasiordered. The other statement says that every linear ordering which does not contain a copy of the rationals is equimorphic to a finite sum of indecomposable linear orderings.While studying the proof theoretic strength of Jullien’s theorem, we prove the extendibility of many linear orderings, including ω2 and η, using just . Moreover, for all these linear orderings, , we prove that any partial ordering, , which does not embed has a linearization, hyperarithmetic in , which does not embed. (shrink)

In this paper, we present a version of Fraïssé theory for categories of metric structures. Using this version, we show that every UHF algebra can be recognized as a Fraïssé limit of a class of C*-algebras of matrix-valued continuous functions on cubes with distinguished traces. We also give an alternative proof of the fact that the Jiang–Su algebra is the unique simple monotracial C*-algebra among all the inductive limits of prime dimension drop algebras.

Let L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}$$\end{document} be the language of group theory with n additional new constant symbols c1,…,cn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${c_1,\ldots,c_n}$$\end{document}. In L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${L}$$\end{document} we consider the class K\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathbb{K}}}$$\end{document} of all finite groups G of exponent p>2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${p > 2}$$\end{document}, where G′⊆⟨c1G,…,cnG⟩⊆Z\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${G'\subseteq\langle c_1^G,\ldots,c_n^G\rangle \subseteq Z}$$\end{document} and c1G,…,cnG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${c_1^G,\ldots,c_n^G}$$\end{document} are linearly independent. Using amalgamation we show the existence of Fraïssé limits D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${D}$$\end{document} of K\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathbb{K}}}$$\end{document}. D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${D}$$\end{document} is Felgner’s extra special p-group. The elementary theories of the D\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${D}$$\end{document} are supersimple of SU-rank 1. They have the independence property. (shrink)

In this paper, we initiate the study of Ehrenfeucht–Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call the Ehrenfeucht–Fraïssé problem. Given nω as a parameter, and two relational structures and from one of the classes of structures mentioned above, how efficient is it to decide if Duplicator wins the n-round EF game (...) ? We provide algorithms for solving the Ehrenfeucht–Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. (shrink)

In this dissertation we explore projective Fraïssé theory and its applications, as well as limitations, to the study of compact metrizable spaces. The goal of projective Fraïssé theory is to approximate spaces via classes of finite structures and glean topological or dynamical properties of a space by relating them to combinatorial features of the associated class of structures. Using the framework of compact metrixable structures, we establish general results which expand and help contextualize previous works in the (...) field. Many proofs in the domain of projective Fraïssé theory are carried out in a context dependent fashion and have thus far eluded clean generalizations. A reason is to be found in the lack of a clear understanding of which spaces are amenable to be studied via projective Fraïssé limits. We give both positive and negative results in this direction. We isolate a combinatorial condition which entails a correspondence between finite structures and regular quasi-partitions of compact metrizable spaces. This correspondence greatly aids the combinatorial-toplogical translation. We apply this machinery to study a class of one-dimensional compact metrizable spaces, which we call smooth fences. To this end, we isolate a class of finite structures—finite partial orders whose Hasse diagram is a forest—whose projective Fraïssé limit approximates a distinctive smooth fence with remarkable properties. We call it the Fraïssé fence and characterize it topologically by carefully exploiting the bridge between the combinatorial and topological worlds. We explore homogeneity and universality features of the Fraïssé fence and the properties of its spaces and endpoints, and provide some results on the dynamics of its group of homeomorphisms. The dissertation is partially based on [1, 2]. (shrink)

Assuming certain conditions on a class equation image of finitely generated first-order structures admitting the model-theoretical construction of a Fraïssé limit, we characterize retracts of such limits as algebraically closed structures in a class naturally related to equation image. In this way we generalize an earlier description of retracts of the countably infinite random graph.

In this paper we consider the classes of all continuous $\mathcal {L}$ -(pre-)structures for a continuous first-order signature $\mathcal {L}$. We characterize the moduli of continuity for which the classes of finite, countable, or all continuous $\mathcal {L}$ -(pre-)structures have the amalgamation property. We also characterize when Urysohn continuous $\mathcal {L}$ -(pre)-structures exist, establish that certain classes of finite continuous $\mathcal {L}$ -structures are countable Fraïssé classes, prove the coherent EPPA for these classes of finite continuous $\mathcal {L}$ -structures, (...) and show that actions by automorphisms on finite $\mathcal {L}$ -structures also form a Fraïssé class. As consequences, we have that the automorphism group of the Urysohn continuous $\mathcal {L}$ -structure is a universal Polish group and that Hall’s universal locally finite group is contained in the automorphism group of the Urysohn continuous $\mathcal {L}$ -structure as a dense subgroup. (shrink)

We study smooth classes without the algebraic closure property. For such smooth classes we investigate the simplicity of the class of generic structures, in the context of Robinson theories.

We study the notion of weak amalgamation in the context of diagonal conjugacy classes. Generalizing results of Kechris and Rosendal, we prove that for every countable structure M, Polish group G of permutations of M, and \, G has a comeager n-diagonal conjugacy class iff the family of all n-tuples of G-extendable bijections between finitely generated substructures of M, has the joint embedding property and the weak amalgamation property. We characterize limits of weak Fraïssé classes that are not (...) homogenizable. Finally, we investigate 1- and 2-diagonal conjugacy classes in groups of ball-preserving bijections of certain ordered ultrametric spaces. (shrink)

The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique countably saturated linear order of cardinality \. We provide some examples of pairwise non-isomorphic countably saturated linear orders of cardinality \, under different set-theoretic assumptions. We give a new proof of the old theorem of Harzheim, that the class of countably saturated linear orders has a uniquely determined one-element basis. (...) From our proof it follows that this minimal linear order is a Fraïssé limit of certain Fraïssé class. In particular, it is homogeneous with respect to countable subsets. Next we prove the existence and uniqueness of the uncountable version of the random graph. This graph is isomorphic to \,\in \cup \ni )\), where \\) is the set of hereditarily countable sets, and two sets are connected if one of them is an element of the other. In the last section, an example of a prime countably saturated Boolean algebra is presented. (shrink)

Disjoint n-amalgamation is a condition on a complete first-order theory specifying that certain locally consistent families of types are also globally consistent. In this article, we show that if a countably categorical theory T admits an expansion with disjoint n-amalgamation for all n, then T is pseudofinite. All theories which admit an expansion with disjoint n-amalgamation for all n are simple, but the method can be extended, using filtrations of Fraïssé classes, to show that certain nonsimple theories are pseudofinite. (...) As case studies, we examine two generic theories of equivalence relations, Tfeq∗ and TCPZ, and show that both are pseudofinite. The theories Tfeq∗ and TCPZ are not simple, but they have NSOP1. This is established here for TCPZ for the first time. (shrink)

We present three examples of countable homogeneous structures whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures.Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification, leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums, leading to a Fraïssé class (...) with all finite symmetric groups appearing as automorphism groups and at the same time with a torsion-free automorphism group of its Fraïssé limit. Our last example is a Fraïssé class of finite models with arbitrarily large finite abelian automorphism groups, such that the automorphism group of its Fraïssé limit is again torsion-free. (shrink)

We study those relational structures S with the property that each partition of S contains a block isomorphic to S. We show that the Fraïsse limits of parametric classes K. have property ; over a binary language, every countable structure in K satisfying along with a condition on 1-extensions must be isomorphic to this limit.

We introduce the notion of positive local combinatorial dividing-lines in model theory. We show these are equivalently characterized by indecomposable algebraically trivial Fraïssé classes and by complete prime filter classes. We exhibit the relationship between this and collapse-of-indiscernibles dividing-lines. We examine several test cases, including those arising from various classes of hypergraphs.

We prove the preservation theorems for NATP; many of them extend the previously established preservation results for other model-theoretic tree properties. Using them, we also furnish proper examples of NATP theories which are simultaneously TP2 and SOP. First, we show that NATP is preserved by the parametrization and sum of the theories of Fraïssé limits of Fraïssé classes satisfying strong amalgamation property. Second, the preservation of NATP for two kinds of dense/co-dense expansions, i.e. the theories of lovely pairs (...) and of [Formula: see text]-structures for geometric theories, and dense/co-dense expansion on vector spaces is proved. Next, we prove the preservation of NATP for the generic predicate expansion and the pair of an algebraically closed field and its distinguished subfield; for the latter, not only NATP, but also the preservation of NTP1 and NTP2 is considered. Finally, we present some proper examples of NATP theories using the results proved in this paper, including the parametrization of DLO and the expansion of an algebraically closed field by adding a generic linear order. In particular, we show that the model companion of the theory of algebraically closed fields with circular orders (ACFO) is NATP. (shrink)

We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of (...) all ${\cal F}$-free structures, and the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics. (shrink)

We consider${\cal S}$, the class of finite semilattices;${\cal T}$, the class of finite treeable semilattices; and${{\cal T}_m}$, the subclass of${\cal T}$which contains trees with branching bounded bym. We prove that${\cal E}{\cal S}$, the class of finite lattices with linear extensions, is a Ramsey class. We calculate Ramsey degrees for structures in${\cal S}$,${\cal T}$, and${{\cal T}_m}$. In addition to this we give a topological interpretation of our results and we apply our result to canonization of linear orderings (...) on finite semilattices. In particular, we give an example of a Fraïssé class${\cal K}$which is not a Hrushovski class, and for which the automorphism group of the Fraïssé limit of${\cal K}$is not extremely amenable but is uniquely ergodic. (shrink)

We build a collection of topological Ramsey spaces of trees giving rise to universal inverse limit structures, extending Zheng’s work for the profinite graph to the setting of Fraïssé classes of finite ordered binary relational structures with the Ramsey property. This work is based on the Halpern-Läuchli theorem, but different from the Milliken space of strong subtrees. Based on these topological Ramsey spaces and the work of Huber-Geschke-Kojman on inverse limits of finite ordered graphs, we prove that for each (...) such Fraïssé class, its universal inverse limit structure has finite big Ramsey degrees under finite Baire-measurable colorings. For such Fraïssé classes satisfying free amalgamation as well as finite ordered tournaments and finite partial orders with a linear extension, we characterize the exact big Ramsey degrees. (shrink)

From classical, Fraïissé-homogeneous, ($\leq \omega$)-categorical theories over finite relational languages, we construct intuitionistic theories that are complete, prove negations of classical tautologies, and admit quantifier elimination. We also determine the intuitionistic universal fragments of these theories.

There is a natural map which assigns to every modelU of typeτ, (U ε Stτ) a groupG (U) in such a way that elementarily equivalent models are mapped into isomorphic groups.G(U) is a subset of a collection whose members are called Fraisse arrows (they are decreasing sequences of sets of partial isomorphisms) and which arise in connection with the Fraisse characterization of elementary equivalence. LetEC λ U be defined as {U εStr τ: ℬ ≡U and |ℬ|=λ; thenEG λ U can (...) be faithfully (i.e. 1-1) represented onto G(U) ×π *, whereπ *, is a collection of partitions over λ∪λ2∪.. (shrink)

A Steiner triple system (STS) is a set S together with a collection B of subsets of S of size 3 such that any two elements of S belong to exactly one element of B. It is well known that the class of finite STS has a Fraïssé limit M_F. Here, we show that the theory T of M_F is the model completion of the theory of STSs. We also prove that T is not small and it has (...) quantifier elimination, TP2, NSOP1, elimination of hyperimaginaries and weak elimination of imaginaries. (shrink)

The first-order logical theory Th $({\mathbb{N}},x + 1,F(x))$ is proved to be complete for the class ATIME-ALT $(2^{O(n)},O(n))$ when $F(x) = 2^{x}$ , and the same result holds for $F(x) = c^{x}, x^{c} (c \in {\mathbb{N}}, c \ge 2)$ , and F(x) = tower of x powers of two. The difficult part is the upper bound, which is obtained by using a bounded Ehrenfeucht–Fraïssé game.

Assume that the class of partial automorphisms of the monster model of a complete theory has the amalgamation property. The beautiful automorphisms are the automorphisms of models ofT which: 1. are strong, i.e. leave the algebraic closure (inT eq) of the empty set pointwise fixed, 2. are obtained by the Fraïsse construction using the amalgamation property that we have just mentioned. We show that all the beautiful automorphisms have the same theory (in the language ofT plus one unary function (...) symbol for the automorphism), and we study this theory. In particular, we examine the question of the saturation of the beautiful automorphisms. We also prove that in some cases (in particular if the theory is ω-stable andG-trivial), almost all (in the sense of Baire categoricity) automorphisms of the saturated countable model are beautiful and conjugate. (shrink)

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.

This paper is a contribution to the study of equality-free logic, that is, first-order logic without equality. We mainly devote ourselves to the study of algebraic characterizations of its relation of elementary equivalence by providing some Keisler-Shelah type ultrapower theorems and an Ehrenfeucht-Fraïssé type theorem. We also give characterizations of elementary classes in equality-free logic. As a by-product we characterize the sentences that are logically equivalent to an equality-free one.

We show a faithful restriction theorem among infinite chains which implies a reconstructibility conjecture of Halin. This incite us to study the reconstructibility in the sense of Fraïssé and to prove it for orders of cardinality infinite or ≥ 3 and for multirelations of cardinality infinite or ≥ 7, what improves the theory obtained by G. Lopez in the finite case. For this work we had to study the infinite classes of difference which have to be a linear order (...) of type ω, ω* or ω* + ω; this complete the theory made by G. Lopez for the finite case . We show also Ulam-reconstructibility for linear orders which have a fixed point. (shrink)

The present article, which is a revised version of part of [Hu1], deals with various relations between models which might serve as exact formulations for the vague concept "similar" or "almost isomorphic". One natural class of such formulations is equivalence in a given logic. Another way to express similarity is by potential isomorphism, i.e., isomorphism in some extension of the set-theoretic universe. The class of extensions may be restricted to give different notions of potential isomorphism. A third method (...) is to study the winning strategies for an Ehrenfeucht-Fraisse-game played between the two models, and the properties of the resulting equivalence and nonequivalence trees. The basic question studied here is whether one such notion of similarity implies another. Some implications and counterexamples listed in this part are previously known or trivial, but all are mentioned for completeness' sake. Only models of cardinality ℵ 1 are considered. Some results are therefore connected with the Continuum Hypothesis. (shrink)

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

Fix an integer $r \ge 3$. We consider metric spaces on n points such that the distance between any two points lies in $\left\{ {1, \ldots,r} \right\}$. Our main result describes their approximate structure for large n. As a consequence, we show that the number of these metric spaces is $\left\lceil {{{r + 1} \over 2}} \right\rceil ^{\left + o\left}.$Related results in the continuous setting have recently been proved by Kozma, Meyerovitch, Peled, and Samotij [34]. When r is even, our (...) structural characterization is more precise and implies that almost all such metric spaces have all distances at least $r/2$. As an easy consequence, when r is even, we improve the error term above from $o\left$ to $o\left$, and also show a labeled first-order 0-1 law in the language ${\cal L}_r $, consisting of r binary relations, one for each element of $[r]$. In particular, we show the almost sure theory T is the theory of the Fraïssé limit of the class of all finite simple complete edge-colored graphs with edge colors in $\left\{ {r/2, \ldots,r} \right\}$.Our work can be viewed as an extension of a long line of research in extremal combinatorics to the colored setting, as well as an addition to the collection of known structures that admit logical 0-1 laws. (shrink)

We will show that almost all nonassociative relation algebras are symmetric and integral (in the sense that the fraction of both labelled and unlabelled structures that are symmetric and integral tends to $1$ ), and using a Fraïssé limit, we will establish that the classes of all atom structures of nonassociative relation algebras and relation algebras both have $0$ – $1$ laws. As a consequence, we obtain improved asymptotic formulas for the numbers of these structures and broaden some known (...) probabilistic results on relation algebras. (shrink)

We provide first-order axioms for the theories of finite trees with bounded branching and finite trees with arbitrary (finite) branching. The signature is chosen to express, in a natural way, those properties of trees most relevant to linguistic theories. These axioms provide a foundation for results in linguistics that are based on reasoning formally about such properties. We include some observations on the expressive power of these theories relative to traditional language complexity classes.

In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Fraïssé’s theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets {0}, {1}, K, and L, which are the only orbits of the group (...) of base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non-trivial extensional BCA we know which has this property. (shrink)

Comment supporter d’apprendre ta mort sur une page de journal? À cette place là, tu es tout à coup morte et vivante à la fois. Tu ne nous as pas laissé approcher ta mort ; et la mort t’a si vite attrapée. Mais cela te va bien de t’absenter sans prévenir. Tu nous avais suffisamment confié, il y a très longtemps, que ta santé n’était pas bonne. C’était à nous de te croire. Je t’ai cru alors ; mais je n’ai (...) pas été assez vigilante. Au temps du féminisme allié au gauchisme, nous te rencontrions à... (shrink)

Cet article est une introduction aux études de morphologie urbaine entreprises à Délos depuis quelques années. Les recherches nouvellement menées, qui, à Délos, sont justifiées par l’étendue des surfaces en jeu et par des conditions d’observation particulièrement favorables, ont pour objectif d’apporter un éclairage nouveau sur la ville et de pallier les manques concernant la connaissance et la compréhension de ses caractères morphologiques. La méthode mise en œuvre est présentée au travers des étapes qu’elle est appelée à suivre, chacune faisant (...) l’objet d’une description détaillée. Après avoir complété le plan de la ville par le relevé des secteurs urbanisés jusqu’ici non fouillés, mené une analyse de la forme urbaine à partir de la documentation produite sur chacun des quartiers, et confronté ces résultats à la réalité archéologique, cette recherche pourrait permettre d’éclairer les différents processus d’urbanisation, leurs modalités et leurs règles, en s’efforçant de les replacer dans une perspective chronologique du développement de la ville. (shrink)