Math Dopers: a reference question about set theory

[scotandrsn]

I am looking for a good online resource (or barring that, a good printed source) for information regarding the second power set.

Specifically, I am trying to find information on what, if anything, has been proved regarding elements of the second power set P(P(S)) of a set S which are sets whose elements are mutually disjoint subsets of S.

I have no idea if there is already a name for such an area of research, if that’s any help in understanding my level of sophistication here (or extreme lack thereof, which seems to me to be why by normally excellent Google-fu is failing me here).

I’m just following a line of inquiry that has led me to this.

[Omphaloskeptic]

@scotandrsn

Specifically, I am trying to find information on what, if anything, has been proved regarding elements of the second power set P(P(S)) of a set S which are sets whose elements are mutually disjoint subsets of S.

The sets you describe are closely related to the partitions of S (a partition of S is a set of disjoint subsets of S whose union is exactly S, so by choosing a partition of S and then throwing out one of the subsets you get a set of disjoint subsets of S as you have described). Without knowing what you want to do with these sets I can’t tell whether that’s helpful information, though.

[ultrafilter]

Each element of P(P(S)) is isomorphic to a boolean function on S. Depending on what you’re looking for, the boolean algebra literature might be a better place to search.

[Omphaloskeptic]

@ultrafilter

Each element of P(P(S)) is isomorphic to a boolean function on S. Depending on what you’re looking for, the boolean algebra literature might be a better place to search.

Each element of P(P(S)) is isomorphic to a boolean function on P(S), not on S.

[ultrafilter]

@Omphaloskeptic

Each element of P(P(S)) is isomorphic to a boolean function on P(S), not on S.

Yeah, that’s what I meant.

[tim314]

@Omphaloskeptic

The sets you describe are closely related to the partitions of S (a partition of S is a set of disjoint subsets of S whose union is exactly S, so by choosing a partition of S and then throwing out one of the subsets you get a set of disjoint subsets of S as you have described). Without knowing what you want to do with these sets I can’t tell whether that’s helpful information, though.

Elaborating slightly:

There’s a surjective function to map each set of disjoint subsets of S onto a partition of S:

Let D be a set of disjoint subsets of S
and let O = {all s in S | for all d in D, s is not in d}
Then we can specify a partition of S by P(D) = union of D and {O}.

The function P(D) (from disjoint subsets of S to partitions of S) is surjective (i.e., onto), because every P is a disjoint subset of S, and P(P) = P.

It’s not injective (i.e., one-to-one), however.
For instance:
Let S = {1,2,3}
Let D1 = {{1},{2}}
Let D2 = {{2},{3}}
Then P(D1) = P(D2) = {{1},{2},{3}}

It seems to me, however, that you could specify a bijective function from disjoint subsets of S to partitions of the union of S and {x}, where x is some element not in S:

For D and O as specified above, let P(D) = union of D and {union of O and {x}}
For the inverse D(P), let D(P) = {all p in P | x is not in p}

Putting this another way: For each element s in S, there is a bijective map from the set of all disjoint subsets of S \ {s} (i.e., S excluding s) to the partitions of S.

Of course, this is all only of any use to you if any of the results for partitions are useful.

[scotandrsn]

Partitions I recall from college, and they are not the reason for my interest in the mutual-disjointedness of the sets.

Rather, there is an inductive proof I am trying to work out for myself, dealing with elements of P(P(S)) which are sets of a particular cardinality, but the specific application I am working out the proof for requires the sets to have no elements in common. The set of results I am seeking grows exponentially for each succeeding n where n is the cardinality of S. I’ve demonstrate the fact of my results to myself for the cases of n = 1,…,6, but each demonstration is taking a longer and longer time. The results of any particular n seem to be based on the results for n-1. I seek to prove this is so for all n, hence my search for an inductive proof.

My main problem is that the only notation I know for sets makes trying to work out this inductive proof a living nightmare. Unfortunately, I don’t know what my alternatives are, but my experience has been that any new mathematics idea I suddenly get in my head has been worked to death by someone else decades or centuries ago, and I think it’s most likely that if I search long enough, I’ll find out that someone else has already worked out the proof I seek. Given that I don’t even know the names of these areas of study, I am at a loss as to where to go next to educate myself.

Thanks greatly for all responses so far!

[Omphaloskeptic]

@scotandrsn

Rather, there is an inductive proof I am trying to work out for myself, dealing with elements of P(P(S)) which are sets of a particular cardinality, but the specific application I am working out the proof for requires the sets to have no elements in common. The set of results I am seeking grows exponentially for each succeeding n where n is the cardinality of S. I’ve demonstrate the fact of my results to myself for the cases of n = 1,…,6, but each demonstration is taking a longer and longer time. The results of any particular n seem to be based on the results for n-1. I seek to prove this is so for all n, hence my search for an inductive proof.

