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)

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.

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.

Louveau and Rosendal [5] have shown that the relation of bi-embeddability for countable graphs as well as for many other natural classes of countable structures is complete under Borel reducibility for analytic equivalence relations. This is in strong contrast to the case of the isomorphism relation, which as an equivalence relation on graphs (or on any class of countable structures consisting of the models of a sentence of L ω ₁ ω ) is far from complete (see [5, 2]). (...) In this article we strengthen the results of [5] by showing that not only does bi-embeddability give rise to analytic equivalence relations which are complete under Borel reducibility, but in fact any analytic equivalence relation is Borel equivalent to such a relation. This result and the techniques introduced answer questions raised in [5] about the comparison between isomorphism and bi-embeddability. Finally, as in [5] our results apply not only to classes of countable structures defined by sentences of ω ₁ ω , but also to discrete metric or ultrametric Polish spaces, compact metrizable topological spaces and separable Banach spaces, with various notions of embeddability appropriate for these classes, as well as to actions of Polish monoids. (shrink)

Carnap’s quasi-analysis is usually considered as an ingenious but definitively flawed approach in epistemology and philosophy of science. In this paper it is argued that this assessment is mistaken. Quasi-analysis can be reconstructed as a representational theory of constitution of structures that has applications in many realms of epistemology and philosophy of science. First, existence and uniqueness theorems for quasi-analytical representations are proved. These theorems defuse the classical objections against the quasi-analytical approach launched forward by Goodman (...) and others. Secondly, the constitution of various kinds of structures is treated in detail: order structures, comparative similarity structures, mereological, mereotopological, and topological structures are considered. In particular, it is pointed out that there exist interesting relations between quasi-analysis and modern theories of pointless topology. (shrink)

The highly enjoyable experiences associated with drinking good wines have been widely misunderstood. It is common to regard wine appreciation as an analytical or quasi-scientific kind of activity, in which wine experts carefully distinguish the precise sensory qualities of each wine, and then pass on their accumulated factual knowledge to less experienced wine enthusiasts. However, this model of wine appreciation is seriously defective. One good way to show its defects is to provide a better and more fundamental scientific account (...) of what is involved in wine appreciation. In order to do so, I outline a novel, evolutionarily based theory of perceptual consciousness that explains why there must be imaginative as well as analytical kinds of experiences of wines. In addition, imaginative wine experiences, unlike typical imaginative artistic experiences, may be shown to involve highly individualistic, improvisatory elements that help to give wine drinking a unique place among the recreational arts. (shrink)

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.

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.

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)

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.

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 (...) class='Hi'>quasi-ordered transition systems which allow the design of efficient symbolic representations of infinite sets of states. (shrink)

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)

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.

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.

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.

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)

Answering some of the main questions from [L. Motto Ros, The descriptive set-theoretical complexity of the embeddability relation on models of large size, Ann. Pure Appl. Logic164(12) (2013) 1454–1492], we show that whenever κ is a cardinal satisfying κ<κ=κ>ω, then the embeddability relation between κ-sized structures is strongly invariantly universal, and hence complete for (κ-)analytic quasi-orders. We also prove that in the above result we can further restrict our attention to various natural classes of structures, including (generalized) trees, (...) graphs, or groups. This fully generalizes to the uncountable case the main results of [A. Louveau and C. Rosendal, Complete analytic equivalence relations, Trans. Amer. Math. Soc.357(12) (2005) 4839–4866; S.-D. Friedman and L. Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symbolic Logic76(1) (2011) 243–266; J. Williams, Universal countable Borel quasi-orders, J. Symbolic Logic79(3) (2014) 928–954; F. Calderoni and L. Motto Ros, Universality of group embeddability, Proc. Amer. Math. Soc.146 (2018) 1765–1780]. (shrink)

We show that if κ is a weakly compact cardinal then the embeddability relation on trees of size κ is invariantly universal. This means that for every analytic quasi-order R on the generalized Cantor space View the MathML source there is an Lκ+κ-sentence φ such that the embeddability relation on its models of size κ, which are all trees, is Borel bi-reducible to R. In particular, this implies that the relation of embeddability on trees of size κ (...) is complete for analytic quasi-orders on View the MathML source. These facts generalize analogous results for κ=ω obtained in Louveau and Rosendal [17] and Friedman and Motto Ros [6], and it also partially extends a result from Baumgartner [3] concerning the structure of the embeddability relation on linear orders of size κ. (shrink)

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

