Namespaces
Variants
Actions

Recursive relation

From Encyclopedia of Mathematics
Revision as of 14:55, 7 June 2020 by Ulf Rehmann (talk | contribs) (tex encoded by computer)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


A relation $ R \subseteq \mathbf N ^ {n} $, where $ \mathbf N $ is the set of natural numbers, such that the function $ f $ defined on $ \mathbf N ^ {n} $ by the condition

$$ f( x _ {1} \dots x _ {n} ) = \left \{ \begin{array}{ll} 1 & \textrm{ if } \langle x _ {1} \dots x _ {n} \rangle \in R , \\ 0 & \textrm{ if } \ \langle x _ {1} \dots x _ {n} \rangle \notin R, \\ \end{array} \right .$$

is a recursive function. In particular, for any $ n $, the universal relation $ \mathbf N ^ {n} $ and the zero relation $ \emptyset $ are recursive relations. If $ R $ and $ S $ are $ n $- place recursive relations, then the relations $ R \cup S $, $ R \cap S $, $ R ^ {c} = \mathbf N ^ {n} \setminus R $, $ R\setminus S $ will also be recursive relations. With regard to the operations $ \cup $, $ \cap $, $ {} ^ {c} $, the system of all $ n $- place recursive relations thus forms a Boolean algebra.

How to Cite This Entry:
Recursive relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Recursive_relation&oldid=49555
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article