Namespaces
Variants
Actions

Difference between revisions of "Recursive relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (Undo revision 48461 by Ulf Rehmann (talk))
Tag: Undo
m (tex encoded by computer)
 
Line 1: Line 1:
A [[Relation|relation]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803201.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803202.png" /> is the set of natural numbers, such that the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803203.png" /> defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803204.png" /> by the condition
+
<!--
 +
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.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803205.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
is a [[Recursive function|recursive function]]. In particular, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803206.png" />, the universal relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803207.png" /> and the zero relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803208.png" /> are recursive relations. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r0803209.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032010.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032011.png" />-place recursive relations, then the relations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032015.png" /> will also be recursive relations. With regard to the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032018.png" />, the system of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080320/r08032019.png" />-place recursive relations thus forms a [[Boolean algebra|Boolean algebra]].
+
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=49396
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article