Talk:Axiom of regularity

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Low Priority  Field: Foundations, logic, and set theory

Contents

[edit] Examples

for every non-empty set S there is an element x in it which is disjoint from S

It may help to see some examples to understand what this is saying. Let's call a set "regular" if it conforms to the Axiom of Regularity. In other words, S is "regular" if and only if it has an element x which is disjoint from S.

Example 1: Let S be the set of all legal residents of Canada. Is this a regular set? Sure. Let x be any member of S at all. It may sound strange to say that S and x are disjoint, but technically it is true. We say that A and B are disjoint if nothing is a member of both A and B. Since x is a person and not a set, of course x has no members. Thus nothing is both a member of both S and x; thus S and x are disjoint. Generalizing from this example, you can see that if every member of S is a non-set, then S has to be regular. Furthermore, the definition of Regular just requires *at least one* element of S which is disjoint from S. Thus, if at least one element of S is a non-set, or if the empty set is an element of S, then S is automatically regular.

Example 2: Let's say that a baseball team is a set of players. Let S be the set of all teams in the American League. Is S a regular set? Sure. Again, we can let x be any member of S; let's say x is the Oakland Athletics. Since the members of S are teams and the members of x are players, and nothing is both a team and a player, you can see that nothing is a member of both S and x.

Example 3: Let S be the set of all natural numbers (i.e. positive integers). Is S regular? Well, probably, but this depends on how you define natural numbers. If you don't want to think of natural numbers as sets, then S is regular the same way as the set in Example 1. If someone working in set theory or foundations of mathematics wants a formal definition of natural number, she or he probably defines natural numbers as sets, so now S is a set of sets. In the standard ZFC set theory definition (see the Von Neumann definition of ordinal), the number 1 is defined to be the set {0} (the set containing 0), and you can see that S is regular since 1 is a member of S, and S and 1 are disjoint. But the fact is, this axiom is a rather obscure part of set theory. If one is confused by it, well, it probably doesn't need to be a real high priority. If you must understand, then it's probably better to learn some more about (ZFC) set theory from a more teachy source than Wikipedia to get the proper context. The Axiom of Regularity isn't really supposed to be an intuitively true fact about sets. At best it's an intuitively true fact about the Cumulative Type Structure, and unfortunately this Structure doesn't seem to be described anywhere in Wikipedia. (The ZFC article probably should have some mention of it.)


for every non-empty set S there is an element a in it which is disjoint from S

I really don't understand what this is saying (but this could well just be me being thick). Are we saying that the element a is both 'in the set S' and 'disjoint from S'? That's what the sentence says to me - does the word 'it' refer to the set S? How can element a be both within the set and disjoint from it? --Stuart Presnell 29/11/2002

One has to keep in mind that elements are themselves sets. So while A ∈ S, we can also consider A ∩ S. S = { A , B , C } and A = { B }, for example. Then A ∩ S = { B }

Ok, now it's my turn being thick :P saying that a is an element of S but they are disjoint sounds to me like a paradox. What subset of S = {A, B, C} is disjoint to S? I mean the only subsets are
a = {}
a = {A}
a = {B}
a = {C}

...

a = {A, B, C}
and so on. None of these are disjoint from S (not counting {} obviously), they all share atleast one element! Can some one please explain :S Gkhan 16:59, Apr 8, 2005 (UTC)
The axiom is about elements of S being disjoint from S, not about subsets. --MarkSweep 19:07, 8 Apr 2005 (UTC)

Surely sets and elements are different! a is not the same as {a} or {{a}}.

This needs some care. -- User:David Martland

You're confusing several things here. First, sets and elements are not ontologically different, since there are sets of sets, i.e., sets whose elements are themselves sets. If you want to, you can introduce a unary predicate is-a-set into most axiomatic set theories, but that doesn't buy you a whole lot. In any case, this issue is somewhat orthogonal to the question of whether generally a is distinct from {a} (they are of course notationally distinct, but the real issue is under what conditions they might be equal).
Second, regarding a not being the same as {a}, this is a good illustration of why axiomatic set theory exists in the first place: people don't have reliable intuitions about what sets are and under what conditions two sets, intuitively defined, are the same. Naive set theory is based on intuitions about well-founded finite sets that one may encounter in the physical world; for those sets a\neq\{a\} holds without exception. But what if you were to allow the set {{{{...}}}} (call it Ω and define it as Ω = {Ω}, i.e. the singleton set that is a member of itself) -- then you would finde that a\neq\{a\} does not hold universally, but has exceptions such as a = Ω. Fact is that people have no reliable intuitions about non-well-founded sets. Zermelo had a problem with them and that's why the Axiom of Foundation rules them out. Aczel and others find non-well-founded sets useful, and consequently there are non-standard set theories that scrap the foundation axiom altogether and indeed postulate the existence of non-well-founded sets. In either case, the axiomatic approach forces people to spell out precisely what they think sets are and how they behave. The Axiom of Foundation is one way of resolving this issue. It is a bit cryptic (or make that "elegant") and its full power only becomes clear when one considers its interaction with the other axioms of Zermelo(-Fraenkel) set theory.
--MarkSweep 08:56, 7 Sep 2004 (UTC)

