Talk:Well-founded relation

Merge discussion

Having written this, I now think it should be merged somehow with the page about well-founded sets. The two pages complement each other well; there isn't much overlap, and I think both pages are good, but I think it might be better if all the information were in one place. Dominus 08:05, 10 Aug 2003 (UTC)

I agree. Since there are only 24 hours in a day, I doubt I will get to this soon, so if someone else is more energetic than I am, go for it. Michael Hardy 03:23, 17 Sep 2003 (UTC)

The merge has been completed yesterday, however the text could use some editing to remove duplication and tidy up the prose. -- Ap 11:26, 17 Sep 2003 (UTC)

I think it might merit some mention that the equivalency of the infinite descending chain condition and well-foundedness only holds under some choice, such as Dependent Choice. -- VV 20:24, 17 Sep 2003 (UTC)

---

There's a bit of a disconnect between the following two passages:

A set equipped with a well-founded relation is sometimes
said to be a well-founded set.

The axiom of regularity, which is one of the axioms of
Zermelo-Fraenkel set theory, asserts that all sets are well-founded.

In the second passage, what is meant by "wellfounded set" is that the elementhood relation on the set (or rather on its transitive closure) is wellfounded, not just any old relation. I think the definition implicit in the second passage is the correct one; the first passage should be amplified or deleted.

On a completely separate note, the spelling "wellfounded" is standard these days and should be acknowledged.--Trovatore 28 June 2005 19:35 (UTC)

for every OTHER element

<Quote> there is an element m of S such that for every element s of S, </Quote>

<Revision suggestion> there is an element m of S such that for every OTHER element s of S, </Revision suggestion>

Well, I'm not quite sure but isn't it more accurate? Cosfly 08:20, 7 December 2006 (UTC).

It depends on whether you're considering "strict" (irreflexive) or "nonstrict" (reflexive) wellfounded relations. There's a different definition for the two cases. But set membership is irreflexive and is sort of the model for this, and if you have a reflexive relation and you want to do induction on it, you're going to be using the strict part of the relation anyway. So the discussion might could use a little elaboration on this point, but I think it's not incorrect as it stands. --Trovatore 07:57, 7 December 2006 (UTC)

Well, but there are relations that are wellfounded AND reflextive. For example, the relation 'is greater or equal to' of the natural numbers is reflexive, AND well-order relation, which is equivalent to Well-Founded total order. So I suspect the suggestion "every OTHER element" encompasses both cases(reflexive and irreflexive) while current version of the article encompasses only the latter, though I cannot assert this strongly to the extent which I feel absolutely certain. Cosfly 08:34, 7 December 2006 (UTC)

The natural and simple definition for well-founded relations is irreflexive. The whole purpose of well-foundedness is to make induction (and recursion) work, and this requires irreflexivity. To deal with reflexivity, one has to insert extra conditions like "every other element" in the definition, in induction, in recursion, and generally in any other application of wellfoundedness I can think of. This is equivalent to working with $R\setminus \operatorname {id}$ instead of $R$, which makes the notion of reflexive wellfounded relations rather pointless. It only confuses the idea of wellfoundedness, and makes things more complicated.

The relation $\leq$ on natural numbers is not wellfounded. A well-order is a well-founded total strict order. As strict and nonstrict orders are interdefinable, and order theorists for whatever reasons prefer to work with nonstrict orders, the term well-order is also applied to the corresponding reflexive orders, but that does not make the "less-than-or-equal" relation itself well-founded. -- EJ 12:58, 7 December 2006 (UTC)

I think you're trying to impose a regularity on the usage that I doubt it really has, in practice. If you assert that the less-than-or-equal-to relation is wellfounded on the naturals, no one will say you're "wrong"; they'll understand from context what you mean, and will agree that you're right, given that meaning. --Trovatore 17:12, 7 December 2006 (UTC)

