An Introduction to Set Theory

Part Of: Algebra sequence
Content Summary: 1800 words, 18 min read

Fundamentals of Sets

Definition 1. A set is a collection of distinct objects.

A few examples to kick us off:

$MyFavoriteFruits = \left\{ apples, persimmon, pineapple \right\}$ represents the set of fruits which I prefer.
$A = \left\{ 1, 2, 3, 4, 5 \right\}$ can represent, among other things, the fingers on my left hand.
The set of natural numbers $\mathbb{N} = \left\{ 0, 1, 2, 3, 4, ... \right\}$ .
The set of integers $\mathbb{Z} = \left\{ ..., -2, -1, 0, 1, 2, ... \right\}$ .

Sets are subject to the following properties:

Order blindness: $\left\{2, 1, 3\right\}$ and $\left\{1, 2, 3\right\}$ expresses the very same set.
Duplicate blindness. $\left\{ 1, 1, 2, 3, 3 \right\} = \left\{1, 2, 3 \right\}$ . We will prefer to express sets with the latter, more compact, notation.
Recursion. $\left\{ 1, \left\{2, 3\right\} \right\}$ is a perfectly valid two-element set, quite distinct from the three-element set $\left\{ 1, 2, 3 \right\}$ .

Definition 2. Two sets A and B are said to be equal ( $A = B$ ) if A and B contain exactly the same elements.

Let $A = \left\{ 1, 2, 3 \right\}$ and $B = \left\{ 3, 1, 2 \right\}$ . Then, $A = B$ .
Let $A = \left\{ 1, 2, 3 \right\}$ and $B = \left\{ 1, \left\{2, 3\right\} \right\}$ . Then, $A \neq B$ .

Definition 3. If an object x is an element of (i.e., member of) set S, we write $x \in S$ . Otherwise, we write $x \notin S$ .

Let $PrimaryColors = \left\{ red, yellow, blue \right\}$ . Then $yellow \in PrimaryColors$ means “yellow is an element of the set of primary colors”.
$-1 \notin \mathbb{N}$ means “-1 is not an element of the natural numbers”.
$1 \notin B = \left\{ 0, \left\{ 1 \right\}, \left\{ \left\{ 2 \right\} \right\} \right\}$ . The element $1$ is not in $B$ : only the set $\left\{ 1 \right\}$ is.

Definition 4. For some set $X$ , its cardinality (i.e., size) $|X|$ , is the number of elements in that set.

Let $A = \left\{ 1, 2, 3, 4, 5 \right\}$ . Then $|A| = 5$ .
Let $B = \left\{ 1, \left\{2, 3 \right\} \right\}$ . Then $|B| = 2$ . Note that cardinality only looks at “the outer layer”.

Definition 5. The empty set (i.e., the null set) $\varnothing$ is the set containing no elements.

$\varnothing = \left\{ \right\}$ .
$| \varnothing | = 0$ .
$| \left\{ \varnothing \right\} | = 1$ .

Definition 6. Instead of listing all elements, set builder notation specifies rules or properties that govern the construction of a set. The notation takes the following form: ${ x | \normalfont{property of} x }$ , where the | symbol is pronounced “such that”.

$A = \left\{ 1, 2, 3, 4, 5 \right\} = \left\{ x \in \mathbb{Z} | x > 0, x < 6 \right\}$ . In words “let A be the set of integers X such that x is greater than zero and less than six.”
The set of rational numbers $\mathbb{Q} = \left\{ x / y \mid x \in \mathbb{Z}, y \in \mathbb{Z}, y \neq 0 \right\}$ .

Sets defined by their properties are often called set comprehension. Such properties or rules are called the intension, the resultant set is called the extension.

Let $A = \left\{ y | x \in \mathbb{R}, y = (x+1)(x-1) \right\}$ and let $B = \left\{ y | x \in \mathbb{R}, y = x^{2} -1 \right\}$ . Here $A = B$ , despite their use of different rules. We say that $A$ and $B$ have the same extension, but different intensions.

The intension-extension tradeoff denotes an inverse relationship between the number of intensional rules versus the size of the set those rules pick out. Let’s consider two examples to motivate this tradeoff.

Consider hierarchical addressing in computer architecture. Suppose we have $2^{6} = 64$ bits of computer memory, each bit of which is uniquely identified with a 6-bit address. Suppose further that our memory has been allocated to data structures of varying size. To promote addressing efficiency, a computer can adopt the following strategy: assign shorter addresses to larger variables.

Naive Set Theory- Hierarchical Addressing

We can also see the intension vs. extension tradeoff in the memory systems of the brain. Specifically, semantic memory is organized into a concept hierarchy. We might classify a Valentine’s day gift according to the following tree:

Naive Set Theory- Concept Hierarchy

The number of objects classified as a RED_ROSE is clearly less than the number of objects classified as LIVING_THING. But as our extensional size decreases, the size of our intension (the number of properties needed to classify a RED_ROSE) increases.