Under the axiom of choice, this axiom is equivalent to saying there is no infinite sequence {an} such that ai+1 is a member of ai

I'm changing this, because the axiom of choice is not required to prove the result. Onebyone 16:08, 25 Oct 2003 (UTC)

... in one of the directions, I meant to say. Onebyone 21:01, 10 Nov 2003 (UTC)

Axiom of regularity implies that no infinite descending sequence of sets exists

Let f be a function of the natural numbers with f(n+1) an element of f(n) for each n.

How can one define such a function in the first place? Which axiom of ZFC allows one to do so? --Fibonacci 17:56, 6 February 2006 (UTC)

I'm not sure I'm interpreting your question correctly. Let me call a function like that an IDS function (Infinite Decreasing Sequence). I think maybe what you are saying/asking is this: "The article says that assuming the axiom of Regularity, IDS functions are impossible. But why is Regularity needed for this? It doesn't seem like an IDS function would exist anyway. How could an IDS function be defined?" Sorry if I've misinterpreted. I will now answer the questions as I have interpreted them.
You are correct that, assuming only ZFC (or ZFC minus regularity) there is no way to provably define an IDS function. That in itself doesn't mean IDS functions don't exist (lots of undefinable things exist under ZFC, like well-orderings of the set of reals, or non Lebesgue measurable sets, etc). If you actually want to prove that they don't exist, you need Regularity. Under ZFC minus Regularity, the question cannot be resolved; maybe IDS functions exist and maybe they don't.

[edit] First-order logic formation

Is it not the case that a colon means 'such that' and a right-pointing arrow 'implies'? So that the experssion of the axiom on this article reads "For all A such that A is non the empty set, implies there exists B..."

That doesn't make any sense, does it? 'such that' OR 'implies' would be fine, but putting both together seems to me to render it meaningless. |Olaf Davis 17:12, 23 Sep 2006 (UTC)

No, the colon doesn't mean anything. Here it's just syntactic sugar to separate the quantifier and bound variable from the rest of the formula. In other words, this notation assumes that whenver φ is a well-formed formula, so is \forall x: \phi. The formula can be read in many ways, but not the way you had in mind. For example: "for all, A, colon, A, not equals, open brace, close brace, right arrow,..." or, in the only slightly more informative (but potentially misleading) "for all A, if A is not equal to the empty set, then...". I've changed the notation and added explicit parentheses to mitigate the confusion. --MarkSweep (call me collect) 02:31, 24 September 2006 (UTC)
I felt that the formula was still hard to read. So I rewrote it again. I hope that you agree with me that this is clearer. JRSpriggs 06:52, 24 September 2006 (UTC)

[edit] Relation to Russel's paradox

I'm not an expert in this field, but it seems to me that although this axiom does not solve Russel's paradox, it is related to it in the following sense: after the axiom of separation was changed in order to solve Russel's paradox, it was unclear whether sets which are members of themselves should be allowed or not. The axiom of regularity was formulated as an answer. Opinions? Dan Gluck 20:39, 26 October 2006 (UTC)

Once we solve Russell's paradox by restricting the axiom of separation, we have to add other axioms to partially compensate for the weakening of that axiom. To decide which possible axioms are appropriate we need a concept of what set theory should be. The Von Neumann universe is that concept. Once we decide that every set must have an ordinal rank, the axiom of regularity follows immediately. One simply chooses the element of minimal rank within the set. It must be disjoint from the given set. JRSpriggs 07:39, 27 October 2006 (UTC)

I just read through the section that has the verify tag on it. The tone of that section is more in line with a diatribe than an encyclopedia. I agree that one or two sentences pointing out that adding axioms to an inconsistent theory doesn't make it consistent would be worthwhile, but I don't think it's worth two paragraphs. So some author don't understand what they're talking about - what's new? CMummert 13:15, 29 October 2006 (UTC)