OK, I might have been overly fundamentalist. If you say that $\leq$ is well-founded, people will indeed understand what it means. However, I think the understanding in such a case is not that the definition of wellfoundedness is altered to allow for reflexive relations, but rather that it is a jargon shorthand for "the irreflexive variant of $\leq$ is well-founded". -- EJ 12:11, 8 December 2006 (UTC)

So Dr. EJ and Dr. Trovatore are anyway agreeing that in 'rigorous' sense well-order is a well-founded total 'strict' order. This implies the article 'well-order' in Wikipedia has not been written rigorously. And what confused me was at this point. Wikipedia and my text were saying different things for the same term! I think that article needs rivision to let novices make no confusion when they encounter two different explanations; strict and not-strict cases. Surely difference between rigorous and shorthand explanation is what a novice should be careful about.

And one more thing. 'well-order is well-founded total strict order' does not, in syntax itself, entail 'well-founded total strict order is well-order', which is its converse. But I was also curious whether the converse is actually true. Delving into this curiosity, I think, though not feeling certain, I proved the converse is false. I, as a novice, want to ask whether my conclusion(that the converse if false) is right. And if I am right, the article 'Well-order' might be improved by revising "Equivalently, a well-ordering is a well-founded linear ordering." into one which entails the falsity of its converse, giving more information. 59.4.224.150 07:14, 9 December 2006 (UTC)

Oops! It seems I've been automatically signed out for time delay. The comment above was written by me. Cosfly 07:16, 9 December 2006 (UTC)

I think there's a difference between "rigor" and assuming that everyone has the same definition for everything. Now, I admit to a personal bias that rigor is a bit overrated anyway. Not a lot overrated; it's still an important concept that people from outside mathematics don't sufficiently appreciate, but not the soul of mathematics, as some would have you believe. Just the same, no practical notion of rigor requires all workers in the field to have exactly the same definitions. Some times you have to check what definition is being used, or work it out from context.

A particular example of a (non-linear-order) relation that's naturally described in its reflexive form, and naturally described as wellfounded (at least up to a certain point) is Wadge reducibility, which is wellfounded on the determined pointclasses.

Still, you're right, if there's an inconsistency between WP articles, that should be addressed. --Trovatore 07:27, 9 December 2006 (UTC)

I agree, as it stands this article is not consistent with the entry on the minimal element of a set with a partial order; one also could add something on "no infinitely descending chains" 2008, 6th Oct

I also agree. The definition: "for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair (s,m) is not in R" eliminates all R which are reflexive, which makes the definition for a well-order absurd (because no relation could be a well-order, since total orders are reflexive). This is an incorrect definition for "minimal element" and needs to be fixed. I'll go ahead and make the edit. --75.180.20.49 (talk) 20:42, 15 March 2009 (UTC)

The definition is perfectly correct. The application to orders is discussed in the "Reflexivity" section. — Emil J. 15:23, 16 March 2009 (UTC)

Reflexivity aside, the definition is still inconsistent with the WP page on the minimal element. The definition here requires a pair (s, m) \not \in R. But according to the other page the least element of every subset also satisfies the condition for being minimal. — Preceding unsigned comment added by 203.143.175.186 (talk) 06:35, 16 February 2013 (UTC)

The inconsistencies (as noted above) between the definition provided here for "wellfounded" and the definition provided for on the article for "minimal elements" has yet to be addressed. I believe it to be likely confusing to novices who come to this site for clarification. In particular, and as noted above, the formal syntax definition for wellfounded currently provided in this article implicitly requires it to be strict (ie, irreflexive); however, the informal language preceding it (ie, stating it is a relation s.t. every nonempty set has a minimal element) cites specifically to the article for minimal element, where one currently finds that term being defined only to partially ordered set (which are reflexive)! Hoping someone can rectify this confusion. — Preceding unsigned comment added by 165.225.38.200 (talk) 19:39, 19 October 2018 (UTC)

Set-like relations and proper classes

