We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

Structuralism is one of the most popular contemporary accounts of mathematics. Despite its popularity, it has been challenged on the grounds of consistency. In this paper, I show that existing arguments purporting to establish an inconsistency miss the mark. I then proceed to develop a new argument against realist structuralism, to show that the commitment to mathematical pluralism and the structural identity criterion embraced by the realist structuralist jointly entail a contradiction.

This paper introduces and defends a new principle for when a structural equation model is apt for analyzing actual causation. Any such analysis in terms of these models has two components: a recipe for reading claims of actual causation off an apt model, and an articulation of what makes a model apt. The primary focus in the literature has been on the first component. But the problem of structural isomorphs has made the second especially pressing (Hall Citation2007; (...) Hitchcock Citation2007a). Those with realist sympathies have reason to resist the standard response to this problem, which introduces a normative parameter into the metaphysics (Hall Citation2007; Halpern and Hitchcock Citation2010, Citation2015; Halpern Citation2016a; Menzies Citation2017; Gallow Citation2021). However, the only alternative solution in the literature leaves central questions unanswered (Blanchard and Schaffer Citation2017). I propose an independently motivated aptness requirement, Evident Mediation, that provides the missing details and resolves the structural isomorph problem without need for a normative parameter. (shrink)

We give some new examples of possible degree spectra of invariant relations on Δ20-categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ20-categorical computable structure is either intrinsically (...) computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings.We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ20-categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14]. (shrink)

We show that if A and $\widehat{A}$ are automorphic via Φ then the structures $S_{R}(A)$ and $S_{R}(\widehat{A})$ are $\Delta_{3}^{0}-isomorphic$ via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.

In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra of structures, computable dimensions, expansions (...) by constants, and the degree spectra of relations. (shrink)

We study the partial orderings of the form ⟨P,⊂⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle \mathbb{P}, \subset\rangle}$$\end{document}, where X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} is a binary relational structure with the connectivity components isomorphic to a strongly connected structure Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Y}}$$\end{document} and P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{P} }$$\end{document} is the set of substructures of X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} (...) \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {X}}$$\end{document} isomorphic to X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document}. We show that, for example, for a countable X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document}, the poset ⟨P,⊂⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle \mathbb {P}, \subset\rangle}$$\end{document} is either isomorphic to a finite power of P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{P} }$$\end{document} or forcing equivalent to a separative atomless σ-closed poset and, consistently, to P/fin. In particular, this holds for each ultrahomogeneous structure X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} such that X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}}$$\end{document} or Xc\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{X}^{c}}$$\end{document} is a disconnected structure and in this case Y\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Y}}$$\end{document} can be replaced by an ultrahomogeneous connected digraph. (shrink)

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (∑ 0 4 , ∑ 0 3 ), i.e. isomorphic to the lattice of ∑ 0 4 sets together with a unary predicate selecting out exactly the ∑ 0 3 sets.

The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...) the minimum element of the partially ordered set is computable. This solves the spectrum problem. The theorem and modifications of its proof produce computably categorical structures whose expansions by finite number of constants are not computably categorical and, indeed, ones whose expansions can have any finite number of computable isomorphism types. They also provide examples of computably categorical structures that remain computably categorical under expansions by constants but have no Scott family. (shrink)

This paper introduces and defends a new principle for when a structural equation model is apt for analyzing actual causation. Any such analysis in terms of these models has two components: a recipe for reading claims of actual causation off an apt model, and an articulation of what makes a model apt. The primary focus in the literature has been on the first component. But the problem of structural isomorphs has made the second especially pressing (Hall 2007; (...) Hitchcock 2007a). Those with realist sympathies have reason to resist the standard response to this problem, which introduces a normative parameter into the metaphysics (Hall 2007; Halpern and Hitchcock 2010, 2015; Halpern 2016a; Menzies 2017; Gallow 2021). However, the only alternative solution in the literature leaves central questions unanswered (Blanchard and Schaffer 2017). I propose an independently motivated aptness requirement, Evident Mediation, that provides the missing details and resolves the structural isomorph problem without need for a normative parameter. (shrink)

