Skip to main content
\(\def\Z{\mathbb{Z}} \def\zn{\mathbb{Z}_n} \def\znc{\mathbb{Z}_n^\times} \def\R{\mathbb{R}} \def\Q{\mathbb{Q}} \def\C{\mathbb{C}} \def\N{\mathbb{N}} \def\M{\mathbb{M}} \def\G{\mathcal{G}} \def\0{\mathbf 0} \def\Gdot{\langle G, \cdot\,\rangle} \def\phibar{\overline{\phi}} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\Ker}{Ker} \def\siml{\sim_L} \def\simr{\sim_R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section1.1Sets

We start off by providing a “definition” of a basic mathematical structure to which we will soon add bells and whistles. We use quotes here because what follows doesn't have the precision we usually require when defining a mathematical object.

Definition1.1.1

A set is an (unordered) collection of objects.

This is only sort of a “definition” because it is not a rigorous definition of a set. For instance, what do we mean by a “collection” of objects? This “definition” will be sufficient for our course, but be warned that defining a set in this vague way can lead to some serious mathematical issues, such as Russell's paradox. A mathematician whose expertise is in set theory may scowl disagreeably if you try to define a set as we have above.

Note1.1.2

Let \(S\) be the set of all sets that aren't members of themselves. Is \(S\) a member of itself? If you think carefully about this, you'll see that \(S\) can be neither a member of itself, nor not a member of itself. Uh oh! This contradiction is known as “Russell's paradox” (named for the British philosopher, mathematician, and all-round academic Bertrand Russell). Mathematicians deal with this by declaring that some object collections, called classes, are not in fact sets.

Definition1.1.3

The members of a set are called its elements. If \(S\) is a set, we write \(x\in S\) to indicate “\(x\) is an element of \(S\text{,}\)” and \(x \not\in S\) to indicate “\(x\) is not an element of \(S\text{.}\)” There is a unique set containing no elements; it is called the empty set, and denoted by \(\emptyset\text{.}\)

Sets must be well-defined: that is, it must be clear exactly which objects are in a set, and which objects aren't. For instance, the set of all integers is well-defined, but the set of all big integers is not well-defined, since it is unclear what “big” means in this context.

We refer to some sets so frequently in mathematics that we have special notation for them.

Example1.1.4

Some common sets are:

\(\Z\)

the set of all integers (the \(\Z\) comes “zahlen,” the German word for “numbers”)

\(\Q\)

set of all rational numbers

\(\R\)

the set of all real numbers

\(\C\)

the set of all complex numbers

\(\N\)

the set of all natural numbers, i.e., \(\{0, 1, 2, \ldots\}\)

(Be aware that many books/mathematicians do not include \(0\) in the set of natural numbers

We can further write denote by \(\Z^+\) the set of all positive integers, and by \(\Z^*\) the set of all nonzero integers. Can you guess what the penultimate notation represents if we replace \(\Z\) with \(\Q\) or \(\R\text{,}\) and/or \(+\) with \(-\text{?}\) What about what the last notation, if we replace \(\Z\) with \(\Q\text{,}\) \(\R\text{,}\) or \(\C\text{?}\)

We also provide notation for commonly considered sets of matrices:

Definition1.1.5

Given \(m,n\in \Z^+\) and a set \(S\text{,}\) we define \(\M_{m\times n}(S)\) to be the set of all \(m\times n\) matrices over \(S\) (that is, of all \(m\times n\) matrices with entries in \(S\)). We use the shorthand notation \(\M_n(S)\) for the set \(\M_{n\times n}(S)\text{.}\)

One common way of describing a set is to list its elements in curly braces, separated by commas; you can use ellipses to indicate a repeated pattern of elements. A few examples are \(\{1,4,\pi\}\text{,}\) \(\{3, 4, 5, \ldots\}\text{,}\) and \(\{\ldots, -4, -2, 0, 2, 4, \ldots\}\text{;}\) the last of these can be written more concisely as \(\{0,\pm 2, \pm 4,\ldots\}\text{.}\) Note that since elements of a set are unordered, the sets \(\{1,4,\pi\}\) and \(\{4,\pi, 1\}\text{,}\) for instance, are identical.

Another method is using set-builder notation. This consists of an element name (or names), followed by a colon (meaning “such that”), followed by a Boolean expression involving the element name(s), all surrounded by curly braces.

Warning1.1.6

The use of a colon to denote “such that” is only valid in the above set-builder notation context. Outside of this context, you should never use a colon to denote “such that”; instead, use the abbreviation “s.t.” or write out the actual words. Conversely, never use one of those ways of indicating “such that” within set-builder notation; always use a colon there. Why? Convention.

For example,

\begin{equation*} \{x\in \Z : x > 4\} \end{equation*}

is the set \(\{5, 6, 7, \ldots\}\text{,}\) while

\begin{equation*} \{z\in \C : |z|=1\} \end{equation*}

is the set of all complex numbers at distance 1 from the origin in the complex plane.

Note1.1.7

If one simply writes \(\{x\,:\,x>4\}\text{,}\) it is unclear what this set is; it could be the set of all integers greater than 4, or the set of all real numbers greater than 4, or something else. When one can, it is better to identify the named element(s) as a member (members) of a known set, such as \(\R\) or \(\Z\text{,}\) whenever possible.

Definition1.1.8

Set \(A\) is a subset of \(B\) (and set \(B\) is a superset of \(A\)) if every element in \(A\) is also in \(B\text{.}\) We denote “\(A\) is a subset of \(B\)” by \(A\subseteq B\text{.}\) Sets \(A\) and \(B\) are said to be equal, and we write \(A=B\text{,}\) if they contain exactly the same elements; equivalently, \(A=B\) if and only if \(A \subseteq B\) and \(B\subseteq A\text{.}\) Set \(A\) is a proper subset of set \(B\) if \(A\subseteq B\) but \(A\neq B\text{;}\) we write this \(A\subsetneq B\text{.}\)

Remark1.1.9

Sometimes the notation \(A\subset B\) is used to indicate that \(A\) is a proper subset of \(B\text{,}\) and sometimes it is simply used to mean that \(A\) is a subset—proper or improper—of \(B\text{.}\) We will not use the notation \(A \subset B\) in this text.

Note1.1.10

One often proves that two sets \(A\) and \(B\) are equal by proving that \(A\subseteq B\) and \(B\subseteq A\text{.}\)

Example1.1.11

We have the following: \(\Z^+ \subseteq \Z \subseteq \Q \subseteq \R \subseteq \C\text{.}\)

Definition1.1.12

The power set of \(A\text{,}\) denoted \(P(A)\text{,}\) is the set of all subsets of \(A\text{.}\) (Note that the power set of any set contains the empty set as an element.)

Warning1.1.13

Be careful to use your curly braces correctly when writing power sets! Remember, the power set of a set is a set of sets.

The following provides a good example of using braces correctly.

Example1.1.14

If \(A=\{a,b\}\text{,}\) then \(P(A)=\{\emptyset, \{a\}, \{b\}, \{a,b\}\}\text{.}\) Note that the element \(\{a,b\}\) of \(P(A)\) could also be written simply as \(A\text{.}\)

Definition1.1.15

  1. If \(A\) and \(B\) are subsets of a set \(U\text{,}\) then the union of \(A\) and \(B\text{,}\) denoted \(A\cup B\text{,}\) is the set \(A\cup B=\{x\in U : x\in A \text{ or } x\in B\};\) the intersection of \(A\) and \(B\text{,}\) denoted \(A\cap B\text{,}\) is the set \(A\cap B=\{x \in U: x\in A \text{ and } x\in B\};\) and the difference of \(A\) and \(B\text{,}\) denoted \(A-B\) (or \(A\setminus B\)), is the set \(A-B=\{x: x\in A \text{ and } x\not\in B\}.\)

  2. More generally, given any collection of subsets \(A_i\) (\(i\) in some index set \(I\)) of a set \(U\text{,}\) the union of the \(A_i\) is

    \begin{equation*} \bigcup_{i\in I}A_i=\{x\in U: x\in A_i \text{ for some } i\in I\}, \end{equation*}

    and the intersection of the \(A_i\) is

    \begin{equation*} \bigcap_{i\in I}A_i=\{x\in U: x\in A_i \text{ for every } i\in I\}. \end{equation*}

  3. Sets \(A\) and \(B\) are disjoint if \(A\cap B=\emptyset\text{.}\) More generally, sets \(A_i\) (\(i\) in some index set \(I\)) are disjoint if

    \begin{equation*} \bigcap_{i\in I}A_i=\emptyset \end{equation*}

    and are mutually disjoint if

    \begin{equation*} A_i\cap A_j=\emptyset \text{ for all } i\neq j \in I. \end{equation*}

Notice that for any subsets \(A\) and \(B\) of a set \(U\text{,}\) \(A\cap B \subseteq A \subseteq A\cup B\) and \(A\cap B \subseteq B \subseteq A\cup B\text{.}\) Also note that if sets \(A_i\) (\(i \in I\)) are mutually disjoint then they are also disjoint, but they may be disjoint without being mutually disjoint. For example, the sets \(\{i, i+1\}\) for \(i\in \Z\) are disjoint but not mutually disjoint. (Do you see why?)

We define one more way of “combining” sets.

Definition1.1.16

Let \(A\) and \(B\) be sets. Then the direct product (or Cartesian product) \(A\times B\) of \(A\) and \(B\) is the set

\begin{equation*} A\times B =\{(a,b): \text{\(a\in A\), \(b\in B\)} \}. \end{equation*}

An element \((a,b)\) of \(A\times B\) is called an ordered pair. More generally, if \(A_1, A_2, \ldots, A_n\) are sets for some \(n\in \Z^+\text{,}\) then the product of the \(A_i\) is

\begin{equation*} A_1\times A_2 \times \cdots \times A_n=\{(a_1, a_2 \ldots, a_n): a_i \in A_i \text{ for } i=1,2, \ldots, n\}; \end{equation*}

the elements \((a_1,a_2,\ldots,a_n)\) of this product are called \(n\)-tuples (or triples, if \(n=3\)). (You can also have products of infinitely many sets, but we will not discuss that in this course.) Finally, if each set \(A_i\) is the same set \(A\text{,}\) we can use the notation \(A^n\) to denote the product

\begin{equation*} A\times A \times \cdots \times A \end{equation*}

of \(n\) copies of \(A\text{.}\)

Example1.1.17

For example, the Cartesian plane is the set \(\R^2\text{,}\) and the set \(\Z \times \R\) consists of exactly the points in the plane with integer \(x\)-coordinates (that is, the points that lie on vertical lines intersecting the \(x\)-axis at integer values).