Perhaps the article should be more careful to distinguish the case of proper classes, and the importance of set-like-ness should be stressed (without this requirement we could define truth by transfinite induction, contrary to Tarski!) --Quux0r 08:17, 16 April 2007 (UTC)

I know this I'm responding a bit late, but 1. I don't understand the remark about defining truth. 2. The requirement that the relation be set-like does not appear to be necessary if the axiom of foundation holds. --Dfeuer (talk) 18:13, 15 April 2013 (UTC)

Horrible mistake?

I'm not a math major (I'm a computer science/engineering major), but I think there's a horrible mistake in this article.

The article states that according to the axiom of regularity/axiom of foundation, all sets are well founded, but I believe that this is totally false and not what the axiom of regularity/foundation says at all.

To see why this is false, consider a set with two elements, a and b, and a relation < such that a < b and b < a. It's obvious that the complete set ( {a, b} ) has no least element.

The axiom of regularity/foundation as I understand it says that the class containing all sets is well-founded under the "contains" relation (i.e., the stylized epsilon symbol). This states that a specific class is well founded under a specific relation, not that every set is well founded under every relation, which is totally different.

This should also draw attention to the difference between a class and a set (they're not the same), so I think there should be some skepticism about the last comment regarding merging this article with well founded sets.

Again, I'm not a math major, so I'd prefer someone more specialized than I am review this before it's acted on, but I'm pretty sure this is a mistake based on my theory classes. Thanks.

EDIT: I went ahead and commented out this paragraph, because based on the previous discussion and looking at it, I'm more and more thinking this is probably a mistake, but I'm not trying to step on anyone's toes--it could be changed back. Thanks. 128.208.36.17 (talk) 11:29, 17 October 2011 (UTC)

The paragraph in question says:

In set theory, a set x is called a well-founded set if the set membership relation is well-founded on the transitive closure of x. The axiom of regularity, which is one of the axioms of Zermelo-Fraenkel set theory, asserts that all sets are well-founded.

It does not say that "every set is well founded under every relation" as you suggested; it says that a set is well-founded if the set membership relation—that is, the ε relation—is well-founded on that set, and claims that every set is well-founded under the ε relation. Your example uses a different relation. Of course nobody is going to say that sets are well-founded under arbitrary relations. I have restored the deleted paragraph. —Mark Dominus (talk) 14:06, 17 October 2011 (UTC)

Reply to this paragraph: I'm not sure whether what you are saying is true or false, however, the counterexample you used is not completely right because sets should have no repeated elements. — Preceding unsigned comment added by 197.161.45.170 (talk) 13:12, 30 November 2018 (UTC)

Variations in definitions

I'm far from an expert, but a small sample suggests substantial variation between different definitions. Leaving aside the descending chain condition (which I don't think is commonly used as a definition these days), there are still quite a few choices to be made:

1. Definition in terms of existence of a minimal/initial element vs. definition in terms of the validity of induction. These are classically equivalent in a rather trivial way, but not intuitionistically so.

2. Requiring the relation to be set-like (proper) or not. If so, then the next matter becomes irrelevant but generality is compromised. At least some sources separate these matters, speaking of well-founded proper relations.

3. Requiring every subclass to have a minimal element or only every subset. In the presence of the axioms of infinity, replacement, and foundation, it doesn't matter. But unless the stronger condition is met, one way or another, induction on proper classes will not work.

When it comes to the question of whether ∈ is well-founded on a class, matters are somewhat simplified, as the stronger form of (3) then follows from the weaker form given the axiom of infinity and the axiom of replacement.

Speculation: my guess is that some shy away from the strong form of (3) because it cannot be expressed directly in a first-order theory, as it quantifies over general classes. --Dfeuer (talk) 21:29, 10 April 2013 (UTC)

A simple example to help non-mathematicians?

For those of us not as conversant with all the terms and symbols of mathematics, a simple example near the top can greatly speed up comprehension. Here is some possible text, which might be placed just before: "(Some authors include ..." Please feel free to improve upon this.

