Infinite Sets
Moderators: gmalivuk, Moderators General, Prelates
Infinite Sets
So, I was thinking about set theory the other day, and came upon this question. I know that it is not possible for a set to contain itself, but it's certainly possible for sets to contain other sets. My question is, is it possible to have sets within sets within sets, etc., going on for infinity? My first idea was something like {{{{...{2}...}}}} (where there are an infinite number of brackets). It seems to me that if this could be constructed it could be argued that it contains itself, though. But what about something like {1, {2, {3, {4, ...}}}}, where each set contains a natural number and another set. It doesn't seem to me that the construction of sets is expressly forbidden, but I'm not really sure. I guess what I am saying is Is it possible to have sets like this, and if so, how would you formally define them and would such a set ever have any purpose?
Re: Infinite Sets
It depends entirely on your axiomatic system. You can make systems where such a thing is consistent. But no matter what, you're not going to have some of the sets you might dream up. In standard ZFC, we don't allow infinite decent like that, and disallowing it removes most of the problems that are apt to appear, but it's a bit of a sledgehammer approach. There are systems where this is allowed (and even a set containing itself is allowed), but you need to be careful that you don't add 'too many' sets and end up in a paradox.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: Infinite Sets
Ah, ok, I see now after doing a bit of reading that this sort of set would violate the axiom of regularity
Re: Infinite Sets
There is a set that does this, but can be definitely stated to not contain itself.
The set of natural numbers (N);
semirigorous definition of N
For all natural numbers (say, m), there exists an element of N that goes down at least m levels deep  m.
Unless I am missing something with your question.
The set of natural numbers (N);
semirigorous definition of N
Spoiler:
For all natural numbers (say, m), there exists an element of N that goes down at least m levels deep  m.
Unless I am missing something with your question.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Infinite Sets
Elmach wrote:There is a set that does this, but can be definitely stated to not contain itself.
The set of natural numbers (N);
semirigorous definition of NSpoiler:
For all natural numbers (say, m), there exists an element of N that goes down at least m levels deep  m.
Unless I am missing something with your question.
The OP isn't trying to find a set which contains arbitrarily deep elements, they're trying to find sets {A_{n}}_{n in N} such that A_{n} is in A_{n+1}. In the standard construction of N, there aren't any collections like that.
gaga654 wrote:I know that it is not possible for a set to contain itself
Its actually possible to come up with perfectly consistent set theories that do allow you to do this. They don't have the axiom of regularity, and they allow you to have sets like the quine atom, A, which satisfies A = {A}.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Infinite Sets
jestingrabbit wrote:Elmach wrote:There is a set that does this, but can be definitely stated to not contain itself.
The set of natural numbers (N);
semirigorous definition of NSpoiler:
For all natural numbers (say, m), there exists an element of N that goes down at least m levels deep  m.
Unless I am missing something with your question.
The OP isn't trying to find a set which contains arbitrarily deep elements, they're trying to find sets {A_{n}}_{n in N} such that A_{n} is in A_{n+1}. In the standard construction of N, there aren't any collections like that.
I still think I'm missing something?
In the set of natural numbers, 0 is a subset of 1  for all n, n is an element of n+1?
EDIT (reread OP): Oh, A_{n+1} is in A_{n}. I am not aware of anything that does that.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Infinite Sets
Elmach wrote:Oh, A_{n+1} is in A_{n}. I am not aware of anything that does that.
Yeah, I made an index error, sorry.
There aren't sets like that in the usual set theory that mathematicians use.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Infinite Sets
There's actually a set theory in which you demand such "not well founded" sets exist. You drop the Foundation Axiom from ZFC and add the Antifoundation Axiom, which states that every graph corresponds to sets such that the arrows correspond to containment. For instance, the graph of one node with one arrow would give a set A that satisfies [imath]A = {A}[/imath], mentioned above. The point is that while Foundation demands that sets be built from the "bottom up", starting with known sets and piecing them together to give new sets, Antifoundation allows us to build sets from the "top down". We specify how the sets should act, and antifoundation produces the objects we want. It also allows us to define sets in terms of themselves.
So for instance, take the set {1, {2, {3, {4, ... }}}}. It contains 1, so we want a node labelled 1 and an arrow pointing into the node that corresponds to the set [imath]v_1.[/imath] But we also want some other set that "starts with" 2. So put a node for [imath]v_2[/imath] that set pointing to [imath]v_1[/imath], along with an arrow from the set 2 into [imath]v_2[/imath]. But we want a set starting with 3, and 4, and so on. This particular example is kind of like an object called a stream. (I think it might just be a stream.) A stream of numbers, for example, is an object that contains a number and... another stream of numbers. So the set [imath]v_1[/imath] contains 1 and the set [imath]v_2[/imath], which in turn contains 2 and the set [imath]v_3[/imath], and so on. Such sets don't exist in ZFC, but they must exist with the Antifoundation axiom.
http://standish.stanford.edu/pdf/00000056.pdf looks like it might be a good book on this kind of thing. But I honestly only know a little bit about the subject.
So for instance, take the set {1, {2, {3, {4, ... }}}}. It contains 1, so we want a node labelled 1 and an arrow pointing into the node that corresponds to the set [imath]v_1.[/imath] But we also want some other set that "starts with" 2. So put a node for [imath]v_2[/imath] that set pointing to [imath]v_1[/imath], along with an arrow from the set 2 into [imath]v_2[/imath]. But we want a set starting with 3, and 4, and so on. This particular example is kind of like an object called a stream. (I think it might just be a stream.) A stream of numbers, for example, is an object that contains a number and... another stream of numbers. So the set [imath]v_1[/imath] contains 1 and the set [imath]v_2[/imath], which in turn contains 2 and the set [imath]v_3[/imath], and so on. Such sets don't exist in ZFC, but they must exist with the Antifoundation axiom.
http://standish.stanford.edu/pdf/00000056.pdf looks like it might be a good book on this kind of thing. But I honestly only know a little bit about the subject.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
Re: Infinite Sets
Thanks for the replies. I was in fact referring to ZFC when I originally thought about this, but I didn't really consider other possible sets of axioms. It's interesting that there is, then, a set theory where they are useful and, in fact, required.
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: Infinite Sets
Just reading about the axiom of regularity as a result of this thread, and I'm having trouble reconciling the definition given on Wikipedia with the results claimed on Wikipedia and in this thread.
http://en.wikipedia.org/wiki/Axiom_of_regularity
Wikipedia says that the axiom of regularity says that for every nonempty set A, there exists an element B of A which is disjoint from A (ie if C is in B then it is not in A). It then goes on to say that this implies the result that no set can contain itself, and the result that the OP's construction can't exist.
I'm having trouble with this conclusion. Here's why:
Consider the 'set' A which has two members, itself and the empty set. Now, it does contain an element  the empty set  which shares no members with A, and so is disjoint from A. So therefore A doesn't violate the axiom of regularity.

