Sets - Defining Sets - Essential Dictionary I

Mathematical Writing - Vivaldi Franco 2014

Sets - Defining Sets
Essential Dictionary I

Franco Vivaldi1

(1)

School of Mathematical Sciences, Queen Mary, University of London, London, UK

Franco Vivaldi

Email: f.vivaldi@qmul.ac.uk

In writing mathematics we use words and symbols to describe facts. We need to explain the meanings of words and symbols, and to state and prove the facts.

We’ll be concerned with facts later. In this chapter and the next we list mathematical words with accompanying notation. This is our essential mathematical dictionary. It contains some 200 entries, organised around few fundamental terms: set, function, sequence, equation. As we introduce new words, we use them in short phrases and sentences.

Dictionaries are not meant to be read through, so don’t be surprised if you find the exposition demanding. Take it in small doses. The last section of this chapter deals with advanced terminology and may be skipped on first reading.

2.1 Sets

A set is a collection of well-defined, unordered, distinct objects. (This is the so-called ’naive definition’ of a set, due to Cantor.1) These objects are called the elements of a set, and a set is determined by its elements. We may write

The set of all odd integers

The set of vertices of a pentagon

The set of differentiable real functions

In simple cases, a set can be defined by listing its elements, separated by commas, enclosed within curly brackets. The expression

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

denotes the set whose elements are the integers $$1$$, $$2$$ and $$3$$. Two sets are equal if they have the same elements:

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

(By definition, the order in which the elements of a set are listed is irrelevant.)

It is customary to ignore repeated set elements: $$\{2,1,3,1,3\}=\{2,1,3\}$$. This convention, adopted by computer algebra systems, simplifies the definition of sets. If repeated elements are allowed and not collapsed, then we speak of a multiset: $$\{2,1,3,1,3\}$$. The multiplicity of an element of a multiset is the number of times the element occurs. Reference to multiplicity usually signals that there is a multiset in the background:

Every quadratic equation has two complex solutions, counting multiplicities.

Multisets are not as common as sets.

The set $$\{\}$$ with no elements is called the empty set, denoted by the symbol $$\emptyset $$. The empty set is distinct from ’nothing’, it is more like an empty container. For example, the statements

This equation has no solutions.

The solution set of this equation is empty.

have the same meaning.

To assign a symbol to a mathematical object, we use an assignment statement (or definition), which has the following syntax:

$$\begin{aligned} A:=\{1,2,3\}. \end{aligned}$$

(2.1)

This expression assigns the symbolic name $$A$$ to the set $$\{1,2,3\}$$, and now we may use the former in place of the latter. The symbol ’$$:=$$’ denotes the assignment operator. It reads ’becomes’, or ’is defined to be’, rather than ’is equal to’, to underline the difference between assignment and equality (in computer algebra, the symbols = and := are not interchangeable at all!). So we can’t write $$\{1,2,3\}:=A$$, because the left operand of an assignment operator must be a symbol or a symbolic expression.

The right-hand side of an assignment statement such as (2.1) is a collection of symbols or words that pick out a unique thing, which logicians call the definiens (Latin for ’thing that defines’). The left-hand side is a symbol that will be used to stand for this unique thing, which is called the definiendum (Latin for ’thing to be defined’). These terms are rather heavy, but they are widely used [36, Chap. 8]. The definiendum may also be a symbolic expression—see below.

While it’s very common to use the equal sign ’$$=$$’ also for an assignment, the specialised notation $$:=$$ improves clarity. There are other symbols for the assignment operator, namely

$$\begin{aligned} \mathop {=}\limits ^\mathrm{def} \qquad \mathop {=}\limits ^{\nabla }, \end{aligned}$$

(2.2)

which make an even stronger point.

To indicate that $$x$$ is an element of a set $$A$$, we write

$$ x\in A \qquad x\; {\textit{is an element of}}\; A \qquad x\; {\textit{belongs to}}\; A. $$