The ability to analyze arguments is critical for higher-level reasoning, yet previous research suggests that standard university education provides at best modest improvements in students’ analytical reasoning abilities. What techniques are most effective for cultivating these skills? Here we investigate the effectiveness of a 12-week undergraduate seminar in which students practice a software-based technique for visualizing the logical structures implicit in argumen- tative texts. Seminar students met weekly to analyze excerpts from contemporary analytic philosophy papers, completed argument visualization problem (...) sets, and received individualized feedback on a weekly basis. We found that Seminar students improved substantially more on LSAT Logical Reasoning test forms than Control students (d = .71, p < .001), suggesting that learning how to visualize arguments in the seminar led to large generalized improvements in students’ analytical reasoning skills. Moreover, blind scoring of final essays from Seminar students and Control students, drawn from a parallel lecture course, revealed large differences in favor of seminar students (d = 0.87, p = .005). Seminar students understood the arguments better, and their essays were more accurate and effectively structured. Taken together, these findings deepen our understanding of how visualizations support logical reasoning, and provide a model for improving analytical reasoning pedagogy. (shrink)

Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...) the LMS 14 285–293]) and Harvey Friedman [S.G. Simpson, Non-provability of certain combinatorial properties of finite trees, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 87–117; R. Smith, The consistency strength of some finite forms of the Higman and Kruskal theorems, in: Harvey Friedman’s Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985, pp. 119–136] who produced the first mathematically interesting independence results in Ramsey theory and well-order and well-quasi-order theory .In this article we investigate Friedman-style principles of combinatorial well-foundedness for the ordinals below ε0. These principles state that there is a uniform bound on the length of decreasing sequences of ordinals which satisfy an elementary recursive growth rate condition with respect to their Gödel numbers.For these independence principles we classify their phase transitions, i.e. we classify exactly the bounding conditions which lead from provability to unprovability in the induced combinatorial well-foundedness principles.As Gödel numbering for ordinals we choose the one which is induced naturally from Gödel’s coding of finite sequences from his classical 1931 paper on his incompleteness results.This choice makes the investigation highly non-trivial but rewarding and we succeed in our objectives by using an intricate and surprising interplay between analytic combinatorics and the theory of descent recursive functions. For obtaining the required bounds on count functions for ordinals we use a classical 1961 Tauberian theorem of Parameswaran which apparently is far remote from Gödel’s theorem. (shrink)

Boltanski and Thévenot constructed in their seminal work On Justification the Orders of Worth framework as a research program for further empirical and theoretical development. This article suggests two methodological additions to extend the analytical capacities of the OW framework: The Socialism OW and the analytical adequacy axiom. The polito-philosophical Socialism OW, which acknowledges ' welfare' as its mode of evaluation and the higher principle of 'solidarity' as its test, is rooted in the political philosophy of Rosanvallon. In addition to (...) the systematic justification of the canonical text, this article also offers a tabular presentation for the construction of a new OW in relation to the axioms. In the article, first, the existing OW are put under scrutiny discussing the test category of solidarity, which was added and creates an analytic overload for the Civic OW. Second, analyzing the case of the German binary statutory health system, comprising of a private and a public healthcare, the capacities of the existing OW are discussed to identify a blank spot in the OW framework for empirical analysis. Accordingly, the descriptive analysis of the German binary health system is less about how the system is justified, and much more about understanding how given OW operate within it as coordinative devices. This systematic analysis of a situation of agreements, especially of investments in forms, amends the OW use for empirical analysis of critique and justification in a situation. (shrink)

The article reconstructs the premises of the reception of analytic philosophy in jurisprudence and shows that the development of a method for clarifying the meanings of legal concepts is not least connected with the problem of legitimizing law enforcement. The article analyzes H.L.A. Hart’s approach to the problem of correlation between the “letter” and “spirit” of the law in the process of interpreting legal norms. The article argues that the process of interpretation is determined teleologically. In its limit, the (...) interpretation of legal norms presupposes the re-creation of the desired image of society, the reconstruction of such social ontology that is most consistent with the ideal of achieving social welfare. The article examines the collision of the “ideal of order” and the “ideal of justice” as two regulations of law enforcement. The author believes that the interpretation of this collision within the analytical tradition was characterized by a gradual movement from the ideal of “mechanical” law enforcement, which minimizes the creative role of the interpreter, to the ideal of flexible interpretation focused on achieving legal goals in a changing environment. It is noted that, according to analytic approach, a theoretical solution to this conflict was proposed due to the development of the ideas of an “open texture” of law. The author demonstrates that the development of the analytic tradition in jurisprudence has shown that the criticism of language and the interpretation of meanings are not technical tasks, but it presupposes the construction of a metaphysics of law. In this regard, the author concludes: the development of the ideas of the analytic tradition in jurisprudence demonstrates that the thesis about the absence of a positive program in analytic philosophy, put forward in the first article of the discussion, can be challenged. (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)

The concept of similarity has had a rather mixed reputation in philosophy and the sciences. On the one hand, philosophers such as Goodman and Quine emphasized the „logically repugnant“ and „insidious“ character of the concept of similarity that allegedly renders it inaccessible for a proper logical analysis. On the other hand, a philosopher such as Carnap assigned a central role to similarity in his constitutional theory. Moreover, the importance and perhaps even indispensibility of the concept of similarity for many empirical (...) sciences can hardly be denied. The aim of this paper is to show that Quine’s and Goodman’s harsh verdicts about this notion are mistaken. The concept of similarity is susceptible to a precise logico-mathematical analysis through which its place in the conceptual landscape of modern mathematical theories such as order theory, topology, and graph theory becomes visible. Thereby it can be shown that a quasi-analysis of a similarity structure S can be conceived of as a sheaf (etale space) over S. (shrink)

