Sets and Number System Notation

I'll review some basics about sets and some of the number systems we'll use. If you're familiar with these things, you can skim this section and refer to it later when you need to.

A set is informally described as a collection of objects. The objects are elements of the set, or members of the set. So a set is kind of like a bag, and its elements are things in the bag.

However, it's easy to get into trouble with that informal description. Trouble can be fun, so let's see how you can get into trouble here. Russell's paradox is named after the British mathematician Bertrand Russell. Here's how it goes. Suppose X is the set whose members are sets which are not members of themselves. (Thus, X is a bag, and the members of X --- the things in the bag --- are themselves bags.) Now is X a member of X? It either is or it isn't.

If X is a member of X, then X is a set which is not a member of itself, by the definition of X. So X is both a member of itself and not a member of itself.

If X is not a member of X, then X is a set which is not a member of itself, so it should be a member of X, by definition of X. Again, X is both a member of itself and not a member of itself.

You may have to think about this a bit, since the words can make your eyes glaze over!

You can see that both alternatives lead to a contradiction. Something is wrong, and it lies in the way we created the set X. It turns out that, to deal with sets in a rigorous way, you have to be careful about how sets can be created. The Zermelo-Fraenkel-Choice Axioms do this, and they are one of the most commonly accepted foundations for mathematics. If you're interested in learning more, you should take a course or read a book in set theory or mathematical logic.

We will stay out of trouble by avoiding weird sets like the one in Russell's paradox.

Let's start by reviewing common set constructions and notations. If A and B are sets, then:

(a) $x \in A$ means that x is an element or member of A. Likewise, $x_1, x_2 \in X$ means that $x_1$ and $x_2$ are elements of X.

$$\hbox{\epsfysize=0.65in \epsffile{sets-1.eps}}$$

We'll often use schematic diagrams like this one (sometimes called Venn diagrams) to picture arbitrary sets. The sets are drawn as rectangles or ovals or other closed shapes, and you think of the elements of the sets as being stuff inside. In this case, the dot labelled "x" is a particular element of A.

(b) A and B are equal if they have exactly the same elements. In that case, we write $A = B$ .

(c) $A \subset B$ means that A is a subset of B --- that is, every element of A is also an element of B. It is possible in this case that $A = B$ ; if we don't want to allow $A = B$ , we'll write $A \propersubset B$ and say that A is a proper subset of B.

$$\hbox{\epsfysize=1in \epsffile{sets-2.eps}}$$

(d) $A \cap B$ is the intersection of A and B --- that is, all the elements which A and B have in common.

$$\hbox{\epsfysize=1.2in \epsffile{sets-3.eps}}$$

(e) $A \cup B$ is the union of A and B --- that is, all the elements which are in A or are in B (or are in both).

$$\hbox{\epsfysize=1.2in \epsffile{sets-4.eps}}$$

(f) $A - B$ is the complement of B relative to A --- that is, all the elements of A which are not elements of B.

$$\hbox{\epsfysize=1in \epsffile{sets-5.eps}}$$

If there is some "big set" S and everything under discussion is contained in S, you can denote the complement of a set A relative to S (sometimes called the absolute complement) by $\complement{A}$ . In order words, $\complement{A}$ is short for $S - A$ when the "big set" S is understood.

$$\hbox{\epsfysize=1.4in \epsffile{sets-6.eps}}$$

(g) The empty set is the set with no elements. It is denoted $\emptyset$ or $\{\hskip0.1in\}$ . (But "$\{\emptyset\}$ " is not the empty set --- if the empty set is like an empty bag, then "$\{\emptyset\}$ " is like a bag containing an empty bag.)

(h) If S and T are sets, their (Cartesian) product consists of all ordered pairs $(s, t)$ , where $s \in S$ and $t \in T$ . "Ordered" means, for example, that $(2, 8)$ and $(8, 2)$ are different ordered pairs.

For example, if $S = \{a, b\}$ and $T = \{1, 2, 3\}$ , then

$$S \times T = \{(a, 1),\ (a, 2),\ (a, 3),\ (b, 1),\ (b, 2),\ (b, 3)\}.$$

Likewise, $S \times T \times U$ consists of ordered triples $(s, t, u)$ , where $s \in S$ , $t \in T$ , and $u \in U$ .

We'll sometimes abbreviate $S \times S$ to $S^2$ , and so on.

The sets which make up standard number systems have special symbols.

(a) $\integer$ is the set of integers (positive, negative, and 0).

(b) $\rational$ is the set of rational numbers, which can be represented as quotients of integers. (Thus, $\rational$ includes $\integer$ , since (for instance) $3 = \dfrac{3}{1}$ .) The use of the letter "Q" is apparently due to the Italian mathematician Giuseppe Peano and stands for the Italian word for "quotient".

