If T is a model complete theory with the strict order property, then the theory of the models of T with an automorphism has no model companion.

Let T be a complete, countable, first-order theory with a finite number of countable models. Assuming that dcl(∅) is infinite we show that T has the strict order property.

We study semi-isolation as a binary relation on the locus of a complete type and prove that—under some additional assumptions—it induces the strict order property.

. We study a local version of the order property in several frameworks, with an emphasis on frameworks where the compactness theorem fails: (1) Inside a fixed model, (2) for classes of models where the compactness theorem fails and (3) for the first order case. Appropriate localizations of the order property, the independence property, and the strict order property are introduced. We are able to generalize some of the results that were (...) known in the case of local stability for the first order theories, and for stability for nonelementary classes (existence of indiscernibles, existence of averages, stability spectrum, equivalence between order and instability). In the first order case, we also prove the local version of Shelah's Trichotomy Theorem. Finally, as an application, we give a new characterization of stable types when the ambient first order theory is simple. (shrink)

A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). (...) This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality. (shrink)

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and (...) the latter is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

Our theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theory T with countable D(T) which cannot have a universal model at ℵ1 without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove--again in ZFC--that for a large class of cardinals there is no universal linear order (e.g. in every regular (...) $\aleph_1 < \lambda < 2^{\aleph_0}$). In fact, what we show is that if there is a universal linear order at a regular λ and its existence is not a result of a trivial cardinal arithmetical reason, then λ "resembles" ℵ1--a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras, p-adic rings and fields, partial orders, models of PA and so on). (shrink)

This is a review of "Properties and Propositions: The Metaphysics of Higher-Order Logic" by Robert Trueman. Following an overview of the main themes of the book, I discuss the metaphysical presuppositions of Trueman's Fregean notation for predicate abstraction and evaluate his argument for strict typing.

The elementary theory of a nontrivial free Lie algebra over a commutative integral domain is unstable and has the strict order property.

We study and characterize stability, the negation of the independence property (NIP) and the negation of the strict order property (NSOP) in terms of topological and measure theoretical properties of classes of functions. We study a measure theoretic property, Talagrand's stability, and explain the relationship between this property and the NIP in continuous logic. Using a result of Bourgain, Fremlin, and Talagrand, we prove almost definability and Baire 1 definability of coheirs assuming the NIP. (...) We show that a formula has the strict order property if and only if there is a convergent sequence of continuous functions on the space of φ‐types such that its limit is not continuous. We deduce from this a theorem of Shelah and point out the correspondence between this theorem and the Eberlein‐Šmulian theorem. (shrink)

A class K of structures is controlled if for all cardinals λ, the relation of L∞,λ-equivalence partitions K into a set of equivalence classes . We prove that no pseudo-elementary class with the independence property is controlled. By contrast, there is a pseudo-elementary class with the strict order property that is controlled 69–88).

In their recent article “A Hierarchy of Classical and Paraconsistent Logics”, Eduardo Barrio, Federico Pailos and Damien Szmuc present novel and striking results about meta-inferential validity in various three valued logics. In the process, they have thrown open the door to a hitherto unrecognized domain of non-classical logics with surprising intrinsic properties, as well as subtle and interesting relations to various familiar logics, including classical logic. One such result is that, for each natural number n, there is a logic which (...) agrees with classical logic on tautologies, inferences, meta-inferences, meta-meta-inferences, meta-meta-...-meta-inferences, but that disagrees with classical logic on n + 1-meta-inferences. They suggest that this shows that classical logic can only be characterized by defining its valid inferences at all orders. In this article, I invoke some simple symmetric generalizations of BPS’s results to show that the problem is worse than they suggest, since in fact there are logics that agree with classical logic on inferential validity to all orders but still intuitively differ from it. I then discuss the relevance of these results for truth theory and the classification problem. (shrink)

We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$, which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$. Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of (...) an ω-model of $CD - PB$, then for every $Z \in M$, there is a $G \in M$ such that G is ${\rm{\Delta }}_1^1$-generic relative to Z. (shrink)

