Sets

Introduction

1.A set is a collection of objects called elements and is determined entirely by which objects belong to it. Two sets are equal precisely when they have the same elements. The order used to list the elements and any repetitions in the list do not change the set. For example, the following three descriptions define the same set:

$$ \{1,2,3\}=\{3,1,2\}=\{1,1,2,3,3\} $$

2.A set with exactly one element is a singleton. Thus $\{a\}$ is a singleton, while $\{a,b\}$ has two elements when $a\neq b.$ Sets are usually represented by uppercase letters $A,$ $B,$ $C,$ and their elements by lowercase letters. The notation $x\in A$ indicates that $x$ belongs to $A,$ while $x\notin A$ indicates that $x$ does not belong to $A.$ Membership must have an unambiguous truth value for every object under consideration.

3.A set can be described by enumeration or by set-builder notation. Enumeration consists in explicitly listing each element of the set, and is practical when the cardinality of the set is finite and small:

$$ A = \{a_1, a_2, a_3, a_4\} $$

4.When the elements are numerous or infinite, set-builder notation is usually shorter. It selects from a previously specified set the elements that satisfy a given condition. For example, we define a subset of the integers by writing:

$$ A = \{\ x \in \mathbb{Z} \mid x > 4, \ x \leq 8 \ \} $$

5.The ambient set $\mathbb{Z}$ limits the candidates for membership. The two inequalities then select the following four integers:

$$ A = \{5, 6, 7, 8\} $$

6.

In naive set theory, an arbitrary condition does not necessarily define a set. An expression of the form $\{\ x\in S\mid P(x)\ \}$ extracts elements from a set $S$ that is already available. Without such an ambient set, a condition may describe a collection that cannot be a set. Russell's paradox arises from an unrestricted definition of this kind.

7.The empty set contains no elements, is denoted by $\emptyset$ or $\{\ \},$ and plays a role in set theory analogous to that of zero in arithmetic.

The universal set

8.A main collection containing all objects under consideration is called the universal set and is written as $U.$ All sets in a given context are subsets of $U.$ The choice of $U$ depends on the situation. In elementary number theory one often works with $U = \mathbb{Z},$ whereas in real analysis the usual choice is $U = \mathbb{R}.$

9.

The universal set is the tool that makes the notion of set complement unambiguous, as discussed in the section on set operations.

Cardinality of finite sets

10.The cardinality of a finite set $A,$ denoted $|A|,$ is the number of elements in $A.$ Cardinality can also be compared through functions. Two sets $A$ and $B$ have the same cardinality when a bijection from $A$ to $B$ exists. This condition is written as follows:

$$ |A|=|B| \iff \text{there is a bijection } f\colon A\to B $$

11.For finite sets this condition is equivalent to equality between their numbers of elements. The empty set has cardinality $|\emptyset|=0.$

12.For infinite sets, bijections define equality of cardinality even when neither set has a finite number of elements. Cardinality and countable sets extends this definition to infinite sets and includes the comparison with power sets.

13.The cardinality of the Cartesian product of two finite sets $A$ and $B$ is given by:

$$ |A \times B| = |A| \cdot |B| $$

14.In this case each element of $A$ can be paired with every element of $B,$ producing $|A| \cdot |B|$ ordered pairs.

15.The cardinality of the union of two sets $A$ and $B$ is given by:

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

16.The previous expression is the inclusion-exclusion principle, which ensures that elements common to both sets are counted once. Every element of $A \cup B$ appears in the sum $|A| + |B|.$ Elements lying in $A \cap B$ are counted twice, so the term is subtracted to guarantee the correct count.

17.The principle extends to three sets, as expressed by:

$$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| $$

18.The structure of the formula can be read as follows:

Subsets and power sets

20.The notions of subset and power set are introduced together. Subsets are sets whose elements all belong to another set, while power sets are sets whose elements are themselves subsets of a given set. A set $A$ is a subset of $B$ if every element of $A$ is also an element of $B$:

$$ A \subseteq B \iff \forall \ x, \ x \in A \rightarrow x \in B $$

21.Two sets are equal if and only if each is contained in the other, which is the standard way to establish set equality in mathematics:

$$ A = B \iff A \subseteq B \text{ and } B \subseteq A $$

22.If $A \subseteq B$ and $A \neq B,$ then $A$ is a proper subset of $B,$ denoted $A \subsetneq B,$ and in this case there exists at least one element in $B$ that does not belong to $A.$ The empty set is a subset of every set. The inclusion $\emptyset \subseteq A$ holds for any set $A,$ because the implication $x \in \emptyset \Rightarrow x \in A$ is vacuously true.

23.The power set of a set $A$ is the set of all subsets of $A,$ denoted $\mathcal{P}(A).$ It includes the empty set $\emptyset$ and the set $A$ itself. If $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements. For example, if $A=\{a,b,c\},$ then the power set contains $2^3=8$ elements:

$$ \mathcal{P}(A) = \{\emptyset, \ \{a\}, \ \{b\}, \ \{c\}, \ \{a,b\}, \ \{a,c\}, \ \{b,c\}, \ \{a,b,c\}\} $$

24.The exponent $2^n$ comes from a correspondence with functions. Every subset $E\subseteq A$ has a characteristic function $\chi_E\colon A\to\{0,1\}$ defined by:

$$ \chi_E(a)= \begin{cases} 1 & \text{if } a\in E \\[6pt] 0 & \text{if } a\notin E \end{cases} $$

25.Conversely, a function $\chi\colon A\to\{0,1\}$ determines the subset $\{\ a\in A\mid \chi(a)=1\ \}.$ These two constructions are inverse to each other. When $A$ has $n$ elements, the value of $\chi$ has two independent possibilities at each element of $A,$ so there are $2^n$ characteristic functions and therefore $2^n$ subsets.

Indexed families of sets

26.When several sets are considered together, labeling them by an index keeps the notation compact. A family of sets indexed by a set $I$ assigns a set $A_i$ to each index $i\in I$ and is written $(A_i)_{i\in I}.$ Formally, the family is a function whose domain is $I$ and whose value at $i$ is $A_i.$ The indices remain distinct even when two values coincide, so $A_i=A_j$ does not imply $i=j.$ The index set can be finite, countable, or uncountable.

27.The union of the family is the set of elements that belong to at least one of its members, and the intersection is the set of elements that belong to every member:

$$ \bigcup_{i\in I} A_i = \{\ x \mid x\in A_i \text{ for some } i\in I \ \} $$

$$ \bigcap_{i\in I} A_i = \{\ x \mid x\in A_i \text{ for every } i\in I \ \} $$

28.An element belongs to the union as soon as one member of the family contains it, and belongs to the intersection only when every member contains it.

29.A family $(A_i)_{i\in I}$ is pairwise disjoint when any two members with distinct indices share no elements:

$$ A_i \cap A_j = \emptyset \quad \forall \ i \neq j $$

30.For each $n\in\mathbb{N}$ the singletons $\{n\}$ form a pairwise disjoint family, and their union is the set $\mathbb{N}.$

Partitions

31.A partition of a set $A$ is a family of non-empty subsets $(A_i)_{i\in I}$ that are pairwise disjoint and cover the whole of $A.$ The following conditions must hold:

$$ \begin{align} &A_i \neq \emptyset \quad \forall \ i \in I \\[6pt] &A_i \cap A_j = \emptyset \quad \forall \ i \neq j \\[6pt] & \bigcup_{i \in I} A_i = A \end{align} $$

32.The subsets $A_i$ are called the blocks of the partition, and each element of $A$ belongs to exactly one of them. A simple example is the set of integers $\mathbb{Z},$ which can be partitioned into the set of even integers and the set of odd integers, since these two blocks are non-empty, disjoint, and together cover the whole of $\mathbb{Z}.$

33.Partitions are related to equivalence relations. Given an equivalence relation on $A$:

Set operations

35.Set operations generate new sets by combining the elements of different sets. The main operations are union, intersection, complement, and difference.

36.The union of $A$ and $B$ is the set of all elements that belong to at least one of the two sets. Elements common to $A$ and $B$ are listed only once, since sets do not allow repetitions.

$$ A \cup B = \{x \mid x \in A \text{ or } x \in B\} $$

37.The intersection of $A$ and $B$ is the set of elements that belong to both sets:

$$ A \cap B = \{x \mid x \in A \text{ and } x \in B\} $$

38.If $A \cap B = \emptyset,$ the two sets are disjoint and share no elements.

39.The complement of $A$ with respect to a universal set $U$ is the set of all elements in $U$ that do not belong to $A.$ It is written as:

$$ A^c = \{x \in U \mid x \notin A\} $$

40.Another way to represent the complement of $A$ is $\overline{A}$ or $U \setminus A.$ A single set may yield different complements when $U$ changes, since the elements of the complement vary with the universal set we pick.

41.The difference of $A$ and $B,$ written $A \setminus B,$ is the set of elements that belong to $A$ but not to $B$:

$$ A \setminus B = \{x \mid x \in A \text{ and } x \notin B\} $$

42.The relation $A \setminus B \neq B \setminus A$ holds in general, since the difference of two sets is not a commutative operation. For any universal set that contains both $A$ and $B$ the identity $A \setminus B = A \cap B^c$ holds, which expresses the difference through the complement.

43.The symmetric difference of $A$ and $B,$ written $A \triangle B,$ is the set of elements that belong to one of the two sets but not to both:

$$ A \triangle B = (A \setminus B) \cup (B \setminus A) $$

44.An equivalent representation is given by the following expression:

$$ A \triangle B = (A \cup B) \setminus (A \cap B) $$

45.The symmetric difference is commutative and associative, and satisfies $A \triangle A = \emptyset$ and $A \triangle \emptyset = A.$ Together with intersection, it gives the collection of all subsets of a given set the structure of a Boolean ring.

