Strictly Well-Founded Relation has no Relational Loops

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\prec$ be a strictly well-founded relation on $A$ and let $x_1, x_2, \ldots, x_n \in A$.


Then:

$\neg \paren {x_1 \prec x_2 \land x_3 \prec x_4 \cdots \land x_n \prec x_1}$

That is, there are no relational loops within $A$.


Proof

Since $x_1, x_2, \ldots, x_n \in A$, there exists a $y$ such that $y = \set {x_1, x_2, \ldots, x_n}$.

Then $y$ is a non-empty subset of $A$.

So, by the definition of a strictly well-founded relation:

$\exists w \in y: \forall z \in y: \neg w \prec z$

Now, suppose $x_1 \prec x_2 \land x_2 \prec x_3 \cdots \land x_n \prec x_1$.

But since the elements of $y$ are $x_1, x_2, \ldots, x_n$, then this contradicts the previous statement, since:

$\forall w \in y: \exists z \in y: w \prec z$

Thus a founded relation has no relational loops.


This article, or a section of it, needs explaining.
In particular: is a "founded relation" the same as a "foundational relation", that is a (strictly) well-founded relation? If so, use the same terminology throughout the entire page; if not, provide a definition for the former.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.


$\blacksquare$

Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Strictly_Well-Founded_Relation_has_no_Relational_Loops&oldid=518436"