Subset

A subset is a portion of a set. 👁 B
is a subset of 👁 A
(written 👁 B subset= A
) iff every member of 👁 B
is a member of 👁 A
. If 👁 B
is a proper subset of 👁 A
(i.e., a subset other than the set itself), this is written 👁 B subset A
. If 👁 B
is not a subset of 👁 A
, this is written 👁 B !subset= A
. (The notation 👁 B !subset A
is generally not used, since 👁 B !subset= A
automatically means that 👁 B
and 👁 A
cannot be the same.)

The subsets (i.e., power set) of a given set can be found using [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 👁 S
is called the power set of 👁 S
, and a set of 👁 n
elements has 👁 2^n
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 👁 n
elements is given by the binomial sum

For sets of 👁 n=1
, 2, ... elements, the numbers of subsets are therefore 2, 4, 8, 16, 32, 64, ... (OEIS A000079). For example, the set 👁 {1}
has the two subsets 👁 emptyset
and 👁 {1}
. Similarly, the set 👁 {1,2}
has subsets 👁 emptyset
(the empty set), 👁 {1}
, 👁 {2}
, and 👁 {1,2}
.

See also

Empty Set, Implies, Improper Subset, k-Subset, p-System, Power Set, Proper Subset, Subset Sum Problem, Superset, Venn Diagram Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Subset

Cite this as:

Weisstein, Eric W. "Subset." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Subset.html

Subject classifications