We prove that the generalized cancellation axiom for incomplete comparative probability relations introduced by Rios Insua and Alon and Lehrer is stronger than the standard cancellation axiom for complete comparative probability relations introduced by Scott, relative to their other axioms for comparative probability in both the finite and infinite cases. This result has been suggested but not proved in the previous literature.

We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{}$-computable Polish space; this answers a question of Nies. (...) We also prove analogous results for compact Polish groups and locally path-connected spaces. (shrink)

We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...) of computing an isomorphism between the given structure and another copy${\cal B}$in the cone is a c.e. degree in${\rm{\Delta }}_\alpha ^0\left$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions. (shrink)

ABSTRACT This essay advances several interrelated arguments concerning the proper role of the state with regard to marriage and divorce but my main contention is that ‘pure’no‐fault divorce laws are unjust—or, at least, they are unjust if marriage involves a genuinely contractual element, and there seems to be very little doubt that it does. Locke, Kant and Hegel are three eminent thinkers who are alike in viewing marriage as a contract and in the first two sections of the essay I (...) consider their views on the role of contract in marriage. Whilst holding that marriage is more than a contract, I also hold that it is not less than a contract. In section three I consider the implications of this ‘not less than’, the most important one being that ‘pure’no‐fault divorce laws are unjust. I shall contend that whilst the irretrievable breakdown of marriage may be regarded as a suitable ground for divorce, it simply cannot, and certainly ought not to, be regarded as a justificatory basis for the laying aside of rights acquired by individuals as a result of their having entered into a marital contract. However minimal one might wish the role of the state to be, or however averse one might be from allowing the state any role at all in purely personal and confidential relationships, yet to allow the expression ‘the irretrievable breakdown of marriage’to be employed as a olanket to cover over the infringement of personal, contractually engendered and civilly recognised rights, is not to exercise commendable restraint but is, rather, to condone what is simply an abnegation by the state of its basic responsibility to ensure that justice prevails. (shrink)

In this article I argue against the view, recently espoused by several authors, that the `incommensurability of values' and `political pespectivism' offer us decisive reasons as to why we should break the link between representation and (the quest for) unity. I hold that it is of paramount importance to retain this essential link. Since Sir Isaiah Berlin has played a major (and in my view unfortunate) role in linking `politics as the quest for unity and the common good' with the (...) `totalitarian temptation', I proceed to show how it is possible to have an understanding of politics as precisely such a quest, but without succumbing to the temptation to totalitarianism that Berlin alerts us to. I then take issue with Chantal Mouffe's view that the tendency to antagonism, rather than the quest for unity and rational consensus, is `the essence of the political'. (shrink)

Every countable structure has a sentence of the infinitary logic $\mathcal {L}_{\omega _1 \omega }$ which characterizes that structure up to isomorphism among countable structures. Such a sentence is called a Scott sentence, and can be thought of as a description of the structure. The least complexity of a Scott sentence for a structure can be thought of as a measurement of the complexity of describing the structure. We begin with an introduction to the area, with short and simple proofs (...) where possible, followed by a survey of recent advances. (shrink)

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma (...) }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel. (shrink)

Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope of being (...) universal. We show that finitely generated groups are as universal as possible, given that they are finitely generated: for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties. The same is not true for finitely generated fields. We apply the results of this investigation to quasi Scott sentences, and also answer a question of Alvir, Knight, and McCoy. (shrink)

This article builds on Humberstone’s idea of defining models of propositional modal logic where total possible worlds are replaced by partial possibilities. We follow a suggestion of Humberstone by introducing possibility models for quantified modal logic. We show that a simple quantified modal logic is sound and complete for our semantics. Although Holliday showed that for many propositional modal logics, it is possible to give a completeness proof using a canonical model construction where every possibility consists of finitely many formulas, (...) we show that this is impossible to do in the first-order case. However, one can still construct a canonical model where every possibility consists of a computable set of formulas and thus still of finitely much information. (shrink)

The problem of inferring probability comparisons between events from an initial set of comparisons arises in several contexts, ranging from decision theory to artificial intelligence to formal semantics. In this paper, we treat the problem as follows: beginning with a binary relation ≥ on events that does not preclude a probabilistic interpretation, in the sense that ≥ has extensions that are probabilistically representable, we characterize the extension ≥+ of ≥ that is exactly the intersection of all probabilistically representable extensions of (...) ≥. This extension ≥+ gives us all the additional comparisons that we are entitled to infer from ≥, based on the assumption that there is some probability measure of which ≥ gives us partial qualitative information. We pay special attention to the problem of extending an order on states to an order on events. In addition to the probabilistic interpretation, this problem has a more general interpretation involving measurement of any additive quantity: e.g., given comparisons between the weights of individual objects, what comparisons between the weights of groups of objects can we infer? (shrink)

