For a complete theory of Boolean algebras T, let MT denote the class of countable models of T. For B1, B2 ∈ MT, let B1 ≤ B2 mean that B1 is elementarily embeddable in B2. Theorem 1. For every complete theory of Boolean algebras T, if T ≠ Tω, then $\langle M_T, \leq\rangle$ is well-quasi-ordered. ■ We define Tω. For a Boolean algebra B, let I(B) be the ideal of all elements of the form a + (...) s such that $B\upharpoonright a$ is an atomic Boolean algebra and $B\upharpoonright s$ is an atomless Boolean algebra. The Tarski derivative of B is defined as follows: B(0) = B and B(n + 1) = B(n)/I(B(n)). Define Tω to be the theory of all Boolean algebras such that for every n ∈ ω, B(n) ≠ {0}. By Tarski [1949], Tω is complete. Recall that $\langle A, \leq\rangle$ is a partial well-quasi-ordering, if it is a partial quasi-ordering and for every $\{a_i\mid i \in \omega\} \subseteq A$ , there are $i < j < \omega$ such that ai ≤ aj. Theorem 2. $\langle M_{T_\omega}, \leq\rangle$ contains a subset M such that the partial orderings $\langle M, \leq \upharpoonright M \rangle$ and $\langle\mathscr{P}(\omega), \subseteq\rangle$ are isomorphic. ■ Let M'0 denote the class of all countable Boolean algebras. For B1, B2 ∈ M'0, let B1 ≤' B2 mean that B1 is embeddable in B2. Remark. $\langle M'_0, \leq'\rangle$ is well-quasi-ordered. ■ This follows from Laver's theorem [1971] that the class of countable linear orderings with the embeddability relation is well-quasi-ordered and the fact that every countable Boolean algebra is isomorphic to a Boolean algebra of a linear ordering. (shrink)

A structure (M, $ ,...) is called quasi-o-minimal if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0-definable subsets and intervals. We give a series of natural examples of quasi-o-minimal structures which are not o-minimal; one of them is the ordered group of integers. We develop a technique to investigate quasi-o-minimality and use it to study quasi-o-minimal ordered groups (possibly with extra structure). Main results: any quasi-o-minimal (...) ordered group is abelian; any quasi-o-minimal ordered ring is a real closed field, or has zero multiplication; every quasi-o-minimal divisible ordered group is o-minimal; every quasi-o-minimal archimedian densely ordered group is divisible. We show that a counterpart of quasi-o-minimality in stability theory is the notion of theory of U-rank 1. (shrink)

We prove that the poset algebra of every scattered poset with finite width is embeddable in the poset algebra of a well ordered poset.

In this article, I consider the positive logic of Boolean groups (i.e. Abelian groups where every non-identity element has order 2), where these are taken as frames for an operational semantics à la Urquhart. I call this logic BG. It is shown that the logic over the smallest nontrivial Boolean group, taken as a frame, is identical to the positive fragment of a quasi-relevance logic that was developed by Robles and Méndez (an extension of this result where (...) negation is included is also discussed). It is proved that BG satisfies the variable sharing property and is Halldén complete, while failing to satisfy the disjunction property. Sound and complete subscripted tableaux are presented for BG. An axiomatization (in the positive language extended with fusion) is presented, which is sound with respect to BG and, with respect to a related ternary relational semantics, complete; the problem of identifying a complete axiomatization for BG itself is left open. Connections between BG and the quasi-relevance logic KR are also discussed. (shrink)

This article describes well quasi orders as a category, focusing on limits and colimits. In particular, while quasi orders with monotone maps form a category which is finitely complete, finitely cocomplete, and with exponentiation, the full subcategory of well quasi orders is finitely complete and cocomplete, but with no exponentiation. It is interesting to notice how finite antichains and finite proper descending chains interact to induce this structure in the category: in fact, the full subcategory of (...) class='Hi'>quasi orders with finite antichains has finite colimits but no products, while the full subcategory of well founded quasi orders has finite limits but no coequalisers. Moreover, the article characterises when exponential objects exist in the category of well quasi orders and well founded quasi orders. This completes the systematic description of the fundamental constructions in the categories of quasi orders, well founded quasi orders, quasi orders with finite antichains, and well quasi orders. (shrink)

