Infinite Sets

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

gaga654
Posts: 12
Joined: Tue Mar 01, 2011 1:37 am UTC

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?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

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.

gaga654
Posts: 12
Joined: Tue Mar 01, 2011 1:37 am UTC

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

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

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);
semi-rigorous definition of N
Spoiler:
Let 0 be the empty set.
Define n+1 to be n U {n}
For all n in N, n+1 is in N.
0 is in 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.

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);
semi-rigorous definition of N
Spoiler:
Let 0 be the empty set.
Define n+1 to be n U {n}
For all n in N, n+1 is in N.
0 is in 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 OP isn't trying to find a set which contains arbitrarily deep elements, they're trying to find sets {An}n in N such that An is in An+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.

Elmach
Posts: 155
Joined: Sun Mar 13, 2011 7:47 am UTC

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);
semi-rigorous definition of N
Spoiler:
Let 0 be the empty set.
Define n+1 to be n U {n}
For all n in N, n+1 is in N.
0 is in 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 OP isn't trying to find a set which contains arbitrarily deep elements, they're trying to find sets {An}n in N such that An is in An+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, An+1 is in An. 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, An+1 is in An. 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.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

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

gaga654
Posts: 12
Joined: Tue Mar 01, 2011 1:37 am UTC

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 non-empty 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.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

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: 1446
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 non-empty 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:
Consider a set A.
Now apply the Axiom of Regularity to {A} (which exists and is bounded by P(A)).
Regularity implies that there must exist an element of {A}, B, such that B and {A} are disjoint. Since {A} has precisely one element, B = A and we have that A and {A} are disjoint.
i.e. A has no elements in common with the elements of {A} (which has precisely one element; A)
Which simply means that A is not a member of itself.

Hence the Axiom of Regularity implies that no set is a member of itself. 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!

Dark Avorian
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 62-foot 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.

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

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.

Aiwendil
Posts: 313
Joined: Thu Apr 07, 2011 8:53 pm UTC
Contact:

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.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.