Definition:Strictly Well-Founded Relation

From ProofWiki
Jump to navigation Jump to search


Let $\struct {S, \RR}$ be a relational structure.

Definition 1

$\RR$ is a strictly well-founded relation on $S$ if and only if every non-empty subset of $S$ has a strictly minimal element under $\RR$.

Definition 2

$\RR$ is a strictly well-founded relation on $S$ if and only if:

$\forall T: \paren {T \subseteq S \land T \ne \O} \implies \exists y \in T: \forall z \in T: \neg \paren {z \mathrel \RR y}$

where $\O$ is the empty set.

Definition 3

Let $\RR$ be a well-founded relation which is also antireflexive.

Then $\RR$ is a strictly well-founded relation on $S$.

Also known as

A strictly well-founded relation is also known in the literature as a foundational relation.

It is commonplace in the literature and on the internet to use the term well-founded relation for strictly well-founded relation.

However, $\mathsf{Pr} \infty \mathsf{fWiki}$ prefers the more cumbersome and arguably more precise strictly well-founded relation in preference to all others.

Some sources do not hyphenate, and present the name as strictly wellfounded relation.

Also see

  • Results about well-founded relations can be found here.