We study the provability in subsystems of second-order arithmetic of two theorems of Harrington and Shelah [6] about Borel quasi-orderings of the reals. These theorems turn out to be provable in ATR0, thus giving further evidence to the observation that ATR0 is the minimal subsystem of second-order arithmetic in which significant portion of descriptive set theory can be developed. As in [6] considering the lightface versions of the theorems will be instrumental in their proof and the main techniques employed (...) will be the reflection principles and Gandy forcing. (shrink)

We define a quasi-order on Borel functions from a zero-dimensional Polish space into another that both refines the order induced by the Baire hierarchy of functions and generalises the embeddability order on Borel sets. We study the properties of this quasi-order on continuous functions, and we prove that the closed subsets of a zero-dimensional Polish space are well-quasi-ordered by bi-continuous embeddability.

Population ethics contains several principles that avoid the repugnant conclusion. These rules rank all possible alternatives, leaving no room for moral ambiguity. Building on a suggestion of Parfit, this paper characterizes principles that provide incomplete but ethically attractive rankings of alternatives with different population sizes. All of them rank same-number alternatives with generalized utilitarianism.

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, and proven to (...) be extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

In this paper we give a proof of the II12-completeness of the set of countable better quasi orderings . This result was conjectured by Clote in [2] and proved by the author in his Ph.d. thesis [6] . Here we prove it using Simpson's definition of better quasi ordering and as little bqo theory as possible.

Normative theories suggest that inconsistencies be pointed out to the Decision Maker who is thus given the chance to modify his/her judgments. In this paper, we suggest that the inconsistencies problem be transferred from the Decision Maker to the Analyst. With the Mixture of Maximal Quasi Orders, rather than pointing out incoherences for the Decision Maker to change, these inconsistencies may be used as new source of information to model his/her preferences.

A quasi-order Q induces two natural quasi-orders on $${\mathcal{P}(Q)}$$, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on $${\mathcal{P}(Q)}$$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on (...) $${\mathcal{P}(Q)}$$ are Noetherian, which means that they contain no infinite strictly descending sequences of closed sets. We analyze various theorems of the form “if Q is a well-quasi-order then a certain topology on (a subset of) $${\mathcal{P}(Q)}$$ is Noetherian” in the style of reverse mathematics, proving that these theorems are equivalent to ACA 0 over RCA 0. To state these theorems in RCA 0 we introduce a new framework for dealing with second-countable topological spaces. (shrink)

The paper discusses normative systems and their revision within an algebraic framework. If a system is logically well-formed, certain norms, called connecting norms, determine the system as a whole. It is maintained that, if the system is well-formed, a relation at least as low as determines a lattice or quasi-lattice of its connecting norms. The ideas are presented mainly in the form of comments on a legal example concerning acquisition of movable property by extinction of another person's previous rights.

In this paper, we give a step by step introduction to the theory of well quasi-ordered transition systems. The framework combines two concepts, namely (i) transition systems which are monotonic wrt. a well-quasi ordering ; and (ii) a scheme for symbolic backward reachability analysis. We describe several models with infinite-state spaces, which can be analyzed within the framework, e.g., Petri nets, lossy channel systems, timed automata, timed Petri nets, and multiset rewriting systems. We will also present better (...) quasi-ordered transition systems which allow the design of efficient symbolic representations of infinite sets of states. (shrink)

We provide partial answers to the following problem: Is the class of Borel linear orders well-quasi-ordered under embeddability? We show that it is indeed the case for those Borel orders which are embeddable in R ω , with the lexicographic ordering. For Borel orders embeddable in R 2 , our proof works in ZFC, but it uses projective determinacy for Borel orders embeddable in some $\mathbf{R}^n, n , and hyperprojective determinacy for the general case.

In the present paper we study how subsystems of a normative system can be combined, and the role of such combinations for the understanding of hypothetical legal consequences. A combination of two subsystems is often accomplished by a normative correlation or an intermediate concept. To obtain a detailed analysis of such phenomena we use an algebraic framework. Normative systems are represented as algebraic structures over sets of conditions. This representation makes it possible to study normative systems using an extension of (...) the theory of Boolean algebras, called the theory of Boolean quasi‐orderings. (shrink)

Two forms of continuity are defined for Pareto representations of preferences. They are designated “continuity” and “coordinate continuity.” Characterizations are given of those Pareto representable preferences that are continuously representable and, in dimension two, of those that are coordinate-continuously representable.

We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets$\mathbb{P}_{emb} $equipped with the order induced by homomorphisms is embedded into the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. We then show that$\mathbb{P}_{emb} $admits both infinite strictly decreasing chains and infinite antichains with respect to (...) this notion of comparison, which therefore transfers to the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. (shrink)

