Subset

"Superset" redirects here. For other uses, see Superset (disambiguation).
Euler diagram showing
A is a proper subset of B and conversely B is a proper superset of A

In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment.

The subset relation defines a partial order on sets.

The algebra of subsets forms a Boolean algebra in which the subset relation is called inclusion.

Definitions

If A and B are sets and every element of A is also an element of B, then:

  • A is a subset of (or is included in) B, denoted by A \subseteq B,
or equivalently
  • B is a superset of (or includes) A, denoted by B \supseteq A.

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

  • A is also a proper (or strict) subset of B; this is written as A \subsetneq B.
or equivalently
  • B is a proper superset of A; this is written as B \supsetneq A.

For any set S, the inclusion relation ⊆ is a partial order on the set \mathcal{P}(S) of all subsets of S (the power set of S) defined by A \leq B \iff A \subseteq B. We may also partially order \mathcal{P}(S) by reverse set inclusion by defining A \leq B \iff B \subseteq A.

When quantified, A ⊆ B is represented as: ∀x{x∈A → x∈B}.[1]

Property

  • A is a subset of (or is included in) B, denoted by A \subseteq B,
If and only if the cardinality of their intersection is equal to the cardinality of A.

Formally:

 A \subseteq B \Leftrightarrow |A \cap B| = |A|

⊂ and ⊃ symbols

Some authors use the symbols ⊂ and ⊃ to indicate subset and superset respectively; that is, with the same meaning and instead of the symbols, ⊆ and ⊇.[2] So for example, for these authors, it is true of every set A that AA.

Other authors prefer to use the symbols ⊂ and ⊃ to indicate proper subset and superset, respectively, instead of ⊊ and ⊋.[3] This usage makes ⊆ and ⊂ analogous to the inequality symbols ≤ and <. For example, if xy then x may or may not equal y, but if x < y, then x may not equal y, and is less than y. Similarly, using the convention that ⊂ is proper subset, if AB, then A may or may not equal B, but if AB, then A definitely does not equal B.

Examples

The regular polygons form a subset of the polygons

Another example in an Euler diagram:

Other properties of inclusion

A ⊆ B and B ⊆ C imply A ⊆ C

Inclusion is the canonical partial order in the sense that every partially ordered set (X, \preceq) is isomorphic to some collection of sets ordered by inclusion. The ordinal numbers are a simple example—if each ordinal n is identified with the set [n] of all ordinals less than or equal to n, then ab if and only if [a] ⊆ [b].

For the power set \mathcal{P}(S) 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 S = {s1, s2, …, sk} and associating with each subset TS (which is to say with each element of 2S) the k-tuple from {0,1}k of which the ith coordinate is 1 if and only if si is a member of T.

See also

References

  1. Rosen, Kenneth H. (2012). Discrete Mathematics and Its Applications (7th ed.). New York: McGraw-Hill. p. 119. ISBN 978-0-07-338309-5.
  2. Rudin, Walter (1987), Real and complex analysis (3rd ed.), New York: McGraw-Hill, p. 6, ISBN 978-0-07-054234-1, MR 924157
  3. Subsets and Proper Subsets (PDF), retrieved 2012-09-07

External links

This article is issued from Wikipedia - version of the Friday, April 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.