The subtle, almost ineffable, and ineffable cardinals were introduced in an unpublished 1971 manuscript of R. Jensen and K. Kunen. The concepts were extended to that of k-subtle, k-almost ineffable, and k-ineffable cardinals in 1975 by J. Baumgartner. In this paper we give a self contained treatment of the basic facts about this level of the large cardinal hierarchy, which were established by J. Baumgartner. In particular, we give a proof that the k-subtle, k-almost ineffable, and k-ineffable cardinals define three (...) properly intertwined hierarchies with the same limit, lying strictly above “total indescribability” and strictly below “arrowing ω”. The innovation here is presented in Section 2, where we take a distinctly minimalist approach. Here the subtle cardinal hierarchy is characterized by very elementary properties that do not mention closed unbounded or stationary sets. This development culminates in a characterization of the hierarchy by means of a striking universal second-order property of linear orderings. (shrink)

This article offers a preliminary critical-historical reconstruction of the concept of dispossession. Part I examines its role in eighteenth- and nineteenth- century struggles against European feudal land tenure. Drawing upon Marx’s critique of French anarchism in particular, I identify a persistent limitation at the heart of the concept. Since dispossession presupposes prior possession, recourse to it appears conservative and tends to reinforce the very proprietary and commoditized models of social relations that radical critics generally seek to undermine. Part II turns (...) to use of the term in Indigenous struggles against colonization, both in order to better grasp the stakes of the above problematic and suggest a way beyond it. Through a reconstruction of arguments by Indigenous scholars and activists, I seek to show the coherence and novelty of their formulation by suggesting that dispossession has come to name a unique historical process, one in which property is generated under conditions that require divestment and alienation from those who appear, only retroactively, as its original owners. In this way, theft and property are related in a recursive, rather than strictly unilinear, manner. Part III provides a specific historical example in the form of nineteenth-century US property law concerning squatters and homesteaders. (shrink)

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As (...) a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)

A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this (...) property until now. We also prove that, over RCA0, INDEC is implied by [Formula: see text] and implies ACA0, but of course, neither ACA0, nor ACA 0+ imply it. We introduce five other statements of hyperarithmetic analysis and study the relations among them. Four of them are related to finitely-terminating games. The fifth one, related to iterations of the Turing jump, is strictly weaker than all the other statements that we study in this paper, as we prove using Steel's method of forcing with tagged trees. (shrink)

By extending the underlying data structure by new elements, we also extend the intput/output relation generated by a program i.e., no existing run is killed, and no new one lying entirely in the old structure is created. We investigate this stability property for the weak second order semantics derived from nonstandard time models. It turns out that the light face, i.e., parameterless collection principle always induces stable semantics, but the bold face one may be unstable. We give an (...) example where an elementary extension kills a bold face run showing also that the light face semantics is strictly weaker than the bold face one. (shrink)

Is the institution of private property part of the natural law? Leo XIII seems to say simply that it is, and many modern Catholic thinkers have followed suit. Aquinas presents a more nuanced view. On the one hand, he denies that the institution of private property is “natural” in the strict sense—unlike the ordering of physical goods to general human use. On the other hand, he maintains that private property does belong to the ius gentium, which (...) is founded directly upon natural law in the strict sense. I argue that this relegation of private property to the ius gentium is necessary in order for Aquinas to coherently maintain that it is licit to “steal” when in dire need, but that this relegation nonetheless does not deprive private property of the kind of “natural” character which Leo XIII ascribes to it. (shrink)

We associate Hanf numbers to triples where T and T1 are theories and p is a type. We show that the Hanf number for the property: “there is a model M1 of which omits p, but is saturated” is larger than the Hanf number of but smaller than the Hanf number of when T is stable with. In fact, surprisingly, we even characterise the Hanf number of when we fix where T is a first order complete (and stable), (...) and demand. (shrink)

