According to Boole it is possible to deduce the principle of contradiction from what he calls the fundamental law of thought and expresses as \. We examine in which framework this makes sense and up to which point it depends on notation. This leads us to make various comments on the history and philosophy of modern logic.

We provide a general theorem implying that for a (strongly) dependent theory T the theory of sufficiently well-behaved pairs of models of T is again (strongly) dependent. We apply the theorem to the case of lovely pairs of thorn-rank one theories as well as to a setting of dense pairs of first-order topological theories.

We settle a number of questions concerning definability in first order logic with an extra predicate symbol ranging over semi-linear sets. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions (...) on the semi-linear sets considered. (shrink)

We propose a set theory, called NRFST, in which the Cantorian axiom of infinity is negated, and a new notion of infinity is introduced via non standard methods, i. e. via adequate notions of standard and internal, two unary predicates added to the language of ZF. After some initial results on NRFST, we investigate its relative consistency with respect to ZF and Kawai's WNST.

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)

We show that several theorems on ordinal bounds in different parts of logic are simple consequences of a basic result in the theory of global inductive definitions.

A topological classification scheme consists of two ingredients: (1) an abstract class K of topological spaces; and (2) a "taxonomy", i.e. a list of first order sentences, together with a way of assigning an abstract class of spaces to each sentence of the list so that logically equivalent sentences are assigned the same class. K is then endowed with an equivalence relation, two spaces belonging to the same equivalence class if and only if they lie in the same classes prescribed (...) by the taxonomy. A space X in K is characterized within the classification scheme if whenever Y ∈ K and Y is equivalent to X, then Y is homeomorphic to X. As prime example, the closed set taxonomy assigns to each sentence in the first order language of bounded lattices the class of topological spaces whose lattices of closed sets satisfy that sentence. It turns out that every compact two-complex is characterized via this taxonomy in the class of metrizable spaces, but that no infinite discrete space is so characterized. We investigate various natural classification schemes, compare them, and look into the question of which spaces can and cannot be characterized within them. (shrink)

By analyzing how one obtains the Stone space of the reduced product of an indexed collection of Boolean algebras from the Stone spaces of those algebras, we derive a topological construction, the "reduced coproduct", which makes sense for indexed collections of arbitrary Tichonov spaces. When the filter in question is an ultrafilter, we show how the "ultracoproduct" can be obtained from the usual topological ultraproduct via a compactification process in the style of Wallman and Frink. We prove theorems dealing with (...) the topological structure of reduced coproducts (especially ultracoproducts) and show in addition how one may use this construction to gain information about the category of compact Hausdorff spaces. (shrink)

Let CH be the class of compacta (i.e., compact Hausdorff spaces), with BS the subclass of Boolean spaces. For each ordinal α and pair $\langle K,L\rangle$ of subclasses of CH, we define Lev ≥α K,L), the class of maps of level at least α from spaces in K to spaces in L, in such a way that, for finite α, Lev ≥α (BS,BS) consists of the Stone duals of Boolean lattice embeddings that preserve all prenex first-order formulas of quantifier rank (...) α. Maps of level ≥ 0 are just the continuous surjections, and the maps of level ≥ 1 are the co-existential maps introduced in [8]. Co-elementary maps are of level ≥α for all ordinals α; of course in the Boolean context, the co-elementary maps coincide with the maps of level ≥ω. The results of this paper include: (i) every map of level ≥ω is co-elementary; (ii) the limit maps of an ω-indexed inverse system of maps of level ≥α are also of level ≥α; and (iii) if K is a co-elementary class, k ≥ k (K,K) = Lev ≥ k+1 (K,K), then Lev ≥ k (K,K) = Lev ≥ω (K,K). A space X ∈ K is co-existentially closed in K if Lev ≥ 0 (K, X) = Lev ≥ 1 (K, X). Adapting the technique of "adding roots," by which one builds algebraically closed extensions of fields (and, more generally, existentially closed extensions of models of universal-existential theories), we showed in [8] that every infinite member of a co-inductive co-elementary class (such as CH itself, BS, or the class CON of continua) is a continuous image of a space of the same weight that is co-existentially closed in that class. We show here that every compactum that is co-existentially closed in CON (a co-existentially closed continuum) is both indecomposable and of covering dimension one. (shrink)