The symbol $$\not \in $$ is used to negate membership. Thus

$$ \{7,5\}\in \{5,\{5,7\}\} \qquad 7\not \in \{5,\{5,7\}\}. $$

(Think about it.)

A subset $$B$$ of a set $$A$$ is a set whose elements all belong to $$A$$. We write

$$ B\subset A \qquad B\; {\textit{is a subset of}}\; A \qquad B\; {\textit{is contained in}}\; A $$

and we use $$\not \subset $$ to negate set inclusion. For example

$$ \{3,1\}\subset \{1,2,3\} \quad \,\emptyset \subset \{1\} \quad \,\{2,3\}\not \subset \{2,\{2,3\}\}. $$

Every set has at least two subsets: itself and the empty set. Sometimes these are referred to as the trivial subsets. Every other subset—if any—is called a proper subset. Motivated by an analogy with $$\leqslant $$ and $$<$$, some authors write $$\subseteq $$ in place of $$\subset $$, reserving the latter for proper inclusion: $$\mathbb {R}\subseteq \mathbb {R}$$, $$\mathbb {Q}\subset \mathbb {R}$$. Proper inclusion is occasionally expressed with the pedantic notation .

The cardinality of a set is the number of its elements, denoted by the prefix $$\#$$:

$$ \#\{7,-1,0\}=3 \qquad \#A=n. $$

The absolute value symbol $$|\cdot |$$ is also used to denote cardinality: $$|A|=n$$. Common sense will tell when this choice is sensible. A set is finite if its cardinality is an integer, and infinite otherwise. To indicate that the set $$A$$ is finite, without disclosing its cardinality, we write

$$\begin{aligned} \# A<\infty . \end{aligned}$$

(2.3)

A more rigorous account of cardinality will be given in Sect. 2.3.3.

Next we consider the words associated with operations between sets. We write $$A\cap B$$ for the intersection of the sets $$A$$ and $$B$$: this is the set comprising elements that belong to both $$A$$ and $$B$$. If $$A\cap B=\emptyset $$, we say that $$A$$ and $$B$$ are disjoint, or have empty intersection. The sets $$A_1,A_2,\ldots $$ are pairwise disjoint if $$A_i\cap A_j=\emptyset $$ whenever $$i\not =j$$.

We write $$A\cup B$$ for the union of $$A$$ and $$B$$, which is the set comprising elements that belong to $$A$$ or to $$B$$ (or to both $$A$$ and $$B$$).

We write $$A{\backslash }B$$ for the (set) difference of $$A$$ and $$B$$, which is the collection of the elements of $$A$$ that do not belong to $$B$$. The symmetric difference of $$A$$ and $$B$$, denoted by $$A\,\varDelta \, B$$, is defined as

$$\begin{aligned} A\,\varDelta \,B \,\mathop {=}\limits ^\mathrm{def}\,(A{\backslash }B)\cup (B{\backslash }A). \end{aligned}$$

The assignment operator ’$$\mathop {=}\limits ^\mathrm{def}$$’ [cf. (2.2)] makes it clear that this is a definition. This notation establishes the meaning of $$A\,\varDelta \,B$$, which is a symbolic expression rather than an individual symbol. The following examples illustrate the action of set operators:

$$\begin{aligned} \{1,2,3\}\cap \{3,4,5\}&= \{3\}\\ \{1,2,3\}\cup \{3,4,5\}&= \{1,2,3,4,5\}\\ \{1,2,3\}{\backslash }\{3,4,5\}&= \{1,2\}\\ \{1,2,3\}\,\varDelta \,\{3,4,5\}&= \{1,2,4,5\}. \end{aligned}$$

The above set operators are binary; they have two sets as operands. The identities

$$ A\cap B=B\cap A \qquad (A\cap B)\cap C =A\cap (B\cap C) $$

