Namespaces
Variants
Actions

Difference between revisions of "Well-founded relation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
 +
[[Category:TeX done]]
 +
 
''well-founded partial order''
 
''well-founded partial order''
  
A ([[Partial order|partial order]]) relation on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976401.png" /> is called well-founded, or recursive, if every non-empty subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976402.png" /> has a least element with respect to this relation. Thus, a total order on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976403.png" /> (cf. [[Totally ordered set|Totally ordered set]]) that is well-founded makes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976404.png" /> a [[Well-ordered set|well-ordered set]].
+
A ([[Partial order|partial order]]) relation on a set $A$ is called well-founded, or recursive, if every non-empty subset of $A$ has a least element with respect to this relation. Thus, a total order on a set $A$ (cf. [[Totally ordered set|Totally ordered set]]) that is well-founded makes $A$ a [[Well-ordered set|well-ordered set]].
  
A relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976405.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976406.png" /> is well-founded if and only if for any set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976407.png" /> and function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976408.png" /> there is a unique function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w0976409.png" /> such that the following diagram commutes (cf. [[#References|[a1]]]):
+
A relation $R\subset A\times A$ on $A$ is well-founded if and only if for any set $B$ and function $g:\mathcal{P}(B)\rightarrow B$ there is a unique function $f$ such that the following diagram commutes (cf. [[#References|[a1]]]):
  
<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/w/w097/w097640/w09764010.png" /></td> </tr></table>
+
\[
 +
\begin{matrix}
 +
A & \xrightarrow{f} & B\\
 +
r\downarrow & & \uparrow g\\
 +
\mathcal{P}(A) & \xrightarrow[\mathcal{P}(f)]{} & \mathcal{P}(B)
 +
\end{matrix}
 +
\]
  
Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w09764011.png" /> is the set of all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w09764012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w09764013.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w09764014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097640/w09764015.png" />. In this form well-foundedness is defined in any elementary [[Topos|topos]].
+
Here, $\mathcal{P}(A)$ is the set of all subsets of $A$, $\mathcal{P}(f)(A')=\{f(a'):\, a'\in A'\}$ for $A'\in\mathcal{P}(A)$ and $r(a)=\{a':\, (a, a')\in R\}$. In this form well-foundedness is defined in any elementary [[Topos|topos]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Osius,  "Categorical set theory: a characterization of the category of sets"  ''J. Pure Appl. Algebra'' , '''4'''  (1974)  pp. 79–119</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. Chapt. II; esp. pp. 199ff</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.I. Goldblatt,  "Topoi: the categorical analysis of logic" , North-Holland  (1984)  pp. 318ff</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Osius,  "Categorical set theory: a characterization of the category of sets"  ''J. Pure Appl. Algebra'' , '''4'''  (1974)  pp. 79–119</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Odifreddi,  "Classical recursion theory" , North-Holland  (1989)  pp. Chapt. II; esp. pp. 199ff</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.I. Goldblatt,  "Topoi: the categorical analysis of logic" , North-Holland  (1984)  pp. 318ff</TD></TR></table>

Latest revision as of 19:23, 15 June 2017


well-founded partial order

A (partial order) relation on a set $A$ is called well-founded, or recursive, if every non-empty subset of $A$ has a least element with respect to this relation. Thus, a total order on a set $A$ (cf. Totally ordered set) that is well-founded makes $A$ a well-ordered set.

A relation $R\subset A\times A$ on $A$ is well-founded if and only if for any set $B$ and function $g:\mathcal{P}(B)\rightarrow B$ there is a unique function $f$ such that the following diagram commutes (cf. [a1]):

\[ \begin{matrix} A & \xrightarrow{f} & B\\ r\downarrow & & \uparrow g\\ \mathcal{P}(A) & \xrightarrow[\mathcal{P}(f)]{} & \mathcal{P}(B) \end{matrix} \]

Here, $\mathcal{P}(A)$ is the set of all subsets of $A$, $\mathcal{P}(f)(A')=\{f(a'):\, a'\in A'\}$ for $A'\in\mathcal{P}(A)$ and $r(a)=\{a':\, (a, a')\in R\}$. In this form well-foundedness is defined in any elementary topos.

References

[a1] G. Osius, "Categorical set theory: a characterization of the category of sets" J. Pure Appl. Algebra , 4 (1974) pp. 79–119
[a2] P. Odifreddi, "Classical recursion theory" , North-Holland (1989) pp. Chapt. II; esp. pp. 199ff
[a3] R.I. Goldblatt, "Topoi: the categorical analysis of logic" , North-Holland (1984) pp. 318ff
How to Cite This Entry:
Well-founded relation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Well-founded_relation&oldid=41630