We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has non-empty interior, and any theory of pure tree is dp-minimal.

We prove a dichotomy theorem for minimal structures and use it to prove that the number of non-isomorphic countable elementary extensions of an arbitrary countable, infinite first-order structure is infinite.

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence Φ iff Φ holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all Φ for which the associated (...) sequence of propositional formulas 〈Φ〉 n , encoding that Φ holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all Φ feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy Φ thus gives a super polynomial lower bound for the size of P-proofs of 〈Φ〉 n . We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R * (log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures. (shrink)

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 119–145] (...) of D)=log1/pn+O. (shrink)

We show that infinite sets whose power-sets are Dedekind-finite can only carry N₀-categorical first order structures. We identify other subclasses of this class of Dedekind-finite sets, and discuss their possible first order structures.

We show that for random bit strings, Up, with probability, image, the first order quantifier depth D) needed to distinguish non-isomorphic structures is Θ, with high probability. Further, we show that, with high probability, for random ordered graphs, G≤,p with edge probability image, D)=Θ, contrasting with the results for random graphs, Gp, given by Kim et al. [J.H. Kim, O. Pikhurko, J. Spencer, O. Verbitsky, How complex are random graphs in first order logic? Random Structures and Algorithms 26 119–145] (...) of D)=log1/pn+O. (shrink)

We introduce a notion of simplicity for types in discretely ordered first order structures. We prove that all the structure on the locus of a simple type is induced exclusively by the ordering relation. As an application we determine all possible expansions of satisfying CB = 1.

O-minimal structures have long been thought to occupy the base of a hierarchy of ordered structures, in analogy with the role that strongly minimal structures play with respect to stable theories. This is the first in an anticipated series of papers whose aim is the development of model theory for ordered structures of rank greater than one. A class of ordered structures to which a notion of finite rank can be assigned, the decomposable structures, is introduced here. (...) These include all ordered structures definable in o-minimal structures. The principal result in this paper, Theorem 5.1, asserts roughly that a decomposable structure [Formula: see text] can be partitioned into finitely many definable subsets such that on each set the restriction of < is a "twisted lexicographic" order. As a consequence, for all n and linear orders ≺ definable on a subset X ⊆ Mn in an o-minimal structure [Formula: see text], there is a definable partition of X such that the restriction of ≺ to each set in the partition is "lexicographic". (shrink)

We show that the 'tail' of a doubly homogeneous chain of countable cofinality can be recognized in the quotient of its automorphism group by the subgroup consisting of those elements whose support is bounded above. This extends the authors' earlier result establishing this for the rationals and reals. We deduce that any group is isomorphic to the outer automorphism group of some simple lattice-ordered group.

A continuum is here a primitive notion intended to correspond precisely to a path-connected subset of the usual euclidean space. In contrast, however, to the traditional treatment, we treat here continua not as pointsets, but as irreducible entities equipped only with a partial ordering ≤ interpreted as parthood. Our aim is to examine what basic topological and geometric properties of continua can be expressed in the language of ≤, and what principles we need in order to prove elementary facts about (...) them. Surprisingly enough ≤ suffices to formulate the very heart of continuity (=jumpless and gapless transitions) in a general setting. Further, using a few principles about ≤ (together with the axioms of ZFC), we can define points, joins, meets and infinite closeness. Most important, we can develop a dimension theory based on notions like path, circle, line (=one-dimensional continuum), simple line and surface (=two-dimensional continuum), recovering thereby in a rigorous way Poincaré's well-known intuitive idea that dimension expresses the ways in which a continuum can be torn apart. We outline a classification of lines according to the number of circles and branching points they contain. The ordering (C,≤) is a topped and bottomed, atomic, almost dense and complete partial ordering, weaker than a lattice. Continuous transformations from C to C are also defined in a natural way and results about them are proved. (shrink)

A topos version of Cantor’s back and forth theorem is established and used to prove that the ordered structure of the rational numbers (Q, <) is homogeneous in any topos with natural numbers object. The notion of effective homogeneity is introduced, and it is shown that (Q, <) is a minimal effectively homogeneous structure, that is, it can be embedded in every other effectively homogeneous ordered structure.

We show, for various classes of totally ordered structures, including o‐minimal and weakly o‐minimal structures, that every definable partial order on a subset of extends definably in to a total order. This extends the result proved in for and o‐minimal.