$\underline{\text{Saturation is} (\mu, \kappa)-\text{transferable in} T}$ if and only if there is an expansion T 1 of T with ∣ T 1 ∣ = ∣ T ∣ such that if M is a μ-saturated model of T 1 and ∣ M ∣ ≥ κ then the reduct M ∣ L(T) is κ-saturated. We characterize theories which are superstable without f.c.p., or without f.c.p. as, respectively those where saturation is (ℵ 0 , λ)- transferable or (κ (T), λ)-transferable for all λ. (...) Further if for some $\mu \geq \mid T \mid, 2^\mu > \mu^+$ , stability is equivalent to for all μ ≥ ∣ T ∣, saturation is (μ, 2 μ )- transferable. (shrink)

Let $\mathbf{I}(\mu,K)$ denote the number of nonisomorphic models of power $\mu$ and $\mathbf{IE}(\mu,K)$ the number of nonmutually embeddable models. We define in this paper the notion of a diverse class and use it to prove a number of results. The major result is Theorem B: For any diverse class $K$ and $\mu$ greater than the cardinality of the language of $K$, $\mathbf{IE}(\mu,K) \geq \min(2^\mu,\beth_2).$ From it we deduce both an old result of Shelah, Theorem C: If $T$ is countable and (...) $\lambda_0 > \aleph_0$ then for every $\mu > \aleph_0,\mathbf{IE}(\mu,T) \geq \min(2^\mu,\beth_2)$, and an extension of that result to uncountable languages, Theorem D: If $|T| < 2^\omega,\lambda_0 > |T|$, and $|D(T)| = |T|$ then for $\mu > |T|$, $\mathbf{IE}(\mu,T) \geq \min(2^\mu,\beth_2).$. (shrink)

A varietyV satisfies a strong Malcev condition ∃f1,…, ∃fnθ where θ is a conjunction of equations in the function variablesf1, …,fnand the individual variablesx1, …,xm, if there are polynomial symbolsp1, …,pnin the language ofVsuch that ∀x1, …,xmθ is a law ofV. Thus a strong Malcev condition involves restricted second order quantification of a strange sort. The quantification is restricted to functions which are “polynomially definable”. This notion was introduced by Malcev [6] who used it to describe those varieties all of (...) whose members have permutable congruence relations. The general formal definition of Malcev conditions is due to Grätzer [1]. Since then and especially since Jónsson's [3] characterization of varieties with distributive congruences there has been extensive study of strong Malcev conditions and the related concepts: Malcev conditions and weak Malcev conditions.In [9], Taylor gives necessary and sufficient semantic conditions for a class of varieties to be defined by a Malcev condition. A key to the proof is the translation of the restricted second order concepts into first order concepts in a certain many sorted language. In this paper we show that, given this translation, Taylor's theorem is an easy consequence of a result of Tarski [8] and the standard preservation theorems of first order logic. (shrink)

Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. In this work, we develop a general framework—the supervised learning game—to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand, Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the other (...) hand, Teacher is able to correct Learner’s mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning and study its properties. Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory. (shrink)

