Re: number of sets in some standard set structures
- From: "Daniel J. Greenhoe" <dgreenhoe@xxxxxxxxx>
- Date: Wed, 7 Jan 2009 14:07:39 -0800 (PST)
On Dec 30 2008, 6:59 pm, Niels Diepeveen
Once you have the association with Boolean lattices...
the atoms ... of the lattice correspond
to minimal nonempty sets in the algebra...
the maximum of the lattice is the supremum (union) of these atoms.
... a finite Boolean lattice is completely
determined by these atoms.
... "a set is in the algebra if and only if it is
the union of a combination of minimal nonempty sets".
... the minimal nonempty sets are a partition of X,
Hi Niels,
Thank you for your help in showing the relationship between algebra of
sets and partitions. The part about a Boolean lattice being completely
determined by its atoms is especially useful. Many many thanks!!!
^___^
I don't currently have my own proof for the atoms being a basis for
boolean lattices. Maybe I will spend some time studying Boolean
lattices before proceeding with other things. If you know of any
especially good references for Boolean lattices, please let me know.
Thanks!
Dan
On Dec 30 2008, 6:59 pm, Niels Diepeveen <n529...@xxxxxxxxxxxx> wrote:
Daniel J. Greenhoe wrote:
On Dec 28, 2:32 am, cbr...@xxxxxxxxxxxxxxxxx (Chas) wrote:On Dec 26, 6:50 am, "Daniel J. Greenhoe" <dgreen...@xxxxxxxxx> wrote:On Dec 27, 3:45 am, Niels Diepeveen <n529...@xxxxxxxxxxxx> wrote:
I did indeed make an error here --- there are 5 rings of sets on X=1.number of rings of sets:Not counting the empty set?
------------------------------------
For example, there are 4 rings of sets on the n=2 element set X={x,y}
{x,y}, as you indicated.
Here are the five rings of sets on the set X={x,y}:
R1 = { ∅, }
R2 = { ∅, {x} }
R3 = { ∅, {y} }
R4 = { ∅, {x, y} }
R5 = { ∅, {x} , {y} , {x,y} }
(I am not sure if "∅" will display correctly on all newsreaders/
browsers, but it is supposed to be the emptyset symbol.)
R4 and R5 are also algebras of sets.
Yes, that one is a ring of sets. In fact, every ring of sets containsOops. I meant to say the ring with only the empty set.So while we should /not/ count R = {}, we /should/ count the trivial R = { {} }
the empty set as an element. In "universal algebra" one would say that
there are 7 standard set operations on X: union, intersection,
difference, symmetric difference, complement, emptyset, and the
universal set X (the first four are binary operations, the complement
is a unary operation, and the last two are nullary operations). And of
these 7 operations, rings of sets are closed under 5 of them ---
union, intersection, difference, symmetric difference, and emptyset.
Here are the 15 rings of sets on the set X={x,y,z}:15 rings of sets on the n=3 element set X={x,y,z}.Counting the empty set this time?
R1 = { ∅ }
R2 = { ∅, {x} }
R3 = { ∅, {y} }
R4 = { ∅, {z} }
R5 = { ∅, {x, y} }
R6 = { ∅, {x, z} }
R7 = { ∅, {y, z} }
R8 = { ∅, {x} , {y} , {x, y} }
R9 = { ∅, {x} , {z} , {x, z} }
R10 = { ∅, {y} , {z} , {y, z} }
R11 = { ∅, X }
R12 = { ∅, {x} , {y, z} , X }
R13 = { ∅, {y} , {x, z} , X }
R14 = { ∅, {z} , {x, y} , X }
R15 = { ∅, {x} , {y} , {z} , {x, y} , {x, z} , {y, z} , X }
The last five, R11--R15, are also algebras of sets.
Algebra of sets are closed under all 7 operations.2 algebras of sets on the n=2 element set X={x,y},
5 algebras of sets on the n=3 element set X={x,y,z}.
Here are the two algebra of sets on X={x,y}:
A1 = {∅, X}
A2 = {∅, {x} , {y} , X}
Here are the five algebra of sets on X={x,y,z}:
A1 = { ∅, X }
A2 = { ∅, {x} , {y, z} , X }
A3 = { ∅, {y} , {x, z} , X }
A4 = { ∅, {z} , {x, y} , X }
A5 = { ∅, {x} , {y} , {z} , {x, y} , {x, z} , {y, z} , X }
That is an interesting observation. In fact, it has been proven as farAs far as I can see both the above are essentially Boolean algebras
back as 1936 that every Boolean lattice is isomorphic to an algebra of
sets:
Stone (1936): Transactions of the American Mathematical Society 40
[1936]
Gr¨atzer (1971): Lattice Theory; first concepts and distributive
lattices, page 76
Gr¨atzer (1998): General Lattice Theory, page 85
In the first case the minimal non-empty sets are an arbitrary partition of a subset of Xin which case f(n) = B(n+1), where B(n) is the nth Bell number;
http://www.research.att.com/~njas/sequences/A000110
and in the second case they are an arbitrary partition of Xin which case f(n) = B(n).
The Bell numbers by definition describe the number of partitions on a
finite set X with n elements (or alternatively, the number of
equivalence relations on X). Using the Bell numbers to describe the
number of rings of setsas B(n+1) and the number of algebras of sets
as B(n) is a very interesting suggestion and it would seem likely to
be true (has it been proven true?). Thank you very much for sharing
this insight!
Dan (original poster)
I have never seen a proof of this particular fact, but all the hard
parts are "well known facts", as far as I can see.
Once you have the association with Boolean lattices, you can use the
fact that the atoms (minimal nonzero elements) of the lattice correspond
to minimal nonempty sets in the algebra. You also know that the maximum
of the lattice is the supremum (union) of these atoms.
Most importantly, you know that a finite Boolean lattice is completely
determined by these atoms. In terms of an algebra of sets this boils
down to "a set is in the algebra if and only if it is the union of a
combination of minimal nonempty sets".
So what remains to be shown is that the minimal nonempty sets are a
partition of X, which is easy. I have already noted that their union
must be X. That they are pairwise disjoint follows from the fact that
the intersection of two distinct sets is a proper subset of at least one
of them.
For rings of sets the story is pretty similar, except that there is no
complement w.r.t. X, only w.r.t. the union of all sets in the ring, so
that union can be an arbitrary subset of X.
On Dec 26, 6:50 am, "Daniel J. Greenhoe" <dgreen...@xxxxxxxxx> wrote:
I have some questions about some standard set structures.
1.number of rings of sets:
------------------------------------
How many rings of sets are there on a finite set of with n labeled
elements?
By "ring of sets" I mean any subset of the powerset of a set X that is
closed under set union and set difference. For example, there are
4 rings of sets on the n=2 element set X={x,y}, and
15 rings of sets on the n=3 element set X={x,y,z}.
2. number of algebras of sets:
-----------------------------------------
How many algebras of sets are there on a finite set of with n labeled
elements?
By "algebra of sets" I mean any subset of the powerset of a set X that
is closed under set complement set intersection. For example, there
are
2 algebras of sets on the n=2 element set X={x,y}, and
5 algebras of sets on the n=3 element set X={x,y,z}.
--------------------------------
For items 1 and 2 above, I am looking for something maybe similar to
what has been done for the number of topologies at
http://www.research.att.com/~njas/sequences/A000798
or for the number of partitions at
http://www.research.att.com/~njas/sequences/A000110
Good references would be especially appreciated. Thanks!
Here are references for the above definition of rings of sets:
* Berezansky, Sheftel and Us (1996): Functional Analysis: Volume
I. . . , page 4
* Halmos (1950): Measure Theory, page 19
* Hausdorff (1937): Set Theory (Grundz¨uge der Mengenlehre), page 90
Here are references for the above definition of algebra of sets:
* Aliprantis and Burkinshaw (1998): Principles of Real Analysis, page
95
* Halmos (1950): Measure Theory, page 21
* Hausdorff (1937): Set Theory (Grundz¨uge der Mengenlehre), page 91
Note, some authors have used an alternative definition of rings of
sets that is incompatible with the one used in this post:
* Hausdorff (1937): Set Theory (Grundz¨uge der Mengenlehre), 90
* Birkhoff (1937): Duke Math. J. 3 [1937], page 443
* Erd¨os and Tarski (1943): Annals of Mathematics, page 315
* MacLane and Birkhoff (1999): Algebra, page 485
Many many thanks in advance!
Dan Greenhoe
On Dec 26, 9:20 am, Niels Diepeveen <n529...@xxxxxxxxxxxx> wrote:
Daniel J. Greenhoe wrote:
I have some questions about some standard set structures.Not counting the empty set?
1.number of rings of sets:
------------------------------------
How many rings of sets are there on a finite set of with n labeled
elements?
By "ring of sets" I mean any subset of the powerset of a set X that is
closed under set union and set difference. For example, there are
4 rings of sets on the n=2 element set X={x,y}, and
15 rings of sets on the n=3 element set X={x,y,z}.Counting the empty set this time?
2. number of algebras of sets:15, 52, 203, if I'm not mistaken.
-----------------------------------------
How many algebras of sets are there on a finite set of with n labeled
elements?
By "algebra of sets" I mean any subset of the powerset of a set X that
is closed under set complement set intersection. For example, there
are
2 algebras of sets on the n=2 element set X={x,y}, and
5 algebras of sets on the n=3 element set X={x,y,z}.
As far as I can see both the above are essentially Boolean algebras, at
least for finite X.
In the first case the minimal non-empty sets are an arbitrary partition
of a subset of X, and in the second case they are an arbitrary partition
of X.
That should make them relatively easy to count.
--
Niels Diepeveen
On Dec 27, 8:26 am, cbr...@xxxxxxxxxxxxxxxxx wrote:
On Dec 25, 5:20 pm, Niels Diepeveen <n529...@xxxxxxxxxxxx> wrote:
Daniel J. Greenhoe wrote:
I have some questions about some standard set structures.Not counting the empty set?
1.number of rings of sets:
------------------------------------
How many rings of sets are there on a finite set of with n labeled
elements?
By "ring of sets" I mean any subset of the powerset of a set X that is
closed under set union and set difference. For example, there are
4 rings of sets on the n=2 element set X={x,y}, and
15 rings of sets on the n=3 element set X={x,y,z}.Counting the empty set this time?
2. number of algebras of sets:
-----------------------------------------
How many algebras of sets are there on a finite set of with n labeled
elements?
By "algebra of sets" I mean any subset of the powerset of a set X that
is closed under set complement set intersection. For
...
read more »
.
- Prev by Date: Re: Example of a subspace of vector space R^n ?
- Next by Date: Re: rational to real number
- Previous by thread: What is this impossible figure?
- Next by thread: involute/evolute
- Index(es):
Relevant Pages
|
