A subset is a portion of a set.  is a subset of
 (written  ) iff
every member of  is a member of  . If  is a proper subset of  (i.e., a subset
other than the set itself), this is written  . If  is not a subset of  , this is written
 . (The notation  is generally
not used, since  automatically means that
 and  cannot be the same.)
The subsets (i.e., power set) of a given set can be found using Subsets[list].
An efficient algorithm for obtaining the next higher number having the same number of 1 bits as a given number (which corresponds to computing the next subset) is given by Gosper (1972) in PDP-10 assembler.
The set of subsets of a set  is called the power set of  , and a set of  elements has  subsets (including
both the set itself and the empty set).
This follows from the fact that the total number of distinct k-subsets on a set of  elements is given
by the binomial sum
For sets of  , 2, ... elements, the numbers of subsets
are therefore 2, 4, 8, 16, 32, 64, ... (Sloane's A000079). For example, the set  has the two
subsets  and  . Similarly,
the set  has subsets  (the empty set),  ,  , and  .
Courant, R. and Robbins, H. What Is Mathematics?: An Elementary Approach to Ideas and Methods,
2nd ed. Oxford, England: Oxford University Press, p. 109, 1996.
Gosper, R. W. Item 175 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239,
Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175.
Kamke, E. Theory of Sets. New York: Dover, p. 6, 1950.
Ruskey, F. "Information of Subsets of a Set." http://www.theory.csc.uvic.ca/~cos/inf/comb/SubsetInfo.html.
Skiena, S. "Binary Representation and Random Sets." §1.5.2 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica.
Reading, MA: Addison-Wesley, pp. 41-42, 1990.
Sloane, N. J. A. Sequence A000079/M1129 in "The On-Line Encyclopedia of Integer
Sequences."
|
Contact the MathWorld Team