Subsets and Power set

Definition 7. A set $A$ is a subset of another set $B$ , written $A \subseteq B$ , if every element of $A$ is also an element of $B$ .

Let $A = \left\{ 2, 3, 9 \right\}$ and $B = \left\{1,9,3,6, 2\right\}$ . Then $A \subseteq B$ (recall that element order is irrelevant).
Let $A = \left\{ 2, 3, 9 \right\}$ and $C = \left\{1,7, 3, 6, 2 \right\}$ . Then $A \nsubseteq C$ (C does not contain 9).
Is $\varnothing$ a subset of $\left\{2,3,9\right\}$ ? Yes. For all $A$ , $\varnothing \subseteq A$ is true.

Definition 8. A set $A$ is a proper subset of another set $B$ , written $A \subset B$ , if $A \subseteq B$ and $A \neq B$ .

Definition 9. For a given set $A$ , its power set $\mathbb{P} (A)$ is the set of all subsets of $A$ .

Let $A = \left\{ 0, 1 \right\}$ . Then $\mathbb{P}(A) = \left\{ \varnothing , \left\{ 0 \right\} , \left\{ 1 \right\}, \left\{ 0, 1 \right\} \right\}$ .

A power set can be constructed by the use of a binary tree, as follows:

Naive Set Theory- Building Powersets (1)

As can be seen above, the total number of subsets must be a power of two. Specifically, if $|A| = n$ , then $|\mathbb{P}(A)| = 2^n$ .

It is important to get clear on the differences between the element-of ( $\in$ ) versus subset-of ( $\subseteq$ ) relations. Consider again $A = \left\{ 0, 1 \right\}$ and its power set $\mathbb{P}(A) = \left\{ \varnothing , \left\{ 0 \right\} , \left\{ 1 \right\}, \left\{ 0, 1 \right\} \right\}$

$A \in \mathbb{P}(A)$ . But $\left\{A\right\} \not\in \mathbb{P}(A)$ . The $\in$ relation requires the brackets match.
$\left\{A\right\} \subseteq \mathbb{P}(A)$ . But $A \nsubseteq \mathbb{P}(A)$ . The $\subseteq$ relation requires the “extra bracket”.

Probability theory is intimately connected with the notion of power set. Why? Because many discrete probability distributions have $\sigma$ -algebras draw from the power set of natural numbers $\mathbb{P} ( \mathbb{N} )$ .

Cartesian Product, Tuples

Definition 10. Given two sets $A$ and $B$ , their Cartesian product $A \times B$ is the set of all ordered pairs $\langle a, b \rangle$ such that $a \in A$ and $b \in B$ . Note that, unlike the elements in a set, the elements of an ordered pair cannot be reordered.

Let $A = \left\{1, 2, 3 \right\}$ and $B = \left\{4, 5, 6\right\}$ . Then $A \times B = \left\{ (1, 4) , (1, 5), (1,6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6) \right\}$ .

We can represent this same example visually, as follows:

Naive Set Theory- Cartesian Product (1)

Contrast this with $B \times A = \left\{ (3, 1) , (4, 1), (2, 4), (1, 3) \right\}$ . Thus, $A \times B \neq B \times A$ . This is because elements within ordered pairs cannot be rearranged.
Note that $|A \times B| = 9 = |A_{1}| \times |A_{2}|$ . In combinatorics, this observation generalizes to the multiplication principle.
The real plane $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ is a well-known example of a Cartesian product.

Definition 11. Given n sets, $A_{1}, A_{2}, \ldots , A_{n}$ , their Cartesian product is the set of all n-tuples.

Let $A = \left\{1, 2\right\}$ , $B = \left\{a, b\right\}$ and $C = \left\{ 100 \right\}$ . Now $A \times B \times C = \left\{ (1, a, 100) , (1, b, 100), (2, a, 100), (2, b, 100) \right\}$ .

Linear algebra is intimately connected with the Cartesian product operation. Why? Because n-tuples are strongly related to n-dimensional vectors.

Intersection and Union

Definition 12. The intersection of two set $A$ and $B$ , written $A \cap B$ , is the set of elements common to both sets.

Let $A = \left\{ 2, 4, 9 \right\}$ and $B = \left\{1, 2, 3, 6, 9 \right\}$ . Then $A \cap B = \left\{ 2, 9 \right\}$ .
Let $A = \left\{ 2, 4, 9 \right\}$ and $B = \left\{1, 3, 6, 8, 10\right\}$ . Then $A \cap B = \varnothing$ .
Let $A = \left\{ 2, 4, 9 \right\}$ . Then $\varnothing \cap A = A \cap \varnothing = \varnothing$ .

Definition 13. The union of two sets $A$ and $B$ , written $A \cup B$ is the set of all elements that are in $A$ or $B$ , or both.