A structure M is pregeometric if the algebraic closure is a pregeometry in all structures elementarily equivalent to M. We define a generalisation: structures with an existential matroid. The main examples are superstable groups of Lascar U-rank a power of ω and d-minimal expansion of fields. Ultraproducts of pregeometric structures expanding an integral domain, while not pregeometric in general, do have a unique existential matroid. Generalising previous results by van den Dries, we define dense elementary pairs of structures expanding (...) an integral domain and with an existential matroid, and we show that the corresponding theories have natural completions, whose models also have a unique existential matroid. We also extend the above result to dense tuples of structures. (shrink)

We explore analogues of o-minimality and weak o-minimality for circularly ordered sets. Much of the theory goes through almost unchanged, since over a parameter the circular order yields a definable linear order. Working over ∅ there are differences. Our main result is a structure theory for ℵ0-categorical weakly circularly minimal structures. There is a 5-homogeneous example which is not 6-homogeneous, but any example which is k-homogeneous for some k ≥ 6 is k-homogeneous for all k.

This paper is a contribution to graded model theory, in the context of mathematical fuzzy logic. We study characterizations of classes of graded structures in terms of the syntactic form of their first-order axiomatization. We focus on classes given by universal and universal-existential sentences. In particular, we prove two amalgamation results using the technique of diagrams in the setting of structures valued on a finite MTL-algebra, from which analogues of the Łoś–Tarski and the Chang–Łoś–Suszko preservation theorems follow.

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not (...) always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures L C . These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L NP . This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993]. (shrink)

Word order alternation has been described as one of the most productive information structure markers and discourse organizers across languages. Psycholinguistic evidence has shown that word order is a crucial cue for argument interpretation. Previous studies about Spanish sentence comprehension have shown greater difficulty to parse sentences that present a word order that does not respect the order of participants of the verb's lexico-semantic structure, irrespective to whether the sentences follow the canonical word order of the language or (...) not. This difficulty has been accounted as the cognitive cost related to the miscomputation of prominence status of the argument that precedes the verb. Nonetheless, the authors only analyzed the use of alternative word orders in isolated sentences, leaving aside the pragmatic motivation of word order alternation. By means of an eye-tracking task, the current study provides further evidence about the role of information structure for the comprehension of sentences with alternative word order and verb type, and sheds light on the interaction between syntax, semantics and pragmatics. We analyzed both “early” and “late” eye-movement measures as well as accuracy and response times to comprehension questions. Results showed an overall influence of information structure reflected in a modulation of late eye-movement measures as well as offline measures like total reading time and questions response time. However, effects related to the miscomputation of prominence status did not fade away when sentences were preceded by a context that led to non-canonical word order of constituents, showing that prominence computation is a core mechanism for argument interpretation, even in sentences preceded by context. (shrink)

We prove a model theoretic generalization of an extension of the Keisler-Morley theorem for countable recursively saturated models of theories having a K-like model, where K is an inaccessible cardinal.

The logics of formal inconsistency (LFIs, for short) are paraconsistent logics (that is, logics containing contradictory but non-trivial theories) having a consistency connective which allows to recover the ex falso quodlibet principle in a controlled way. The aim of this paper is considering a novel semantical approach to first-order LFIs based on Tarskian structures defined over swap structures, a special class of multialgebras. The proposed semantical framework generalizes previous aproaches to quantified LFIs presented in the literature. The case of QmbC, (...) the simpler quantified LFI expanding classical logic, will be analyzed in detail. An axiomatic extension of QmbC called QLFI1o is also studied, which is equivalent to the quantified version of da Costa and D'Ottaviano 3-valued logic J3. The semantical structures for this logic turn out to be Tarkian structures based on twist structures. The expansion of QmbC and QLFI1o with a standard equality predicate is also considered. (shrink)

Let T be a countable complete first-order theory with a definable, infinite, discrete linear order. We prove that T has continuum-many countable models. The proof is purely first order, but it raises the question of Borel completeness of T.