We simultaneously generalize Silver’s perfect set theorem for co-analytic equivalence relations and Harrington-Marker-Shelah’s Dilworth-style perfect set theorem for Borel quasi-orders, establish the analogous theorem at the next definable cardinal, and give further generalizations under weaker definability conditions.

We generalize Kada’s definable strengthening of Dilworth’s characterization of the class of quasi-orders admitting an antichain of a given finite cardinality.

A sequent calculus S for the variety tqBa of all topological quasi-Boolean algebras is established. Using a construction of syntactic finite algebraic model, the finite model property of S is shown, and thus the decidability of S is obtained. We also introduce two non-distributive variants of topological quasi-Boolean algebras. For the variety TDM5 of all topological De Morgan lattices with the axiom 5, we establish a sequent calculus S5 and prove that the cut elimination holds for (...) it. Consequently the decidability of S5 is established. Furthermore, this proof-theoretic method is applied to some subvarieties of TDM5. (shrink)

The aim of the present paper is to provide an axiomatic analysis of incomplete social judgments. In particular, we clarify the underlying power structure of Arrovian collective choice rules when social preferences are allowed to be incomplete. We propose the concept of quasi-decisiveness and investigate the properties of the collection of quasi-decisive sets associated with an Arrovian collective choice rule. In the course of this, we offer a series of applications.

In this paper we prove general exact unprovability results that show how a threshold between provability and unprovability of a finite well-quasi-orderedness assertion of a combinatorial class is transformed by the sequence-construction, multiset-construction, cycle-construction and labeled-tree-construction. Provability proofs use the asymptotic pigeonhole principle, unprovability proofs use Weiermann-style compression techniques and results from analytic combinatorics.

The basic quasi-Boolean negation expansions of relevance logics included in Anderson and Belnap’s relevance logic R are defined. We consider two types of QB-negation: H-negation and D-negation. The former one is of paraintuitionistic or superintuitionistic character, the latter one, of dual intuitionistic nature in some sense. Logics endowed with H-negation are paracomplete; logics with D-negation are paraconsistent. All logics defined in the paper are given a Routley-Meyer ternary relational semantics.

In so-called full second-order logic, the second-order variables range over all subsets and relations of the domain in question. In so-called Henkin second-order logic, every model is endowed with a set of subsets and relations which will serve as the range of the second-order variables. In our Boolean-valued second-order logic, the second-order variables range over all Boolean-valued subsets and relations on the domain. We show that under large cardinal assumptions Boolean-valued second-order logic is more robust than full (...) second-order logic. Its validity is absolute under forcing, and its Hanf and Löwenheim numbers are smaller than those of full second-order logic. (shrink)

As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players – they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x depends on variable (...) y, then we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables—the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly logic. (shrink)

The logic B M is Sylvan and Plumwood's minimal De Morgan logic. The aim of this paper is to investigate extensions of B M endowed with a quasi-Boolean negation of intuitionistic character included...

In the present paper, we introduce the notions of quasi-Boolean algebras as the generalization of Boolean algebras. First we discuss the related properties of quasi-Boolean algebras. Second we define filters of quasi-Boolean algebras and investigate some properties of filters in quasi-Boolean algebras. We also show that there is a one-to-one correspondence between the set of filters and the set of filter congruences on a quasi-Boolean algebra. Then we investigate the (...) prime filters and maximal filters of quasi-Boolean algebras, showing that the prime filters of a quasi-Boolean algebra are precisely the maximal filters and the prime spectrum of a quasi-Boolean algebra is a compact Hausdorff topological space. Finally, we define and study the reticulation of a quasi-Boolean algebra. (shrink)

We characterize Δ20-categoricity in Boolean algebras and linear orderings under some extra effectiveness conditions. We begin with a study of the relativized notion in these structures.

Let (M, ≤,...) denote a Boolean ordered o-minimal structure. We prove that a Boolean subalgebra of M determined by an algebraically closed subset contains no dense atoms. We show that Boolean algebras with finitely many atoms do not admit proper expansions with o-minimal theory. The proof involves decomposition of any definable set into finitely many pairwise disjoint cells, i.e., definable sets of an especially simple nature. This leads to the conclusion that Boolean ordered structures with o-minimal (...) theories are essentially bidefinable with Boolean algebras with finitely many atoms, expanded by naming constants. We also discuss the problem of existence of proper o-minimal expansions of Boolean algebras. (shrink)