Representing sets

Section 1.1 Representing sets

Sets are a fundamental concept in modern mathematics. Often in this book we will adopt the viewpoint that ideas or problems can be encoded in the “language” of mathematics. What this means is that we have a mathematical object that suitably represents the idea or the relevant objects in the problem. It is likely you have had the experience of doing a word problem where something is represented with a point

(x, y)

in the coordinate plane.

🔗

Often, the starting point for such a representation is a set, or an element of a set. Every mathematical object you have ever encountered can be described as a set, from numbers themselves to functions, shapes, and matrices.

🔗

This book is written as if it were the first math book you've ever needed to read and understand. So, for the first few chapters, you might see comments like this one telling you what to write down. You do not need to write down every word of the text, but you should definitely be writing down definitions, theorems, and examples. Students in more advanced courses or self-studiers with more background should also be writing down the proofs.

The definition of an object or concept is a sentence (or paragraph) that uniquely characterize that object. A definition is the final authority on what a mathematical object is. Theorems may extend the properties an object has or what you can do with the object, but the theorems must follow from the definition. Definitions don't require proof; they are chosen by the mathematician. (What constitutes a good definition is a huge question that is well outside the scope of this book, but we will talk about it now and then.)
Theorems are mathematical facts requiring proof. Loosely speaking, a theorem is a new idea that arises from a combination of other theorems and definitions. Once a theorem is conjectured (suspected to be true based on some sort of evidence), we can use definitions, other theorems, and the rules of logic (which will learn shortly) to justify the theorem.
An example uses a specific choice of objects to illustrate a theorem or an idea. Whereas theorems must be proven in full generality, we can use examples to convince ourselves that a theorem is true or to help get our heads around a difficult idea. This book is littered with examples and you should work them yourself (on paper!) to make sure you understand what is going on. When possible, you should try to stop reading the example and finish it on your own before checking to see whether you had the right idea.
A proof is an argument that a mathematical fact is true. We will more thoroughly discuss (simple kinds of) proofs in a later chapter, but for now, consider a proof to be a convincing and logically correct explanation of why a theorem is true.

🔗

Now that we know a bit about the building blocks of mathematical writing, let's have our first definition.

🔗

Definition 1.1.1.

A set is an unordered collection of objects called its elements. When $a$ is an element, or member, of the set $a,$ we write $a \in A .$ This sentence reads, in English, “ $a$ is an element of the set $A .$ ” If $a$ is not an element of $A,$ then we can write $a \notin A .$

🔗

There are two ways to represent a set. One is to simply list all the objects in the set; or, if a pattern is obvious, to use ellipses to list all of the objects in a large or infinite set. This is called list or roster notation. Some sets defy easy listing, in which case we instead describe all the elements in the set. This is called set-builder notation.

🔗

Below is your first example. If you are reading the web or e-book version of this textbook, you will have to click to un-“knowl” it. This makes it easier to review a chapter for the specific information you are looking for. You should write this example down, and try to think of another example. This example gives a set in both list and set-builder notation. Can you write down another set in both notations?

🔗

Example 1.1.2.

Let's start with a simple set with just a few familiar elements:

\begin{equation*} A = \{1,2,3,4,5\}. \end{equation*}

Above, the set $A$ has been represented in roster notation. This is the easiest way to write down sets with only a few elements. When there are more elements that defy simple listing, we can use set-builder notation. Set-builder notation is more difficult to read, but it is extremely useful. In set-builder notation, we'd write

\begin{equation*} A = \{n \; | \; n\text{ is an integer and }1 \le n \le 5\}. \end{equation*}

Set-builder notation starts by naming an arbitrary item in the set, in this case $n$ for one of the elements of $A\text{,}$ and then following up with a phrase that characterizes the elements of the set. Here, “characterizes” means that this sentence describes the elements of the set, and does not describe anything that isn't in the set. In this case, the sentence is “$n$ is an integer and $1 \le n \le 5\text{.}$” (If you don't know, or forgot, an integer is a whole number.)

If we replace $n$ with anything in the set, then the sentence should be true. For instance, $2$ is an integer, and $1 \le 2 \le 5\text{.}$ Therefore, $2 \in A\text{.}$ If we replace $n$ with anything outside the set, then the sentence should be false. For instance, $6$ is not between or equal to $1$ and $5\text{;}$ so, $6 \not\in A\text{.}$ To see a different non-example, the word “apple” does not represent an integer, so apple $\not\in A\text{.}$