For example, the relation "is less than" is wellfounded on the class of positive integers because any subset (eg, {5,3,9}) has a minimum (ie, 3). In the formalism: none of these are true: (5<3), (3<3), nor (9<3) -- or more generally, (s,m) does not observe the relation "is less than" for any s in the subset.

Just trying to make this accessible to a broader audience. EJR (talk) 06:41, 10 November 2013 (UTC)

R or > ?

The relation R and the concept of "minimal" might be understood easier if we use the letter > instead of R. Then again, maybe it's better to use the ambiguous R which doesn't bring with it all the assumptions of the more familiar ordering on the number line. Crasshopper (talk) 15:53, 19 January 2014 (UTC)

Definition

There seems to be a discrepancy in the definition. A wellfounded relation is defined in terms of minimal elements, but they on turn are only defined (in this wiki) for partial orderings. Madyno (talk) 18:16, 5 July 2015 (UTC)

Also: "some element m of any S is not related by sRm (for instance, "m is not smaller than") for the rest of the s ∈ S." Should sRm hold for s unequal to m? Madyno (talk) 12:35, 7 July 2015 (UTC)

Induction and recursion

Should there be an assumption that P(x) is true for every x∈X such that (z,x)∉R for every z∈X in order for the induction proof to work properly? Lapasotka (talk) 14:53, 18 October 2018 (UTC)

For such an x, the property   "P(y) is true for all y such that yRx"   is trivially true, so P(x) is required to be true by the induction rule given in the article. No change of text is necessary. - Jochen Burghardt (talk) 18:47, 18 October 2018 (UTC)

That's true. But at the same time, this is a hard enough problem for novices to work out that it may be worth saying something about it. I think explanatory footnotes are good for this sort of thing — they're visible without following a link, but they don't interrupt the flow as much as an inline explanation. --Trovatore (talk) 20:25, 18 October 2018 (UTC)

Parenthesis were deleted, fixed it

Revision as of 10:25, 10 June 2018 was correct, induction principle:

https://en.wikipedia.org/w/index.php?title=Well-founded_relation&type=revision&diff=845221027&oldid=845219501

Revision as of 16:27, 16 March 2014 was correct, wellfounded criteria:

https://en.wikipedia.org/w/index.php?title=Well-founded_relation&type=revision&diff=599890411&oldid=599870855

Both had the correct parenthesis. Added them again back.

Jan Burse (talk) 20:28, 13 November 2018 (UTC)

I would prefer to use some precedence rules to save parantheses. Unfortunately, there are several conventions around in textbooks, but I didn't find any of the mentioned in Universal quantification or quantification. Two conventions I remember are: :*Quantification has lower binding precedence than any other logical connective, that it, the scope of a quantifier is the maximally possible formula. For example, "∀x p(x) → q(y)" means the same as "∀x (p(x) → q(y))".

• Quantification has highest precedence, that is, the scope is minimal. With thi convention, "∀x p(x) → q(y)" means the same as "(∀x p(x)) → q(y)".

I don't see any use in surrounding the quantifier itself by parantheses, as in "(∀x) p(x)". It just makes the formula harder to read, but doesn't disambiguate anything. It is not even listed at Wikipedia:WikiProject_Logic/Standards_for_notation#Quantifiers (which fails to give any binding precedences).

