Talk:Axiom of regularity

From formulasearchengine
Jump to navigation Jump to search

Template:Maths rating


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 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 does not hold universally, but has exceptions such as . 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.

I think you math gods should make it clear that the intersection is a property that isn't just defined on pairs of sets (as was my original assumption.) After all, Intersection_(set_theory) starts off by saying "In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements."-- (talk) 03:24, 14 April 2009 (UTC)

This article only needs the intersection of two sets: the given set and one of its elements. There is no point to including irrelevant information in this article, even though true. JRSpriggs (talk) 03:16, 15 April 2009 (UTC)

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 . 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)

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 the variable cannot appear free in . Otherwise you would be able to form the set 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 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)

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)
Sorry to reawaken a dog that has slept for over two years now, but I just noticed that this section still says "In fact, if the ZF axioms without Regularity were already inconsistent, then adding Regularity would not make them consistent." The definition of "is inconsistent" as "proves FALSE" makes this a vacuous statement that remains true when Regularity is replaced by "P = NP". How did such an obviously vacuous statement survive such close scrutiny back in 2006?
The Axiom of Regularity implies that xx is always false, whence the set of all sets that are not members of themselves is the set of all sets. This elementary inference does not require a whole section, and should be shoe-horned into a suitable place in some other section. The rest of the section is meaningless and should be deleted. --Vaughan Pratt (talk) 05:02, 23 December 2008 (UTC)
What is obvious (or vacuous) to you may not be obvious to the reader. JRSpriggs (talk) 01:56, 24 December 2008 (UTC)
In the meantime that occurred to me too. I'd be ok with a section on this provided it's explained better. --Vaughan Pratt (talk) 11:22, 7 January 2009 (UTC)

Hi everyone, something I think might make this clearer to the reader would be an encoding of Russell's paradox which does not *appear* to involve or be solved by regularity. It is all well and good to say that if ZF without regularity is consistent then so is ZF, and hence that regularity does not resolve Russell's paradox, but to a naive reader is it still going to *feel like* regularity solves Russell's paradox since xx is now forbidden. A good example which explicitly shows the paradox is still there would help such a reader. — Preceding unsigned comment added by (talk) 19:09, 20 September 2011 (UTC)

To You have it backwards — the inconsistency of ZF-AxReg implies the inconsistency of ZF. That is, the consistency of ZF implies the consistency of ZF-AxReg. (The converse is also true, but harder to prove and irrelevant to this issue.) The point is that an additional axiom cannot unprove something which was proved before. JRSpriggs (talk) 05:04, 21 September 2011 (UTC)

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


Now, the lemma states




Take the earlier expression


Expand the E


and we also have


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 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)

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. 06:33, 4 December 2007 (UTC)

infinite decreasing sequences

I thought the ordinal ω was included in ZF. If so, isn't it true that ω intersects ? It seems then, that since ω is in ZF, we can create the sequence . What's my error? (talk) 12:25, 23 December 2008 (UTC)

There is no in the universe of sets. JRSpriggs (talk) 01:53, 24 December 2008 (UTC)

Mistaken "proofs" exposed

Template:User-multi asked what was wrong with the attempted proofs which he added on 14 August 2009 and which I reverted. The first one said

"Another proof [that A cannot be an element of A] which does not use pairing is as follows. Suppose for reductio that A is in (i.e. an element of) A. By regularity there is a B in A disjoint from A. But as A is in A and B is in A, B is in the intersection of B with A. Contradiction.".

The underlined statement does not follow from its purported justification. In particular, you did not establish that B is in B itself. This cannot be fixed simply by correcting one of the set-labels. Let A = {A, {} }, then B = {} which is certainly not a member of itself.

Thanks. Nortexoid (talk) 03:07, 2009-8-20 (UTC)

The second one said

"A more intuitive proof proceeds as follows. Suppose for reductio that there is a sequence
for i a natural number. Let
Notice that for all i,
But then for all i
which contradicts regularity, viz. that there is a member of B disjoint from B."