We introduce several highness notions on degrees related to the problem of computing isomorphisms between structures, provided that isomorphisms exist. We consider variants along axes of uniformity, inclusion of negative information, and several other problems related to computing isomorphisms. These other problems include Scott analysis (in the form of back-and-forth relations), jump hierarchies, and computing descending sequences in linear orders.

Feature structures are employed in various forms in many areas of linguistics. Informally, one can picture a feature structure as a sort of tree decorated with information about constraints requiring that specific subtrees be identical (isomorphic). Here I show that this informal picture of feature structures can be used to characterize exactly the class of feature structures under their usual subsumption ordering. Furthermore, once a precise definition of tree is fixed, this characterization makes use only of standard domain-theoretic notions regarding (...) the information borne by elements in a domain, thus removing (or better, explaining) all apparentlyad hoc choices in the original definition of feature structures. In addition, I show how this characterization can be parameterized in order to yield similar characterizations of various different notions of feature structure, including acyclic structures, structures with appropriateness conditions and structures with apartness conditions (used to model path inequations). The generalizations to other notions of feature structure also emphasize that the construction given here is in fact independent of the application to feature structures. (shrink)

The theory of institutional isomorphism has been criticized for overemphasizing organizational convergence and neglecting organizational divergence. Drawing on a range of empirical data, this paper shows that multi-dimensional accounts of isomorphic change are not necessarily incompatible with accounts emphasizing divergence as a typical form of organizational response to environmental uncertainties. The specific case investigated is the proliferation of academic organizational units teaching law at Australian universities over a ten-year period that saw far-reaching structural transformations of the Australian university system. (...) The key heuristic strategy employed in this paper is to scrutinize when isomorphic responses appear to occur, and which specific organizational form they take. In the empirical case examined, scrutiny of each of these dimensions strongly suggests that at least some isomorphic responses of universities were driven by a dual agenda of manifesting not only similarity but also distinction. (shrink)

A popular interpretation of linguistic theories has it that they should describe the brain at a high level of abstraction. One way this has been understood is as the requirement that the theory’s derivational structure reflect (by being isomorphic to) relevant structural properties of the language user’s brain. An important criticisrn of this idea, made originally by Crispin Wright against Gareth Evans in the 1980s, still has purchase, notwithstanding attempts to reply to it, notably by Martin Davies and, indirectly, (...) Christopher Peacocke. Wright’s objection seems to have been forgotten rather than seen off. (shrink)

In this paper we argue that structural explanations are an effective way of explaining well known relativistic phenomena like length contraction and time dilation, and then try to understand how this can be possible by looking at the literature on scientific models. In particular, we ask whether and how a model like that provided by Minkowski spacetime can be said to represent the physical world, in such a way that it can successfully explain physical phenomena structurally. We conclude by (...) claiming that a partial isomorphic approach to scientific representation can supply an answer only if supplemented by a robust injection of pragmatic factors. (shrink)

In this paper we study a notion of HL-extension for a structure in a finite relational language $\mathcal {L}$. We give a description of all finite minimal HL-extensions of a given finite $\mathcal {L}$ -structure. In addition, we study a group-theoretic property considered by Herwig–Lascar and show that it is closed under taking free products. We also introduce notions of coherent extensions and ultraextensive $\mathcal {L}$ -structures and show that every countable $\mathcal {L}$ -structure can be extended to a countable (...) ultraextensive structure. Finally, it follows from our results that the automorphism group of any countable ultraextensive $\mathcal {L}$ -structure has a dense locally finite subgroup. (shrink)

For a computable structure $\mathcal {M}$, the categoricity spectrum is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable copies of $\mathcal {M}$. If the spectrum has a least degree, this degree is called the degree of categoricity of $\mathcal {M}$. In this paper we investigate spectra of categoricity for computable rigid structures. In particular, we give examples of rigid structures without degrees of categoricity.

We present three examples of countable homogeneous structures whose automorphism groups are not universal, namely, fail to contain isomorphic copies of all automorphism groups of their substructures.Our first example is a particular case of a rather general construction on Fraïssé classes, which we call diversification, leading to automorphism groups containing copies of all finite groups. Our second example is a special case of another general construction on Fraïssé classes, the mixed sums, leading to a Fraïssé class with all finite symmetric (...) groups appearing as automorphism groups and at the same time with a torsion-free automorphism group of its Fraïssé limit. Our last example is a Fraïssé class of finite models with arbitrarily large finite abelian automorphism groups, such that the automorphism group of its Fraïssé limit is again torsion-free. (shrink)

