Subset
المؤلف:
Sloane, N. J. A
المصدر:
Sequence A000079/M1129 in "The On-Line Encyclopedia of Integer Sequences."
الجزء والصفحة:
...
17-1-2022
3805
Subset
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, ... (OEIS A000079). For example, the set ![<span style=]()
{1}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline22.svg" style="height:22px; width:22px" /> has the two subsets 
and ![<span style=]()
{1}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline24.svg" style="height:22px; width:22px" />. Similarly, the set ![<span style=]()
{1,2}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline25.svg" style="height:22px; width:43px" /> has subsets 
(the empty set), ![<span style=]()
{1}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline27.svg" style="height:22px; width:22px" />, ![<span style=]()
{2}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline28.svg" style="height:22px; width:22px" />, and ![<span style=]()
{1,2}" src="https://mathworld.wolfram.com/images/equations/Subset/Inline29.svg" style="height:22px; width:43px" />.
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."
الاكثر قراءة في نظرية المجموعات
اخر الاخبار
اخبار العتبة العباسية المقدسة