This is simply a sloppy reiteration of the first proof in that section which says

"Suppose, to the contrary, that there is a function, f, on the natural numbers with f(n+1) an element of f(n) for each n. Define S = {f(n): n a natural number}, the range of f, which can be seen to be a set from the axiom schema of replacement. Applying the axiom of regularity to S, let B be an element of S which is disjoint from S. By the definition of S, B must be f(k) for some natural number k. However, we are given that f(k) contains f(k+1) which is also an element of S. So f(k+1) is in the intersection of f(k) and S. This contradicts the fact that they are disjoint sets. Since our supposition led to a contradiction, there must not be any such function, f."

Where you overlook the important question of whether the sequence is actually a set (function) within the model in question. JRSpriggs (talk) 08:08, 18 August 2009 (UTC)

The proof is informal, not sloppy. Nortexoid (talk) 03:07, 20 August 2009 (UTC)
I read
as a statement in the metatheory, and it does not imply to me that there actually is a function f at hand that enumerates the sequence. As a parallel example, any countable model M of ZFC will have a sequence of finite sets Bi such that
and such that is a Cohen generic real over M, but no such model of ZFC will contain a function that enumerates such a sequence. — Carl (CBM · talk) 03:20, 20 August 2009 (UTC)

Where is the axiom of foundation in von Neumann 1925 ?

I have von Neumann 1925 in From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press at hand and I cannot locate the instance of the axiom of foundation. Can someone tell me on which page and under which name I can found it? --Pierre de Lyon (talk) 12:37, 8 January 2010 (UTC)

Since both Levy (1979) and Jech (2003) attribute the axiom to von Neumann (1925), it seems that the claim in the article is safe; the question is why they attribute the axiom to von Neumann at all.
The initial set of axioms that von Neumann (1925) lays out in part I does not include the axiom of regularity; von Nuemann directly says this on p. 404 in section II.1. It was known at the time that the well-founded part of a model of set theory should again be a model of set theory (this is also in Skolem 1922 in the same collection). On the bottom of page 407 through the top of 408 (part II.2), von Neumann explains how to make a model of his axioms by following the cumulative hierarchy inside a given, possibly non-well-founded model of his axioms. Since the axiom of regularity is equivalent over the rest of ZF to the proposition that every set is in the cumulative hierarchy, my guess is that this is where the inspiration of the axiom of foundation came from.
Levy also cites Skolem 1922 (he calls it Skolem 1923) for the axiom of foundation. Both Skolem and von Neumann were interested in it for the same reason: they were interested in noncategoricity of set theory, hence interested in inner models, and the well-founded sets are the easiest inner model to come up with. — Carl (CBM · talk) 15:46, 8 January 2010 (UTC)
Interesting; von Neumann appears to have stated the axiom in first-order terms as "for every set x, there is an ordinal y such that x appears in the y^th stage of the cumulative hierarchy". This is provably equivalent (over ZF without regularity) to the formulation of regularity we use today (every nonempty set is disjoint from one of its members). But this raises the question: who came up with the simplified formulation and proved it equivalent to von Neumann's? AshtonBenson (talk) 06:08, 31 January 2010 (UTC)
Zermelo in 1930 it seems. In Ewald's translation (p. 1220): "Axiom of foundation: Every (decreasing) chain of elements, in which each term is an element of the preceding term, breaks off with finite index at an urelement. Or equally: Every partial domain T contains at least one element t0 none of whose elements are in T. ¶ This last axiom, which excludes all 'circular' sets, and thus all 'sets that contain themselves', and in general all 'groundless' sets, has always been satisfied in all practical applications of set-theory. Thus, for the time being, it presents no essential restriction of the theory." Zermelo comes back to the issue on p. 1227 (in the translation) where he cites a later paper for "von Neuman's 'axiom'", namely J. v. Neumann, "Die Axiomatisierung der Mengenlehre", Math Zeitarch. Bd. 26 S. 669-752, 1928. It looks like the volume was off by one though, it's in volume 27 actually [1]. Tijfo098 (talk) 10:58, 2 November 2012 (UTC)
By the way [2] spanks Zermelo for not proving the equivalence (as Regularity => Foundation requires (Dependent) Choice). Tijfo098 (talk) 13:53, 2 November 2012 (UTC)