I think you're right. Ruakh 17:57, 29 October 2006 (UTC)
If one of you wants to remove that section, I would not object. However, *I* do not want to remove something which appears to be true merely because it lacks references (unless it were irrelevant to the article which this is not). If the section is really needed, someone will try again to say that the axiom resolves Russell's paradox. In that case, we can refute him. JRSpriggs 05:52, 30 October 2006 (UTC)
Re: "However, *I* do not want to remove something which appears to be true merely because it lacks references […]": I think you must have misread something. The {{verify}} tag was added because of the lack of references, but that's not the reason that CMummert gave for removing the section. Ruakh 17:46, 30 October 2006 (UTC)

I edited the section to make it correct. Just for the record, here is the comment originally left in the article source code by Ruakh.

"This section not only doesn't cite sources to support its claim, but actually names various sources for the opposite claim. The section does do a good job supporting its claim logically, but since Wikipedia isn't a venue for original research, that's not enough; it's essential to cite reputable sources for the claims that Everything and More and The Philosophy of Set Theory make erroneous claims. If no reputable sources can be found, then this section should be removed; indeed, a good argument could be made for this section to state that the Axiom of Regularity resolves Russell's paradox, since that's what the sources say."

I haven't read the sources that were mentioned in the previous version of the article, so I can't say exactly what argument they make. Thus I removed the statements in this article claiming those books were in error. The fact that adding an axiom to an inconsistent theory can't make it consistent follows immediately from the definition of an inconsistent theory. CMummert 18:12, 30 October 2006 (UTC)

To Ruakh: You seem to be assuming that my previous message here was written after CMummert's recent rewrite. It was written before. To CMummert: I think that Ruakh is saying that "The fact that adding an axiom to an inconsistent theory can't make it consistent follows immediately from the definition of an inconsistent theory." is Original Research, even though it is obviously true. JRSpriggs 07:42, 31 October 2006 (UTC)
Let's wait and see if Ruakh comments on the new version. By the way, I don't really agree with your explanation in the article of why the axiom of separation prevents the Russell set from being constructed. I have always believed it was the requirement that in the axiom \forall y \exists z [ z = \{x \in y \mid \phi(x)\}] the variable z cannot appear free in φ. Otherwise you would be able to form the set z = \{x \in y \mid x \not \in z\} which leads to a Russell-type paradox. I didn't want to go into this in this article, which is why I just gave a link to the axiom of separation page. CMummert 11:21, 31 October 2006 (UTC)
It is certainly true that the variable for the set being defined may not appear in the formula which selects the elements which will be its members. However, I think that even in the axiom of comprehension used in naive set theory that that restriction would have been applied -- nothing should be defined in terms of itself (except in special situations like recursive functions). Russell's paradox involves a kind of HIDDEN self-reference which is not apparent until you ask whether the Russell set is a member of itself. That is what is blocked by restricting the axiom to separating a subset from a given set. JRSpriggs 11:47, 31 October 2006 (UTC)
In the most naive of naive set theory there is not even a formal language defined, and so the issue of free variables is hidden. In any event, if either the limitation to only forming a subset of a given set or the restriction on free variables is removed, a contradiction can be easily produced. I have always thought of these as the "same" paradox, because they have to do with syntactic self reference. After rereading the article, I see that it only talks about the specific paradoxical set \{x \mid x \not \in x\} from Russell's paradox, and is correct about why separation cannot form that set. Information about these things should go in the axiom of separation article (someday). CMummert 12:01, 31 October 2006 (UTC)

[edit] part 2

Russell discovered his paradox in Frege's version of logic (set theory) which was quite mathematical. JRSpriggs 12:38, 31 October 2006 (UTC)

