This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)
<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).
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 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)
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'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)
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)
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)
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)
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)
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)
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)
Revision as of 10:25, 10 June 2018 was correct, induction principle:
Revision as of 16:27, 16 March 2014 was correct, wellfounded criteria:
Both had the correct parenthesis. Added them again back.
Jan Burse ( talk) 20:28, 13 November 2018 (UTC)
@ Jochen Burghardt: et al: the lede currently includes
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)
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)
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 trueincludes the proof of P(x) for every mimimal element x. D.Lazard ( talk) 13:55, 25 May 2023 (UTC)
This
level-5 vital article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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)
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)
<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).
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 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)
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'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)
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)
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)
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)
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)
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)
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)
Revision as of 10:25, 10 June 2018 was correct, induction principle:
Revision as of 16:27, 16 March 2014 was correct, wellfounded criteria:
Both had the correct parenthesis. Added them again back.
Jan Burse ( talk) 20:28, 13 November 2018 (UTC)
@ Jochen Burghardt: et al: the lede currently includes
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)
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)
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 trueincludes the proof of P(x) for every mimimal element x. D.Lazard ( talk) 13:55, 25 May 2023 (UTC)