Hmm, this is still too vague for me, at least, to have any real suggestions. Maybe if you can state what you’re trying to prove someone can give better references (or proofs or hints, if you want those).

[scotandrsn]

@Omphaloskeptic

Hmm, this is still too vague for me, at least, to have any real suggestions. Maybe if you can state what you’re trying to prove someone can give better references (or proofs or hints, if you want those).

Probably because I mis-typed myself. Let me try again.

Assume set S with n elements.

Take second power set of S P(P(S)).

I am interested in the subset T of P(P(S)), where elements of T are those elements of S which are sets Q.1, Q.2, etc. of cardinality k where each member of each set Q.x is a mutually disjoint subset of S. It not important to my proof, however, whether the mutually disjoint subsets form a partition on S.

I have discovered something about the cardinality of T for various values of n that I believe is universal, and could be proved by induction, namely that card(T(n)) = f(card(T(n-1))), where f is a function.

Trouble is, I’m screwed once i get to the inductive step of the proof. I only know how to express sets by listing their elements, and once I do that for k and k+1, I have no idea how to begin to turn one into a variation of the other. I’m hoping that there’s some standard way of approaching my problem, either through a proven set of operations on sets, or a different notation. I just don’t know very much about set theory.

[Omphaloskeptic]

@scotandrsn

Assume set S with n elements.

Take second power set of S P(P(S)).

I am interested in the subset T of P(P(S)), where elements of T are those elements of S [I assume this should be “P(P(S))”] which are sets Q.1, Q.2, etc. of cardinality k where each member of each set Q.x is a mutually disjoint [nonempty?] subset of S. It not important to my proof, however, whether the mutually disjoint subsets form a partition on S.

I have discovered something about the cardinality of T for various values of n that I believe is universal, and could be proved by induction, namely that card(T(n)) = f(card(T(n-1))), where f is a function.

Trouble is, I’m screwed once i get to the inductive step of the proof. I only know how to express sets by listing their elements, and once I do that for k and k+1, I have no idea how to begin to turn one into a variation of the other. I’m hoping that there’s some standard way of approaching my problem, either through a proven set of operations on sets, or a different notation. I just don’t know very much about set theory.

I would probably classify this as a problem in combinatorics, not set theory, since everything is nice and finite and discrete; just fix some convenient n-element set S_n such as S_n={1,2,3,…,n} and work with that. tim314’s nice observation allows you to work with partitions of S’_n={0,1,2,3,…,n} (where “0” is the tag element; the subset containing 0 is thrown out) instead of arbitrary collections of disjoint subsets; this may be helpful.

Combinatoric proofs often proceed by forming some sort of counting isomorphism. A simple example is the combinatoric proof of the Pascal’s-triangle formula for the binomial coefficients, C(n,r)=C(n-1,r-1)+C(n-1,r), where C(n,r) is defined as the number of r-element subsets of an n-element set (say, the set S_n as defined above). To count C(n,r), first consider all of the subsets without element n. Clearly there are just C(n-1,r) of these, since these are just the r-element subsets of S_(n-1)={1,…,n-1}. Now consider the subsets with element n. Now there are C(n-1,r-1) of these, since we’ve picked one element and know there must be r-1 more elements to pick from S_(n-1). We’ve obviously considered all cases, and counted each element exactly once, so we’ve proved the statement. (Note that we were able to do this without explicitly listing the subsets, so this doesn’t have the scaling problem that you are encountering.) Can you find some isomorphism from T_n to a collection of other sets whose cardinalities you already know?

Let me see if I understand your particular problem, with an example. You count the number t_4 of collections of k=3 disjoint subsets of, say, {1,2,3,4} (including, for example, {{1,2},{3},{4}} and {{1},{2},{4}}; if I counted right and empty sets don’t count then there should be t_4=10), and similarly you count the number t_5 (=65?) of collections of 3 disjoint subsets of {1,2,3,4,5}, and you believe that you have a function f (with some nice form) having f(t_4)=t_5, etc. Is that the idea? If so, my previous Wikipedia link, together with tim314’s observation, has some relevant information.

[scotandrsn]

@Omphaloskeptic

I would probably classify this as a problem in combinatorics, not set theory, since everything is nice and finite and discrete; just fix some convenient n-element set S_n such as S_n={1,2,3,…,n} and work with that. tim314’s nice observation allows you to work with partitions of S’_n={0,1,2,3,…,n} (where “0” is the tag element; the subset containing 0 is thrown out) instead of arbitrary collections of disjoint subsets; this may be helpful.

Well, tim314’s caution at the end that his offering was only important if I needed partitions put me off deciphering the whole post, but I will take another look at it taking what you say into consideration.