We present a computational analysis of de re, de dicto, and de se belief and knowledge reports. Our analysis solves a problem first observed by Hector-Neri Castañeda, namely, that the simple rule -/- `(A knows that P) implies P' -/- apparently does not hold if P contains a quasi-indexical. We present a single rule, in the context of a knowledge-representation and reasoning system, that holds for all P, including those containing quasi-indexicals. In so doing, we explore the difference (...) between reasoning in a public communication language and in a knowledge-representation language, we demonstrate the importance of representing proper names explicitly, and we provide support for the necessity of considering sentences in the context of extended discourse (for example, written narrative) in order to fully capture certain features of their semantics. (shrink)

Interpreters of Hume on causation consider that an advantage of the ‘quasi-realist’ reading is that it does not commit him to scepticism or to an error theory about causal reasoning. It is unique to quasi-realism that it maintains this positive epistemic result together with a rejection of metaphysical realism about causation: the quasi-realist supplies an appropriate semantic theory in order to justify the practice of talking ‘as if’ there were causal powers in the world. In this (...) paper, I problematise the quasi-realist reading of Hume on causation by showing how quasi-realism does not speak to inductive scepticism. I also offer evidence that Hume takes inductive scepticism to result from his theory of causation, and that his scepticism is tied to his rejection of metaphysical causal realism. (shrink)

Quasi-truth is a formal approach to a pragmatically-oriented view of truth. The basic plan motivating the framework consists in providing for a more realistic account of truth, accommodating situations where there is incomplete information, as typically happens in the practice of science. The historical sciences are a case in hand, where incomplete information is the rule. It would seem, then, that the quasi-truth approach would be the most appropriate one to deal with historical sciences, then. In this paper, (...) we explore this possibility and use the historical sciences as a test case for the approach of quasi-truth. Our claim is that, on what concerns historical sciences, the quasi-truth approach fails in two basic senses; first, by misrepresenting some cases concerning incomplete information, and second, by falling short of accounting for many features of incomplete information peculiar to historical sciences. We conclude that, despite its stated goals, quasi-truth must be either amended or substituted if the goal of a more faithful representation of scientific practice is to be achieved. (shrink)

A canonical Gentzen-type system is a system in which every rule has the subformula property, it introduces exactly one occurrence of a connective, and it imposes no restrictions on the contexts of its applications. A larger class of Gentzen-type systems which is also extensively in use is that of quasi-canonical systems. In such systems a special role is given to a unary connective \ of the language. Accordingly, each application of a logical rule in such systems introduces either a (...) formula of the form \\), or of the form \\), and all the active formulas of its premises belong to the set \. In this paper we investigate the whole class of quasi-canonical systems. We provide a constructive coherence criterion for such systems, and show that a quasi-canonical system is coherent iff it is analytic iff it has a characteristic non-deterministic matrix which is based on some subset of the set of the four truth-values which are used in the famous Dunn–Belnap four-valued matrix for information processing. In addition, we determine when a quasi-canonical system admits cut-elimination. (shrink)

In 1986, Mikenberg et al. introduced the semantic notion of quasi-truth defined by means of partial structures. In such structures, the predicates are seen as triples of pairwise disjoint sets: the set of tuples which satisfies, does not satisfy and can satisfy or not the predicate, respectively. The syntactical counterpart of the logic of partial truth is a rather complicated first-order modal logic. In the present article, the notion of predicates as triples is recursively extended, in a natural (...) way, to any complex formula of the first-order object language. From this, a new definition of quasi-truth is obtained. The proof-theoretic counterpart of the new semantics is a first-order paraconsistent logic whose propositional base is a 3-valued logic belonging to hierarchy of paraconsistent logics known as Logics of Formal Inconsistency, which was proposed by Carnielli and Marcos in 2002. (shrink)

In order to develop an account of scientific rationality, two problems need to be addressed: (i) how to make sense of episodes of theory change in science where the lack of a cumulative development is found, and (ii) how to accommodate cases of scientific change where lack of consistency is involved. In this paper, we sketch a model of scientific rationality that accommodates both problems. We first provide a framework within which it is possible to make sense of scientific (...) revolutions, but which still preserves some (partial) relations between old and new theories. The existence of these relations help to explain why the break between different theories is never too radical as to make it impossible for one to interpret the process in perfectly rational terms. We then defend the view that if scientific theories are taken to be quasi-true, and if the underlying logic is paraconsistent, it's perfectly rational for scientists and mathematicians to entertain inconsistent theories without triviality. As a result, as opposed to what is demanded by traditional approaches to rationality, it's not irrational to entertain inconsistent theories. Finally, we conclude the paper by arguing that the view advanced here provides a new way of thinking about the foundations of science. In particular, it extends in important respects both coherentist and foundationalist approaches to knowledge, without the troubles that plague traditional views of scientific rationality. (shrink)