A subset A $\subseteq$ M of a totally ordered structure M is said to be convex, if for any a, b $\in A: [a . A complete theory of first order is weakly o-minimal (M. Dickmann [D]) if any model M is totally ordered by some $\emptyset$ -definable formula and any subset of M which is definable with parameters from M is a finite union of convex sets. We prove here that for any model M of a weakly o-minimal theory (...) T, any expansion M + of M by a family of unary predicates has a weakly o-minimal theory iff the set of all realizations of each predicate is a union of a finite number of convex sets (Theorem 63), that solves the Problem of Cherlin-Macpherson-Marker-Steinhorn [MMS] for the class of weakly o-minimal theories. (shrink)

Under a proper translation, the languages of propositional (and quantified relevant logic) with an absurdity constant are characterized as the fragments of first order logic preserved under (world-object) relevant directed bisimulations. Furthermore, the properties of pointed models axiomatizable by sets of propositional relevant formulas have a purely algebraic characterization. Finally, a form of the interpolation property holds for the relevant fragment of first order logic.

The question “what is an interpretation?” is often intertwined with the perhaps even harder question “what is a scientific theory?”. Given this proximity, we try to clarify the first question to acquire some ground for the latter. The quarrel between the syntactic and semantic conceptions of scientific theories occupied a large part of the scenario of the philosophy of science in the 20th century. For many authors, one of the two currents needed to be victorious. We endorse that such debate, (...) at least in the terms commonly expressed, can be misleading. We argue that the traditional notion of “interpretation” within the syntax/semantic debate is not the same as that of the debate concerning the interpretation of quantum mechanics. As much as the term is the same, the term “interpretation” as employed in quantum mechanics has its meaning beyond (pure) logic. Our main focus here lies on the formal aspects of the solutions to the measurement problem. There are many versions of quantum theory, many of them incompatible with each other. In order to encompass a wider variety of approaches to quantum theory, we propose a different one with an emphasis on pure formalism. This perspective has the intent of elucidating the role of each so-called “interpretation” of quantum mechanics, as well as the precise origin of the need to interpret it. (shrink)

We consider the theory Thprin of Boolean algebras with a principal ideal, the theory Thmax of Boolean algebras with a maximal ideal, the theory Thac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Thsa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Thprin and Thsa. If T is a theory in a first order language and α is a linear (...) order with least element, then we let Sentalg be the Lindenbaum-Tarski algebra with respect to T, and we let intalg be the interval algebra of α. Using rank diagrams, we show that Sentalg ⋍ intalg, Sentalg ⋍ intalg ⋍ Sentalg, and Sentalg ⋍ intalg. For Thmax and Thac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic. (shrink)

We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.

We prove that Standardization fails in every nontrivial universe definable in the nonstandard set theory BST, and that a natural characterization of the standard universe is both consistent with and independent of BST. As a consequence we obtain a formulation of nonstandard class theory in the ∈-language.

We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

The randomization of a complete first-order theory [Formula: see text] is the complete continuous theory [Formula: see text] with two sorts, a sort for random elements of models of [Formula: see text] and a sort for events in an underlying atomless probability space. We study independence relations and related ternary relations on the randomization of [Formula: see text]. We show that if [Formula: see text] has the exchange property and [Formula: see text], then [Formula: see text] has a strict independence (...) relation in the home sort, and hence is real rosy. In particular, if [Formula: see text] is o-minimal, then [Formula: see text] is real rosy. (shrink)

We investigate in an algebraic setting the question of which logical languages can express the properties integral, permutational, and rigid for algebras of relations.

Let K be a finite set of finite structures. We give a syntactic characterization of the property: every element of K is injective in ISP(K). We use this result to establish that A is injective in ISP(A) for every two-element algebra A.

We characterize the model companions of universal Horn classes generated by a two-element algebra (or ordered two-element algebra). We begin by proving that given two mutually model consistent classes M and N of L (respectively L') structures, with $\mathscr{L} \subseteq \mathscr{L}'$ , M ec = N ec ∣ L , provided that an L-definability condition for the function and relation symbols of L' holds. We use this, together with Post's characterization of ISP(A), where A is a two-element algebra, to show (...) that the model companions of these classes essentially lie in the classes of posets and semilattices, or characteristic two groups and relatively complemented distributive lattices. (shrink)

This is a survey article on algebraic logic. It gives a historical background leading up to a modern perspective. Central problems in algebraic logic (like the representation problem) are discussed in connection to other branches of logic, like modal logic, proof theory, model-theoretic forcing, finite combinatorics, and Gödel’s incompleteness results. We focus on cylindric algebras. Relation algebras and polyadic algebras are mostly covered only insofar as they relate to cylindric algebras, and even there we have not told the whole story. (...) We relate the algebraic notion of neat embeddings (a notion special to cylindric algebras) to the metalogical ones of provability, interpolation and omitting types in variants of first logic. Another novelty that occurs here is relating the algebraic notion of atom-canonicity for a class of boolean algebras with operators to the metalogical one of omitting types for the corresponding logic. A hitherto unpublished application of algebraic logic to omitting types of first order logic is given. Proofs are included when they serve to illustrate certain concepts. Several open problems are posed. We have tried as much as possible to avoid exploring territory already explored in the survey articles of Monk [93] and Németi [97] in the subject. (shrink)

We develop an untyped framework for the multiverse of set theory. $\mathsf {ZF}$ is extended with semantically motivated axioms utilizing the new symbols $\mathsf {Uni}(\mathcal {U})$ and $\mathsf {Mod}(\mathcal {U, \sigma })$, expressing that $\mathcal {U}$ is a universe and that $\sigma $ is true in the universe $\mathcal {U}$, respectively. Here $\sigma $ ranges over the augmented language, leading to liar-style phenomena that are analyzed. The framework is both compatible with a broad range of multiverse conceptions and suggests its (...) own philosophically and semantically motivated multiverse principles. In particular, the framework is closely linked with a deductive rule of Necessitation expressing that the multiverse theory can only prove statements that it also proves to hold in all universes. We argue that this may be philosophically thought of as a Copernican principle that the background theory does not hold a privileged position over the theories of its internal universes. Our main mathematical result is a lemma encapsulating a technique for locally interpreting a wide variety of extensions of our basic framework in more familiar theories. We apply this to show, for a range of such semantically motivated extensions, that their consistency strength is at most slightly above that of the base theory $\mathsf {ZF}$, and thus not seriously limiting to the diversity of the set-theoretic multiverse. We end with case studies applying the framework to two multiverse conceptions of set theory: arithmetic absoluteness and Joel D. Hamkins’ multiverse theory. (shrink)

There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

Akama et al. [1] introduced a hierarchical classification of first-order formulas for a hierarchical prenex normal form theorem in semi-classical arithmetic. In this paper, we give a justification for the hierarchical classification in a general context of first-order theories. To this end, we first formalize the standard transformation procedure for prenex normalization. Then we show that the classes $$\textrm{E}_k$$ and $$\textrm{U}_k$$ introduced in [1] are exactly the classes induced by $$\Sigma _k$$ and $$\Pi _k$$ respectively via the transformation procedure in (...) any first-order theory. (shrink)

The maximum entropy principle is widely used to determine non-committal probabilities on a finite domain, subject to a set of constraints, but its application to continuous domains is notoriously problematic. This paper concerns an intermediate case, where the domain is a first-order predicate language. Two strategies have been put forward for applying the maximum entropy principle on such a domain: applying it to finite sublanguages and taking the pointwise limit of the resulting probabilities as the size n of the sublanguage (...) increases; selecting a probability function on the language as a whole whose entropy on finite sublanguages of size n is not dominated by that of any other probability function for sufficiently large n. The entropy-limit conjecture says that, where these two approaches yield determinate probabilities, the two methods yield the same probabilities. If this conjecture is found to be true, it would provide a boost to the project of seeking a single canonical inductive logic—a project which faltered when Carnap's attempts in this direction succeeded only in determining a continuum of inductive methods. The truth of the conjecture would also boost the project of providing a canonical characterisation of normal or default models of first-order theories. Hitherto, the entropy-limit conjecture has been verified for languages which contain only unary predicate symbols and also for the case in which the constraints can be captured by a categorical statement of quantifier complexity. This paper shows that the entropy-limit conjecture also holds for categorical statements of complexity, for various non-categorical constraints, and in certain other general situations. (shrink)

Preferential model is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(·) and μ(·) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(·) and ΠD(·), we introduce an operator ∂D(·). Then (...) the isomorphism theorem is obtained in terms of ∂D(·), which asserts that for any two preferential models M₁ and M₂, they generate the same preferential inference if and only if ∂D(M₁) and ∂D(M₂) are isomorphic. Based on ∂D(·), we also get an alternative model-theoretical characterization of the well-known postulate "Weaken Disjunctive Rationality". Moreover, in the finite language framework, we show that Δ(μ(·)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations. (shrink)

In Ockhamist branching-time logic [Prior 67], formulas are meant to be evaluated on a specified branch, or history, passing through the moment at hand. The linguistic counterpart of the manifoldness of future is a possibility operator which is read as `at some branch, or history (passing through the moment at hand)'. Both the bundled-trees semantics [Burgess 79] and the $\langle moment, history\rangle$ semantics [Thomason 84] for the possibility operator involve a quantification over sets of moments. The Ockhamist frames are (3-modal) (...) Kripke structures in which this second-order quantification is represented by a first-order quantification. The aim of the present paper is to investigate the notions of modal definability, validity, and axiomatizability concerning 3-modal frames which can be viewed as generalizations of Ockhamist frames. (shrink)