express the commutative and associative properties of the intersection operator. Union and symmetric difference enjoy the same properties, but set difference doesn’t.

Let $$A$$ be a subset of a set $$X$$. The complement of $$A$$ (in $$X$$) is the set $$X{\backslash }A$$, denoted by $$A^{\,\prime }$$ or by $$A^c$$. The complement of a set is defined with respect to an ambient set $$X$$. Reference to the ambient set may be omitted if there is no ambiguity. So we write

The odd integers is the complement of the even integers

since it’s clear that the ambient set is the integers.

With set operators we can construct new sets from old ones, although, in a sense, we are recycling things we already have. To create genuinely new sets, we introduce the notion of ordered pair. This is an expression of the type $$(a,b)$$, with $$a$$ and $$b$$ arbitrary quantities. Ordered pairs are defined by the property

$$\begin{aligned} (a,b)=(c,d) \qquad \text{ if }\qquad a=c\quad \text{ and }\quad b=d. \end{aligned}$$

(2.4)

The ordered pair $$(a,b)$$ should not be confused with the set $$\{a,b\}$$, since for pairs order is essential and repetition is allowed. (Ordered pairs may be defined solely in terms of sets—see Exercise 2.14.) Let $$A$$ and $$B$$ be sets. We consider the set of all ordered pairs $$(a,b)$$, with $$a$$ in $$A$$ and $$b$$ in $$B$$. This set is called the cartesian product of $$A$$ and $$B$$, and is written as

$$ A \times B. $$

Note that $$A$$ and $$B$$ need not be distinct; one may write $$A^2$$ for $$A\times A$$, $$A^3$$ for $$A\times A\times A$$, etc. Because the cartesian product is associative, the product of more than two sets is defined unambiguously. Also note that the explicit presence of the multiplication operator ’$$\times $$’ is needed here, because the expression $$AB$$ has a different meaning [see Eq. (2.21), Sect. 2.3].

2.1.1 Defining Sets

Defining a set by listing its elements is inadequate for all but the simplest situations. How do we define large or infinite sets? A simple device is to use the ellipsis ’$$\ldots $$’, which indicates the deliberate omission of certain elements, the identity of which is made clear by the context. For example, the set $$\mathbb {N}$$ of natural numbers is defined as

$$ \mathbb {N}:=\{1,2,3,\ldots \}. $$

Here the ellipsis represents all the integers greater than 3. Some authors regard $$0$$ as a natural number, so the definition

$$ \mathbb {N}:=\{0,1,2,3,\ldots \} $$

is also found in the literature. Both definitions have merits and drawbacks; mathematicians occasionally argue about it, but this issue will never be resolved. So, when using the symbol $$\mathbb {N}$$, one may need to clarify which version of this set is employed.2 The set of integers, denoted by $$\mathbb {Z}$$ (from the German Zahlen, meaning numbers), can also be defined using ellipses:

$$ \mathbb {Z}:=\{\ldots ,-2,-1,0\,,1\,,2,\ldots \} \qquad \text{ or }\qquad \mathbb {Z}:=\{0,\pm 1,\pm 2,\dots \}. $$

To define general sets we need more powerful constructs. A standard definition of a set is an expression of the type

$$\begin{aligned} \{ x : x \text { has } {\fancyscript{P}}\} \end{aligned}$$

(2.5)

where $${\fancyscript{P}}$$ is some unambiguous property that things either have or don’t have. This expression identifies the set of all objects $$x$$ that have property $${\fancyscript{P}}$$. The colon ’$$:$$’ separates out the object’s symbolic name from its defining properties. The vertical bar ’$$|$$’ or the semicolon ’$$;$$’ may be used for the same purpose.

Thus the empty set may be defined symbolically as

$$\begin{aligned} \emptyset \mathop {=}\limits ^\mathrm{def}\{x\,:\,x\not =x\}. \end{aligned}$$

(2.6)

