Difference between revisions of "Recursive relation"
From Encyclopedia of Mathematics
Ulf Rehmann (talk | contribs) m (Undo revision 48461 by Ulf Rehmann (talk)) Tag: Undo |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | r0803201.png | ||
| + | $#A+1 = 19 n = 0 | ||
| + | $#C+1 = 19 : ~/encyclopedia/old_files/data/R080/R.0800320 Recursive relation | ||
| + | Automatically converted into TeX, above some diagnostics. | ||
| + | Please remove this comment and the {{TEX|auto}} line below, | ||
| + | if TeX found to be correct. | ||
| + | --> | ||
| − | + | {{TEX|auto}} | |
| + | {{TEX|done}} | ||
| − | is a [[Recursive function|recursive function]]. In particular, for any | + | A [[Relation|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|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|Boolean algebra]]. | ||
Latest revision as of 14:55, 7 June 2020
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
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