Sets and Sequences
[Video Tutorials] (coming soon)
Students are introduced to the ideas of sets very early – starting as early as kindergarten when they learn to count and do addition and subtraction with physical objects in a set, and then in elementary school they see and use Venn diagrams. While the use of sets at an early age is informal and intuitive, collections of objects are fundamental concepts that show up repeatedly. We briefly review some of the formal notation and terminology in this section, as well as notation for commonly-used sets of numbers. While the basic concepts are simple, there’s a lot more to sets and properties of set operations than we cover here – our focus is just on establishing a foundation, and we start with a basic definition and some terminology.
Definition 1: Set
Specifying a Set and Talking About Sets
If we want to define a specific set, how can we do that? There are three main ways: full enumeration of small sets, giving a pattern, or using set-builder notation. Below, we describe each of these, as well as notation for some standard and widely-used sets.
Specifying a Set Using Full Enumeration
When a set is small, we can simply list (or enumerate) all of its values between curly braces. Some authors call this the “roster method” or “set-roster method.” For example, the set of values on a six-sided die 
is D_6=\{1,2,3,4,5,6\}. It’s important to remember that a set is an unordered collection, so the order we write the elements in is irrelevant. This means we could just have easily said D_6=\{6,5,4,3,2,1\} or D_6=\{2,5,1,6,4,3\}, and these alternatives define the same set. In addition, since elements are distinct, repeating an element doesn’t change the set (it is still in the set only once), so it’s also true that D_6=\{1,2,2,3,3,3,4,5,6\}. Repeating elements like this is bad style, and should only be done if there is some compelling reason to do so.
While we are usually interested in sets of numbers, there’s no reason that elements need to be numbers. For example, we can define the set of suits of a standard deck of cards as C_S=\{\heartsuit,\clubsuit,\diamondsuit,\spadesuit\}. Elements of a set can themselves be sets, giving us a set of sets. For example, the set of all 2-element sets of letters a, b, and c is L_2=\{\{ a, b\}, \{a, c\}, \{b, c\} \}. We’ll see an important example of sets of sets below when we talk about the power set.
In the above examples, there is nothing special about the names we have given the sets, D_6, C_S, and L_2. We are simply giving them unique names so we can refer to them later – we could just as easily have named the set of card suits \textit{Fred} or anything else, but it’s good to use names that relate to what the set consists of. For suits we have C for “cards” and S to narrow that down to suits of cards. Again though, this is totally arbitrary, and as far as we know this name for a set of suits is not used anywhere in the world outside of this lesson. While names really can be anything, we note that mathematical tradition uses capital letters for set names.
Since a set can be empty, we can also specify the null set in this notation, with the curly braces and nothing in between (the full enumeration is empty). In other words, \emptyset=\{\}.
Some Notation About Sets
There is notation and terminology for many of the things we might want to talk about with sets, so we cover those here. Let’s define a few sets to illustrate the definitions and notation in this section. In particular, let A=\{1,2,3\} and B=\{1,2,3,4,5\}.
The most common thing we talk about with sets is whether an object is in a set or not. If we want to say, for example, that 2 is in the set A, we write 2\in A, which we read as “2 is an element of A” or simply “2 is in A.” We can also use A as the subject by saying “A contains 2.” We can say that 5 is not an element of A using “5\not\in A.”
For a finite set, we can indicate the number of elements in the set with vertical bars, and we write |A| for the size of set A. This is also sometimes called the cardinality of A. There are ways to talk about the cardinality of infinite sets as well, but that is a topic for a different lesson. The only set with cardinality zero is the empty set, and we have |\emptyset|=0.
A common mistake students make is to see the vertical bars around a set, and confuse that for other uses of vertical bars that they have seen. This is not an “absolute value,” so don’t call it that! It is the cardinality of the set, or the size of the set.
Since an element in a set S can be a set, or a set of sets, or even a set of sets of sets, it’s important to note that such a set is just one element in the set S no matter how complex or large it is. For example, what is the cardinality of the set \{ 3, \{1, 2\}, x, \{\}, \{a, \{b, \{c,d\}\}\} \} \ ?
Beyond individual elements, we can talk about one set being contained in another. If every element of A is also an element of B we say that A is a subset of B, and can write A\subseteq B. We can also negate the statement, to say that B is not a subset of A, using notation B\not\subseteq A, which means that B contains at least one element that is not in A.
There are two cases on the extremes that aren’t “special cases,” but deserve a mention to understand why they are not special cases. The first is the case of the null set, which is a subset of any set — in other words, \emptyset\subseteq S for any set S because “every element of \emptyset is in S” is true (when we talk about logic, we’ll say that this is “vacuously true”). The second extreme is when the sets are equal: for any set S it is true that S\subseteq S (every element of S is in S).
If S_1\subseteq S_2 for some sets S_1 and S_2, where S_1\neq S_2, then S_2 contains some element that S_1 does not. In this case, we say that S_1 is a proper subset of S_2, and we can indicate that with a modified subset notation: S_1\subset S_2. Notice how this is analogous to notation for comparison of numbers, and the difference between “x\leq y” and “x<y” – the bar at the bottom of the notation indicates that equality is possible, and the lack of the bar means that equality is not an option.
Unfortunately, the notation regarding subsets and proper subsets is not universal. While it is rare, some authors use \subset to indicate any kind of subset and not just a proper subset. So they might have A\subset A. Others may emphasize a proper subscript by crossing out the bar at the bottom of the subset notation, like A\subsetneq B. In our tutorials we are always careful to use \subset when referring to proper subsets, and \subseteq when referring to subsets in general.
Specifying a Set With a Pattern
Enumerating a set, like we did above, can only be done for finite sets and is only practical for small sets. While D_6 only has six elements, so they can be listed, what if you wanted a set of the numbers from 1 to 1000? Consider writing something like D_{1000}=\{1,2,3,\ldots,1000\}, where the “\ldots” is saying “fill this in with the pattern that has been established.”
For infinite sets, you can do the same thing but with an open-ended pattern. For example, the natural numbers are the “counting numbers,” or integer values starting at 0 and going up. A pattern-based definition of the set of natural numbers could look something like \{0,1,2,3,\ldots\}.
There is no universal agreement about whether the natural numbers include 0. Some people think the “counting numbers” should start at 1, because that is where you usually start counting. Others say that 0 is a counting number, since you can have zero of something (like in the empty set). If you are in a math class or working problems, make sure you know what definition of the natural numbers is being used, and use that one! For all of our lessons at Logical Learning, we define the natural numbers to contain 0. We have a separate notation (see below) for positive integers, which start at 1.
There is standard notation for various sets of numbers, including the natural numbers, as defined below. For some definitions we use patterns, and for others we simply describe the set in English.
Definition 2
The following notations are used to represent standard sets of numbers:
- \mathbb{N}: Natural numbers, \{0,1,2,3,\ldots\}
- \mathbb{Z}: Integers, \{..., -2, -1, 0, 1, 2, ...\}
- \mathbb{Z}^+: Positive integers, \{1,2,3,\ldots\}
- \mathbb{Q}: Rationals, or numbers that can be written as a fraction x/y where x and y are integers.
- \mathbb{R}: Reals, which are numbers on a continuous number line, including all the rational as well as irrational numbers such as \sqrt{2} and \pi.
An important thing to remember is that 0 is neither positive nor negative, so the set of positive integers should not contain 0. We could instead talk about the “non-negative integers,” which would include 0, but this is just the natural numbers. This terminology is more commonly used when referring to rationals or reals (for example, we might refer to the non-negative reals).
The notations above are standard, but you might see slight variations. For example, some people use a script font where {\mathcal R} denotes the reals, and others use simply boldface as in \mathbf{R}.
A set defined with a pattern will always involve some guess-work and the possibility of guessing wrong. For example, consider S=\{3,5,7,..\}. What is this? Is it the set of odd integers greater than one? Is it the set of prime numbers greater than two? There’s no way to tell!
Example 3
The bottom line is to use patterns to specify a set only when there is a clear and natural meaning. A good guiding principle is Occam’s razor, which says that if there are two competing theories, the simpler one is the correct one. If this isn’t the case for a pattern-based description of a set (i.e., if the simpler explanation of the pattern isn’t correct), then don’t use patterns!
Often the pattern notation is used to give a more mathematical style clarification to an English language description. For example, “Let E_N be the set of even natural numbers, E_N=\{0,2,4,...\}.”
Using Set-Builder Notation
Set-builder notation gives us a way of defining infinite sets without relying on the reader guessing patterns. To use this notation we give a rule that precisely defines every element of the set – typically this is almost like an algorithm that generates the set, but it doesn’t have to be. Above, we defined the set E_N of even natural numbers by relying on a pattern (and guessing how the pattern extends beyond those listed values). Instead, since every even natural number is two times some natural number, we can write
E_N=\{ x\in\mathbb{N} \ |\ x=2k \text{ for } k\in\mathbb{N} \} \ .
In this notation, to the left of the vertical bar you have a set of potential elements for the set, and to the right of the bar is a condition that says which are actually in the set. You would read this in English as “E is the set natural numbers x such that x=2k for some natural number k.” The vertical bar is the “such that” part. Some people will call the condition a “filter,” relating this to programming language constructs.
There are several “styles” or variants of set-builder notation. While there is no universally-accepted standard, they are generally clear as to what they mean. However, if you are reading these tutorials because you’re taking a discrete mathematics class, make sure you use the style used in your class – just being clear isn’t enough!
As an example of a different style, some people allow for a computation to the left of the vertical bar, rather than simply defining the set of possible values. In this style, you could define the set of even natural numbers by \{ 2k\ |\ k\in\mathbb{N}\}. This allows for some nice, compact definitions, and the meaning of sets described in this variant is clear; however, in the interest of consistency, we will stick with the style of set-builder notation defined at the beginning of this section.
The style in the note above is closely related to combining a map and a filter in programming, or the list comprehension construction in Python. If you want to read more about this, open the optional note below.
While not important for the mathematics, if you have experience with Python programming, you might notice a similarity to list comprehensions in Python. These work with lists (mathematically: sequences, discussed below) rather than sets, but the idea and notation is similar. In Python, range(10) gives a list of natural numbers less than 10. So if we want a list of even numbers less than 20=2\cdot 10 we can write
e = [ 2*k for k in range(10) ]The word for stands in for the vertical bar in the set-builder notation, but the notation is basically the same. A subtle point, which you don’t need to dwell on too much now, is that set-builder notation can define sets based on a property, which may or may not be computable, while the Python programming construction is a computation.
Example 4
We give some additional examples here. At the beginning of the section about using patterns, we defined the set D_{1000}=\{1,2,3,\ldots,1000\}. We can remove all ambiguity and make this definition more precise by defining
- D_{1000} = \{ x\in\mathbb{N}\ |\ 1\leq x\leq 1000 \}
We often will use a clear and unambiguous English-language statement to describe the condition. Here’s an example of a set that would be awkward to define using just formulas:
- \{ x\in\mathbb{N}\ |\ x\text{ has an odd number of digits in base 10}\}
In some cases, the set of values is clear from context, so we omit the set from the left side of the bar. For example, the following set defines the set of perfect squares. Since k has to be an integer, x can only be an integer, so we can write simply
- \{ x\ |\ x=k^2 \text{ for } k\in\mathbb{Z} \}
Other Set Descriptions
In computer science, we often deal with sets of objects other than numbers. For instance, data in a modern digital computer is represented by a sequence of 0s and 1s (i.e., “bits”), so we might look at sets of these sequences. A sequence of bits is also called a binary string. One common way to describe a set of binary strings is to use a regular expression, and while a full coverage of regular expressions isn’t appropriate here we give a few as examples.
\{0,1\}^* represents the set of all finite-length binary strings, including an empty string denoted \varepsilon. This set can be seen as the following pattern-described set: \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}.
01^*0 represents the set of all strings that start and end in 0, with only 1s allowed (but not required) between them. So this set is \{00, 010, 0110, 01110, \ldots\}.
Sets of strings (more formally called languages), as well as regular expressions, have fundamental importance to what it means to compute something, and is a major topic in Theory of Computing.
Making Sets from Other Sets – Operations
Much like you can add two numbers together to get a new number, you can perform operations on sets to get new sets. We talk about the most common of these operators here, illustrating with example sets A=\{1,2,3\}, B=\{1,2,3,4,5\}, and C=\{2,4\}. We’ll use S_1 and S_2 for unspecified generic sets.
The union of two sets S_1 and S_2, which is written S_1\cup S_2, is a set consisting of all of the elements in S_1 and all of the elements in S_2. Remember that sets have distinct elements, so there cannot be duplicates, and if an element is in both S_1 and S_2 then it only appears once in S_1\cup S_2. Using our specific sets above we have A\cup B=\{1,2,3,4,5\} and A\cup C=\{1,2,3,4\}. Notice that in the first of these, the result of the union is just B. This is a general property: whenever S_1\subseteq S_2, we have S_1\cup S_2=S_2. Do you see why? Can you give a logical explanation of why this property holds? In the section on writing proofs, we will write a clear mathematical proof of this property.
We can write more complex formulas such as (A\cup B)\cup C; however, since the union operation is associative, meaning we can apply a the union operations in any order, we typically leave off the parentheses and write simply A\cup B\cup C. If we have a large number of sets S_1, S_2,\ldots, S_n that we want to union together, we can use the notation
\bigcup_{i=1}^n S_i
for this. In situations where we have an infinite sequence of sets where the union is well-defined, we can write
\bigcup_{i=1}^{\infty} S_i
for the union.
The intersection of two sets S_1 and S_2, written S_1\cap S_2, is the set consisting of all elements that appear in both S_1 and S_2. Using our sets above, we have A\cap B=\{1,2,3\} and A\cap C=\{2\}. As above, when S_1\subseteq S_2 there is a special property of the intersection, namely S_1\cap S_2=S_1. When the intersection of two sets is empty, so S_1\cap S_2=\emptyset, we say that the sets are disjoint.
As with union we can indicate the intersection of multiple sets using notation like A\cap B\cap C,
\bigcap_{i=1}^n S_i\ , \text{\ \ \ \ or\ \ \ \ } \bigcap_{i=1}^{\infty} S_i
Example 5
S_1\cup S_2 = \{ x \ |\ x\in S_1\text{ or } x\in S_2 \}\ .
Now try your hand at this. Work this out on your own first, and then reveal the solution to check your work.
Example 6
The set difference is written S_1-S_2, or sometimes S_1\setminus S_2, and means the set of elements that are in A and not in B. Using the sets above, B-A=\{4,5\}. There is no requirement the second set has to be a subset of the first set, and any elements in the second set that aren’t in the first are just ignored. For instance, A-C=\{1,3\}. Note also that this is not a commutative operator, and order matters. For example, while B-A=\{4,5\}, we have A-B=\emptyset.
The following figure is a regular Venn diagram illustrating the union, intersection, and difference operations.
In some situations, a set S is considered in the context of being a subset of a universe or a universal set, which is the set of possible values that S is drawn from. For a set S in the context of a universal set U, we can define a set of elements that are not in S. This is the complement of set S, and it is written \overline{S}. Using set difference, we have \overline{S}=U-S. A few easy-to-see properties of the complement operation are S\cup\overline{S}=U and S\cap\overline{S}=\emptyset.
Example 7
Note that just because a set S=\{0,2,4,\ldots\} looks like it consists of natural numbers, don’t assume that the universe is \mathbb{N} unless some other context indicates that this is the case. These could just as easily be considered as numbers from \mathbb{R}, in which case \overline{S} would contain not just 1 and 3, but also 2.5, 1.875, and \pi. As a general rule of thumb, if a set is defined using set-builder notation as values from a set that satisfy certain properties (like our definition of E_N using set-builder notation above), then the universe is generally the set that the values are drawn from in that notation (given to the left of the vertical line). However, there’s no real mathematical requirement for this, so exercise caution and use your best judgment!
It is often important to know the size of sets constructed using these set operations. For now we simply state these properties without justification or proof, but we will talk about them more in a future tutorial (you are also encouraged to think through why these are true using the Venn diagram above). In particular, the first formula below is a simple two set version of something called the “inclusion-exclusion principle” which is a very important formula in probability theory.
Theorem 8
The following are true for any finite sets S_1 and S_2 with finite universe U:
|S_1\cup S_2| = |S_1|+|S_2|-|S_1\cap S_2|
|S_1-S_2| = |S_1|-|S_1\cap S_2|
|\overline{S_1}|=|U|-|S_1|
The Cartesian product or two sets, written S_1\times S_2, is the set of pairs or elements, where the first item in the pair comes from S_1 and the second comes from S_2. The pairs are written in regular parentheses, so we would write
A\times C = \{ (1,2), (1,4), (2,2), (2,4), (3,2), (3,4) \}\ .
The two sets don’t have to be different, so we could also have
A\times A = \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \}\ .
Similar to the way we can use powers with multiplication of numbers, we can use power notation to represent the Cartesian product of a set with itself, so A\times A can be written A^2.
This last example illustrates that the pairs are ordered, so (1,2) is different from (2,1), and both must appear in the Cartesian product. As one more fun example, recall that we defined C_S to be the set of suits in a standard deck of playing cards. Let C_{KA}=\{K,A\} represent face values of king and ace in the deck. Then the Cartesian product gives a set with the king and ace of every suit:
C_{KA}\times C_{S} = \{ (K, \heartsuit), (A, \heartsuit), (K, \clubsuit), (A, \clubsuit), (K, \diamondsuit), (A, \diamondsuit), (K, \spadesuit), (A, \spadesuit), \} \ .
The Cartesian product generalizes to more than two sets, so we can talk about S_1\times S_2\times S_3, which contains ordered triples (a,b,c) where a\in S_1, b\in S_2, and c\in S_3. Or even n-way Cartesian products, S_1\times S_2\times\cdots\times S_n. Elements of these sets are called tuples, or you can specify the size and call them n-tuples (or a specific number like 3-tuples).
If the Cartesian product uses the same set for each part of the tuple, we can use the powering notation as A\times A\times A=A^3 or A\times A\times\cdots\times A (n times) is A^n.
Example 9
For finite sets S_1 and S_2, in S_1\times S_2 each of the |S_1| elements of S_1 is paired up with each of the |S_2| elements of S_2, so it’s easy to see that |S_1\times S_2|=|S_1|\cdot |S_2|. This is generalized to any number of sets in the following theorem.
Theorem 10
|S_1\times S_2\times\cdots\times S_n|=|S_1|\cdot |S_2|\cdots |S_n|\ .
As a special case, for finite set S we have |S^n|=|S|^n.
The power set of a set S_1, written {\mathcal P}(S_1), is the set of all subsets of S_1. When thinking about the power set, remember that the empty set is a subset of S_1 as is the full set S_1. The power set of our example set A is
{\mathcal P}(A) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \} \ .
Note that while |A|=3, we have |{\mathcal P}(A)|=2^3=8. This relation between the size of a set and the size of a power set holds for any finite set, as stated in the following theorem.
Theorem 11
We will give a formal proof of this theorem in the lesson on induction proofs, but for now consider the following intuition: Every time the set S gets a new element x, the size of the power set doubles since we must include all subsets that don’t contain x (the power set before we added x) plus all subsets that do contain x. Since it doubles in size for each addition of one element, that means the size of the power set grows as the power of two of the number of elements.
While the calligraphic letter {\mathcal P} that we use above is very common, used in books like the Discrete Mathematics book by Rosen, the Theory of Computation book by Sipser, and more, there are a variety of notations that people have adopted for the power set.
Some authors (like in the popular Discrete Math book by Susanna Epp) use a more “fancy” script letter, as in {\mathscr P}(S). Others, (like in the Discrete Structures book by Hein) write out the word, like power(S). The same idea is used in the Mathematics for Computer Science book by Lehman, Leighton, and Meyer, but abbreviated as pow(S). With reference to how the size of the power set grows, in the popular algorithms book by Cormen et al., the authors denote the power set of S as 2^S (note that S is a set, not a number, so this is not a simple algebraic formula).
As in all situations where there are different notations for the same concept, make sure you use the notation that is relevant for your context – for example, used by your instructor or by the textbook used in your class.
Note: You can find links to some of the books mentioned here on our Outside Resources page.
Throughout our discussion of sets, we have mentioned a few properties of set operations. We give a list of useful properties here, which apply to any sets S_1, S_2, and S_3 from universe U. We will return to some of these and prove them in our tutorial on proofs.
Complement laws
S_1\cup \overline{S_1}=U
S_1\cap \overline{S_1}=\emptyset
De Morgan’s laws
\overline{S_1\cup S_2}=\overline{S_1}\cap\overline{S_2}
\overline{S_1\cap S_2}=\overline{S_1}\cup\overline{S_2}
Distributive laws
S_1\cap(S_2\cup S_3) = (S_1\cap S_2)\cup (S_1\cap S_3)
S_1\cup(S_2\cap S_3) = (S_1\cup S_2)\cap (S_1\cup S_3)
Absorption laws
S_1\cup(S_1\cap S_2) = S_1
S_1\cap(S_1\cup S_2) = S_1
Practice Problems
The following problems can be used to test your understanding of the material above. Each problem has a solution that you can open, but you should try to solve it yourself first. In particular, you are strongly encouraged to actually write down a solution to commit yourself to it, and then open the answer to see if you were correct.
Use set-builder notation to define the set difference A-B, where A and B are arbitrary sets.
What is the value of each expression below?
|\{1,2\}|
|{\mathcal P}(\{1,2\})|
|{\mathcal P}({\mathcal P}(\{1,2\}))|
|\{1,2\}\times {\mathcal P}(\{1,2\})|
|{\mathcal P}(\{\{1,2,\{3,4\}\}\})|
Answer the following.
What is {\mathcal P}(\emptyset)?
What is the size of the set in part a (i.e., what is |{\mathcal P}(\emptyset)|)?
What is |{\mathcal P}({\mathcal P}(\emptyset))|?
Give set-builder definitions for the following sets:
The set of positive integers less than 20.
The set of perfect squares less than 400.
The set of rational numbers x such that x^2=2.
The set of points in the plane (with real number coordinates) at distance 1 or less from the origin.
For each set in the previous problem, give the cardinality of the set if it is finite, or say “infinite” if it is infinite.
For each set below, write out the set using full enumeration.
\{x\in\mathbb{Z}\ |\ 4\leq x<10\}
\{x\in\mathbb{R}\ |\ x^2=16\}
\{x\in\mathbb{Z^{+}}\ |\ 2^x=16\}
\{x\ |\ x \text{ is an English language vowel}\}
For the following claims, state whether they are true or false.
5 is the same as \{5\}
|\{5\}|=1
|\{\emptyset\}|=0
\{1,2\}\subseteq \{1, \{2\}\}
\text{red}\in\{\text{red}, \text{green}, \text{blue}\}
\text{red}\in\{\{\text{red}\}\}
Give two non-empty sets A and B such that A\in B and A\subseteq B.
Let A=\{\emptyset,\{1\},\{3\},\{1,2\},\{2,3\},\{1,2,3\}\}. If you are told that A\subseteq{\mathcal P}(S) and |{\mathcal P}(S)|=8, what is the set S? Since A has 6 elements, what 2 elements from {\mathcal P}(S) are missing?
If |A\times B|=0, what must be true about A and B?
Let A=\{1,2\}, B=\{3,4\}, C=\{5,6\}. What are the elements of A\times B? Give one element of (A\times B)\times C. Give one element of A\times B\times C.
YouTube
Facebook