🔗

Some important sets with their own symbols will streamline the process of writing set-builder notation.

🔗

Definition 1.1.3.

The set of natural numbers is

N = {0, 1, 2, 3, \dots},

where the ellipses ( $\dots$ ) imply that the pattern continues. Taking the natural numbers and including their negatives gives us the integers:

Z = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots} .

The set of all integers, their reciprocals, and all products thereof is the set of rational numbers:

Q = {p / q | p, q \in Z and q \neq 0} .

The rational numbers are contained in the set of $R$ of real numbers, which includes familiar members $\sqrt{2},$ $π,$ and $e .$

🔗

Notice that the set of rational numbers is described using set-builder notation because it is easier to describe a quotient than it is to list them all. The sentence

Q = {p / q | p, q \in Z and q \neq 0}

🔗

reads “the set

Q

is the set of all quotients

p / q

where

p

and

q

are both integers, but

q \neq 0 .

”

🔗

Additionally, not everyone agrees that

0

should be counted among the natural numbers. (Remember earlier that we said definitions were matters of convention?) However, computer scientists typically do consider

0

a member of

N .

Since this book is being written for a course full of computer science majors, we will consider it one as well. (It is also the view of the author that

0 \in N;

see how nicely

0

plays with its fellow natural numbers in Part III of this book.)

🔗

Example 1.1.4.

This example will give us an idea of how to use the membership symbol ($\in$) as well as its negation ($\not\in$) for “not an element of.”

The number $2$ is a natural number and an integer and since $2=2/1\text{,}$ it is a rational number as well. Therefore $2 \in \mathbb{N}\text{,}$ $2 \in \mathbb{Z}\text{,}$ and $2 \in \mathbb{Q}\text{.}$

The number $-4$ is an integer and a rational number but not a natural number, so $-4 \in \mathbb{Z}$ and $-4 \in \mathbb{Q}$ but $-4 \not\in \mathbb{N}\text{.}$

The number $-3/2$ is a rational number but not an integer nor a natural number. Therefore, $-3/2 \in \mathbb{Q}$ but $-3/2 \not\in \mathbb{N}$ and $-3/2 \not\in \mathbb{Z}\text{.}$

The number $\sqrt{2}$ is not a rational number, integer, nor natural number. In that case we write $\sqrt{2} \not\in \mathbb{N}\text{,}$ $\sqrt{2} \not\in \mathbb{Z}\text{,}$ and $\sqrt{2} \not\in \mathbb{Q}\text{.}$

🔗

The next definition describes an important set of integers that does not behave nicely in roster notation.

🔗

Definition 1.1.5.

A prime number is a positive integer

p

with exactly two factors: itself and

1 .

We will denote the set of primes

P = {p | p \in Z, p > 1, p has no factors besides 1 and itself} .

🔗

Example 1.1.6.

The first few primes are $2, 3, 5, 7, 11, 13, 17, \ldots$ Notice there is not a clear pattern that allows the ellpises to say exactly what we mean. Therefore, set-builder notation is appropriate for the primes. In fact, if the primes were easily listed, we would have a lot fewer unsolved problems in mathematics!

🔗

Numbers give convenient examples, but sets do not need to contain numbers. Sets can contain almost anything, as evidenced in the following example.

🔗

Example 1.1.7.

Consider the set of all U.S. states. In roster notation this set is a nightmare:

\begin{align*} \{ \amp AL, AK, AZ, AR, CA, CO, CT, DE, FL, GA,\\ \amp HI, ID, IL, IN, IA, KS, KY, LA, ME, MD,\\ \amp MA, MI, MN, MS, MO, MT, NE, NV, NH, NJ,\\ \amp NM, NY, NC, ND, OH, OK, OR, PA, RI, SC,\\ \amp SD, TN, TX, UT, VT, VA, WA, WV, WI, WY \} \end{align*}

But in set-builder notation we simply write:

\begin{equation*} \{ \, S \, | \, S \text{ is a U.S. state} \}. \end{equation*}

🔗

Now you know how to write down the different kinds of sets you will encounter in this book (and you will encounter a lot of them!) In the next section, we will explore the idea of containment, where one set contains the elements of another.