Provided anybody can supply references (I'll try to find some, too), a standard (resp. a few different variants) should be agreed upon, it (resp. they) should be listed at the above project page, and Well-founded relation, as any other mathematics article, then should adhere to it (resp. one of them). - Jochen Burghardt (talk) 15:33, 14 November 2018 (UTC)

Presently, the first formula is

$(\forall S\subseteq X)[S\neq \emptyset \implies (\exists m\in S)(\forall s\in S)\lnot (sRm)].$

Your suggestion is

$\forall S\subseteq X\;[S\neq \emptyset \implies \exists m\in S\;\forall s\in S\;\lnot (sRm)].$

Using commas as in Epsilon-delta definition gives

$\forall S\subseteq X\;[S\neq \emptyset \implies \exists m\in S,\forall s\in S\;\lnot (sRm)],$

or

$\forall S\subseteq X,\;[S\neq \emptyset \implies \exists m\in S,\forall s\in S,\;\lnot (sRm)],$

IMO, the last version is acceptable, but it involves commas that do not appear in any logical theory. The second and third version are slightly confusing, as X may be viewed as a function of the remainder of the formula.

I believe (I have not verified recently) that parentheses around quantifiers are commonly used by Bourbaki and his followers. In any case, lacking of commonly accepted rules, we have to chose the less astonishing notation, that is the one that is the most immediately clear for the reader, namely the first one.

D.Lazard, 14 November 2018

I agree. I didn't see commas after quantifiers in textbooks, but I saw periods, like "$\forall S\subseteq X.\;[S\neq \emptyset \implies \exists m\in S.\forall s\in S.\;\lnot (sRm)]$". I don't know Bourbaki works, so I missed their notation. My above comment may be more appropriate at the Wikipedia:WikiProject_Logic/Standards_for_notation#Quantifiers talk page, as I'd like to agree on some commonly accepted rules; independent of that, the rules found in textbooks should be listed at Quantification, with sources. And I agree to use the least astonishing notation (i.e. that with the most parantheses), for now. - Jochen Burghardt (talk) 09:56, 15 November 2018 (UTC)

Infinite descending chains

@Jochen Burghardt: et al: the lede currently includes

Equivalently, assuming the axiom of dependent choice, a relation is well-founded if it contains no countable infinite descending chains: that is, there is no infinite sequence x₀, x₁, x₂, ... of elements of X such that x_n+1 R x_n for every natural number n.

My question is about whether the word "countable" is appropriate here. Chains need not be countable—e.g. something with the total ordering of the real numbers would constitute a chain—and an example chain that demonstrates that a relation is not well-founded could be uncountable. That would argue that the word "countable" is inappropriate here. On the other hand, such an uncountable chain will necessarily have a countable subchain so, in order to show that a relation is well-founded, a proof that there are no countable infinite descending chains would be sufficient. Such a proof would imply that there are also no uncountable infinite descending chains. So, does "countable" help or hurt in this context? Would it be worth it to add a sentence that tries to explain this? —Quantling (talk | contribs) 14:53, 15 August 2022 (UTC)

I'd appreciate if you'd add an explanatory note along your above argument, to which I agree. In the text of the axiom itself, I'd prefer the weakest version, viz. including "countable". Axioms should be as weak as possible. - Jochen Burghardt (talk) 17:15, 15 August 2022 (UTC)

I don't see any axioms here — we're discussing a definition. It sounds like you're saying that definitions should be stated in the way that makes them formally easiest to satisfy, when the definitions are actually equivalent? I'm not convinced that's a good general rule.

I think it's a close call, but on balance I'd leave out "countable", because it doesn't really add anything and makes the reader wonder why it was included. I think the good general rule is that definitions should be as easy to understand as possible. --Trovatore (talk) 17:28, 15 August 2022 (UTC)

I tried to address this in the article. If it needs changes, please edit there or discuss here. Thank you —Quantling (talk | contribs) 18:15, 15 August 2022 (UTC)

Induction Base

The bit on induction is missing the base case. The statement as written is false. To convince yourself, take P the false statement and X any non-empty set. 2A00:1398:4:A0F:8877:8440:3C36:92D5 (talk) 11:25, 25 May 2023 (UTC)

There is nothing wrong. The base cases (in general, there are many) are provided by the minimal elements. Indeed, if x is minimal then P(y) is true for all y such that y R x, even if P is the false statement. So, the proof of If x is an element of X and P(y) is true for all y such that y R x, then P(x) must also be true includes the proof of P(x) for every mimimal element x.D.Lazard (talk) 13:55, 25 May 2023 (UTC)