The property $$\fancyscript{P}$$ is ’$$x$$ is not equal to $$x$$’, which is not satisfied by any $$x$$. Likewise, the cartesian product $$A\times B$$ of two sets (see Sect. 2.1) may be specified as

$$ \{ x : x=(a,b)\, \text { for some }\, a\, \in A \text { and }\, b\, \in B\}. $$

The rule ’$$x$$ has property $${\fancyscript{P}}$$’ now reads: ’$$x$$ is of the form $$(a,b)$$ with $$a\in A$$ and $$b\in B$$’. The same set may be defined more concisely as

$$ \{ (a,b)\,:\, a \in A\, \text { and }\, b \in B\}. $$

This is a variant of the standard definition (2.5), where the type of object being considered (ordered pair) is specified at the outset. This form of standard definition can be very effective.

The set $$\mathbb {Q}$$ of rational numbers—ratios of integers with non-zero denominator—is defined as follows:

$$\begin{aligned} \mathbb {Q}:=\bigl \{\frac{a}{b}\,:\,\,\,a\in \mathbb {Z},\,\,b\in \mathbb {N},\,\,\mathrm{gcd}(a,b)=1)\bigr \}. \end{aligned}$$

(2.7)

The property $${\fancyscript{P}}$$ is phrased in such a way as to avoid repetition of elements. This is the so-called reduced form of rational numbers. The rational numbers may also be defined abstractly, as infinite sets of equivalent fractions—see Sect. 4.6.

One might think that in the expression for a set we could choose any property $${\fancyscript{P}}$$. Unfortunately this doesn’t work for a reason known as the Russell-Zermelo paradox 3 (1901). Consider the set definition

$$\begin{aligned} W:=\{x\,:\,x\not \in x\} \end{aligned}$$

(2.8)

in which $${\fancyscript{P}}$$ is the property of being a set that is not a member of itself. The quantity

$$ x=\{3,\{3,\{3,\{3\}\}\}\} $$

has property $${\fancyscript{P}}$$ and hence belongs to $$W$$, whereas

$$ x=\{3,\{3,\{3,\{3,\ldots \}\}\}\} \qquad \text{ or }\qquad x=\{3,x\} $$

does not have property $${\fancyscript{P}}$$ and hence does not belong to $$W$$. (In the above expression, the nested parentheses must match, so the notation $$\{3,\{3,\{3,\{3,\ldots \}$$ is incorrect.)

Given that $$W$$ is a set of sets, we ask: does $$W$$ belong to $$W$$? We see that if $$W\in W$$, then $$W$$ has property $${\fancyscript{P}}$$, that is, $$W\not \in W$$, and vice-versa. Impossible! Thus the standard definition (2.8), so deceptively similar to (2.6), does not actually define any set.

Fortunately, we can define a set in such a way that the definition guarantees the existence of the set. A Zermelo definition identifies a set $$W$$ by describing it as

The set of members of $$X$$ that have property $${\fancyscript{P}}$$

where the ambient set $$X$$ is given beforehand, and $${\fancyscript{P}}$$ is a property that the members of $$X$$ either have or do not have. In symbols, this is written as

$$\begin{aligned} W:=\{x \in X : x \text { has } {\fancyscript{P}} \}. \end{aligned}$$

(2.9)

For example, the expression

The set of real numbers strictly between 0 and 1

is a Zermelo definition: the ambient set is the set of real numbers, and we form our set by choosing from it the elements that have the stated property.

Zermelo definitions work because it’s a basic principle of mathematics (the so-called subset axiom) that for any set $$X$$ of objects and any property $${\fancyscript{P}}$$, there is exactly one set consisting of the objects that are in $$X$$ and have property $${\fancyscript{P}}$$. In Sect. 4.3 we shall see that the definiens of a Zermelo definition—a sentence with a variable $$x$$ in it—is just a special type of function, called a predicate.

Both styles of definitions, standard and Zermelo, are widely used in mathematical writing.