A computable structure [Formula: see text] is decidable if, given a formula [Formula: see text] of elementary first-order logic, and a tuple [Formula: see text], we have a decision procedure to decide whether [Formula: see text] holds of [Formula: see text]. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is [Formula: see text]-complete. We also show that for each [Formula: see text] (...) the index set of the computable structures with [Formula: see text]-decidable presentations is [Formula: see text]-complete. (shrink)

This paper investigates the principles that one must add to Boolean algebra to capture reasoning not only about intersection, union, and complementation of sets, but also about the relative size of sets. We completely axiomatize such reasoning under the Cantorian definition of relative size in terms of injections.

We investigate the computability-theoretic properties of valued fields, and in particular algebraically closed valued fields and p-adically closed valued fields. We give an effectiveness condition, related to Hensel’s lemma, on a valued field which is necessary and sufficient to extend the valuation to any algebraic extension. We show that there is a computable formally p-adic field which does not embed into any computable p-adic closure, but we give an effectiveness condition on the divisibility relation in the value group which is (...) sufficient to find such an embedding. By checking that algebraically closed valued fields and p-adically closed valued fields of infinite transcendence degree have the Mal’cev property, we show that they have computable dimension \. (shrink)

We can measure the complexity of a logical formula by counting the number of alternations between existential and universal quantifiers. Suppose that an elementary first-order formula $\varphi $ (in $\mathcal {L}_{\omega,\omega }$ ) is equivalent to a formula of the infinitary language $\mathcal {L}_{\infty,\omega }$ with n alternations of quantifiers. We prove that $\varphi $ is equivalent to a finitary formula with n alternations of quantifiers. Thus using infinitary logic does not allow us to express a finitary formula in a (...) simpler way. (shrink)

Our main result is that there exist structures which cannot be computably recovered from their tree of tuples. This implies that there are structures with no computable copies which nevertheless cannot code any information in a natural/functorial way.

An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial p. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we answer (...) a question previously raised by Bienvenu and Downey, who asked whether there is a minimal degree which is low-for-speed. The standard method of constructing a set of minimal degree via forcing is incompatible with making the set low-for-speed; but we are able to use an interesting new combination of forcing and full approximation to construct a set which is both of minimal degree and low-for-speed. (shrink)

We say that a theory [Formula: see text] satisfies arithmetic-is-recursive if any [Formula: see text]-computable model of [Formula: see text] has an [Formula: see text]-computable copy; that is, the models of [Formula: see text] satisfy a sort of jump inversion. We give an example of a theory satisfying arithmetic-is-recursive non-trivially and prove that the theories satisfying arithmetic-is-recursive on a cone are exactly those theories with countably many [Formula: see text]-back-and-forth types.

We say that a theory T satisfies arithmetic-is-recursive if any X′-computable model of T has an X-computable copy; that is, the models of T satisfy a sort of jump inversion. We give an example of a...

In this article I argue that the kind of ethical-metaphysical theory of the state that we broadly associate with idealist political philosophy provides us with a theoretical account of the state that is both sound and insightful and that, far from having been consigned to the dustbin of history by the hostile criticisms to which it has been subjected in the 20th century , it still remains the most profound and powerful account of the state available to the political science (...) community today. It is extremely important, I contend, in helping us to understand the state’s vital function as the font of emancipatory political criticism. I also suggest that the ethical-metaphysical theory of the state has the distinct advantage of providing us with a genuine ‘theory of the state’, for it alone wholeheartedly subscribes to the view that the state is the inner core or substance of political life, whereas its critics generally hold that the state is a dangerous illusion. (shrink)

In this article I argue that the kind of ethical-metaphysical theory of the state that we broadly associate with idealist political philosophy provides us with a theoretical account of the state that is both sound and insightful and that, far from having been consigned to the dustbin of history by the hostile criticisms to which it has been subjected in the 20th century, it still remains the most profound and powerful account of the state available to the political science community (...) today. It is extremely important, I contend, in helping us to understand the state’s vital function as the font of emancipatory political criticism. I also suggest that the ethical-metaphysical theory of the state has the distinct advantage of providing us with a genuine ‘theory of the state’, for it alone wholeheartedly subscribes to the view that the state is the inner core or substance of political life, whereas its critics generally hold that the state is a dangerous illusion. (shrink)