Where is the axiom of foundation in Mirimanoff 1917?

Mirimanoff 1917 appears to be about the Russell and Burali-Forti paradoxes; could somebody point me to the page/paragraph where the axiom of regularity is stated? AshtonBenson (talk) 06:08, 31 January 2010 (UTC)

Seeing that there's been no response in almost four months, I'm going to remove the Mirimanoff citation. AshtonBenson2 (talk) 01:31, 5 June 2010 (UTC)
Mirimanoff considers Russel's paradox (and Burali-Forti) as a reason (p. 40) for defining his notion of regular ("ordinaire") sets on p. 42. He then says on p. 43 that a set of regular sets is regular, but then show that the the set (it should be in quotes, but he doesn't put it) of all regular sets (which he denotes by V) does not "exist" (as a set). So it's not true that he did not consider the consquences. [He lacks a consistent terminlogical distinction between set and class. He first calls classes "extraordinary sets" ("extraordinaire", p. 42), but he doesn't use his terminlogy consistently; later he just says that certain sets "don't exist" instead of calling them "extraordinary". In his conculsions on p. 52 he says that he solved Russell's paradox for regular sets (and also Burali-Forti's, but that involves rank etc. His proofs definitely look wonky by modern standards but when secondary sources credit him with the generally right idea for well-founded sets, they probably know what they are talking about. [3] [4] [5] Tijfo098 (talk) 12:49, 2 November 2012 (UTC)
Luckily secondary sources agree:
  • [6] "he calls a set x regular (French "ordinaire") if every sequence xx1x2 ∋ ... is finite. However he did not postulate the regularity of sets as an axiom, but if one would do so, one would get the Axiom or Regularity saying that every set is regular."
  • [7] "His main interest, motivated by Burali-Forti and Russell's paradoxes, is understandind what are the conditions for the existence of sets as objects. And his main results are theorems asserting -- using modern terminology -- that certain classes are not sets."
-- Tijfo098 (talk) 13:52, 2 November 2012 (UTC)
The most extensive discussion (in English) of Mirimanoff's contribution is in Hallett §4.4. [8]. Tijfo098 (talk) 06:37, 3 November 2012 (UTC)

Clarify "No set is an element of itself"?

"Let A be a set such that A is an element of itself and define B = {A}, which is a set by the axiom of pairing. Applying the axiom of regularity to B, we see that the only element of B, namely, A, must be disjoint from B. But A is both an element of itself and an element of B. Thus B does not satisfy the axiom of regularity and we have a contradiction, proving that A cannot exist."

This appears to prove merely that no singleton is an element of itself, which does not necessarily generalize to sets with more than one element. Consider the set A = {A, {∅} }. In this case, {∅} is both an element of A and disjoint from A, which appears to satisfy the axiom of regularity even though A is an element of itself. Can anyone explain why this doesn't work? Jesin (talk) 17:02, 2 August 2010 (UTC)

The article is saying that if A is any set that is an element of itself, then the axiom of regularity as stated here fails for the corresponding set {A}. The fact that the axiom of regularity would work for the other set {A, ∅} is neither here nor there. It just takes one failure of the axiom of regularity to show that the set A could not be an element of itself. — Carl (CBM · talk) 18:18, 2 August 2010 (UTC)
I don't think that the proof as written is sufficient--it's incomplete and has poor pedagogy because of this. A more complete proof might note one of the various other axioms that require that if A is an element, then there must be a set that contains A and only A. If we have such a set and call it B, then the axiom of regularity fails because both A and B contain A.Guyminuslife (talk) 00:57, 22 July 2012 (UTC)
The article clearly states that B={A}={A,A} is a set due to the axiom of pairing. JRSpriggs (talk) 12:16, 22 July 2012 (UTC)