In this paper I begin with a recent challenge to the Semantic Approach and identify an underlying assumption, namely that identity conditions for theories should be provided. Drawing on previous work, I suggest that this demand should be resisted and that the Semantic Approach should be seen as a philosophical device that we may use to represent certain features of scientific practice. Focussing on the partial structures variant of that approach, I then consider a further challenge that arises from a (...) concern with the role of idealisations in that practice. I argue that the partial structures approach is capable of meeting this challenge and I conclude with some broader observations about the role of such formal accounts within the philosophy of science. (shrink)

A countable, atomically stable structure U in a finite, relational language has fewer than 2 ω non-isomorphic substructures if and only if U is cellular. An example shows that the finiteness of the language is necessary.

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M' over the same vocabulary if Φ is true on M but false on M'. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M'. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M'. We prove that every n-element structure M is identifiable by a (...) formula with quantifier rank less than (1- 1/2k)n+k²-k+4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than (1-1/2k²+2)n+k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n-√ n+k²+k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n-O(√ n) quantifiers are necessary. (shrink)

We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order ($$\mathbb {Z},<$$ Z, < ) are dense. Finally we characterise the Boolean algebras which have a punctually 1-decidable (...) presentation that is computably isomorphic to a 1-decidable presentation. (shrink)

A common way to understand memory structures in the cognitive sciences is as a cognitive map​. Cognitive maps are representational systems organized by dimensions shared with physical space. The appeal to these maps begins literally: as an account of how spatial information is represented and used to inform spatial navigation. Invocations of cognitive maps, however, are often more ambitious; cognitive maps are meant to scale up and provide the basis for our more sophisticated memory capacities. The extension is not meant (...) to be metaphorical, but the way in which these richer mental structures are supposed to remain map-like is rarely made explicit. Here we investigate this missing link, asking: how do cognitive maps represent non-spatial information?​ We begin with a survey of foundational work on spatial cognitive maps and then provide a comparative review of alternative, non-spatial representational structures. We then turn to several cutting-edge projects that are engaged in the task of scaling up cognitive maps so as to accommodate non-spatial information: first, on the spatial-isometric approach​ , encoding content that is non-spatial but in some sense isomorphic to spatial content; second, on the ​ abstraction approach​ , encoding content that is an abstraction over first-order spatial information; and third, on the ​ embedding approach​ , embedding non-spatial information within a spatial context, a prominent example being the Method-of-Loci. Putting these cases alongside one another reveals the variety of options available for building cognitive maps, and the distinctive limitations of each. We conclude by reflecting on where these results take us in terms of understanding the place of cognitive maps in memory. (shrink)

This paper studies the structure of semisimple rings using techniques of reverse mathematics, where a ring is left semisimple if the left regular module is a finite direct sum of simple submodules. The structure theorem of left semisimple rings, also called Wedderburn-Artin Theorem, is a famous theorem in noncommutative algebra, says that a ring is left semisimple if and only if it is isomorphic to a finite direct product of matrix rings over division rings. We provide a proof for the (...) theorem in $$\mathrm RCA_{0}$$, showing the structure theorem for computable semisimple rings. The decomposition of semisimple rings as finite direct products of matrix rings over division rings is unique. Based on an effective proof of the Jordan-Hölder Theorem for modules with composition series, we also provide an effective proof for the uniqueness of the matrix decomposition of semisimple rings in $$\mathrm RCA_{0}$$. (shrink)

An interesting feature of some sets of representations is that their structure mirrors the structure of the items they represent. Founding an account of representational content on isomorphism, homomorphism or structural resemblance has proven elusive, however, largely because these relations are too liberal when the candidate structure over representational vehicles is unconstrained. Furthermore, in many cases where there is a clear isomorphism, it is not relied on in the way the representations are used. That points to a potential resolution: (...) that an isomorphism must be used, hence usable, if it is to be an ingredient in a theory of content. This paper argues that the class of exploitable isomorphisms can indeed play a content-constituting role. (shrink)