Re: "You seem to be assuming that my previous message here was written after CMummert's recent rewrite": Nonsense; I also wrote my comment before CMummert's recent rewrite. As I'm not clairvoyant, I can assure you that I did not think the then-future preceded the then-already-past.
Re: "I think that Ruakh is saying that 'The fact that adding an axiom to an inconsistent theory can't make it consistent follows immediately from the definition of an inconsistent theory.' is Original Research, even though it is obviously true": You think wrong; I'm not saying that at all. The original research isn't in that fact, but in the conclusion that such-and-such books are wrong. You can't go around Wikipedia claiming sources are wrong without citing any sort of reference to support your claims, even if you provide a convincing logical argument to support them.
Ruakh 15:37, 31 October 2006 (UTC)
I did not understand your statement "...but that's not the reason that CMummert gave for removing the section.". I took it to imply that he had already removed the section. Perhaps instead, you wanted me to respond to his argument that "So some authors don't understand what they're talking about - what's new?". If so, then I would expect you to say so more explicitly. I had presumed that the section was in the article because someone had previously tried to claim (supported by the references) that the axiom of regularity does block Russell's paradox.
The books themselves are references for what they claim. So the fact that they contradict what is manifestly true is just as apparent as that manifest truth. So I think that your distinction as to what aspect is Original Research is a distinction without any (significant) difference. JRSpriggs 10:02, 1 November 2006 (UTC)
In a reply to CMummert, you wrote, "However, *I* do not want to remove something which appears to be true merely because it lacks references (unless it were irrelevant to the article which this is not)." I replied that CMummert did not give lack of references as a reason for removing that section; rather, the reason he gave was its unencyclopedic tone. (I assumed that reducing the contents of the section to two sentences would mean removing the section and moving those sentences elsewhere, since a two-sentence section would be kind of silly. I apologize if that assumption was unwarranted or confusing.)
And there's a huge difference between making a sensible claim without giving any sources (which isn't really the Wikipedia ideal, but is at least understandable), and making a sensible claim while giving only sources that dispute it. Do you really not see a difference?
Ruakh 17:13, 1 November 2006 (UTC)
My reply was not principally directed at CMummert. It was mostly a response to your explanation of the verify-tag where you said "If no reputable sources can be found, then this section should be removed; ...". I am sorry that I was not clear about that to which I was responding.
I prefer the section the way it is now that CMummert has rewritten it and it does not mention those references. However, I did not feel comfortable about removing references when the attitude expressed around here is that we should be adding them. Perhaps I was being too simplistic. We should add good references and delete bad ones. JRSpriggs 07:18, 2 November 2006 (UTC)
Okay, then it seems like we all agree on CMummert's version. Kudos to him/her. :-) Ruakh 12:57, 2 November 2006 (UTC)

[edit] A strange lemma

I probably have some math wrong in this, but I feel there must exsist a set that has itself as a member. For example, take the universal set, which is defined as EV,Ax(x=x <-> x<V) Now, its possible, though difficult, to prove that Ax(x=x), so using a version of modus ponens, we get EV,Ax(x<V). Now, by the axiom of power sets, there is a set that contains all of the subsets of the universal set. Since all members of sets are sets, and the universal set is a subset of the universal set, the universal set is a set, and therefore

Ax,EV(x<V)
EV(x<V)
EV(V<V)

Now, the lemma states

~(V<V)

Generalize

AV~(V<V)

Take the earlier expression

EV(V<V)

Expand the E

~AV~(V<V)

and we also have

AV~(V<V)

I use the principle of explosion to say that I did something wrong, the lemma is incorectly justified, or that there is a big hole in set theory. Does anyone know which of the three it is? Thanks! Indeed123 02:21, 26 May 2007 (UTC)

There is no all-purpose "universal set" in ZF. The claim that \exists V \ni \forall x \left ( x = x \leftrightarrow x \subset V \right ) requires unrestricted comprehension — that is, it requires that you be able to define a set based only on a predicate (in this case, being an element of another set), rather than based on a predicate plus a superset. (If you've no clue what I'm talking about, see Axiom schema of specification#Unrestricted comprehension.) So, all you've shown is that the axiom of regularity is incompatible with some axioms, which is fine; the only necessary thing is that it be compatible with the other axioms of ZF (though there are other sets of axioms it's also compatible with). —RuakhTALK 06:01, 26 May 2007 (UTC)

[edit] Defining the orrdered pair

The article includes the following lines:

The axiom of regularity enables defining the ordered pair (a,b) as {a,{a,b}}
This definition eliminates one pair of braces from Kuratowski's canonical definition (a,b) = {{a},{a,b}}.

Why is the axiom of regularity necessary for this? If we define the ordered pair (a,b) as {a,{a,b}}, then the only way we couldn't extract the order is if {a,{a,b}}={b,{a,b}}, which can only be the case if a=b or a={a,b} and b={a,b}, in which case again a=b, and so (a,b)=(b,a) and there's no problem. skeptical scientist (talk) 13:41, 8 October 2007 (UTC)

If a = {a,b}, then { a, {a,b} } = { {a,b} } is a singleton. — Carl (CBM · talk) 14:50, 8 October 2007 (UTC)
And more to the point, if a = {a', b'} and a' = {a, b}, where b and b' are distinct, then (a, b) = { a, {a, b} } = { {a', b'}, a' } = (a', b'), but a is not a' and b is not b'. So the definition doesn't work. 70.135.20.81 06:33, 4 December 2007 (UTC)