Namespaces
Variants
Actions

Isol

From Encyclopedia of Mathematics
Revision as of 19:50, 29 April 2014 by Ivan (talk | contribs) (TeX)
Jump to: navigation, search

The recursive equivalence type of an isolated (that is, finite or immune, cf. Immune set) set of natural numbers. The set of all isols has the cardinality of the continuum and is a semi-ring under the operations of addition and multiplication defined for arbitrary recursive equivalence types. This semi-ring is called the arithmetic of isols. It has a number of properties of the arithmetic of natural numbers; in particular, all universal Horn formulas whose elementary subformulas represent equality of so-called combinatorial functions are true in it. An example of such a formula is the cancellation law: $X+Z=Y+Z\Rightarrow X=Y$. Isols can be regarded as recursive analogues of the cardinalities of Dedekind-finite sets, that is, sets not equivalent to any of their proper subsets.


Comments

A subset of the natural numbers $\mathbf N$ is an isolated set if it contains no infinite recursively-enumerable subset of $\mathbf N$.

References

[a1] Th.G. McLaughlin, "Regressive sets and the theory of isols" , M. Dekker (1982)
How to Cite This Entry:
Isol. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Isol&oldid=31995
This article was adapted from an original article by A.L. Semenov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article