Axiom Schema of Replacement Not Necessary

In the proof that no infinitely decreasing membership sequence of sets exists, it claims range(f) is a set due to the Axiom Schema of Replacement. In fact, the Axioms of Union and Restricted Comprehension are sufficient given the definition of a function, meaning Zermelo Set Theory is sufficient -- we don't need to use ZF.

--Achur (talk) 19:38, 14 March 2011 (UTC)

I see what you mean, and I'm not certain why it is phrased that way. perhaps the reasoning was that the current proof shows something stronger, that there is not even a definable function that enumerates an infinite sequence of sets each of which is an element of the previous one. — Carl (CBM · talk) 20:20, 14 March 2011 (UTC)

"Regularity does not resolve Russell's paradox"

This section, more precisely the sentence "Russell's paradox does not manifest in ZF because ZF does not admit the proposed set--that is, ZF's axiom of separation only allows us to construct subsets of some existing set, and thus it cannot be used to construct the desired set." appears to contradict Frankel et al. [9] who say that:

By I-VIII they mean all other std. axioms in ZFC (VIII is Choice). So can someone sketch here how the axiom of separation (or even ZFC minus Regularity) prohibits sets which only contain themselves as the only element, as it's now stated in the wiki article? Tijfo098 (talk) 16:07, 2 November 2012 (UTC)

I do not understand what your question is.
As far as I know, ZFC-minus-Regularity does not show A={A} is impossible. It merely fails to provide any way to prove the existence of such a set. JRSpriggs (talk) 08:12, 3 November 2012 (UTC)
The problem is that the wiki article says (see first sentence cited above) that ZFC-minus-Regularity somehow does prevent Quine atoms, and that [therefore] Regularity is somehow useless, which is a clear misunderstanding of what the independence of Regularity from the other ZF(C) axioms actually means. Tijfo098 (talk) 08:19, 3 November 2012 (UTC)

Stated even more clearly here: "if we do not assume the axiom of foundation, we can easily construct models containing as many Quine atoms (sets x = {x}) as we want." Tijfo098 (talk) 08:09, 3 November 2012 (UTC)

The thing you quoted says, "ZF's axiom of separation only allows us to construct subsets of some existing set, and thus it cannot be used to construct the desired set". That is not at all contradictory to the existence of models with Quine atoms. Instead, the quoted material basically say that we cannot prove that there are Quine atoms. Indeed, even in a model M with Quine atoms, the constructible universe L(M) for that model will not have any Quine atoms. Now for Russell's paradox to affect ZFC, it would be necessary for ZFC to prove that the set in question ({x : ¬(x∈x)}). Since ZFC can't prove that set exists, it's not possible to derive a contradiction from ZFC that involves constructing that set. — Carl (CBM · talk) 12:29, 3 November 2012 (UTC)

Ok, let's take it more slowly. I think the issue is that words like "admit", "construct", "resolves", "banishes" are ambiguous. This is the text I deleted [10]. I'll break it down with bullets. I'll add my comments with color.

  • Heading/conclusion: Regularity does not resolve Russell's paradox. Template:!xt
  • In naive set theory, Russell's paradox is the fact "the set of all sets that do not contain themselves as members" leads to a contradiction. Template:Xt
  • The paradox shows that that set cannot be constructed using any consistent set of axioms for set theory. Template:!xt
  • Even though the axiom of regularity implies that no set contains itself as a member, that axiom does not banish Russell's paradox from Zermelo–Fraenkel set theory (ZF). Template:!xt
  • In fact, if the ZF axioms without Regularity were already inconsistent, then adding Regularity would not make them consistent. Template:Xt Template:!xt
  • Russell's paradox does not manifest in ZF because ZF does not admit the proposed set--that is, ZF's axiom of separation only allows us to construct subsets of some existing set, and thus it cannot be used to construct the desired set. Template:Xt Template:!xt
  • A line of reasoning similar to Russell's paradox will, in ZF, only end up proving that the collection of all sets which do not contain themselves is not a set but a proper class (actually, the class of all sets). Template:Xt Template:!xt

