**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:

- represents the set of fruits which I prefer.
- can represent, among other things, the fingers on my left hand.
- The set of natural numbers .
- The set of integers .

Sets are subject to the following properties:

- Order blindness: and expresses the very same set.
- Duplicate blindness. . We will prefer to express sets with the latter, more compact, notation.
- Recursion. is a perfectly valid two-element set, quite distinct from the three-element set .

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

- Let and . Then, .
- Let and . Then, .

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

- Let . Then means “yellow is an element of the set of primary colors”.
- means “-1 is not an element of the natural numbers”.
- . The element is not in : only the set is.

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

- Let . Then .
- Let . Then . Note that cardinality only looks at “the outer layer”.

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

- .
- .
- .

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: , where the | symbol is pronounced “such that”.

- . 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 .

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 and let . Here , despite their use of different rules. We say that and 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 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.*

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:

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 is a **subset **of another set , written , if every element of is also an element of .

- Let and . Then (recall that element order is irrelevant).
- Let and . Then (C does not contain 9).
- Is a subset of ? Yes. For all , is true.

Definition 8. A set is a **proper subset** of another set , written , if and .

Definition 9. For a given set , its **power set** is the set of all subsets of .

- Let . Then .

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

As can be seen above, the total number of subsets must be a power of two. Specifically, if , then .

It is important to get clear on the differences between the element-of ( ) versus subset-of ( ) relations. Consider again and its power set

- . But . The relation requires the brackets match.
- . But . The relation requires the “extra bracket”.

Probability theory is intimately connected with the notion of power set. Why? Because many discrete probability distributions have -algebras draw from the power set of natural numbers .

Cartesian Product, Tuples

Definition 10. Given two sets and , their **Cartesian product** is the set of all **ordered pairs** such that and . Note that, unlike the elements in a set, the elements of an ordered pair cannot be reordered.

- Let and . Then .

We can represent this same example visually, as follows:

- Contrast this with . Thus, . This is because elements within ordered pairs cannot be rearranged.
- Note that . In combinatorics, this observation generalizes to the
**multiplication principle**. - The
**real plane**is a well-known example of a Cartesian product.

Definition 11. Given n sets, , their Cartesian product is the set of all n-tuples.

- Let , and . Now .

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 and , written , is the set of elements common to both sets.

- Let and . Then .
- Let and . Then .
- Let . Then .

Definition 13. The **union **of two sets and , written is the set of all elements that are in or , or both.

- Let and . Then .
- Let . Then .

**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:

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

Note that . 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 and , their **difference ** is the set of elements in but not also in .

- Let and . Then and .
- Let and . Then and .

Definition 15. Given two sets and , the **symmetric difference** is the set of elements in or , but not both.

- Let and . Then .

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

- Let and let its universe be the set of complex numbers . It is true that .

Definition 17. Relative to a universe , the **complement **of , written is the set of all elements of not contained in .

- Let U be the set of positive integers less than 10: and . Then .

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

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.