PS: I think that one of the four following things has happened, in order of likelihood:
a) My reasoning is faulty.
b) I am misinterpreting the axiom of regularity, or the results that follow from it.
c) Other axioms of ZFC make this construction invalid (perhaps in conjunction with the axiom of regularity).
d) Wikipedia has it wrong.
http://en.wikipedia.org/wiki/Axiom_of_regularity
Wikipedia says that the axiom of regularity says that for every nonempty set A, there exists an element B of A which is disjoint from A (ie if C is in B then it is not in A). It then goes on to say that this implies the result that no set can contain itself, and the result that the OP's construction can't exist.
I'm having trouble with this conclusion. Here's why:
Consider the 'set' A which has two members, itself and the empty set. Now, it does contain an element  the empty set  which shares no members with A, and so is disjoint from A. So therefore A doesn't violate the axiom of regularity.

PS: I think that one of the four following things has happened, in order of likelihood:
a) My reasoning is faulty.
b) I am misinterpreting the axiom of regularity, or the results that follow from it.
c) Other axioms of ZFC make this construction invalid (perhaps in conjunction with the axiom of regularity).
d) Wikipedia has it wrong.
Re: Infinite Sets
Just scroll down the page a bit. The set you constructed doesn't violate regularity, but it implies the existence of a set that does.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
 Xenomortis
 Not actually a special flower.
 Posts: 1445
 Joined: Thu Oct 11, 2012 8:47 am UTC
