Set theory
Set theory is a branch of mathematics that studies sets. Sets are a collection of (typically) well-defined objects. Below are a few examples:
- {a, b, c, d, e}
- {n|n ∈ ℕ, 1 ≤ n ≤ 10}
- {green, red, blue, yellow, white, black, purple}
- The Venn diagram shows a set that is made up of fruits and vegetables.
Notice that a set can be made up of virtually any type of object. While this is true, set theory is mostly concerned with objects that are relevant to mathematics. The objects in a set are referred to as elements. For example, in the Venn diagram, each fruit or vegetable is an element of their respective set, and both vegetables and fruits are part of the universal set 𝕌. The middle portion where the set of fruits and vegetables intersect contains only tomatoes, which are considered a fruit botanically, but are commonly considered a vegetable in the context of cooking. These kinds of relationships are the foundation of basic set theory.
Basic set theory concepts and notation
At its most basic level, set theory describes the relationship between objects and whether they are elements (or members) of a given set. Sets are also objects, and thus can also be related to each other typically through use of various symbols and notations.
Although set theory may seem arbitrary and not necessarily useful on its own, it is used throughout mathematics and can be thought of as a fundamental building block. Many mathematical concepts would be difficult to define precisely (and concisely) without the use of set theory. As such, it is important to be familiar with the various symbols and notations used in set theory in order to both understand and communicate mathematical concepts effectively. The table below includes some of the most common symbols.
| Symbol | Definition/meaning | Example |
|---|---|---|
| { } | Indicates a collection of elements | {1, 3, 7, 9} |
| ∅ | Empty set - set contains no elements | {} |
| ... | Indicates that the set continues the pattern in the corresponding direction towards negative (left) or positive (right) infinity | {..., -9, -7, -3, -1, 1, 3, 7, 9, ...} |
| | | "Such that" | a∈ℤ | a > 3 - "a is an integer such that a is greater than 3" |
| ∩ | "and" or "intersection" | A = {1, 2, 3, 4} B = {4, 5, 6} A ∩ B = {4} |
| ∪ | "or" or "union" | A = {1, 2, 3, 4} B = {4, 5, 6} A ∪ B = {1, 2, 3, 4, 5, 6} |
| ⊆ | Subset - A is a subset of B if all its elements are included in B | {1, 2} ⊆ {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} ⊆ {1, 2, 3, 4, 5} |
| ⊂ | Proper/strict subset - A is a proper subset of B if A is a subset of B, but not equal to B | {1} ⊂ {1, 2, 3, 4, 5} {1, 2} ⊂ {1, 2, 3, 4, 5} {1, 2, 3} ⊂ {1, 2, 3, 4, 5} {1, 2, 3, 4} ⊂ {1, 2, 3, 4, 5} |
| ∈ | Element of - indicates that the object on the left of the symbol is an element of the object on the right | x∈ℚ - "x is an element of the rational numbers" |
| 𝕌 | Universal set - the set of all possible values | A = {1, 2} B = {3, 4, 5} 𝕌 = {1, 2, 3, 4, 5} |
| Ac or A' | Complement - all the elements not in set A | 𝕌 = {1, 2, 3, 4, 5} A = {1, 2, 3} Ac = {4,5} |
| [a, b] | Closed interval - values between a and b including a and b | [1,4] = {1, 2, 3, 4} if only including integers |
| (a, b) | Open interval - values between a and b not including a and b | (1,4) = {2, 3} if only including integers |
| |A| | Order/cardinality - number of elements in the set | A = {3, 6, 7, 9} |A| = 4 |
| ℕ | Natural numbers - only positive numbers with no decimals or fractions | {1, 2, 3, ...} |
| ℤ | Integers - all positive and negative numbers with no decimals or fractions, including 0 | {..., -3, -2, -1, 0, 1, 2, 3, ...} |
| ℚ | Rational numbers - a number that can be represented as a fraction comprised of integers | ⅔ |
| ℝ | Real numbers - rational numbers and irrational numbers | π, e, 3, ½, 0.25 |
| ℂ | Complex numbers - numbers made up of a real and imaginary component | 4 + 2ⅈ |
Order and equality of sets
The order of a set refers to the size of a set. It is also referred to as the cardinality of the set. Sets can have a finite or infinite order. If a set has a finite order, the order of a set is determined by the number of elements in the set. For example, the set A = {1, 2, 5, 7, 9} has an order of 5, since it contains 5 elements. Using set notation, we could express the order of A as:
|A| = 4
Note that the order of elements in a set does not matter. For example, given the sets
A = {1, 2, 5, 7, 9}
B = {1, 5, 2, 9, 7}
we would say that A and B are equal sets, or A = B. This is because equality of sets is determined by the elements within the set, not by the order in which the elements are listed.
Example
Given the sets
A = {5, 3, 1}
B = {3, 1, 5, 13, 10,}
C = {2, 10, 6, 4}
refer to the table as necessary, and determine the outcomes of the following operations:
- A ∩ B
- A ∩ C
- B ∪ C
i. A ∩ B = {1, 3, 5}
- Because all of the elements of A are also in B, we can also say that A is a proper subset of B, or A ⊂ B. Also, |A| = 3, and |B| = 5.
ii. A ∩ C = ∅
- A and C have no common elements, so their intersection is an empty set. We can also say that A and B are mutually exclusive sets.
iii. B ∪ C = {1, 2, 3, 4, 5, 6, 10, 13}
- The union of B and C is the set that contains all elements of B and C.
Infinite sets
Sets can be finite or infinite. Furthermore, infinite sets can be countable or uncountable.
Countable
Any infinite set that can be paired with the natural numbers in a one-to-one correspondence such that each of the elements in the set can be identified one at a time is a countably infinite set. For example, given the set
{0, -1, 1, -2, 2, -3, 3, ...}
its elements can be paired with a natural number as follows:
Thus, it is possible to identify the nth element as the natural number n.
Uncountable
Uncountably infinite sets cannot be arranged in the same way as countably infinite sets. The set of real numbers from zero to one, or (0, 1), is not countable because it is not possible to pair each of the elements in the set with a unique element in the set of natural numbers. For example, let {0, x1, x2, ..., 1} be the set of real numbers from zero to one where x1 ≠ x2. The figure below shows that the elements cannot be mapped in the same way as the figure above (with countably infinite sets):
Natural numbers can be mapped to the elements, as shown in the figure, but because there are real numbers between any two distinct real numbers, there are no natural numbers to map to the real numbers between 0 and x1, x1 and x2, and so on. Thus, the set is uncountably infinite.
Set operations
Some of the basic set operations (union and intersection) were discussed above. Below are a few other operations.
Cartesian product
The Cartesian product of A and B, denoted A × B, is the set comprised of all ordered pairs (a, b) such that a is an element of A, and b is an element of B. Using set-builder notation, this can be denoted as:
For example, if A = {a, b} and B = {i, j, k}, then the Cartesian product of A and B is:
Note that the order in which the six elements of the set is written does not matter, but the order of the ordered pairs does. For example, (a, i) is not the same ordered pair as (i, a). Generally, if there are m elements in A and n elements in B, there are m · n elements in A × B.
Power set
A power set is a set that is made up of all possible subsets of a set. Let A = {1, 2, 3}. The power set of A, denoted ℘(A), is:
℘(A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Notice that both the empty set and set A itself are considered subsets of A. In general, if there are n elements in A, there are 2n subsets in ℘(A).
De Morgan's laws
In set theory, De Morgan's laws are a set of rules that relate the union and intersection of sets through their complements.
Union of sets:
The complement of the union of two sets is equal to the intersection of their complements:
(A ∪ B)C = AC ∩ BC
Given that A and B are subsets of the universal set 𝕌, this relationship can be seen in the figure below:
The union of A and B, A ∪ B, is shaded in blue. Its complement, (A ∪ B)C is shaded in yellow. The intersection of the complements of A and B, AC ∩ BC is also shaded in yellow.
Intersection of sets:
The complement of the intersection of two sets is equal to the union of their complements:
A ∩ B = AC ∪ BC
Given that A and B are subsets of the universal set 𝕌, this relationship can be seen in the figure below:
The intersection of A and B, A ∩ B, is shaded in red. Its complement, (A ∩ B)C is shaded in grey. The union of the complements of A and B, AC ∪ BC, is also shaded in grey.