Elementary Discrete Mathematics 2

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.

In the preface, it was said that this book would be 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.

Two things about this definition. First, it is unusually wordy for a mathematical definition. This book is written for mathematical novices, so definitions will typically include a little more detail than they might otherwise. Second, this is actually not the definition of a set. This definition leads to paradoxes when sets get very large; however, we will never encounter this issue. Also, you were told to write down every definition, so I wanted to put this “definition” inside a definition block.

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

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

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

reads “the set \(\mathbb{Q}\) is the set of all quotients \(p/q\) where \(p\) and \(q\) are both integers, but \(q \neq 0\text{.}\)”

Additionally, not everyone agrees that \(0\) should be counted among the natural numbers. (Remember earlier that I said definitions were matters of convention?) However, computer scientists typically do consider \(0\) a member of \(\mathbb{N}\text{.}\) Since this book is being written for a course full of computer science majors, we will consider it one as well. (It is also my personal view that \(0 \in \mathbb{N}\text{;}\) see how nicely \(0\) plays with its fellow natural numbers in Part III of this book.)

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

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

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.