View source for Subset

{{short description|Set whose elements all belong to another set}}
{{redirect|Superset}}

{{redirect|⊃|the logic symbol|Horseshoe (symbol)|other uses|Horseshoe (disambiguation)}}
[[File:Venn A subset B.svg|150px|thumb|right|class=skin-invert-image|[[Euler diagram]] showing<br /> ''A'' is a [[subset]] of ''B'' (denoted <math>A \subseteq B</math>) and, conversely, ''B'' is a superset of ''A'' (denoted <math>B \supseteq A</math>)]] 

In mathematics, a [[Set (mathematics)|set]] ''A'' is a '''subset''' of a set ''B'' if all [[Element (mathematics)|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, <math>A \subseteq B</math> is represented as <math>\forall x \left(x \in A \Rightarrow x \in B\right).</math><ref>{{cite book|last=Rosen|first=Kenneth H.|title=Discrete Mathematics and Its Applications|url=https://archive.org/details/discretemathemat00rose_408|url-access=limited|date=2012|publisher=McGraw-Hill|location=New York|isbn=978-0-07-338309-5|page=[https://archive.org/details/discretemathemat00rose_408/page/n139 119]|edition=7th}}</ref>

One can prove the statement <math>A \subseteq B</math> by applying a proof technique known as the element argument<ref>{{Cite book|last=Epp|first=Susanna S.|title=Discrete Mathematics with Applications|year=2011|isbn=978-0-495-39132-6|edition=Fourth|pages=337|publisher=Cengage Learning }}</ref>:<blockquote>Let sets ''A'' and ''B'' be given. To prove that <math>A \subseteq B,</math>

# '''suppose''' that ''a'' is a particular but arbitrarily chosen element of A
# '''show''' that ''a'' is an element of ''B''.
</blockquote>The validity of this technique can be seen as a consequence of [[universal generalization]]: the technique shows <math>(c \in A) \Rightarrow (c \in B)</math> for an arbitrarily chosen element ''c''. Universal generalisation then implies <math>\forall x \left(x \in A \Rightarrow x \in B\right),</math> which is equivalent to <math>A \subseteq B,</math> as stated above.<!-- to allow easy linking to this section which contains math in its name -->

==Definition==
If ''A'' and ''B'' are sets and every [[element (mathematics)|element]] of ''A'' is also an element of ''B'', then:
:*''A'' is a '''subset''' of ''B'', denoted by <math>A \subseteq B</math>, or equivalently,
:* ''B'' is a '''superset''' of ''A'', denoted by <math>B \supseteq A.</math>

{{anchor|proper subset}}
If ''A'' is a subset of ''B'', but ''A'' is not [[equal (math)|equal]] to ''B'' (i.e. [[there exists]] at least one element of B which is not an element of ''A''), then: 
:*''A'' is a '''proper''' (or '''strict''') '''subset''' of ''B'', denoted by <math>A \subsetneq B</math>, or equivalently,
:* ''B'' is a '''proper''' (or '''strict''') '''superset''' of ''A'', denoted by <math>B \supsetneq A.</math>

The [[empty set]], written <math>\{ \}</math> or <math>\varnothing,</math> has no elements, and therefore is [[Vacuous truth|vacuously]]  a subset of any set ''X''.  

==Basic properties==
[[File:Subset with expansion.svg|thumb|<math>A \subseteq B</math> and <math>B \subseteq C</math> implies <math>A \subseteq C.</math>]]
* ''[[Reflexive relation|Reflexivity]]'': Given any set <math>A</math>, <math>A \subseteq A</math><ref>{{cite book|first=Robert R.|last=Stoll|date=1 January 1968|title=Set Theory and Logic|publisher=Dover Publications|location=San Francisco, CA|isbn=978-0-486-63829-4}}</ref>
* ''[[Transitive relation|Transitivity]]'': If <math>A \subseteq B</math> and <math>B \subseteq C</math>, then <math>A \subseteq C</math>
* ''[[Antisymmetric relation|Antisymmetry]]'': If <math>A \subseteq B</math> and <math>B \subseteq A</math>, then <math>A = B</math>.

===Proper subset===
* ''[[Reflexive relation|Irreflexivity]]'': Given any set <math>A</math>, <math>A \subsetneq A</math> is False.
* ''[[Transitive relation|Transitivity]]'': If <math>A \subsetneq B</math> and <math>B \subsetneq C</math>, then <math>A \subsetneq C</math>
* ''[[Asymmetric relation|Asymmetry]]'': If <math>A \subsetneq B</math> then <math>B \subsetneq A</math> is False.

==⊂ and ⊃ symbols==
Some authors use the symbols <math>\subset</math> and <math>\supset</math> to indicate {{em|subset}} and {{em|superset}} respectively; that is, with the same meaning as and instead of the symbols <math>\subseteq</math> and <math>\supseteq</math>.<ref>{{Citation|last1=Rudin|first1=Walter|author1-link=Walter Rudin|title=Real and complex analysis|publisher=[[McGraw-Hill]]|location=New York|edition=3rd|isbn=978-0-07-054234-1|mr=924157 |year=1987|page=6}}</ref> For example, for these authors, it is true of every set ''A'' that <math>A \subset A.</math> (a [[reflexive relation]]).

Other authors prefer to use the symbols <math>\subset</math> and <math>\supset</math> to indicate {{em|proper}} (also called strict) subset and {{em|proper}} superset respectively; that is, with the same meaning as and instead of the symbols <math>\subsetneq</math> and <math>\supsetneq.</math><ref>{{Citation|title=Subsets and Proper Subsets|url=http://it.edgecombe.edu/homepage/killorant/MAT140/Module1/Subsets.pdf|access-date=2012-09-07|archive-url=https://web.archive.org/web/20130123202559/http://it.edgecombe.edu/homepage/killorant/MAT140/Module1/Subsets.pdf|archive-date=2013-01-23|url-status=dead }}</ref> This usage makes <math>\subseteq</math> and <math>\subset</math> analogous to the [[inequality (mathematics)|inequality]] symbols <math>\leq</math> and <math><.</math> For example, if <math>x \leq y,</math> then ''x'' may or may not equal ''y'', but if <math>x < y,</math> then ''x'' definitely does not equal ''y'', and ''is'' less than ''y'' (an [[irreflexive relation]]). Similarly, using the convention that <math>\subset</math> is proper subset, if <math>A \subseteq B,</math> then ''A'' may or may not equal ''B'', but if <math>A \subset B,</math> then ''A'' definitely does not equal ''B''.

== Examples of subsets ==
[[File:PolygonsSet EN.svg|thumb|The [[regular polygon]]s form a subset of the polygons.]]
* The set A = {1, 2} is a proper subset of B = {1, 2, 3}, thus both expressions <math>A \subseteq B</math> and <math>A \subsetneq B</math> are true.
* The set D = {1, 2, 3} is a subset (but {{em|not}} a proper subset) of E = {1, 2, 3}, thus <math>D \subseteq E</math> is true, and <math>D \subsetneq E</math> is not true (false).
* The set {''x'': ''x'' is a [[prime number]] greater than 10} is a proper subset of {''x'': ''x'' is an odd number greater than 10}
* The set of [[natural number]]s is a proper subset of the set of [[rational number]]s; likewise, the set of points in a [[line segment]] is a proper subset of the set of points in a [[:line (mathematics)|line]]. These are two examples in which both the subset and the whole set are infinite, and the subset has the same [[Cardinality#Infinite sets|cardinality]] (the concept that corresponds to size, that is, the number of elements, of a finite set) as the whole; such cases can run counter to one's initial intuition.
* The set of [[Rational number|rational numbers]] is a proper subset of the set of [[real number]]s. In this example, both sets are infinite, but the latter set has a larger cardinality (or {{em|power}}) than the former set.

Another example in an [[Euler diagram]]:

<gallery widths="270">
File:Example of A is a proper subset of B.svg|A is a proper subset of B.
File:Example of C is no proper subset of B.svg|C is a subset but not a proper subset of B.
</gallery>

==Power set==
The set of all subsets of <math>S</math> is called its [[power set]], and is denoted by <math>\mathcal{P}(S)</math>.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Subset|url=https://mathworld.wolfram.com/Subset.html|access-date=2020-08-23|website=mathworld.wolfram.com|language=en}}</ref>

The inclusion [[Binary relation|relation]] <math>\subseteq</math> is a [[partial order]] on the set <math>\mathcal{P}(S)</math> defined by <math>A \leq B \iff A \subseteq B</math>. We may also partially order <math>\mathcal{P}(S)</math> by reverse set inclusion by defining <math>A \leq B  \text{ if and only if }  B \subseteq A.</math>

For the power set <math>\operatorname{\mathcal{P}}(S)</math> of a set ''S'', the inclusion partial order is—up to an [[order isomorphism]]—the [[Cartesian product]] of <math>k = |S|</math> (the [[cardinality]] of ''S'') copies of the partial order on <math>\{0, 1\}</math> for which <math>0 < 1.</math> This can be illustrated by enumerating <math>S = \left\{ s_1, s_2, \ldots, s_k \right\},</math>, and associating with each subset <math>T \subseteq S</math> (i.e., each element of <math>2^S</math>) the ''k''-tuple from <math>\{0, 1\}^k,</math> of which the ''i''th coordinate is 1 if and only if <math>s_i</math> is a [[set membership|member]] of ''T''.

The set of all <math>k</math>-subsets of <math>A</math> is denoted by <math>\tbinom{A}{k}</math>, in analogue with the notation for [[binomial coefficients]], which count the number of <math>k</math>-subsets of an <math>n</math>-element set. In [[set theory]], the notation <math>[A]^k</math> is also common, especially when <math>k</math> is a [[transfinite number|transfinite]] [[cardinal number]].

== Other properties of inclusion ==
* A  set ''A'' is a '''subset''' of ''B'' [[if and only if]] their intersection is equal to A. Formally:
:<math> A \subseteq B \text{ if and only if } A \cap B = A. </math>
* A  set ''A'' is a '''subset''' of ''B'' if and only if their union is equal to B. Formally:
:<math> A \subseteq B \text{ if and only if } A \cup B = B. </math>
* A '''finite''' set ''A'' is a '''subset''' of ''B'', if and only if the [[cardinality]] of their intersection is equal to the cardinality of A. Formally:
:<math> A \subseteq B \text{ if and only if } |A \cap B| = |A|.</math>
* The subset relation defines a [[partial order]] on sets. In fact, the subsets of a given set form a [[Boolean algebra (structure)|Boolean algebra]] under the subset relation, in which the [[join and meet]] are given by [[Intersection (set theory)|intersection]] and [[Union (set theory)|union]], and the subset relation itself is the [[Inclusion (Boolean algebra)|Boolean inclusion relation]].
* Inclusion is the canonical [[partial order]], in the sense that every partially ordered set <math>(X, \preceq)</math> is [[isomorphic]] to some collection of sets ordered by inclusion. The [[ordinal number]]s are a simple example: if each ordinal ''n'' is identified with the set <math>[n]</math> of all ordinals less than or equal to ''n'', then <math>a \leq b</math> if and only if <math>[a] \subseteq [b].</math>

==See also==
*{{annotated link|Convex subset}}
*{{annotated link|Inclusion order}}
*{{annotated link|Mereology}}
*{{annotated link|Region (mathematics)|Region}}
*{{annotated link|Subset sum problem}}
*{{annotated link|Hierarchy#Subsumptive_containment_hierarchy|Subsumptive containment}}
*{{annotated link|Subspace (mathematics)|Subspace}}
*{{annotated link|Total subset}}

==References==
{{Reflist}}

== Bibliography ==
* {{cite book|author-link=Thomas Jech|author=Jech, Thomas|title=Set Theory|publisher=Springer-Verlag|year=2002|isbn=3-540-44085-2}}

==External links==
*{{Commons category-inline|Subsets}}
*{{MathWorld |title=Subset |id=Subset }}

{{Mathematical logic}}
{{Set theory}}
{{Common logical symbols}}

[[Category:Basic concepts in set theory]]