Let $A = \left\{ 2, 4, 9 \right\}$ and $B = \left\{1, 2, 3, 6, 9 \right\}$ . Then $A \cup B = \left\{ 1, 2, 3, 4, 6, 9 \right\}$ .
Let $A = \left\{ 2, 4, 9 \right\}$ . Then $\varnothing \cup A = A \cup \varnothing = A$ .

Venn diagrams represent sets as enclosed areas in a 2D plane. If two (or more!) sets have shared elements, their areas overlap. We can use this technique to visualize sets and their overlap:

Naive Set Theory- Elements vs Venn Diagram

We can also use Venn diagrams to represent our intersection and union relations:

Naive Set Theory- Union vs Intersection Venn (1)

Note that $|A \cup B| = |A| + |B| - |A \cap B|$ . This makes sense in light of the Venn diagram. Adding the cardinality of both sets counts the elements that exist in the middle section twice. To avoid this, we subtract the cardinality of the intersection. In combinatorics, this formula is generalized by the inclusion-exclusion principle.

Difference and Complement

Definition 14. Given two sets $A$ and $B$ , their difference $A \setminus B$ is the set of elements in $A$ but not also in $B$ .

Let $A = \left\{ 1, 2, 3, 4, 5, 6 \right\}$ and $B = \left\{0, 2, 4, 6, 8 \right\}$ . Then $A \setminus B = \left\{ 1, 3, 5 \right\}$ and $B \setminus A = \left\{ 0, 8 \right\}$ .
Let $A = \left\{ 1, 2, 3, 4, 5, 6 \right\}$ and $B = \left\{7, 8, 9, 10 \right\}$ . Then $A \setminus B = A$ and $B \setminus A = B$ .

Definition 15. Given two sets $A$ and $B$ , the symmetric difference $A \triangle B$ is the set of elements in $A$ or $B$ , but not both.

Let $A = \left\{ 1, 2, 3, 4, 5, 6 \right\}$ and $B = \left\{0, 2, 4, 6, 8 \right\}$ . Then $A \triangle B = \left\{ 0, 1, 3, 5, 8 \right\}$ .

Definition 16. In many set problems, all sets are defined as subsets of some reference set. This reference set is called the universe $U$ .

Let $A = \left\{ 1+i, 12-8j, 3+0i \right\}$ and let its universe be the set of complex numbers $\mathbb{C}$ . It is true that $A \subseteq \mathbb{C}$ .

Definition 17. Relative to a universe $U$ , the complement of $A$ , written $\overline{A}$ is the set of all elements of $U$ not contained in $A$ .

Let U be the set of positive integers less than 10: $U = \left\{ x | x \in \mathbb{Z}^{+}, x < 10 \right\}$ and $A = \left\{ 1, 2, 3, 4, 5 \right\}$ . Then $\overline{A} = \left\{ 6, 7, 8, 9 \right\}$ .

We can again represent these relations graphically, via Venn diagrams:

Naive Set Theory- Complement and Difference Venn (2)

Takeaways

Let me summarize this post in terms of our 17 definitions 🙂

Def 1-5 introduced the notion of set, set equality, the element-of operator, cardinality (set size), and empty set.
Def 6 introduced set builder notation, and the intension-extension tradeoff.
Def 7-9 introduced subset, proper subset, and power set.
Def 10-11 introduced Cartesian product, ordered pairs, and n-tuples.
Def 12-13 introduced intersection (“and”) and union (“or”), as well as Venn diagrams.
Def 14-17 introduced difference, symmetric difference (“xor”), and complement (“not”).

Want to learn more? I recommend the following resources:

Articles: A Little Set Theory (Never Hurt Anybody), Sets, Functions, Relations
Videos: The Trev Tutor, Discrete Math 1 series

This introductory article focused on promoting intuitions through worked examples. Next time, we’ll look at these same operations more carefully, and examine the relationship between set theory and classical predicate logic.

2 thoughts on “An Introduction to Set Theory”

Travis R says:

October 21, 2017 at 7:42 pm

Kevin,
Nice summary. Heads up on a few typos:
1) Definition 6, bullet 3 – did you mean to swap the + and -?
2) Definition 7 – sets B and C should include a 4.
3) Definition 10, bullets 1 and 2 – something went awry, but not sure what.

LikeLiked by 1 person

kevinbinz says:

October 22, 2017 at 6:13 pm

Hey Travis,

Appreciate the detailed feedback! All typos have been fixed, I think.

Also, in November, me and another reader are embarking on the textbook “Conceptual Mathematics: A First Introduction to Categories”. https://www.quora.com/What-is-the-best-textbook-for-Category-theory/ If you’re interested in joining, please shoot me an email! 🙂

LikeLike

Fewer Lacunae

Distilled, Integrative Research

An Introduction to Set Theory

2 thoughts on “An Introduction to Set Theory”

Leave a comment Cancel reply

Share this:

Related

2 thoughts on “An Introduction to Set Theory”

Leave a comment Cancel reply