The results herein form part of a larger project to characterize the classification properties of the class of submodels of a homogeneous stable diagram in terms of the solvability (in the sense of [1]) of the potential isomorphism problem for this class of submodels. We restrict ourselves to locally saturated submodels of the monster model m of some power π. We assume that in Gödel's constructible universe ������, π is a regular cardinal at least the successor of the first cardinal (...) in which ������ is stable. We show that the collection of pairs of submodels in ������ as above which are potentially isomorphic with respect to certain cardinal-preserving extensions of ������ is equiconstructible with 0 # . As 0 # is highly "transcendental" over ������, this provides a very strong statement to the effect that potential isomorphism for this class of models not only fails to be set-theoretically absolute, but is of high (indeed of the highest possible) complexity. The proof uses a novel method that does away with the need for a linear order on the skeleton. (shrink)

This paper investigates whether there is an acceptable version of Functionalism that avoids commitment to second-order properties. I argue that the answer is "no". I consider two reductionist versions of Functionalism, and argue that both are compatible with multiple realization as such. There is a more specific type of multiple realization that poses difficulties for these views, however. The only apparent Functionalist solution is to accept second-order properties.

We prove a generalization of Maehara’s lemma to show that the extensions of classical and intuitionistic first-order logic with a special type of geometric axioms, called singular geometric axioms, have Craig’s interpolation property. As a corollary, we obtain a direct proof of interpolation for (classical and intuitionistic) first-order logic with identity, as well as interpolation for several mathematical theories, including the theory of equivalence relations, (strict) partial and linear orders, and various intuitionistic order theories such (...) as apartness and positive partial and linear orders. (shrink)

Qualitative Reasoning (QR) is an area of research within Artificial Intelligence that automates reasoning and problem solving about the physical world. QR research aims to deal with representation and reasoning about continuous aspects of entities without the kind of precise quantitative information needed by conventional numerical analysis techniques. Order-of-magnitude Reasoning (OMR) is an approach in QR concerned with the analysis of physical systems in terms of relative magnitudes. In this paper we consider the logic OMR_N for order-of-magnitude reasoning (...) with the bidirectional negligibility relation. It is a multi-modal logic given by a Hilbert-style axiomatization that reflects properties and interactions of two basic accessibility relations (strict linear order and bidirectional negligibility). Although the logic was studied in many papers, nothing was known about its decidability. In the paper we prove decidability of OMR N by showing that the logic has the strong finite model property. (shrink)

The paper argues that grounding is neither irreflexive, nor asymmetric, nor transitive. In arguing for that conclusion the paper also arguesthat truthmaking is neither irreflexive, nor asymmetric, nor transitive.

Although Boyle has been regarded as a champion of the seventeenth century Cartesian mechanical philosophy, I defend the position that Boyle’s views conciliate between a strictly mechanistic conception of fundamental matter and a non-reductionist conception of chemical qualities. In particular, I argue that this conciliation is evident in Boyle’s ontological distinction between fundamental corpuscles endowed with mechanistic properties and higher-level corpuscular concretions endowed with chemical properties. Some of these points have already been acknowledged by contemporary scholars, and I actively engage (...) with their ideas in this paper. However I attempt to contribute to the debate over Boyle’s mechanical philosophy by arguing that Boyle’s writings suggest an emergentist, albeit still mechanistic, notion of chemical properties. I contrast Boyle’s views against those of strict reductionist mechanical philosophers, focusing on the famous debate with Spinoza over the redintegration of niter, and argue that Boyle’s complex chemical ontology provides a more satisfactory understanding of chemical phenomena than is provided by a strictly reductionist and Cartesian mechanical philosophy. (shrink)

The paper sets forth an argument against Kim's distinction between levels and orders.

We defend Jaegwon Kim’s ‘causal inheritance’ principle from an objection raised by Jurgen Schröder. The objection is that the principle is inconsistent with a view about mental properties assumed by Kim, namely, that they are second-order properties. We argue that Schröder misconstrues the notion of second-order property. We distinguish three notions of second-order property and highlight their problems and virtues. Finally, we examine the consequence of Kim’s principle and discuss the issue of whether Kim’s ‘supervenience (...) argument’ generalizes to all special sciences or not. (shrink)

