Namespaces
Variants
Actions

Difference between revisions of "Recursive relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (Undo revision 48461 by Ulf Rehmann (talk))
Tag: Undo
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.
 
−
-->
 
  
−
{{TEX|auto}}
+
<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|done}}
 
  
−
A [[Relation|relation]]  $  R \subseteq \mathbf N  ^ {n} $,
+
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]].
−
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 \{
 
−
 
 
−
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]].
 

Revision as of 14:53, 7 June 2020

A relation , where is the set of natural numbers, such that the function defined on by the condition

is a recursive function. In particular, for any , the universal relation and the zero relation are recursive relations. If and are -place recursive relations, then the relations , , , will also be recursive relations. With regard to the operations , , , the system of all -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=48461
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article
Retrieved from "https://encyclopediaofmath.org/index.php?title=Recursive_relation&oldid=49396"