In mathematics, a set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion (or sometimes containment). A is a subset of B may also be expressed as B includes (or contains) A or A is included (or contained) in B. A k-subset is a subset with k elements. When quantified, is represented as One can prove the statement by applying a proof technique known as the element argument : Let sets A and B be given. To prove that The validity of this technique can be seen as a consequence of universal generalization: the technique shows for an arbitrarily chosen element c. Universal generalisation then implies which is equivalent to as stated above.

Definition

If A and B are sets and every element of A is also an element of B, then: If A is a subset of B, but A is not equal to B (i.e. there exists at least one element of B which is not an element of A), then: The empty set, written { } or has no elements, and therefore is vacuously a subset of any set X.

Basic properties

Proper subset

⊂ and ⊃ symbols

Some authors use the symbols \subset and \supset to indicate and respectively; that is, with the same meaning as and instead of the symbols \subseteq and \supseteq. For example, for these authors, it is true of every set A that (a reflexive relation). Other authors prefer to use the symbols \subset and \supset to indicate (also called strict) subset and superset respectively; that is, with the same meaning as and instead of the symbols \subsetneq and \supsetneq. This usage makes \subseteq and \subset analogous to the inequality symbols \leq and <. For example, if x \leq y, then x may or may not equal y, but if x < y, then x definitely does not equal y, and is less than y (an irreflexive relation). Similarly, using the convention that \subset is proper subset, if then A may or may not equal B, but if then A definitely does not equal B.

Examples of subsets

Another example in an Euler diagram:

Power set

The set of all subsets of S is called its power set, and is denoted by. The inclusion relation \subseteq is a partial order on the set defined by. We may also partially order by reverse set inclusion by defining For the power set of a set S, the inclusion partial order is—up to an order isomorphism—the Cartesian product of k = |S| (the cardinality of S) copies of the partial order on {0, 1} for which 0 < 1. This can be illustrated by enumerating, and associating with each subset (i.e., each element of 2^S) the k-tuple from {0, 1}^k, of which the ith coordinate is 1 if and only if s_i is a member of T. The set of all k-subsets of A is denoted by, in analogue with the notation for binomial coefficients, which count the number of k-subsets of an n-element set. In set theory, the notation [A]^k is also common, especially when k is a transfinite cardinal number.

Other properties of inclusion