@Omphaloskeptic

Combinatoric proofs often proceed by forming some sort of counting isomorphism. A simple example is the combinatoric proof of the Pascal’s-triangle formula for the binomial coefficients, C(n,r)=C(n-1,r-1)+C(n-1,r), where C(n,r) is defined as the number of r-element subsets of an n-element set (say, the set S_n as defined above). To count C(n,r), first consider all of the subsets without element n. Clearly there are just C(n-1,r) of these, since these are just the r-element subsets of S_(n-1)={1,…,n-1}. Now consider the subsets with element n. Now there are C(n-1,r-1) of these, since we’ve picked one element and know there must be r-1 more elements to pick from S_(n-1). We’ve obviously considered all cases, and counted each element exactly once, so we’ve proved the statement. (Note that we were able to do this without explicitly listing the subsets, so this doesn’t have the scaling problem that you are encountering.) Can you find some isomorphism from T_n to a collection of other sets whose cardinalities you already know?

Ah, now a combinatorics angle is something I could sink my teeth into! I could look into whether there’s a variation on the combination formula that allows for excluding elements from a combination’s count if they share or do not share some property. Now that we are in the realm of statistics, maybe I should just have a chat with my Dad the retired actuary.

@Omphaloskeptic

Let me see if I understand your particular problem, with an example. You count the number t_4 of collections of k=3 disjoint subsets of, say, {1,2,3,4} (including, for example, {{1,2},{3},{4}} and {{1},{2},{4}}; if I counted right and empty sets don’t count then there should be t_4=10), and similarly you count the number t_5 (=65?) of collections of 3 disjoint subsets of {1,2,3,4,5}, and you believe that you have a function f (with some nice form) having f(t_4)=t_5, etc. Is that the idea? If so, my previous Wikipedia link, together with tim314’s observation, has some relevant information.

That is it, I’ll have a look at your links. Thanks very much!

[scotandrsn]

@ultrafilter

Each element of P(P(S)) is isomorphic to a boolean function on S. Depending on what you’re looking for, the boolean algebra literature might be a better place to search.

Granted the correction to “Each element of P(P(S)) is isomorphic to a boolean function on P(S)” I’ll look for a proof of that in order to understand how this is so.

Thanks.

[Indistinguishable]

@scotandrsn

Granted the correction to “Each element of P(P(S)) is isomorphic to a boolean function on P(S)” I’ll look for a proof of that in order to understand how this is so.

Thanks.

Well, this is actually pretty immediate; no complicated proof to look for. An element of P(X) is just a subset of X, right? And a subset of X is just a rule saying for each element of X “This guy is in me” or “This guy is not in me”; if you think of “This guy is in me” as True and “This guy is not in me” as False, then you can look at this as a Boolean function on X. Thus, P(X) is always isomorphic to the Boolean functions on X, no matter what X is.

[Indistinguishable]

Incidentally, as has been noted above by Omphaloskeptic, it’s unclear whether you want empty sets to be admissible or not. For example, when k = 2 and n = 4 (so that we’re looking at unordered pairs of disjoint subsets of {1, 2, 3, 4}), does { {}, {1} } count? They really are mutually disjoint, those two, in that they don’t share any elements, but people get all kinds of odd hangups about empty sets.

[scotandrsn]

@Indistinguishable

Incidentally, as has been noted above by Omphaloskeptic, it’s unclear whether you want empty sets to be admissible or not. For example, when k = 2 and n = 4 (so that we’re looking at unordered pairs of disjoint subsets of {1, 2, 3, 4}), does { {}, {1} } count? They really are mutually disjoint, those two, in that they don’t share any elements, but people get all kinds of odd hangups about empty sets.

Let’s say S = {a,b}, so n=2

P(S) = {{}, {a}, {b}, {a,b}}

P(P(S)) = {
{},
{{}},
{{a}},
{{b}},
{{a,b}},
{{},{a}},
{{},{b}},
{{},{a,b}},
{{a},{b}},
{{a},{a,b}},
{{b},{a,b}},
{{},{a},{b}},
{{},{a},{a,b}},
{{},{b},{a,b}},
{{a},{b},{a,b}},
{{},{a},{b},{a,b}}
}

Let’s say the cardinality I’m interested is 2.

There are 6 elements of P(P(S)) that have cardinality 2:

{{},{a}},
{{},{b}},
{{},{a,b}},
{{a},{b}},
{{a},{a,b}},
{{b},{a,b}}

However, only four of them have elements that are mutually disjoint subsets of S:

T = { {{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}} } and has cardinality 4 in this case.

If the cardinality I wanted were 3, there would be only one element in my set:

T= { {{},{a},{b}} }