This chapter is concerned with the question to what extent free word order phenomena are regulated by information-structural constraints. Progress on this question must combine detailed empirical study with bold theoretical work that aims to test restrictive hypotheses about available syntactic operations, available IS-primitives, and their mapping. The present chapter evaluates four cross-cutting word order generalizations on the basis of a rough classification of syntactic operations and IS-primitives. Operations will be divided into those that are A-related, those that are A′-related, (...) those that involve doubling with a pronoun or clitic, and finally those that involve extraposition, and it is assumed that IS-primitives are restricted to topic, focus, contrast, and givenness. Some discussion is offered of how the four generalizations identified here might emerge as effects of deeper properties of the language faculty or human psychology. (shrink)

Being building block of data sciences, link prediction plays a vital role in revealing the hidden mechanisms that lead the networking dynamics. Since many techniques depending in vertex similarity and edge features were put forward to rule out many well-known link prediction challenges, many problems are still there just because of unique formulation characteristics of sparse networks. In this study, we applied some graph transformations and several inequalities to determine the greatest value of first and second Zagreb invariant, S K (...) and S K 1 invariants, for acyclic connected structures of given order, diameter, and pendant vertices. Also, we determined the corresponding extremal acyclic connected structures for these topological indices and provide an ordering giving a sequence of acyclic connected structures having these indices from greatest in decreasing order. (shrink)

Two recent conversation analytical studies draw contrary conclusions from seemingly very similar materials. Hutchby and Barnett ‘show that, far from revolutionizing the organization of telephone conversation, mobile phone talk retains many of the norms associated with landline phone talk’. Arminen and Leinonen, however, state that landline and mobile calls differ systematically from each other. These incommensurate findings raise the question of why the comparisons between landline and mobile call openings have not been able to determine whether social and communicative practices (...) are changing. It is suggested that auxiliary elements in CA allow the emergence of incompatible findings. The auxiliary assumptions enable authors to construct the phenomenon examined from their chosen perspective. Further, it will be shown that unquestioned assumptions materialize into theoretical notions that guide the research. CA studies seem to conceptualize the relationship between sequential order and sequence structure in different ways, which leads to different findings and results. (shrink)

We propose a notion of -minimality for partially ordered structures. Then we study -minimal partially ordered structures such that is a Boolean algebra. We prove that they admit prime models over arbitrary subsets and we characterize -categoricity in their setting. Finally, we classify -minimal Boolean algebras as well as -minimal measure spaces.

Contemporary architecture is increasingly grounded in science and mathematics. Architectural discourse has shifted radically from the sometimes disorienting Derridean deconstruction, to engaging scientific terms such as fractals, chaos, complexity, nonlinearity, and evolving systems. That's where the architectural action is -- at least for cutting-edge architects and thinkers -- and every practicing architect and student needs to become conversant with these terms and know what they mean. Unfortunately, the vast majority of architecture faculty are unprepared to explain them to students, not (...) having had a scientific education themselves. Here is an architecture book by an architect/scientist, just in time to help architects in the new millennium. Alexander discusses many of the scientific terms arising in cutting-edge architecture, and explains them to those who don't have scientific training or advanced mathematical knowledge. We find discussions of the evolution of forms; the importance of process in design; iteration; genetic algorithms; sequences of transformations; different levels of scale (i.e. fractals); etc. They are explained here by an architect who is also a scientist, because he wants to change the way architects think and build. Alexander is not merely popularizing other scientists' results and making them accessible to architects: he is in fact presenting new and original scientific work that ties many of these concepts together in a way that will be useful to architects. (shrink)

We give a construction assigning classes of Boolean algebras to first-order theories; several classes of Boolean algebras considered previously in the literature can be thus obtained. In particular it turns out that the class of semigroup algebras can be defined in this way, in fact by a Horn theory, and it is the largest class of Boolean algebras defined by a Horn theory.

This paper presents a sound and complete five-sided sequent calculus for first-order weak Kleene valuations which permits not only elegant representations of four logics definable on first-order weak Kleene valuations, but also admissibility of five cut rules by proof analysis.

The study of graph structure has advanced in recent years with great strides: finite graphs can be described algebraically, enabling them to be constructed out of more basic elements. Separately the properties of graphs can be studied in a logical language called monadic second-order logic. In this book, these two features of graph structure are brought together for the first time in a presentation that unifies and synthesizes research over the last 25 years. The author not only provides (...) a thorough description of the theory, but also details its applications, on the one hand to the construction of graph algorithms, and, on the other to the extension of formal language theory to finite graphs. Consequently the book will be of interest to graduate students and researchers in graph theory, finite model theory, formal language theory, and complexity theory. (shrink)