Our aim in this paper is to evaluate Frank Jackson and Philip Pettit’s ‘program explanation’ framework as an account of the autonomy of the special sciences. We argue that this framework can only explain the autonomy of a limited range of special science explanations. The reason for this limitation is that the framework overlooks a distinction between two kinds of properties, which we refer to as ‘higher-level’ and ‘higher-order’ properties. The program explanation framework can account for the autonomy of special (...) science explanations that appeal to higher-level properties but it does not account for the autonomy of most of those explanations that appeal to higher-order properties. (shrink)

We generalise the properties $\mathsf {OP}$, $\mathsf {IP}$, k- $\mathsf {TP}$, $\mathsf {TP}_{1}$, k- $\mathsf {TP}_{2}$, $\mathsf {SOP}_{1}$, $\mathsf {SOP}_{2}$, and $\mathsf {SOP}_{3}$ to positive logic, and prove various implications and equivalences between them. We also provide a characterisation of stability in positive logic in analogy with the one in full first-order logic, both on the level of formulas and on the level of theories. For simple theories there are the classically equivalent definitions of not having $\mathsf {TP}$ and (...) dividing having local character, which we prove to be equivalent in positive logic as well. Finally, we show that a thick theory T has $\mathsf {OP}$ iff it has $\mathsf {IP}$ or $\mathsf {SOP}_{1}$ and that T has $\mathsf {TP}$ iff it has $\mathsf {SOP}_{1}$ or $\mathsf {TP}_{2}$, analogous to the well-known results in full first-order logic where $\mathsf {SOP}_{1}$ is replaced by $\mathsf {SOP}$ in the former and by $\mathsf {TP}_{1}$ in the latter. Our proofs of these final two theorems are new and make use of Kim-independence. (shrink)

This paper investigates a connection between the semantic notion provided by the ordering * among theories in model theory and the syntactic SOPn hierarchy of Shelah. It introduces two properties which are natural extensions of this hierarchy, called SOP2 and SOP1. It is shown here that SOP3 implies SOP2 implies SOP1. In Shelah's article 229) it was shown that SOP3 implies *-maximality and we prove here that *-maximality in a model of GCH implies a property called SOP2″. It has (...) been subsequently shown by Shelah and Usvyatsov that SOP2″ and SOP2 are equivalent, so obtaining an implication between *-maximality and SOP2. It is not known if SOP2 and SOP3 are equivalent. Together with the known results about the connection between the SOPn hierarchy and the existence of universal models in the absence of GCH, the paper provides a step toward the classification of unstable theories without the strict order property. (shrink)

We show how to build various models of first-order theories, which also have properties like: tree with only definable branches, atomic Boolean algebras or ordered fields with only definable automorphisms. For this we use a set-theoretic assertion, which may be interesting by itself on the existence of quite generic subsets of suitable partial orders of power λ + , which follows from ♦ λ and even weaker hypotheses . For a related assertion, which is equivalent to the morass see (...) Shelah and Stanley [16]. The various specific constructions serve also as examples of how to use this set-theoretic lemma. We apply the method to construct rigid ordered fields, rigid atomic Boolean algebras, trees with only definable branches; all in successors of regular cardinals under appropriate set- theoretic assumptions. So we are able to answer the following algebraic question. Saltzman's Question . Is there a rigid real closed field, which is not a subfield of the reals? (shrink)

Abstract: In this paper, I examine the current case against the second-order property view of existence through a discussion of Colin McGinn's up to date statement of this case. I conclude that the second-order property view of existence remains viable.

Shelah, S., C. Laflamme and B. Hart, Models with second order properties V: A general principle, Annals of Pure and Applied Logic 64 169–194. We present a general framework for carrying out the construction in [2-10] and others of the same type. The unifying factor is a combinatorial principle which we present in terms of a game in which the first player challenges the second player to carry out constructions which would be much easier in a generic extension of (...) the universe, and the second player cheats with the aid of ♦. Section 1 contains an axiomatic framework suitable for the description of a number of related constructions, and the statement of the main theorem 1.9 in terms of this framework. In Section 2 we illustrate the use of our combinatorial principle. The proof of the main result is then carried out in Sections 3–5. (shrink)