We look for a converse to a result from [N. Thapen, A model-theoretic characterization of the weak pigeonhole principle, Annals of Pure and Applied Logic 118 175–195] that if the weak pigeonhole principle fails in a model K of bounded arithmetic, then there is an end-extension of K interpretable inside K. We show that if a model J of an induction-free theory of arithmetic is interpretable inside K, then either J is isomorphic to an initial segment of K , or (...) K is isomorphic to an initial segment of J and in this case the weak pigeonhole principle fails in K. This result is formulated in terms of a theory of bounded arithmetic with a greatest element. We go on to consider structures defined by oracles, and use the probabilistic witnessing theorem for to give a general criterion for what can be proved about these using the weak pigeonhole principle. We also show that the injective WPHP is not provable in this theory in the relativized case. (shrink)

We study those relational structures S with the property that each partition of S contains a block isomorphic to S. We show that the Fraïsse limits of parametric classes K. have property ; over a binary language, every countable structure in K satisfying along with a condition on 1-extensions must be isomorphic to this limit.

We introduce and study the framework of compact metric structures and their associated notions of isomorphisms such as homeomorphic and bi-Lipschitz isomorphism. This is subsequently applied to model various classification problems in analysis such as isomorphism ofC*-algebras and affine homeomorphism of Choquet simplices, where among other things we provide a simple proof of the completeness of the isomorphism relation of separable, simple, nuclearC*-algebras recently established by M. Sabok.

Let equation image denote the inverse limit of all finite cyclic groups. Let F, G and H be abelian groups with H ≤ G. Let FβH denote the abelian group , where +βis defined by +β = + β — β) for a certain β : F → G linear mod H meaning that β = 0 and β + β — β ∈ H for all a, b in F. In this paper we show that the following hold: The (...) additive group of any nonstandard model ℤ* of the ring ℤ is isomorphic to βH for a certain β : ℤ*+/H → equation image linear mod H. equation image is isomorphic to βH for some β : equation image/H →ℚ linear mod H, though equation image is not the additive group of any model of Th and the exact sequence H → equation image → equation image/H is not splitting. (shrink)

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

Ramsey algebras are an attempt to investigate Ramsey spaces generated by algebras in a purely combinatorial fashion. Previous studies have focused on the basic properties of Ramsey algebras and a few specific examples. In this article, we study the properties of Ramsey algebras from a structural point of view. For instance, we will see that isomorphic algebras have the same Ramsey algebraic properties, but elementarily equivalent algebras need not be so, as expected. We also answer an open question about (...) Cartesian products of Ramsey algebras. (shrink)

This paper presents a new language for isomorphic representations of legalknowledge in feature structures. The language includes predefinedstructures based on situation theory for common-sense categories, andpredefined structures based on Van Kralingens frame-based conceptualmodelling language for legal rules. It is shown that the flexibility of thefeature-structure formalism can exploited to allow for structure-preservingrepresentations of non-primitive concepts, and to enable various types ofinteraction and cross- reference between language elements. A fragment of theDutch Opium Act is used to illustrate how modelling and reasoning (...) proceed in practice. (shrink)

Debates about the ontological implications of the general theory of relativity have long oscillated between spacetime substantivalism and relationism. I evaluate such debates by claiming that we need a third option, which I refer to as “structural spacetime realism.” Such a tertium quid sides with the relationists in defending the relational nature of the spacetime structure, but joins the substantivalists in arguing that spacetime exists, at least in part, independently of particular physical objects and events, the degree of “independence” (...) being given by the extent to which geometrical laws exist “over and above” physical events exemplifying them. By showing that structural spacetime realism is the natural outcome of a semantic, model-theoretic approach to the nature of scientific theories, I conclude by arguing that the notion of partial isomorphic representation is the most plausible candidate to connect spacetime models with reality. (shrink)

Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...) classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields. (shrink)

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...) definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

We show that there is a complete, consistent Borel theory which has no "Borel model" in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel. We also investigate Borel isomorphisms between Borel structures.

