Set Theory

Foundations

We begin by defining some basic terminology and fundamental axioms.

definition. A set is a collection of objects, called the elements or members of the set. Given a set ${S,}$ if ${x}$ is an element of ${S,}$ we write ${x \in S.}$ If ${x}$ is not an element of ${S,}$ we write ${x \notin S.}$

If we want to explicitly list the elements of a set, we use curly braces. For example, here is a set of two elements:

A set is called a finite set if it contains a finite number of elements. A set is called an infinite set if it contains an infinite number of elements.

definition. The number of distinct elements in a set ${S}$ is denoted ${n(S)}$ or ${\lvert S \rvert.}$ If ${S}$ is a finite set, we call ${n(S)}$ the cardinality or cardinal number of the set ${S.}$

The Empty Set

axiom. There is exactly one set with no elements, called the empty set or null set, denoted ${\varnothing.}$

Subsets

definition. Given sets ${A}$ and ${B,}$ if every element of ${B}$ is also an element of ${A,}$ then ${B}$ is a subset of ${A,}$ and we write ${B \subseteq A.}$

From the definition above, we can see that every set is a subset of itself. Given a set ${A,}$ every element of ${A}$ is also an element of ${A.}$ Moreover, ${\varnothing}$ is a subset of every set ${A,}$ since every element of ${\varnothing}$ (nothing) is also an element of ${A.}$ Given a set ${A,}$ we call the subsets ${A}$ and ${\varnothing}$ the trivial subsets of ${A.}$

definition. Let ${A}$ and ${B}$ be sets. If every element of ${B}$ is an element of ${A,}$ ${B \neq \varnothing,}$ and ${B \neq A,}$ then ${B}$ is a proper subset of ${A,}$ and we write ${B \subset A.}$

Equality of Sets

definition. Two sets are equal if and only if they contain the same elements.

example. Let ${A = \lbrace 1,2,3 \rbrace}$ and ${B = \lbrace 1,2,3 \rbrace.}$ The sets ${A}$ and ${B}$ contain the same elements, so ${A = B.}$

Now that we have subsets, we can provide an alternative definition of equality:

definition. Two sets ${A}$ and ${B}$ are equal if and only if ${B \subseteq A}$ and ${A \subseteq B.}$

From this definition, we see that two prove two sets are equal, we must prove that ${x \in A \implies x \in B,}$ and ${x \in B \implies x \in A.}$

Power Sets

Consider the set ${A = \lbrace p, q, r, \rbrace.}$ What are all the possible ways we can reach into this set and pull a handful of these elements? Remember that sets are unordered collections. So, what we're asking for, formally, is what are all the possible subsets of ${A}$? We have following possible results:

1. ${\varnothing}$ (we pull out nothing).
2. ${\lbrace p \rbrace}$
3. ${\lbrace q \rbrace}$
4. ${\lbrace r \rbrace}$
5. ${\lbrace p, q \rbrace}$
6. ${\lbrace p, r \rbrace}$
7. ${\lbrace q, r \rbrace}$
8. ${\lbrace p, q, r \rbrace}$

The set of all these results is called the power set of ${A.}$

definition. Let ${A}$ be a set. Then the set of all subsets of ${A}$ is called the power set of ${A,}$ denoted ${P(A).}$

In our previous example, we saw that there are eight subsets. We generalize this result with the following counting theorem:

theorem. Let ${A}$ be a set. If ${\lvert A \rvert = n,}$ then ${\lvert P(A) \rvert = 2^n.}$

Set Algebra

Set algebra refers to the definitions, theorems, and procedures for operations on sets.

Intersection

definition. Given sets ${A}$ and ${B,}$ the set of all elements common to both ${A}$ and ${B}$ is called the intersection of ${A}$ and ${B,}$ written ${A \cap B.}$ Symbolically:

$$A \cap B \coloneqq \lbrace x ~|~ x \in A \land x \in B \rbrace.$$

Below, the purple shaded region corresponds to the intersection of ${A}$ and ${B.}$

Union

definition. Given sets ${A}$ and ${B,}$ the set of all elements found in ${A}$ or ${B}$ (or both) is called the union of ${A}$ and ${B,}$ written ${A \cup B.}$ Symbolically:

$$A \cup B \coloneqq \lbrace x ~|~ x \in A \lor x \in B \rbrace.$$

Laws of Intersection & Union

Below are some basic laws of intersection and union.

