View source for Complement (set theory)

{{Short description|Set of the elements not in a given subset}}
{{multiple image
| align = right
| image1 = Venn01.svg
| width1 = 150
| alt1 = A circle filled with red inside a square. The area outside the circle is unfilled. The borders of both the circle and the square are black.
| caption1 = If {{mvar|A}} is the area colored red in this image…
| image2 = Venn10.svg
| width2 = 150
| alt2 = An unfilled circle inside a square. The area inside the square not covered by the circle is filled with red. The borders of both the circle and the square are black.
| caption2 = … then the complement of {{mvar|A}} is everything else.
}}

In [[Set theory|set theory]], the '''complement''' of a [[Set (mathematics)|set]] {{mvar|A}}, often denoted by <math>A^\complement</math> (or {{math|''A''′}}),<ref>{{Cite web|title=Complement and Set Difference|url=http://web.mnstate.edu/peil/MDEV102/U1/S6/Complement3.htm|access-date=2020-09-04|website=web.mnstate.edu}}</ref> is the set of [[Element (mathematics)|elements]] not in {{mvar|A}}.<ref name=":1">{{Cite web|title=Complement (set) Definition (Illustrated Mathematics Dictionary)|url=https://www.mathsisfun.com/definitions/complement-set-.html|access-date=2020-09-04|website=www.mathsisfun.com}}</ref>

When all elements in the universe, i.e. all elements under consideration, are considered to be [[Element (mathematics)|members]] of a given set {{mvar|U}}, the '''absolute complement''' of {{mvar|A}} is the set of elements in {{mvar|U}} that are not in {{mvar|A}}.

The '''relative complement''' of {{mvar|A}} with respect to a set {{mvar|B}}, also termed the '''set difference''' of {{mvar|B}} and {{mvar|A}}, written <math>B \setminus A,</math> is the set of elements in {{mvar|B}} that are not in {{mvar|A}}.

== Absolute complement ==
<!-- This section is linked from [[Bayes' theorem]] and absolute set complement -->
[[File:Venn10.svg|150px|thumb|The '''absolute complement''' of the white disc is the red region]]

=== Definition ===
If {{mvar|A}} is a set, then the '''absolute complement''' of {{mvar|A}} (or simply the '''complement of {{mvar|A}}''') is the set of elements not in {{mvar|A}} (within a larger set that is implicitly defined). In other words, let {{mvar|U}} be a set that contains all the elements under study; if there is no need to mention {{mvar|U}}, either because it has been previously specified, or it is obvious and unique, then the absolute complement of {{mvar|A}} is the relative complement of {{mvar|A}} in {{mvar|U}}:<ref>The set in which the complement is considered is thus implicitly mentioned in an absolute complement, and explicitly mentioned in a relative complement.</ref>
<math display=block>A^\complement = U \setminus A = \{ x \in U : x \notin A \}.</math>

The absolute complement of {{mvar|A}} is usually denoted by <math>A^\complement</math>. Other notations include <math>\overline A, A',</math><ref name=":1" /> <math>\complement_U A, \text{ and } \complement A.</math><ref name="Bou">{{harvnb|Bourbaki|1970|p=E II.6}}.</ref>

=== Examples ===
* Assume that the universe is the set of [[Integer|integer]]s. If {{mvar|A}} is the set of odd numbers, then the complement of {{mvar|A}} is the set of even numbers. If {{mvar|B}} is the set of [[Multiple (mathematics)|multiples]] of 3, then the complement of {{mvar|B}} is the set of numbers [[Modular arithmetic|congruent]] to 1 or 2 modulo 3 (or, in simpler terms, the integers that are not multiples of 3).
* Assume that the universe is the standard 52-card deck. If the set {{mvar|A}} is the suit of spades, then the complement of {{mvar|A}} is the [[Union (set theory)|union]] of the suits of clubs, diamonds, and hearts. If the set {{mvar|B}} is the union of the suits of clubs and diamonds, then the complement of {{mvar|B}} is the union of the suits of hearts and spades.
*When the universe is the [[Universe (mathematics)|universe of sets]] described in formalized [[Set theory|set theory]], the absolute complement of a set is generally not itself a set, but rather a proper class.  For more info, see [[Universal set|universal set]].

=== Properties ===
Let {{mvar|A}} and {{mvar|B}} be two sets in a universe {{mvar|U}}. The following identities capture important properties of absolute complements:

[[De Morgan's laws]]:<ref name="Halmos-1960" />
* <math>\left(A \cup B \right)^\complement = A^\complement \cap B^\complement.</math>
* <math>\left(A \cap B \right)^\complement = A^\complement \cup B^\complement.</math>

Complement laws:<ref name="Halmos-1960" />
* <math>A \cup A^\complement = U.</math>
* <math>A \cap A^\complement = \empty .</math>
* <math>\empty^\complement = U.</math>
* <math> U^\complement = \empty.</math>
* <math>\text{If }A\subseteq B\text{, then }B^\complement \subseteq A^\complement.</math>
*: (this follows from the equivalence of a conditional with its contrapositive).

[[Involution (mathematics)|Involution]] or double complement law:
* <math>\left(A^\complement\right)^\complement = A.</math>

Relationships between relative and absolute complements:
* <math>A \setminus B = A \cap B^\complement.</math>
* <math>(A \setminus B)^\complement = A^\complement \cup B = A^\complement \cup (B \cap A).</math>

Relationship with a set difference:
* <math> A^\complement \setminus B^\complement = B \setminus A. </math>

The first two complement laws above show that if {{math|''A''}} is a non-empty, proper subset of {{math|''U''}}, then {{math|{''A'', ''A''<sup>∁</sup>}{{null}}}} is a [[Partition of a set|partition]] of {{math|''U''}}.

== Relative complement ==
<!-- Many links redirect to this section: difference (set theory), difference of two sets, relative complement, set-theoretic difference, set difference, set minus, set subtraction, set theoretic difference, setminus -->
=== Definition ===
If {{math|''A''}} and {{math|''B''}} are sets, then the '''relative complement''' of {{math|''A''}} in {{math|''B''}},<ref name="Halmos-1960">{{harvnb|Halmos|1960|p=17}}.</ref> also termed the '''set difference''' of {{math|''B''}} and {{math|''A''}},<ref>{{harvnb|Devlin|1979|p=6}}.</ref> is the set of elements in {{math|''B''}} but not in {{math|''A''}}.
[[File:Relative compliment.svg|thumb|230x230px|The '''relative complement''' of {{math|''A''}} in {{math|''B''}}: <math>B \cap A^\complement = B \setminus A</math>]]
The relative complement of {{math|''A''}} in {{math|''B''}} is denoted <math>B \setminus A</math> according to the [[ISO 31-11#Sets|ISO 31-11 standard]]. It is sometimes written <math>B - A,</math> but this notation is ambiguous, as in some contexts (for example, [[Minkowski addition|Minkowski set operations]] in [[Functional analysis|functional analysis]]) it can be interpreted as the set of all elements <math>b - a,</math> where {{math|''b''}} is taken from {{math|''B''}} and {{math|''a''}} from {{math|''A''}}.

Formally:
<math display=block>B \setminus A = \{ x\in B : x \notin A \}.</math>

=== Examples ===
* <math>\{ 1, 2, 3\} \setminus \{ 2,3,4\} = \{ 1 \}.</math>
* <math>\{ 2, 3, 4 \} \setminus \{ 1,2,3 \} = \{ 4 \} .</math>
* If <math>\mathbb{R}</math> is the set of [[Real number|real number]]s and <math>\mathbb{Q}</math> is the set of [[Rational number|rational number]]s, then <math>\mathbb{R}\setminus\mathbb{Q}</math> is the set of [[Irrational number|irrational number]]s.

=== Properties ===

Let {{math|''A''}}, {{math|''B''}}, and {{math|''C''}} be three sets. The following [[Identity (mathematics)|identities]] capture notable properties of relative complements:

:* <math>C \setminus (A \cap B) = (C \setminus A) \cup (C \setminus B).</math>
:* <math>C \setminus (A \cup B) = (C \setminus A) \cap (C \setminus B).</math>
:* <math>C \setminus (B \setminus A) = (C \cap A) \cup (C \setminus B),</math>
:*:with the important special case <math>C \setminus (C \setminus A) = (C \cap A)</math> demonstrating that intersection can be expressed using only the relative complement operation.
:* <math>(B \setminus A) \cap C = (B \cap C) \setminus A = B \cap (C \setminus A).</math>
:* <math>(B \setminus A) \cup C = (B \cup C) \setminus (A \setminus C).</math>
:* <math>A \setminus A = \emptyset.</math>
:* <math>\empty \setminus A = \empty.</math>
:* <math>A \setminus \empty = A.</math>
:* <math>A \setminus U = \empty.</math>
:* If <math>A\subset B</math>, then <math>C\setminus A\supset C\setminus B</math>.
:* <math>A \supseteq B \setminus C</math> is equivalent to <math>C \supseteq B \setminus A</math>.

== Complementary relation ==
A [[Binary relation|binary relation]] <math>R</math> is defined as a subset of a product of sets <math>X \times Y.</math> The '''complementary relation''' <math>\bar{R}</math> is the set complement of <math>R</math> in <math>X \times Y.</math> The complement of relation <math>R</math> can be written
<math display=block>\bar{R} \ = \ (X \times Y) \setminus R.</math>
Here, <math>R</math> is often viewed as a [[Logical matrix|logical matrix]] with rows representing the elements of <math>X,</math> and columns elements of <math>Y.</math> The truth of <math>aRb</math> corresponds to 1 in row <math>a,</math> column <math>b.</math> Producing the complementary relation to <math>R</math> then corresponds to switching all 1s to 0s, and 0s to 1s for the logical matrix of the complement.

Together with [[Composition of relations|composition of relations]] and [[Converse relation|converse relation]]s, complementary relations and the [[Algebra of sets|algebra of sets]] are the elementary [[Operation (mathematics)|operation]]s of the calculus of relations.

== LaTeX notation ==

In the [[Software:LaTeX|LaTeX]] typesetting language, the command <code>\setminus</code><ref name="The Comprehensive LaTeX Symbol List">[http://ctan.unsw.edu.au/info/symbols/comprehensive/symbols-a4.pdf] {{Webarchive|url=https://web.archive.org/web/20220305100117/http://ctan.unsw.edu.au/info/symbols/comprehensive/symbols-a4.pdf |date=2022-03-05 }} The Comprehensive LaTeX Symbol List</ref> is usually used for rendering a set difference symbol, which is similar to a backslash symbol. When rendered, the <code>\setminus</code> command looks identical to <code>\backslash</code>, except that it has a little more space in front and behind the slash, akin to the LaTeX sequence <code>\mathbin{\backslash}</code>. A variant <code>\smallsetminus</code> is available in the amssymb package, but this symbol is not included separately in Unicode. The symbol <math>\complement</math> (as opposed to <math>C</math>) is produced by <code>\complement</code>. (It corresponds to the Unicode symbol {{unichar|2201|COMPLEMENT}}.)

== See also ==

* {{annotated link|Algebra of sets}}
* {{annotated link|Intersection (set theory)}}
* {{annotated link|List of set identities and relations}}
* {{annotated link|Naive set theory}}
* {{annotated link|Symmetric difference}}
* {{annotated link|Union (set theory)}}

== Notes ==

{{reflist}}
{{reflist|group=note}}

== References ==

* {{cite book 
 | last = Bourbaki
 | first = N.
 | title = Théorie des ensembles
 | publisher = Hermann
 | place = Paris
 | year = 1970
 | isbn = 978-3-540-34034-8
 | language = fr
}}
* {{cite book
 | last = Devlin
 | first = Keith J.
 | title = Fundamentals of contemporary set theory
 | series = Universitext
 | publisher = [[Physics:Springer-Verlag|Springer]]
 | year = 1979
 | isbn = 0-387-90441-7
 | zbl = 0407.04003
}}
* {{cite book
 | last = Halmos
 | first = Paul R.
 | title = Naive set theory
 | url = https://archive.org/details/naivesettheory0000halm
 | url-access = registration
 | series = The University Series in Undergraduate Mathematics
 | publisher = van Nostrand Company
 | year = 1960
 | isbn = 9780442030643
 | zbl = 0087.04403
}}

==External links==
* {{MathWorld |title=Complement |id=Complement }}
* {{MathWorld |title=Complement Set |id=ComplementSet }}

{{Mathematical logic}}

{{DEFAULTSORT:Complement (set theory)}}

[[Category:Basic concepts in set theory]]

{{Sourceattribution|Complement (set theory)}}