(c) $\real$ is the set of real numbers, which are often represented as decimals (finite or infinite). $\real$ includes $\rational$ (and so it includes $\integer$ ).

(d) $\complex$ is the set of complex numbers: Numbers that can be written in the form $a + b i$ , where a and b are real numbers and $i = \sqrt{-1}$ . The old phrase "imaginary numbers" is not that good --- there's nothing "imaginary" about $\complex$ ! --- and so is less often used. $\complex$ includes $\real$ --- for instance, the real number 13 can be written as $13 + 0 \cdot i$ --- so $\complex$ also includes $\rational$ and $\integer$ . Using our subset notation, we could write $\integer \subset \complex$ , for instance.

The convention is to use boldface capital letters (like " Z" or " Q") or "blackboard bold" capital letters (like $\integer$ , $\rational$ , $\real$ , $\complex$ ) for "number systems". You may see other letters (like the quaternions $\quaternion$ ) used as well. I'll use blackboard bold, since it is easier to distinguish blackboard bold letters from ordinary capital letters than boldface. It's also the way you write these symbols on blackboards or in handwriting.

I'll use these number systems informally based on your prior experience with them; actually constructing them rigorously is pretty involved and belongs in other courses (though we can use matrices to construct the complex numbers from the real numbers).

You can specify a finite set by listing its elements, placed between braces ("curly brackets"). Here's a set consisting of 5 elements:

$$\left\{\pi,\ -117,\ 32.83,\ \dfrac{19}{17},\ \hbox{the pepperoni pizza in my refrigerator}\right\}.$$

A set does not have duplicate elements, so don't write things like "$\{1,\ 2,\ 2,\ 3\}$ ". The order in which you list the elements doesn't matter: $\{a,\ b,\ c\}$ is the same set as $\{c,\ a,\ b\}$ . (It's like a bag of stuff, as we noted at the start.)

Sets can have other sets as elements:

$$\{1,\ 2,\ \{3, 4\}\}.$$

You can picture this set as a bag. Inside the bag are 1, 2, and another bag which contains 3 and 4. The number of elements in this set is 3; in other words, in determining the number of elements in a big set, you don't peek inside any little sets inside the the big set.

You can sometimes specify infinite sets by listing elements:

$$\{1,\ 2,\ 3,\ 4, \ldots \}.$$

Most people would assume that you mean the elements to continue 5, 6, 7, and so on. Of course, when you do this you're assuming that the "pattern" the elements follow is clear; the "$\ldots$ " means "continue in the same way". But there's some ambiguity here; perhaps the elements of the set above are actually

$$\{1,\ 2,\ 3,\ 4,\ 10,\ 20,\ 30,\ 40,\ 100,\ 200,\ 300,\ 400, \ldots \}.$$

If there's any chance of confusion, it's better to use set constructor notation to make the "pattern" the elements follow explicit. Set constructor notation has the form

$$T = \{x \in S \mid P(x)\}.$$

The braces "$\{$ " and "$\}$ " indicate that we're building a set, and its name is T. (You may give a set a name to make it easier to talk about, but the name isn't required.) The first part "$x \in S$ " tells us that the elements of T come from some "big set" S. And "$P(x)$ " is some property that a typical element x must satisfy to belong to T.

For example, this is the set of positive integers:

$$\{x \in \integer \mid x > 0\}.$$

This is the set of positive real numbers:

$$\{x \in \real \mid x > 0\}.$$

You can see how the specification of the "big set" from which the elements come ($x \in \integer$ or $x \in \real$ ) can be important.

Sometimes it's convenient to relax the rules for set constructor notation a bit. Here's the set of even integers:

$$\{x \in \integer \mid x = 2 y \quad\hbox{for some}\quad y \in \integer\}.$$

It says that even integers are integers which are twice another integer. We can save writing (and a variable) by writing the set this way:

$$\{2 y \mid y \in \integer\}.$$

This says even integers are numbers which are twice another integer. Since twice an integer is automatically an integer, the word "numbers" must mean "integers".

We'll often use this kind of shortcut in writing sets. Here's another example. It's the set of all points on the graph of $y = x^2$ in the x-y-plane:

$$\{(x, x^2) \mid x \in \real\}.$$

Example. Consider the following set of integers:

$$S = \{3 n + 1 \mid n \in \integer\}.$$

(a) Is 46 an element of S?

(b) Is 17 an element of S?

(a) 46 is an element of S, since $46 = 3 \cdot 15 + 1$ and $15 \in \integer$ .

(b) 17 is not an element of S. Suppose on the contrary that $17 \in S$ . Then $17 = 3 n + 1$ for some $n \in \integer$ . Subtracting 1 from both sides, I get $16 = 3 n$ for some integer n. This is impossible, since 16 is not "evenly divisible" by 3.