Properties of set operations

46.The set operations satisfy a series of identities that form the foundation of Boolean algebra and hold for any sets $A,$ $B,$ and $C$ within a universal set $U.$ Union and intersection are commutative operations. The order in which two sets are combined does not affect the result.

$$ \begin{align} A \cup B &= B \cup A \\[6pt] A \cap B &= B \cap A \end{align} $$

47.Both operations are also associative, meaning that when three sets are combined, the grouping of the operands is irrelevant.

$$ \begin{align} (A \cup B) \cup C &= A \cup (B \cup C) \\[6pt] (A \cap B) \cap C &= A \cap (B \cap C) \end{align} $$

48.Union and intersection distribute over each other, in a manner analogous to the distributive law of arithmetic.

$$ \begin{align} A \cap (B \cup C) &= (A \cap B) \cup (A \cap C) \\[6pt] A \cup (B \cap C) &= (A \cup B) \cap (A \cup C) \end{align} $$

49.The empty set and the universal set act as the identity element for union and intersection respectively. Combining any set with either of them returns the original set.

$$ \begin{align} A \cup \emptyset &= A \\[6pt] A \cap U &= A \end{align} $$

50.The empty set annihilates intersection and the universal set annihilates union. Combining any set with these elements returns the absorbing element rather than the original set:

$$ \begin{align} A \cap \emptyset &= \emptyset \\[6pt] A \cup U &= U \end{align} $$

51.Each element of $U$ lies either in $A$ or in its complement, never in both. Applying the complement operation a second time in succession returns the original set:

$$ \begin{align} A \cup A^c &= U \\[6pt] A \cap A^c &= \emptyset \\[6pt] (A^c)^c &= A \end{align} $$

Disjoint union

52.The ordinary union has only one occurrence of an element that belongs to both $A$ and $B.$ The disjoint union has two labeled versions of such an element, one for each source set. One construction is given by:

$$ A\sqcup B=(\{0\}\times A)\cup(\{1\}\times B) $$

53.The sets $\{0\}\times A$ and $\{1\}\times B$ are disjoint because their ordered pairs have different first components. The functions $i_A\colon A\to A\sqcup B$ and $i_B\colon B\to A\sqcup B$ defined by $i_A(a)=(0,a)$ and $i_B(b)=(1,b)$ are injective. Their images are disjoint and their union is $A\sqcup B.$ Thus every element of the disjoint union comes from exactly one of the two source sets.

54.If $A$ and $B$ are finite, the two tagged copies have $|A|$ and $|B|$ elements, respectively. Their disjointness gives the formula:

$$ |A\sqcup B|=|A|+|B| $$

55.When $A\cap B=\emptyset,$ removing the labels defines a bijection from $A\sqcup B$ to $A\cup B.$ If $A\cap B\neq\emptyset,$ the same rule is not injective. For an element $x\in A\cap B,$ the distinct elements $(0,x)$ and $(1,x)$ of $A\sqcup B$ would both map to $x.$

The ordered pair

56.The discussion so far has treated the ordered pair $(a, b)$ as an intuitive notion, namely a pair of objects in which the first component is $a$ and the second is $b.$ In formal terms, the ordered pair can be defined set-theoretically as a set containing two elements:

$$ (a, b) = \{\{a\}, \ \{a, b\}\} $$

57.The term $a$ is the singleton, and $\{a, b\}$ is the unordered pair. The element $a$ appears in both, whereas $b$ appears only in one. This definition is justified by the following result:

$$ (a, b) = (c, d) \implies a = c \text{ and } b = d $$

58.To verify this property, suppose $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}.$ There are two cases, depending on whether $a = b$ or $a \neq b.$

59.In the first case, when $a = b,$ we have $\{a, b\} = \{a\},$ so the left-hand side becomes $\{\{a\}\},$ a singleton set. For equality, the right-hand side must also be a singleton, which requires $\{c\} = \{c, d\}$ and so $c = d.$ The single element on each side must coincide, so $\{a\} = \{c\},$ and therefore $a = c.$ Since $b = a = c = d,$ it follows that $a = c$ and $b = d.$

60.If $a \neq b,$ then the left-hand side contains two distinct elements: $\{a\}$ and $\{a, b\}.$ The singleton $\{a\}$ must correspond either to $\{c\}$ or to $\{c, d\}$ on the right-hand side. If $\{a\} = \{c, d\},$ then $c = d = a,$ which would make $\{c\} = \{c, d\},$ resulting in a singleton on the right, contradicting the presence of two distinct elements on the left. Therefore $\{a\} = \{c\},$ so $a = c.$ It follows that $\{a, b\} = \{c, d\} = \{a, d\},$ and since $a \neq b,$ it must be that $b = d.$

61.In both cases, $a = c$ and $b = d,$ as required. The converse is straightforward, since if $a = c$ and $b = d$ then the two sets are identical by substitution.