Maarten Maartensz:    Philosophical Dictionary | Filosofisch Woordenboek                      

 S - Subset


Subset: A subset A is a set that is contained in another set B in the sense that every element of A is an element of B. The set theoretical notation and definition comes to this: (A a B) iff (x)(xeA --> xeB).

In the sense given, which did not refer to any characteristic property of a subset other than that it contains only elements of the set it is a subset of, this may be somewhat problematic.

The reason is that it is easy to prove that for any finite set with n elements the number of its subsets must be 2n - and even for rather small sets this gets quickly quite large. Thus, if n=10, 2n =1024, and if n=100 then 2n= 1267650600228229401496703205376. Hence, there are that many distinct subsets of 100 elements - and it would be quite impossible, in practice, to list them all or characterize them all by some property that would differ from a mere explicit list of all and only elements of the set.

Hence, while the notion of a subset is quite easy to grasp and define, and seems quite sensible, it easily leads to possibilities that are hard to fathom since they are impossible to survey in a finite human life, other than by formal means - which in the case of n=100 mentioned above might be to refer to all the distinct subsets of a given 100 elements by the numbers of 1 to 2n.

For more, see Powerset.

See also: Powerset, Set, Set Theory


Halmos, Quine, Suppes


 Original: Aug 25, 2004                                                Last edited: 12 December 2011.   Top