• ${A \cap B \subseteq A \cup B}$
• If ${A \cup B = A \cap B,}$ then ${A = B.}$
• ${A \cup B = A}$ if and only if ${B \subseteq A.}$
• ${A \cap B = A}$ if and only if ${A \subseteq B.}$
• ${A \cap A = A}$ (Indempotent Law).
• ${A \cup A = A}$ (Indempotent Law).
• ${A \cap \varnothing = \varnothing.}$ (Identity Law).
• ${A \cup \varnothing = A.}$ (Identity Law).
• Let ${A \subset S.}$ Then ${A \cup S = S.}$
• Let ${A \subset S.}$ Then ${A \cap S = A.}$

Set Complement

definition. Suppose ${A \subset S.}$ The complement of ${A,}$ written ${A',}$ contains all elements of ${S}$ which are not in ${A.}$

Disjoint Sets

Suppose ${A}$ and ${B}$ are sets. If ${A \cap B = \varnothing,}$ then ${A}$ and ${B}$ are said to be disjoint. Put differently: Two sets ${A}$ and ${B}$ are disjoints if they have no elements in common. Now suppose that ${A \cup B = S.}$ If ${A \cap B = \varnothing,}$ we say that ${A}$ and ${B}$ partition ${S.}$

Special Number Sets

Some sets are so often used that they're reserved special symbols:

Ordered Pairs

definition. An ordered pair ${(a,b)}$ is defined as

$$(a,b) \coloneqq \lbrace \lbrace a \rbrace, \lbrace a, b \rbrace \rbrace.$$

axiom. ${(a,b) = (c,d)}$ if and only if ${a = c}$ and ${b = d.}$

Cartesian Product

definition. Given two sets ${A}$ and ${B,}$ the set which contains all the ordered pairs (a,b) such that ${a \in A}$ and ${b \in B}$ is called the Cartesian product of ${A}$ and ${B,}$ written ${A \times B.}$ I.e.,

$$A \times B = \lbrace (a,b) ~|~ a \in A, b \in B \rbrace.$$

Relations

definition. A relation is any set of ordered pairs.

From the definition above, given two sets ${A}$ and ${B,}$ any subset of ${A \times B}$ is a relation. If ${R}$ is a relation and ${(a,b) \in R}$ we may write ${a ~ R ~ b.}$ If ${R = A \times B,}$ we say that ${R}$ is a relation from ${A}$ to ${B.}$ We call ${A}$ the domain of ${R}$ and ${B}$ its range. Thus, the domain consists of all possible first components of the ordered pairs in ${R,}$ and the range consists of all possible second components. From the definition of subsets, we can conclude that if ${R}$ is a relation from ${A}$ to ${B,}$ then the domain of ${R}$ is a subset of ${A,}$ and the range of ${R}$ is a subset of ${B.}$

example. The set ${\lbrace (1,3), (2,4), (3,1), (3,4) \rbrace}$ is a relation in ${\natnums.}$

example. The set ${\lt}$ is a relation: ${\lbrace (0,1), (2,3), (\pi, 5.25), \ldots \rbrace.}$ Notice that: ${0 \lt 1,}$ ${2 \lt 3,}$ ${\pi \lt 5.25,}$ etc.

example. The set ${\lbrace y = x^2 ~|~ x,y \in \reals \rbrace}$ is a relation.

Types of Relations

Relations come in various types. We examine these types in the next sections.

Reflexive Relations

definition. A relation ${R}$ in a set ${S}$ is reflexive if, for all ${x \in S,}$ ${x ~R~ x.}$

In other words, if we know that an element ${x}$ exists in a set ${S,}$ and ${R}$ is a reflexive relation on ${S,}$ then ${R}$ definitely has a pair ${(x,x).}$

Symmetric Relations

In a symmetric relation ${R,}$ if we know that a pair ${(a,b)}$ exists in ${R,}$ then the pair ${(b,a)}$ also exists in ${R.}$

definition. A relation ${R}$ in a set ${S}$ is symmetric if, for all ${a,b \in S,}$ ${a ~ R ~ b \implies b ~ R ~ A.}$

From this definition, we see that ${R}$ is not symmetric if it contains a pair ${(a,b)}$ but does not contain a pair ${(b,a).}$ If ${R}$ is not symmetric, we say that ${R}$ is nonsymmetric. The term antisymmetric is a special case of non-symmetric relations, as we'll see shortly.

Antisymmetric Relations

definition. A relation ${R}$ in a set ${S}$ is antisymmetric if, for all ${(x,y) \in R}$ and ${x \neq y,}$ ${(y,x) \notin R.}$ That is, if ${x \neq y}$ and ${x ~ R ~ y,}$ then ${y ~\cancel{R}~ x.}$

Transitive Relations

definition. A relation ${R}$ in a set ${S}$ is transitive if, for all ${a,b,c \in S:}$ If ${a ~ R ~ b}$ and ${b ~ R ~ c,}$ then ${a ~ R ~ c.}$

Functions