Even though there are four elements of P(P(S)) whose members have cardinality 3.

[Indistinguishable]

I believe, then, that one expression for the value T(n, k) which you want is T(n, k) = S(n+1, k) + S(n+1, k+1), where S(n, k) is the Stirling number of the second kind. S(n+1, k) is the number of things you’re looking for that contain an empty set, and S(n+1, k+1) is the number which don’t contain an empty set.

Of course, what you actually have seems to be a recurrence relation giving T(n, k) in terms of T(n-1, k) (and possibly n and k). One such relation would be T(n, k) = (k+1)*T(n-1, k) + S(n, k-1), which still involves Stirling numbers. I can’t think of anything better that gives T(n, k) strictly in terms of T(n-1, k), n, and k, but perhaps you have. Or perhaps I’ve misinterpreted the structure of your recurrence.

At any rate, as noted above, if you told us what exactly it was you were trying to prove, we may be more helpful. Hopefully I haven’t “spoiled” anything for you with this post.

[scotandrsn]

@Indistinguishable

…At any rate, as noted above, if you told us what exactly it was you were trying to prove, we may be more helpful. Hopefully I haven’t “spoiled” anything for you with this post.

Nothing spoiled but my conceit that perhaps I was onto something fresh that I needed to be cagey about. But then that 's what always happens.

I was moved to examine the set T(n, 2) by a problem in social networking theory I’m looking at. I discovered that:

card(T(1,2)) = 1
card(T(2,2)) = 4
card(T(3,2)) = 13
card(T(4,2)) = 40
card(T(5,2)) = 121

simply by generating the second power sets for each n and counting. Why yes, the last one DID take several hours, why do you ask? What, I had to be SURE!!!

So the principle seems to be that card(T(n+1, 2)) = 3(card(T(n, 2)) +1 = 3^n + card(T(n, 2)).

So I’m looking for how to construct an inductive proof of this.

[tim314]

@scotandrsn

So the principle seems to be that card(T(n+1, 2)) = 3(card(T(n, 2)) +1 = 3^n + card(T(n, 2)).

Hmm . . . let me try to reason out why that formula holds.

Start with S with n elements. Suppose we find that there are N sets of 2 disjoint subsets of S.

Now, move to S’ with n+1 element. That gives one more element to work with. Call the new element x.

So, the sets of 2 disjoint subsets of S’ will be all the sets of 2 disjoint subsets of S, plus we can take each of them again but add x to the first (inner) subset, plus we can take each of them again and add x to the second inner subset.

So that gives three times as many sets of two disjoint subsets.

Example:
If n was 2, we had:
{{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}}

and now we have:
(1) The original sets:
{{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}}
(2) The sets where x is added to the first set:
{{x},{a}}, {{x},{b}}, {{x},{a,b}}, {{a,x},{b}}
(3) The sets where x is added to the second set:
{{},{a,x}}, {{},{b,x}}, {{},{a,b,x}}, {{a},{b,x}}

However, what about taking sets of one disjoint subset, and then promoting them to sets of two disjoint subsets by adding the set containing x alone? It seems like this would add one set of two disjoint subsets for each of our original sets of one disjoint subset, but in fact there’s some double counting here:

Example (n=2):
We had:
{{}},{{a}},{{b}}
And now we have:
{{},{x}},{{a},{x}},{{b},{x}}

Note that the latter two of these already occured above. The key observation is this:
For every set of one set that isn’t the nullset, there was a set of two sets which contained that set and the nullset. Adding {x} to the set of one set then produces the same thing as adding x to the nullset within the set of two sets.

E.g.:
{{a}} → {{a},{x}}
{{a},{}} → {{a},{x}}

So, the only sets of one set that matter are those that already contain the nullset (because you can’t have a set of two sets that contains the nullset twice).

So, we only have to add 1 for the set {{},{x}}, which I produced by adding {x} to to the set {{}}.

This gives:
card(T(n+1, 2)) = 3(card(T(n, 2)) +1

And it seems (but I haven’t checked carefully) that it should generalize to:
card(T(n+1, k)) = (k+1)(card(T(n, k)) + card({All t in T(n, k-1) such that t contains the nullset})

It just happens that for k = 2 there’s only one set in T(n,k-1) that contains the nullset (namely {{}}), making the formula a bit simpler.

[tim314]

Assuming I haven’t made a mistake in my reasoning above, it shouldn’t be hard to turn that into a formal proof for the k = 2 case. For k > 2, I’d think you could define T[sub]0/sub as {All t in T(n, k) such that t contains the nullset} and then work out a recursion relation for T[sub]0/sub, use this to determine T[sub]0/sub in closed form, and plug that into your recursion relation for T(n,k)

[scotandrsn]

You are my god, tim314. Thank you!