原始再帰的関係
原始再帰的集合
は同じ意味である．
集合
$ A \sube \N^n
の
特性関数
$ \chi_A
が
原始再帰的関数
であるとき，
$ A
は
原始再帰的集合
または
原始再帰的関係
という．