Among the results of this paper are the following: 1. Every Boolean (ultra) power is the union of an updirected elementary family of direct ultrapowers. 2. Under certain conditions, a finitely iterated Boolean ultrapower is isomorphic to a single Boolean ultrapower. 3. A ω-bounded filtral power is an elementary substructure of a filtral power. 4. Let K be an elementary class closed under updirected unions (e.g., if K is an amalgamation class); then K is closed under finite products if and (...) only if K is closed under reduced products if and only if K is a Horn class. (shrink)

Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose (...) domain the image of R is hypersimple and of arbitrary nonzero computably enumerable Turing degree. (shrink)

We show how to encode, by classical structures, both the objects and the morphisms of the category of complete metric spaces and uniformly continuous maps. The result is a category of, what we call, cognate metric spaces and cognate maps. We show this category relativizes to all models of set theory. We extend this encoding to an encoding of complete metric structures by classical structures. This provide us with a general technique for translating results about infinitary logic on classical structures (...) to the setting of infinitary continuous logic on continuous structures. Our encoding will also allow us to talk about not only the relations between complete metric structures, but also the potential relations between complete metric structures, i.e. those which are satisfied in some larger model of set theory. For example we will show that given any two complete metric structures we can determine if they are potentially isomorphic by looking at any admissible set which contains them both. (shrink)

Logical semantics includes once again structured meanings in its repertoire. The leading idea is that semantic and syntactic structure are more or less isomorphic. A key motive for reintroducing sensitivity to semantic structure is to obtain fine‐grained meanings, which are individuated more finely than in possible‐world semantics, namely up to necessary equivalence. Just getting the truth‐conditions right is deemed insufficient for a full semantic analysis of sentences. This paper surveys some of the most recent contributions to the program of structured (...) meaning, while providing historical background. I suggest that to make substantial advances the program needs to solve the problem of propositional unity and develop an intensional mereology of abstract objects. (shrink)

We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size $2^{2^{\aleph }0}$ , the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size $2^{2^{\aleph }0}$ , and in fact these big chains occur in every infinite interval. We also (...) study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice. (shrink)

The model theoretic `back and forth' construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ 0 -categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called `going forth') and to determine when it works and when it fails. Partial answers to this question are found, extending those (...) earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ 0 -categorical ω-stable structures. The work is based on the author's Ph.D. thesis. (shrink)

We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

LetMbe a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by definingd(g, h) = Ω{2−n:g(xn) ≠h(xn) org−1(xn) ≠h−1(xn)} where {xn:n∈ ω} is an enumeration ofMAn automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In the (...) present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms ofMwhich can be considered as an atomic model of some theory naturally associated toM. We do it in a general context of weak models for second-order quantifiers.The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks. (shrink)

We give a general framework for the treatment of perturbations of types and structures in continuous logic, allowing to specify which parts of the logic may be perturbed. We prove that separable, elementarily equivalent structures which are approximately $aleph_0$-saturated up to arbitrarily small perturbations are isomorphic up to arbitrarily small perturbations. As a corollary, we obtain a Ryll-Nardzewski style characterisation of complete theories all of whose separable models are isomorphic up to arbitrarily small perturbations.

We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.

Let $\scr{M}=\langle M,+,<,0,S\rangle $ be a linear o-minimal expansion of an ordered group, and $G=\langle G,\oplus ,e_{G}\rangle $ an n-dimensional group definable in $\scr{M}$ . We show that if G is definably connected with respect to the t-topology, then it is definably isomorphic to a definable quotient group U/L, for some convex ${\ssf V}\text{-definable}$ subgroup U of $\langle M^{n},+\rangle $ and a lattice L of rank equal to the dimension of the 'compact part' of G.

Let M be a big o-minimal structure and G a type-definable group in Mⁿ. We show that G is a type-definable subset of a definable manifold in Mⁿ that induces on G a group topology. If M is an o-minimal expansion of a real closed field, then G with this group topology is even definably isomorphic to a type-definable group in some Mk with the topology induced by Mk. Part of this result holds for the wider class of so-called invariant (...) groups: each invariant group G in Mⁿ has a unique topology making it a topological group and inducing the same topology on a large invariant subset of the group as Mⁿ. (shrink)