-- Tijfo098 (talk) 15:23, 3 November 2012 (UTC)

Also, maybe Reuben Hersh is a dummy or at least [11] this particular work of his is intended for such audiences, but he writes for instance:

-- Tijfo098 (talk) 15:36, 3 November 2012 (UTC)

I am having a very hard time understanding what you are saying; it's too long and all the colors are confusing to me. On one hand, if ZFC without regularity is inconsistent, then ZFC with regularity would be too - do you agree? An immediate consequence of that is that, if ZFC without the axiom of regularity had problems because of Russell's paradox (so it was already inconsistent), then adding the axiom would not resolve those problems. Instead, if ZFC avoids the inconcistency in naive set theory that comes from Russell's paradox, it must be because the other axioms of ZFC have been chosen to avoid the issue.
On two other points: ZFC can't construct any models of ZFC, because of the incompleteness theorems. And Quine atoms are not related to Russell's paradox; the former are sets that only contain themselves, the latter are sets that contains all sets that don't contain themselves.
It seems to me that you are confused about the distinction between an a set of axioms proving something does not exist vs. a set of axioms not being able to prove that something does exist. In order to use Russell's paradox to get an inconsistency we have to prove that a certain set does exist. — Carl (CBM · talk) 16:08, 3 November 2012 (UTC)

As would be expected, there are sources that explain what's going on. For example Robert Vaught's Set Theory says this on pp. 11-12:

It is natural to ask at this point: are there any sets z such that zz. It turns out that in our axiomatic set theory this question will remain unresolved until the last, and very little used, axiom, the Regularity Axiom, is added – see Chapter 8. But notice that in fact Russell's argument above is completely indifferent to the answer to this question.

The italics are in the original. The quote from Hersch above is quite odd, since adding another axiom can't possibly make an inconsistent system consistent. — Carl (CBM · talk) 16:17, 3 November 2012 (UTC)