This paper describes intellectual property legislation in the European Union, the US and the Draft Treaty on the legal protection of unoriginal databases, usually available in the Internet. I argue that this type of legislation, if enforced upon developing countries and countries in transition through international ‘agreements’, could in effect deprive them of their own information commons, their own public domain. With examples from China, India, Africa and Iceland, I argue that this deprivation in the case of developing countries (...) is, morally, equal to a virtual war against them by the West, wholly unjustified and dangerous-an example of virtual imperialism. (shrink)

This paper continues the work in [S. Shelah, Towards classifying unstable theories, Annals of Pure and Applied Logic 80 229–255] and [M. Džamonja, S. Shelah, On left triangle, open*-maximality, Annals of Pure and Applied Logic 125 119–158]. We present a rank function for NSOP1 theories and give an example of a theory which is NSOP1 but not simple. We also investigate the connection between maximality in the ordering left triangle, open* among complete first order theories and the SOP2 (...) class='Hi'>property. We prove that left triangle, open*-maximality implies SOP2 and obtain certain results in the other direction. The paper provides a step toward the classification of unstable theories without the strict order property. (shrink)

We consider semi-isolation on the locus of a strongly non-isolated, RK-minimal type in a small theory, and we prove that its asymmetry (as a binary relation) is caused by a specific form of the strict order property: the partial definability of semi-isolation.

We give a new characterization of _SOP_ (the strict order property) in terms of the behaviour of formulas in any model of the theory as opposed to having to look at the behaviour of indiscernible sequences inside saturated ones. We refine a theorem of Shelah, namely a theory has _OP_ (the order property) if and only if it has _IP_ (the independence property) or _SOP_, in several ways by characterizing various notions in functional analytic (...) style. We point out some connections between dividing lines in first order theories and subclasses of Baire 1 functions, and give new characterizations of some classes and new classes of first order theories. (shrink)

Our aim was to try to generalize some theorems about the saturation of ultrapowers to reduced powers. Naturally, we deal with saturation for types consisting of atomic formulas. We succeed to generalize “the theory of dense linear order (or T with the strict order property) is maximal and so is any which is SOP3”, (where Δ consists of atomic or conjunction of atomic formulas). However, the theorem on “it is enough to deal with symmetric pre‐cuts” (so (...) the theorem) cannot be generalized in this case. Similarly the uniqueness of the dual cofinality fails in this context. (shrink)

Let L(Q) be first order logic with Keisler's quantifier, in the λ + interpretation (= the satisfaction is defined as follows: $M \models (\mathbf{Q}x)\varphi(x)$ means there are λ + many elements in M satisfying the formula φ(x)). Theorem 1. Let λ be a singular cardinal; assume □ λ and GCH. If T is a complete theory in L(Q) of cardinality at most λ, and p is an L(Q) 1-type so that T strongly omits $p (= p$ has no support, (...) to be defined in $\S1$ ), then T has a model of cardinality λ + in the λ + interpretation which omits p. Theorem 2. Let λ be a singular cardinal, and let T be a complete first order theory of cardinality λ at most. Assume □ λ and GCH. If Γ is a smallness notion then T has a model of cardinality λ + such that a formula φ(x) is realized by λ + elements of M iff φ(x) is not Γ-small. The theorem is proved also when λ is regular assuming $\lambda = \lambda^{ . It is new when λ is singular or when |T| = λ is regular. Theorem 3. Let λ be singular. If $\operatorname{Con}(ZFC + GCH + (\exists\kappa)$ [κ is a strongly compact cardinal]), then the following in consistent: ZFC + GCH + the conclusions of all above theorems are false. (shrink)

We study a family of ultraproducts of finite fields with the Frobenius automorphism in this paper. Their theories have the strict order property and TP2. But the coarse pseudofinite dimension of the definable sets is definable and integer-valued. Moreover, we establish a partial connection between coarse dimension and transformal transcendence degree in these difference fields.

We study a family of ultraproducts of finite fields with the Frobenius automorphism in this paper. Their theories have the strict order property and TP2. But the coarse pseudofinite dimension of the definable sets is definable and integer-valued. Moreover, we also discuss the possible connection between coarse dimension and transformal transcendence degree in these difference fields.