- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Switch to: Citations
References in:
Add references
You must login to add references.
|
|
|
Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...) |
|
|
We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are p-divisible for infinitely many primes p, or groups of the form ⊕ p∈I Z(p ∞ ), where I is an infinite set of primes. |
|
|
. We prove a jump inversion theorem for the enumeration jump and a minimal pair type theorem for the enumeration reducibilty. As an application some results of Selman, Case and Ash are obtained. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We show that if H is an effectively completely decomposable computable torsion-free abelian group, then there is a computable copy G of H such that G has computable orders but not orders of every degree. |
|
|
Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...) |
|
|
We show that a set has an η-representation in a linear order if and only if it is the range of a 0'-computable limitwise monotonic function. We also construct a Δ₃ Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey. |
|
|
The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply (...) |
|
|
We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω. |
|
|
|
|
|
We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$. |
|
|
|
|
|
|
|
|
The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders. |
|
|
We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical. |
|
|
In order to apply known general theorems about the effective properties of recursive structures in a particular recursive structure, it is necessary to verify that certain decidability conditions are satisfied. This requires the determination of when certain relations, called back and forth relations, hold between finite strings of elements from the structure. Here we determine this for recursive reduced abelian p-groups, thus enabling us to apply these theorems. |
|
|
In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations. |
|
|
We show, for each computable ordinal α and degree $\alpha > {0^{\left( \alpha \right)}}$, the existence of a torsion-free abelian group with proper α th jump degree α. |
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-hc2g5 uwo