It looks like other sources (besides Hersch) are confused too. For example, before adding the replacement paragraph which you copy-edited (so we seem to agree on it), I had found [12] (but didn't post here because I was in a hurry) It says: "Russell's paradox is avoided in this system of assumption. The axiom of replacement provides, for each set a, a set . But it does not create a set because, if U were a set, we would have violating regularity." ¶ The source of confusion, as Adam Rieger correctly points out, is that the existence of a universal set (containing itself) is also prohibited by Regularity (not just by Separation). Although, I've seen no source discussing the following, perhaps it's worth adding to the article what happens if you replace Separation with unrestricted comprehension while keeping Regularity? Tijfo098 (talk) 05:11, 4 November 2012 (UTC)
And (worse perhaps) the identification of the cumulative hierarchy as the solution to Russell's paradox even happens in the text of some set theorists, e.g. Levy (1979, pp. 72-73): "Many logicians take up the view that this process [the cumulative hierarchy] is the true basis of our intuition about sets. Accordingly, the full axiom of comprehension, [ref], was a mistake anyway because it is a result of attempting to construct a new set while assuming that all the sets are already at hand. According to this view, Russell's antinomy is not a bad surprise, but an obstacle which may naturally occur when one follows an unsound way. One can formulate an axiom system of set theory which is based directly on the idea that the whole universe of sets is obtained by the process associated with the R(a)'s, and which turns out to be equivalent to ZF (Scott 1974)." The paper he cites is "Scott, D., 1974, Axiomatizing set theory. Axiomatic set theory. Amer. Math. Soc. Proc. Symposia Pure Math. 13, vol. II, 207-214" Tijfo098 (talk) 08:27, 4 November 2012 (UTC)
The issue is that if we can already prove a paradoxical set exists, adding a new axiom that says it doesn't exist doesn't change the fact that we can prove it exists. One axiom can't nullify other axioms in the way that new legislation can nullify old legislation.
The cumulative hierarchy approach does solve the problem of Russell's paradox, but it doesn't need the axiom of regularity. For sets in the cumulative hierarchy, we can prove the axiom of regularity based on the definition of the hierarchy. (There is only one set of rank 0, and it is well founded. If there was a set at a higher rank that was not well founded, because all elements of a ranked set are of lower rank than the set, there would be a set of smaller rank that is not well founded. Every set in the cumulative hierarchy has a rank because the way a set gets into the hierarchy is by being assigned a rank.) Indeed this is one of the motivations for the axiom of regularity, showing that it holds for the sets in the intended model. — Carl (CBM · talk) 12:59, 4 November 2012 (UTC)
Well, the usual (von Neumann) cumulative hierarchy "produces" (in the sense of Scott's paper mentioned above) a system of axioms which includes regularity. The non-well-founded approaches also have a sort of hierarchy (or at least two layers) which is what seems to avoid Russell's paradox there; I'm not very familiar with the specifics, but the basic idea is that a pointed graph (which models a non-well-founded set) generalizes to the [rather poorly named] notion of a system, which has nwf-sets as its children, but the system itself is not pointed. A system is basically a model of a nwf-class. (The page on Non-well-founded set theory needs a section on its model theory...) Tijfo098 (talk) 18:10, 4 November 2012 (UTC)
[Musing:] Intuitively one should be able to define a partial order on nwf-sets, but I've not seen this done. Tijfo098 (talk) 06:58, 5 November 2012 (UTC)

Oh, and Peter Cameron also uses Regularity instead of Separation to prove that Russell's paradox doesn't happen. From Sets, Logic, and Categories, p. 117. "Once we have justified the axioms, we do not need the Zermelo hierarchy any more; we can feel secure that Russell's Paradox has been avoided. Let us note immediately that in fact no set can be a member of itself. Suppose that у is any set whatsoever. Let x = {у} (this exists by the Pair Set Axiom). The only member of x is y, so according to the Axiom of Foundation, x ∩ у = ∅. But у ∈ x; so we must have у ∉ у, as required. ¶ Hence Russell's set, if it exists, would be the 'set of all sets'. However, if there were a set S consisting of all sets, then S would certainly include itself, contrary to what we have just proved." So which axiom avoids Russell's paradox tricks even authors of set theory books. :0 Tijfo098 (talk) 09:04, 5 November 2012 (UTC)

It still seems that you are looking at this backwards. There is no axiom whose presence "avoids Russell's paradox". Contradiction can be avoided only by excluding axioms (or combinations of axioms) which cause it, such as the axiom of comprehension. JRSpriggs (talk) 18:30, 5 November 2012 (UTC)
To be fair, there really are a surprising number of authors who talk about how the paradoxical set cannot exist because of the axiom of regularity. And it is true that regularity implies the set of all sets doesn't exist - the problem, which the authors only sometimes mention, is that if we can already show that a set does exists then adding another axiom that shows it doesn't exist can only make the situation worse. — Carl (CBM · talk)
@JRSpriggs: I don't think it's outlandish to try identify which axiom(s) are responsible for the avoidance of the paradox in the sense that using it/them we can show only "half" of the potentially contradictory statement (from Russel's paradox) i.e. that the universal does not exist (nor is outlandish to do reverse mathematics in general.) Some authors cited here (Vaught, Rieger) do this too. I agree however that no single axiom can be held responsible for not being able to prove that the universal set exists (as well), which would cause the contradiction. There is some difficulty in expressing this clearly. I think the previous version of the article which said "Regularity does not resolve Russell's paradox" was more confusing than the current one, which says (1) regularity is relatively consistent with [and also independent from] the rest of ZF and (2) you can prove the non-existence of the universal set in ZF using either Separation of Regularity, and (3) you can replace Regularity with some anti-foundation axiom and still have an axiomatic system which avoids Russell's paradox in the exact same sense as ZF does, e.g. "Aczel's" anti-foundation axiom is also shown to be relatively consistent with the rest of ZF; the SEP page [13] has a "Theorem. If ZFC is consistent, then so is ZFA, and vice-versa." So (2)+(3) is the sense in which Regularity is not "preventing" or not "resolving" Russel's paradox, according to Adam Rieger. Vaught however said that only (2) is the reason, which seems less convincing to me. Tijfo098 (talk) 04:11, 6 November 2012 (UTC)
I do not see what reverse mathematics has to do with what you are talking about. Reverse mathematics is such things as showing that the axiom of choice can be deduced from one of the theorems which are normally deduced from it. For example, see König's theorem (set theory)#Axiom of choice. JRSpriggs (talk) 12:53, 6 November 2012 (UTC)

Set-like confusion

Template:User-multi added some material to the lead including the sentence "However, it ... allows induction to be done on well-ordered sets (or even well-founded relational structures) whether or not the relations are set-like.". What does this mean? And how do you justify it? JRSpriggs (talk) 04:55, 13 May 2013 (UTC)

A relation is set-like on a class if and only if for each , is a set. Smullyan and Fitting call a relational system whose relation is set-like a "proper relational system". A well-ordering (or well-founded relation) can always be used for induction if it is set-like on the class involved (note that every relation on a set is set-like, and note also that the set membership relation is set-like, so this isn't an issue for induction on sets or on the class of ordinals). If the axiom of regularity is accepted, then every set can be shown to have a "rank", a least ordinal such that the set is in the corresponding level of the "cumulative hierarchy". It's then possible to use that fact to prove that induction works regardless of whether the relation involved is set-like. For a proof of the key fact that the axiom of regularity implies that each non-empty class under a well-founded relation has a minimal element, see for example ProofWiki. This is also an exercise in Kunen's text. As far as I can tell, the most important applications of well-founded induction actually are on set-like relations (most notably the set membership relation), but the axiom of regularity allows for utterly unfettered application of induction, which some people apparently like. --Dfeuer (talk) 17:17, 13 May 2013 (UTC)
Thank you for the explanation and link.
At the proof you linked, you are implicitly using the axiom of replacement together with both of the instances of the axiom of union which you identified. JRSpriggs (talk) 17:51, 13 May 2013 (UTC)
The example you added is non-optimal. $\omega \times \operatorname{On}$ is a subclass of the cumulative hierarchy regardless of whether the axiom of regularity is accepted. I think you will need something much stranger, if in fact it's even possible to come up with a good application. --Dfeuer (talk) 21:58, 13 May 2013 (UTC)
Did I misunderstand you? I thought that you were giving examples of what the axiom of regularity allows one to do. If you are assuming the axiom of regularity, then the cumulative hierarchy (Von Neumann universe) is all you have. Right? So there would be no room for this "much stranger" example.
Or perhaps you want a counter-example, a well-founded relation on a class in not-well-founded set theory where one cannot prove that induction on the relation is possible (or only prove it with much greater difficulty). JRSpriggs (talk) 23:49, 13 May 2013 (UTC)
Slippery, slippery. What I was thinking was that perhaps some other condition would turn out to imply that a relation was well-founded and you'd want to be able to rely on that for whatever reason. But that could be silly. What I meant is that your example, by construction, is in the cumulative hierarchy. There is no need to accept the axiom of foundation to use that fact, except as a convenience. --Dfeuer (talk) 11:53, 14 May 2013 (UTC)