Re: Infinite Sets
dudiobugtron wrote:Wikipedia says that the axiom of regularity says that for every nonempty set A, there exists an element B of A which is disjoint from A (ie if C is in B then it is not in A). It then goes on to say that this implies the result that no set can contain itself, and the result that the OP's construction can't exist.
I'm having trouble with this conclusion. Here's why:
Consider the 'set' A which has two members, itself and the empty set. Now, it does contain an element  the empty set  which shares no members with A, and so is disjoint from A. So therefore A doesn't violate the axiom of regularity.
You're considering the wrong set.
This is the first thing covered after the introductory paragraphs.
Spoiler:
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: Infinite Sets
Ah I see. Basically, if there is a set which contains itself, then there is a set which contains only itself (by the axiom of paring, apparently), and then that set violates regularity.
So my set effectively violates the axiom of pairing in conjunction with the axiom of regularity. So 'c' was the correct problem (and the most reassuring one). Thanks for the help!
So my set effectively violates the axiom of pairing in conjunction with the axiom of regularity. So 'c' was the correct problem (and the most reassuring one). Thanks for the help!

 Posts: 546
 Joined: Mon May 03, 2010 10:48 pm UTC
Re: Infinite Sets
dudiobugtron wrote:Ah I see. Basically, if there is a set which contains itself, then there is a set which contains only itself (by the axiom of paring, apparently), and then that set violates regularity.
So my set effectively violates the axiom of pairing in conjunction with the axiom of regularity. So 'c' was the correct problem (and the most reassuring one). Thanks for the help!
Um, not quite. If any set A contains itself, then the set B = {A} = {A,A} exists by pairing. B violates the axiom of regularity. But B doesn't contain itself...
The 62foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.
meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"
 dudiobugtron
 Posts: 1098
 Joined: Mon Jul 30, 2012 9:14 am UTC
 Location: The Outlier
Re: Infinite Sets
Ah right, that makes more sense.
It also means we can't have some weird construction where A is an element of B, and B is an element of A.
It also means we can't have some weird construction where A is an element of B, and B is an element of A.

 Posts: 33
 Joined: Tue Feb 01, 2011 5:57 pm UTC
Re: Infinite Sets
Is there some axiom that allows you to have some set consisting of all other sets?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Infinite Sets
benoitowns wrote:Is there some axiom that allows you to have some set consisting of all other sets?
No. That set causes problems. For instance, there is a thing called Russell's paradox.
http://en.wikipedia.org/wiki/Russell%27s_paradox
You would run straight into that (people often think that Russell's paradox means that sets that contain themselves are paradoxical  they're not, but the set of all sets is). Another reason it would cause you problems would be its cardinality. For every set, PowerSet(S) > S (this is called Cantor's theorem), but if S is the set of all sets, then S must be the biggest set and must contain PowerSet(S) as a subset, which would be a paradox.
There are probably other problems that you could locate, but basically the set of all sets will always cause big problems. There be dragons is what I'm saying.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Infinite Sets
Is there some axiom that allows you to have some set consisting of all other sets?
In ZFC, there is no such set, as Jestingrabbit explained. However, some axiomatic systems do have a set of all sets (the 'universal set'), notably Quine's 'New Foundations'. It gets around Russell's paradox by requiring 'stratified formulas' in its version of the axiom schema of comprehension.
Note also that while ZFC has no set of all sets, it does have a conservative extension (NBG) that includes both sets and 'proper classes', in which there is a class of all sets.
Re: Infinite Sets
Just to expand on the previous two posts, having an object (either calling it a set as well or something different like 'class') containing all objects of one type, possibly including itself, is not inherently a problem. It becomes a problem when you add other features to it, such as being able to take arbitrary subobjects (Russel's Paradox) or having maps between that object and the collection of its subobjects (Cantor).
ZFC gets around the issue by not allowing such a set to exist, but other theories can restrict the other structures, such as what subobjects are allowed.
ZFC gets around the issue by not allowing such a set to exist, but other theories can restrict the other structures, such as what subobjects are allowed.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Who is online
Users browsing this forum: No registered users and 26 guests