You may have seen the notations $\real^2$ and $\real^3$ in a multivariable calculus course. $\real^2$ is the set of ordered pairs of real numbers, like $(-5, 11)$ or $(\sqrt{3}, \pi)$ --- the "x-y plane". Likewise, $\real^3$ is the set of ordered triples of real numbers, like $(9, 0, -13)$ or $\left(\dfrac{11}{17}, \sin 1, 32\right)$ --- 3-dimensional space. Using set constructor notation, you can write these sets like this:

$$\real^2 = \{(x, y) \mid x, y \in \real\} \quad\hbox{and}\quad \real^3 = \{(x, y, z) \mid x, y, z \in \real\}.$$

Arbitrary collections of objects.

In some cases, we'll need to deal with collections of objects which aren't finite, but are infinite "in a big way". This presents notational issues, which I'll discuss here. The objects might be elements of a sets, or they might be sets themselves.

If we have just two objects, we could call them x and y. If we have a small finite number of objects, we can use numerical subscripts. For instance, for 5 objects, we could use $x_1$ , $x_2$ , $x_3$ , $x_4$ , and $x_5$ .

If we have a finite number of objects but the number is undetermined --- say there are n of them --- we can still use subscripts: $x_1$ , $x_2$ , ... $x_n$ .

If we have an infinite but countable number of objects, we can continue to use natural numbers as subscripts:

$$x_1,\ x_2,\ \ldots, x_n,\ \ldots .$$

The "$\ldots$ " on the right indicates that the number of objects is infinite.

In fact, you can take " countable" to mean that the objects are either finite in number, or can be arranged in a sequential list as above. If the objects can't be arranged in a sequential list as above, the objects are uncountable. Thus, if you have an uncountable number of objects, you can't use natural number subscripts to index them. For example, suppose the objects are the real numbers. You can't arrange the real numbers in a sequential list.

So how do we describe an uncountable collection of objects?

To handle this kind of situation is actually simple. We take an index set --- say I. We don't assume anything about the size of I, or what its elements look like. We use the elements of I as subscripts for our objects. So if we're discussing a particular object indexed by I, we refer to "$x_i$ , where $i \in I$ ". If we need another object indexed by I, we say "$x_j$ , where $j \in I$ ". If we need 4 such objects, we can use subscripts with subscripts, this way:

$$x_{i_1},\ x_{i_2},\ x_{i_3},\ x_{i_4}, \quad\hbox{where}\quad i_1, i_2, i_3, i_4 \in I.$$

If we wanted 4 possibly different objects, we'd have to specify that $i_1$ , $i_2$ , $i_3$ , and $i_4$ are distinct (though maybe in a given situation our collection of objects contains duplicates, so different i's might still give the same object).

In these cases, we're not saying what i, j, $i_1$ , $i_2$ , $i_3$ , or $i_4$ are, beyond that they're elements of I, and that I is some set.

Arbitrary intersections and unions.

As examples of arbitrary collections of objects, we'll discuss arbitrary unions and intersections of sets. Begin with an arbitrary collection of sets $\{S_i\}_{i \in I}$ . This means that each $S_i$ is a set, and there is one such set for each element i in the index set I. The index set I might be finite, or if it is infinite, it might be countable or uncountable.

The intersection of the sets $\{S_i\}_{i \in I}$ is denoted $\displaystyle \bigcap_{i \in I} S_i$ . By definition, an element x is in $\displaystyle \bigcap_{i \in I} S_i$ if and only if x is in $S_i$ for all $i \in I$ . In other words,

$$x \in \bigcap_{i \in I} S_i \quad\hbox{if and only if}\quad x \in S_i \quad\hbox{for all}\quad i \in I.$$

The big intersection symbol $\displaystyle \bigcap_{i \in I}$ is like a summation symbol ("$\displaystyle \sum_{i = 1}^n$ ") that you've probably seen elsewhere.

For just two sets U and V, the definition would say $x \in U \cap V$ if and only if $x \in U$ and $x \in V$ . This agrees with the definition of "intersection" we gave earlier.

In similar fashion, the union of the sets $\{S_i\}_{i \in I}$ is denoted $\displaystyle \bigcup_{i \in I} S_i$ . By definition, an element x is in $\displaystyle \bigcup_{i \in I} S_i$ if and only if x is in $S_i$ for some $i \in I$ . ("For some" means "for at least one".) In other words,

$$x \in \bigcup_{i \in I} S_i \quad\hbox{if and only if}\quad x \in S_i \quad\hbox{for some}\quad i \in I.$$

We won't have to deal with arbitrary intersections and unions that often, so don't worry if this seems a bit abstract. When it comes up, you'll see that the notation isn't that difficult to handle.

Contact information

Bruce Ikenaga's Home Page

Copyright 2022 by Bruce Ikenaga