Talk:Well-founded relation

From Wikipedia, the free encyclopedia

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)

[edit] 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 \le 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 \le 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 \le 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)
Retrieved from "http://en.wikipedia.org../../../w/e/l/Talk%7EWell-founded_relation_e267.html"