Sets and Notation
August 25, 20266 min readbeginner
Before any talk of adding numbers or multiplying them, there has to be a clear way to say what kind of numbers are in play.
Before any talk of adding numbers or multiplying them, there has to be a clear way to say what kind of numbers are in play. The vocabulary mathematicians use for this is the language of sets. This note builds that vocabulary from scratch. If , , and the bold-blackboard letters , , , already feel comfortable to you, you can skim this and move on.
01.What a set is
A set is a collection of distinct things. The things in the collection are called its elements. That is the whole definition.
Two sets are equal whenever they have exactly the same elements. The order in which elements are listed does not matter, and writing the same element twice does not change the set. So the three ways of writing
all describe the same set.
The elements can be anything. They do not have to be numbers. The set of primary colours is just as much a set as the set of single-digit positive integers:
has nine elements. has three. Sets with finitely many elements like these are called finite. The size of a finite set is sometimes written , so and .
There is one set with no elements at all, called the empty set, written or . It is the same idea as the empty bag: a collection containing nothing.
02."Is an element of": the symbol
If is one of the elements of a set , that fact is written and read as " is in " or " is an element of ". If is not in , it is written .
For the set from above:
Notice that is not in even though is a perfectly fine number, because the definition of left it out of the curly braces.
03.Sets that go on forever
Some sets have infinitely many elements. The natural numbers, the integers, the rationals, and the reals are the four most important examples in this chapter, and they get their own special blackboard-bold names:
- is the set of natural numbers. The "" reads "and so on, forever". The set never stops.
- is the set of integers. Every whole number, positive, negative, and zero. The "" comes from the German Zahlen, meaning "numbers".
- is the set of rational numbers, that is, every number that can be written as a fraction with and . Examples: , , , .
- is the set of real numbers. This contains every rational, plus numbers like , , and , which cannot be written as fractions.
These four sets sit inside one another, each containing all the previous: every natural number is an integer, every integer is a rational, every rational is a real. The symbol for "sits inside" is , which appears in a moment.
It is common to put a "" subscript to mean "the positive ones". So is the positive integers, and is the positive reals.
04.Set-builder notation
Listing all the elements of a set works only when there are not too many of them. For larger sets you need a different way. The standard way is set-builder notation, which has the shape
and is read "the set of all such that the following condition holds". The colon "" reads "such that". A vertical bar "" is sometimes used in place of the colon and means the same thing.
A few examples will make this concrete.
The set of all even integers is
The "" before the colon says where ranges. The condition after the colon picks out which of those values get to stay. So .
The rationals can be written in set-builder form:
The set of integers between and inclusive can be written either way:
Both descriptions are correct. Use the listing form when it is short enough, and use set-builder when it is not.
05."Is a subset of": the symbol
If every element of a set also happens to be an element of another set , is called a subset of , written . The symbol is the same idea as for numbers: it allows the case where the two sides are equal.
Quick examples:
The last one is the chain of containments mentioned earlier, written with the proper symbol now.
A subtle point: is always true, because every element of is also (trivially) an element of . The empty set is a subset of every set, including itself, because the statement "every element of is in " has nothing to check.
When and , is a proper subset of , and some books write or . The notation varies. This chapter writes everywhere and adds the words "proper" if it matters.
06.A small worked example
Let
Reading the description, is the set of natural numbers below that are divisible by . Listing them out: is divisible by (because ), then , then , then . So
Check: is ? Yes, every element of is in . Is ? No, is not divisible by . Is ? Yes.
07.What you need to remember
Three symbols carry most of the work in everything that follows: (is an element of), (set-builder), and (is a subset of). The four named number sets will appear constantly. Once these feel routine, the rest of the chapter is about putting operations like addition and multiplication on top of these sets, and that is the next note.
— Anirban
Hardware–software at the seam where compilers meet microcode.