Abstract Algebra — Chapter 1 Set theory

Part 1 A First Course

Chapter 1
Set theory

1.1. Sets and functions

In these notes, we assume some basic notions from set theory, for which we give only the briefest of reviews. We won’t attempt to define a set formally here. Instead, we simply make some remarks about them. Vaguely, a set is a collection of objects. Not every collection of objects is a set: the “collection” of all sets is not a set. On the other hand, most reasonable collections of objects are sets: the integers, the real numbers, the movies in your DVD collection (seemingly, a soon-to-be dated notion), those are sets.

Sets consist of elements. If $X$ is a set, we write $x \in X$ to mean that $x$ is an element of $X$ (or “ $x$ is in $X$ ”). Similarly, $x \notin X$ means that $x$ is not an element of $X$ (which only really makes sense if both $x$ and the elements of $X$ are elements of some common larger set so they can be compared.)

Examples 1.1.1. §

a.: The empty set $∅$ is the set with no elements.
b.: The set consisting of elements called $1$ , $2$ , and $3$ is denoted ${1, 2, 3}$ , and this notation extends to any finite collection of objects.
c.: The set ${1, 2, 3, \dots}$ of positive integers is again a set.
d.: The real numbers $ℝ$ form a set.

Any collection of elements of a set $X$ is called a subset of $X$ and is a set itself. We write $Y \subseteq X$ to mean that $Y$ is a subset of $X$ . If $Y$ and $Z$ are different subsets of $X$ , then we write $Y \neq Z$ and we say that $Y$ and $Z$ are distinct subsets.

A property $P$ that only some elements of $X$ satisfy allows us to specify a subset of $X$ consisting of elements of $X$ that satisfy $P$ , which we denote in set-theoretic notation by

{x \in X ∣ x satisfies P},

or just ${x ∣ x satisfies P}$ if $X$ is understood.

Example 1.1.2. §

The subset ${n \in ℤ ∣ 2 divides n}$ of $ℤ$ is the set of even integers.

Definition 1.1.3. §

Let $X$ be a set and $Y$ be a subset of $X$ . Then $X - Y$ denotes the complement of $Y$ in $X$ , which is defined as

X - Y = {x \in X ∣ x \notin Y} .

If $Y$ is a subset of $X$ that is not $X$ itself, then it is called a proper subset, and we write $Y \subset X$ (or $Y ⊊ X$ ). Given two subsets $Y$ and $Z$ of a larger set $X$ , we can form their union $Y \cup Z$ and their intersection $Y \cap Z$ , which are also subsets of $X$ .

Definition 1.1.4. §

Given sets $X$ and $Y$ , the direct product $X \times Y$ is the set of pairs $(x, y)$ with $x \in X$ and $y \in Y$ .

In set-theoretic notation, we may write this as

X \times Y = {(x, y) ∣ x \in X, y \in Y} .

Definition 1.1.5. §

A function $f : X \to Y$ from a set $X$ to a set $Y$ is a rule that to each $x \in X$ associates a single element $f (x) \in Y$ , known as the value of $f$ at $x$ .

Notation 1.1.6. §

We sometimes refer to a function as a map, and we sometimes write $f : x \mapsto y$ to indicate that $f (x) = y$ , or in other words that $f$ maps (or sends) $x$ to $y$ .

We can, of course, compose functions, as in the following definition.

Definition 1.1.7. §

Let $X$ , $Y$ , and $Z$ be sets and $f : X \to Y$ and $g : Y \to Z$ functions. The composition (or composite function) $g \circ f : X \to Z$ of $g$ with $f$ is the function such that $(g \circ f) (x) = g (f (x))$ for all $x \in X$ .

Definition 1.1.8. §

Let $f : X \to Y$ be a function.

a.: The function $f$ is one-to-one (or injective, or an injection) if for every $x, y \in X$ such that $f (x) = f (y)$ , one has $x = y$ .
b.: The function $f$ is onto (or surjective, or a surjection) if for every $y \in Y$ , there exists an $x \in X$ such that $f (x) = y$ .
c.: The function $f$ a one-to-one correspondence (or bijective, or a bijection) if it is both one-to-one and onto.

Remark 1.1.9. §

In other words, to say a function $f : X \to Y$ is one-to-one is to say that it sends at most one element of $X$ to any given element of $Y$ . To say that it is onto is to say that it sends at least one element of $X$ to any given element of $Y$ . So, of course, to say that it is a one-to-one correspondence is to say that it sends exactly one element of $X$ to each element of $Y$ .

Examples 1.1.10. §

a.: The map $f : ℤ \to ℤ$ defined by $f (x) = 2 x$ for every $x \in ℤ$ is one-to-one, but not onto.
b.: The function $f : ℝ \to ℝ$ defined by $f (x) = x^{3}$ is a bijection.
c.: The function $f : ℝ \to ℝ$ defined by $f (x) = x \sin (x)$ is onto, but not one-to-one.

Definition 1.1.11. §

a.: A set $X$ is finite if $X$ has only a finite number of elements, and it is infinite otherwise.
b.: If $X$ is a finite set, then the order $| X |$ of $X$ is the number of elements it has.

Proposition 1.1.12. §

Let $X$ and $Y$ be finite sets of the same order, and let $f : X \to Y$ be a function. Then $f$ is one-to-one if and only if it is onto.

Proof.

Let $n = | X |$ , and denote the elements of $X$ by $x_{1}, \dots, x_{n}$ . If $f (x_{i}) = f (x_{j})$ for some $i \neq j$ , then the subset ${f (x_{1}), \dots, f (x_{n})}$ of $Y$ has fewer than $n$ elements, hence cannot equal $Y$ . Conversely, if ${f (x_{1}), \dots, f (x_{n})}$ has fewer than $n$ elements, then $f (x_{i}) = f (x_{j})$ for some $i \neq j$ . Therefore $f$ is not one-to-one if and only if it is not onto, as desired. □

Note that every bijection has an inverse.

Definition 1.1.13. §

If $f : X \to Y$ is a bijection, then we define the inverse of $f$ to be the function $f^{- 1} : Y \to X$ satsifying $f^{- 1} (y) = x$ for the unique $x$ such that $f (x) = y$ .

Given a bijection $f : X \to Y$ , note that

\begin{array}{rcl} f^{- 1} (f (x)) = x & and & f (f^{- 1} (y)) = y \end{array}

for all $x \in X$ and $y \in Y$ . In other words, $f^{- 1} \circ f$ (resp., $f \circ f^{- 1}$ ) is the function that takes every element of $Y$ (resp., $X$ ) to itself.

Example 1.1.14. §

The function $f : ℝ \to ℝ$ defined by $f (x) = x^{3}$ has inverse $f^{- 1} (x) = x^{- 1 ∕ 3}$ .

Often, it is useful to use what is called an indexing set $I$ to define a collection, which is just some given set, like the natural numbers. Given objects $x_{i}$ for each $i \in I$ , we can use set-theoretic notation to define a set consisting of them

{x_{i} ∣ i \in I}

that is in one-to-one correspondence with $I$ via the map that takes $i$ to $x_{i}$ .

Definition 1.1.15. §

Let $X$ be a set and ${Y_{i} ∣ i \in I}$ be a collection of subsets of $X$ indexed by a set $I$ .

a.

The intersection and union of the sets $Y_{i}$ are defined as

\begin{array}{rcl} ⋂_{i \in I} Y_{i} = {x \in X ∣ x \in Y_{i} for all i \in I} & and & ⋃_{i \in I} Y_{i} = {x \in X ∣ x \in Y_{i} for some i \in I}, \end{array}

respectively.

b.

If $Y_{i} \cap Y_{j} = \emptyset$ for every $i, j \in I$ with $i \neq j$ , we say that the sets $Y_{i}$ are disjoint.

c.

If the collection of $Y_{i}$ is disjoint, then their union is called a disjoint union and is often written as

\underset{i \in I}{∐} Y_{i} .

Definition 1.1.16. §

Let ${X_{i} ∣ i \in I}$ be a collection of sets. The direct product $\prod_{i \in I} X_{i}$ of the $X_{i}$ is the set of tuples

\prod_{i \in I} X_{i} = {{(x_{i})}_{i \in I} ∣ x_{i} \in X_{i}} .

In other words, an element of $\prod_{i \in I} X_{i}$ is a choice of one element of $X_{i}$ for each $i \in I$ .

1.2. Relations

In this section, we consider several types of a very general construct called a relation.

Definition 1.2.1. §

A relation $R$ is a subset of $X \times Y$ . We often write $𝑥𝑅𝑦$ to indicate that $(x, y) \in R$ .

Examples 1.2.2. §

a.: The circle $S^{1} = {x^{2} + y^{2} = 1}$ forms a relation in $ℝ \times ℝ$ . As is well-known, a pair $(x, y)$ is in $S^{1}$ if and only if $(x, y) = (\cos 𝜃, \sin 𝜃)$ for some $𝜃 \in [0, 2 π)$ .
b.: The relation $\leq$ on $ℝ \times ℝ$ is given by ${(x, y) ∣ x \leq y}$ .

As a first example, we see that functions can be considered as relations.

Remark 1.2.3. §

A function $f : X \to Y$ gives rise to a relation

Γ_{f} = {(x, f (x)) ∣ x \in X} \subseteq X \times Y,

known as the graph of $f$ . Equivalently, each relation $R$ in $X \times Y$ such that for each $x \in X$ there exists a unique $y \in Y$ with $𝑥𝑅𝑦$ gives rise to a function $f$ defined by $f (x) = y$ (where $𝑥𝑅𝑦$ ).

Example 1.2.4. §

The relation in $ℝ^{2}$ corresponding to $f : ℝ \to ℝ$ is the graph of $f$ in the usual sense.

We will consider two other types of relations.

Definition 1.2.5. §

An equivalence relation $\sim$ on $X$ is a relation in $X \times X$ that satisfies the following properties.

a.: (reflexivity) For all $x \in X$ , we have $x \sim x$ .
b.: (symmetry) For any $x, y \in X$ , we have $x \sim y$ if and only if $y \sim x$ .
c.: (transitivity) If $x, y, z \in X$ satisfy $x \sim y$ and $y \sim z$ , then $x \sim z$ .

Examples 1.2.6. §

a.: Equality is an equivalence relation $=$ on any set $X$ . As a relation, it defines the subset ${(x, x) ∣ x \in X}$ of $X \times X$ .
b.: The relation $\leq$ on $ℝ$ is not an equivalence relation, as it is not symmetric.
c.: Let $n$ be a positive integer, and consider the relation $\equiv_{n}$ on $ℤ$ defined by $a \equiv_{n} b$ if $a - b$ is divisible by $n$ . This is an equivalence relation known as congruence modulo $n$ . We will write $a \equiv b mod n$ in place of $a \equiv_{n} b$ , as is standard.

Definition 1.2.7. §

Let $\sim$ be an equivalence relation on a set $X$ . The equivalence class of $x \in X$ is the set ${y \in X ∣ x \sim y}$ .

Examples 1.2.8. §

a.: The equivalence classes under $=$ on a set $X$ are just the singleton sets ${x}$ for $x \in X$ .
b.: The equivalence class of $3$ under $\equiv_{7}$ on $ℤ$ is ${\dots, - 11, - 4, 3, 10, 17, \dots}$ .

Definition 1.2.9. §

We refer to the set of equivalence classes of $ℤ$ under congruence modulo $n$ as the integers modulo $n$ , and denote it $ℤ ∕ 𝑛ℤ$ . (Note that number theorists usually denote this set $ℤ ∕ 𝑛ℤ$ .) A typical member $\bar{a}$ has the form

\bar{a} = {a + 𝑏𝑛 ∣ b \in ℤ}

for some integer $a$ . An equivalence class $\bar{a}$ is known as a congruence class modulo $n$ .

Lemma 1.2.10. §

The distinct equivalence classes of $X$ under an equivalence relation $\sim$ are disjoint, and $X$ is the disjoint union of its distinct equivalence classes.

Proof.

The second statement follows from the first once we known that different equivalence classes are disjoint, since every $x \in X$ is in some equivalence class. For the first statement, suppose that $x$ and $y$ are elements of $X$ , and let $E_{x}$ and $E_{y}$ denote their respective equivalence classes under $\sim$ . If $E_{x}$ and $E_{y}$ are not disjoint, then there exists $z \in E_{x} \cap E_{y}$ , so $x \sim z$ and $y \sim z$ . But then $z \sim x$ by symmetry of $\sim$ , and so for any $w \in X$ , we have $x \sim w$ implies $z \sim w$ by transitivity of $\sim$ . Given that and using $y \sim z$ , we then have $y \sim w$ , again by transitivity. Hence $E_{x} \subseteq E_{y}$ . But since $x$ and $y$ are interchangeable in the last sentence, we have $E_{y} \subseteq E_{x}$ as well. Therefore, $E_{x} = E_{y}$ , which is to say any two equivalence classes of $X$ are either distinct or equal. □

Definition 1.2.11. §

Let $X$ be a set and $\sim$ an equivalence relation on $X$ .

a.: For any equivalence class $E$ of $\sim$ , a representative of $E$ is just an element of $E$ .
b.: A set of representatives (of the equivalence classes) of $X$ under $⋆$ is a subset $S$ of $X$ such that each equivalence class of $X$ contains exactly one element of $S$ .

Example 1.2.12. §

The set ${0, 1, 2, \dots, n - 1}$ is a set of representatives of $ℤ$ under congruence modulo $n$ .

Definition 1.2.13. §

A partial ordering on a set $X$ is a relation $\leq$ in $X \times X$ that satisfies the following properties.

i.: (reflexivity) For all $x \in X$ , we have $x \leq x$ .
ii.: (antisymmetry) If $x, y \in X$ satisfy $x \leq y$ and $y \leq x$ , then $x = y$ .
iii.: (transitivity) If $x, y, z \in X$ satisfy $x \leq y$ and $y \leq z$ , then $x \leq z$ .

A set $X$ together with a partial ordering $\leq$ is referred to as a partially ordered set.

Examples 1.2.14. §

a.: The relation $\leq$ on $ℝ$ is a partial ordering, as is $\geq$ .
b.: The relation $<$ on $ℝ$ is not a partial ordering, as it is not reflexive.
c.: The relation $\subseteq$ on the set of subsets $𝒫_{X}$ of any set $X$ , which is known as the power set of $X$ , is a partial ordering.
d.: The relation $=$ is a partial ordering on any set.
e.: The relation $\equiv_{n}$ is not a partial ordering on $ℤ$ , as $0$ and $n$ are congruent, but not equal.

Given a partial ordering $\leq$ on a set $X$ , we can speak of minimal and maximal elements of $X$ .

Definition 1.2.15. §

Let $X$ be a set with a partial ordering $\leq$ .

a.: A minimal element in $X$ (under $\leq$ ) is an element $x \in X$ such that if $z \in X$ and $z \leq x$ , then $z = x$ .
b.: A maximal element $y \in X$ is an element such that if $z \in X$ and $y \leq z$ , then $z = y$ .

Minimal and maximal elements need not exist, and when they exist, they need not be unique. Here are some examples.

Examples 1.2.16. §

a.: The set $ℝ$ has no minimal or maximal elements under $\leq$ .
b.: The interval $[0, 1)$ in $ℝ$ has the minimal element $0$ but no maximal element under $\leq$ .
c.: The power set $𝒫_{X}$ of $X$ has the minimal element $∅$ and maximal element $X$ under $\subseteq$ .
d.: Under $=$ on $X$ , every element is both minimal and maximal.
e.: Consider the set $S$ of nonempty sets of the integers $ℤ$ , with partial ordering $\subseteq$ . The minimal elements of $S$ are exactly the singleton sets ${n}$ for $n \in ℤ$ .

One can ask for a condition under which maximal (or minimal) elements exist. To phrase such a condition, we need two more notions.

Definition 1.2.17. §

Let $X$ be a set with a partial ordering $\leq$ . A chain in $X$ is a subset $C$ of $X$ such that if $x, y \in C$ , then either $x \leq y$ or $y \leq x$ .

That is, a chain is a subset under which every two elements can be compared by the partial ordering.

Example 1.2.18. §

The power set $𝒫_{X}$ of $X = {1, 2, 3}$ is not a chain, as we have neither ${1, 2}$ contained in ${2, 3}$ , nor ${2, 3}$ contained in ${1, 2}$ . However, its subset ${\emptyset, {1}, {1, 2}, {1, 2, 3}}$ does form a chain.

Example 1.2.19. §

Any subset of $ℝ$ forms a chain under $\leq$ .

The previous example leads us to the following definition, which we mention primarily as a remark.

Definition 1.2.20. §

If $X$ is itself a chain under $\leq$ , then $\leq$ is said to be a total ordering on $X$ .

We need the notion of bounds on subsets of a partially ordered set.

Definition 1.2.21. §

Let $X$ be a set with a partial ordering $\leq$ . Let $A$ be a subset of $X$ . An upper bound on $A$ under $\leq$ is an element $x \in X$ such that $a \leq x$ for all $a \in A$ .

That is, an upper bound on a subset is an element of the set that is at least as large as every element in the subset. Note that the upper bound need not, but can, be contained in the subset itself. (And, of course, lower bounds could have been defined similarly.)

Examples 1.2.22. §

a.: The subset $[0, 1)$ of $ℝ$ has an upper bound $1 \in ℝ$ under $\leq$ . In fact, any element $x \geq 1$ is an upper bound for $[0, 1)$ . The subset $[0, 1]$ has the same upper bounds.
b.: The subset $ℚ$ of $ℝ$ has no upper bound under $\leq$ .

We now come to Zorn’s lemma, which is equivalent to the so-called “axiom of choice”, and as such, is as much an axiom as it is a theorem (and more of a theorem than it is a lemma). Some, though far from most, mathematicians prefer not to include the axiom of choice among the axioms of set theory, fearing that the resulting collection of axioms may be logically incompatible. For the purposes of this book, we will have no such qualms, and we state Zorn’s lemma without proof: the reader may take it as an axiom.

Theorem 1.2.23 (Zorn’s lemma). §

Let $X$ be a set with a partial ordering $\leq$ , and suppose that every chain in $X$ has an upper bound. Then $X$ contains a maximal element.

Later on in these notes, we will see a couple of examples where Zorn’s lemma can be used to produce the existence of maximal elements in situations of use to algebraists. Zorn’s lemma is the form of the axiom of choice considered most conducive to applications in algebra.

Finally, let us consider the notion of generation. We have the following rather obvious lemma.

Lemma 1.2.24. §

Let $X$ be a set and $S$ be a subset. Let $P$ be a subset of $𝒫_{X}$ containing $X$ such that $P$ is closed under intersection, and let $P_{S}$ be the (nonempty) subset of elements of $P$ containing $S$ . Then the intersection of the elements of $P_{S}$ is the unique minimal element of $P_{S}$ . That is, it is the smallest subset of $X$ in $P$ containing $S$ .

We think of $P$ of some property of certain subsets of $X$ that $X$ itself satisfies, where a subset of $X$ is in $P$ it has the property. As $P$ is closed under intersection, for any subset $S$ of $X$ , we may speak of the smallest subset that contains $S$ and has property $P$ . We then think of this subset as the subset of $X$ with property $P$ generated by $S$ . For instance, we have the following.

Example 1.2.25. §

Let $X$ be a set and $S \subseteq X \times X$ be a relation on $X$ . The set of equivalence relations on $X$ is closed under intersection, as one may easily check, and $X \times X$ is an equivalence relation. Thus, the intersection all equivalence relations containing $S$ is the smallest equivalence relation $\sim_{S}$ containing $S$ . We call $\sim_{S}$ the equivalence relation generated by $S$ .

Two elements $x, y \in X$ are equivalent under $\sim_{S}$ if and only if there exist a sequence of elements $z_{0}, \dots, z_{n} \in X$ with $x = z_{0}$ and $y = z_{n}$ for some $n \geq 1$ such that $z_{i} = z_{i + 1}$ , $(z_{i}, z_{i + 1}) \in S$ , or $(z_{i + 1}, z_{i}) \in S$ for every $0 \leq i \leq n - 1$ . To see this, one checks two things: first, that what we have just described defines an equivalence relation on $S$ , and secondly, that any equivalence relation on $S$ must contain every such pair $(x, y)$ .

1.3. Binary operations

To give context to the term “binary operation”, which we study in this section, here is what one might refer to simply as an “operation”.

Definition 1.3.1. §

A (left) operation $⋆$ of a set $X$ on a set $Y$ is a function $⋆ : X \times Y \to Y$ .

Notation 1.3.2. §

The value $⋆ (x, y)$ of $(x, y) \in X \times Y$ under an operation $⋆ : X \times Y \to Y$ is denoted $x ⋆ y$ . It is often referred to as the product of $x$ and $y$ under $⋆$ (when confusion does not arise from this language).

Example 1.3.3. §

The set $ℝ$ acts on $ℝ^{n}$ for any $n \geq 1$ by left diagonal multiplication. That is, we have

a \cdot (x_{1}, \dots, x_{n}) = (a x_{1}, \dots, a x_{n})

for $a \in ℝ$ and $(x_{1}, \dots, x_{n}) \in ℝ^{n}$ . Geometrically, this is the action of scaling of a vector.

If $Z$ is a subset of $Y$ , we can ask if the values $x ⋆ z$ for $x \in X$ and $z \in Z$ land in $Z$ .

Definition 1.3.4. §

Let $⋆ : X \times Y \to Y$ be a (left) operation of $X$ on $Y$ . A subset $Z$ of $Y$ is said to be closed under $⋆$ (or, left multiplication by $⋆$ ) if $x ⋆ z \in Z$ for all $x \in X$ and $z \in Z$ .

Example 1.3.5. §

Consider the operation $\cdot : ℤ \times ℤ \to ℤ$ of multiplication. The subset $E$ of even numbers in $ℤ$ is closed under this operation, which is to say left multiplication by integers. That is, if $a \in ℤ$ and $b \in E$ , then $𝑎𝑏 \in E$ . However, the subset $O$ of odd numbers is not closed under this operation. For instance, $2 \in ℤ$ and $1 \in O$ , but $2 \cdot 1 = 2 \notin O$ .

Definition 1.3.6. §

Let $⋆ : X \times Y \to Y$ be an operation and $Z$ be a subset of $Y$ that is closed under $⋆$ . Then the restriction of $⋆$ to an operation of $X$ on $Z$ is the operation $⋆_{Z} : X \times Z \to Z$ defined by $x ⋆_{Z} z = x ⋆ z$ for all $x \in X$ and $z \in Z$ .

In this text, we will most often encounter binary operations.

Definition 1.3.7. §

A binary operation on a set $X$ is an operation of $X$ on itself.

Remarks 1.3.8. §

Let $X$ be a set.

a.: A binary operation $⋆$ on $X$ is simply a function $⋆ : X \times X \to X$ .
b.: We often refer to a binary operation on $X$ more simply as an “operation” on $X$ , the fact that $X$ is operating on itself being implied.

Examples 1.3.9. §

The following are binary operations.

a.: Addition (or subtraction) $+$ on $ℤ$ , $ℚ$ , $ℝ$ , $ℂ$ , $ℝ^{n}$ , and $m$ -by- $n$ matrices $M_{𝑚𝑛} (ℝ)$ with entires in $ℝ$ for any $m, n \geq 1$ .
b.: Multiplication $\cdot$ on $ℤ$ , $ℚ$ , $ℝ$ , $ℂ$ , and square $n$ -by- $n$ matrices $M_{n} (ℝ)$ for any $n \geq 1$ .
c.: Composition $\circ$ on the set $Maps (X, X)$ of maps from a set $X$ to itself, e.g., $X = ℝ$ .
d.: Union $\cup$ and intersection $\cap$ on power set $𝒫_{X}$ of any set $X$ .

Examples 1.3.10. §

a.: Exponentiation is not a binary operation on $ℂ$ , as ${(- 1)}^{1 ∕ 2}$ , for instance, has two possible values. It is therefore not well-defined.
b.: Addition is not a binary operation on the set $ℝ^{\times}$ of nonzero real numbers, as $- 1 + 1 = 0$ , and $0 \notin ℝ^{\times}$ . We say that $ℝ^{\times}$ is not closed under addition.
c.: Division in not a binary operation on $ℝ$ , as division by $0$ is not defined, but division is a binary operation on $ℝ^{\times}$ .

We can define a binary operation on a finite set via a multiplication table.

Example 1.3.11. §

Consider the set $X = {a, b, c}$ . The following table defines a binary operation $⋆$ on $X$ :

$⋆$	$a$	$b$	$c$



$a$	$b$	$c$	$a$

$b$	$a$	$c$	$c$

$c$	$b$	$a$	$c$

The entry in row $b$ and column $a$ is, by way of example, $b ⋆ a$ , and therefore, $b ⋆ a = a$ . On the other hand, $a ⋆ b$ is located in the row corresponding to $a$ and column of $b$ , and hence $a ⋆ b = c$ .

In the previous example, we could have filled in the nine entries in the bottom right 3-by-3 square arbitrarily with elements of $X$ , as there are no conditions of the values of a binary operation. Often, it is useful to impose conditions that give additional structure.

Definition 1.3.12. §

Let $X$ be a set.

a.

A binary operation $⋆$ on $X$ is associative if

(x ⋆ y) ⋆ z = x ⋆ (y ⋆ z)

for all $x, y, z \in X$ .

b.

A binary operation $⋆$ on $X$ is commutative if

x ⋆ y = y ⋆ x

for all $x, y \in X$ .

Examples 1.3.13. §

a.: Addition is associative and commutative on $ℤ$ , $ℚ$ , $ℝ$ , $ℂ$ , $ℝ^{n}$ , $M_{𝑚𝑛} (ℝ)$ , and $Maps (ℝ, ℝ)$ .
b.: Subtraction is neither associative nor commutative on the sets $ℤ$ , $ℚ$ , $ℝ$ , $ℂ$ , $ℝ^{n}$ , $M_{𝑚𝑛} (ℝ)$ , and $Maps (ℝ, ℝ)$ .
c.: Multiplication is associative and commutative on $ℤ$ , $ℚ$ , $ℝ$ , $ℂ$ , $ℝ^{n}$ , $Maps (ℝ, ℝ)$ , and is associative but not commutative on $M_{n} (ℝ)$ for $n \geq 2$ .
d.: Union and intersection are associative and commutative binary operations on $𝒫_{X}$ .
e.: Composition on $Maps (X, X)$ is an associative binary operation, but it is not commutative if $X$ has at least $3$ elements.

Definition 1.3.14. §

Let $X$ be a set and $⋆$ a binary operation on $X$ . Two elements $x, y \in X$ are said to commute under $⋆$ if $x ⋆ y = y ⋆ x$ .

Commutativity of a binary operation on a finite set can be seen on its mutliplication table, as the table is then symmetric across the diagonal. Associativity is hard to see, but it is a strong condition. Here are some examples.

Examples 1.3.15. §

The following are tables of binary operations on the set ${a, b}$ :

$⋆$	$a$	$b$



$a$	$b$	$a$

$b$	$b$	$a$

$*$	$a$	$b$



$a$	$a$	$b$

$b$	$b$	$a$

$◇$	$a$	$b$



$a$	$b$	$a$

$b$	$a$	$a$

Of these, only $*$ is associative, while only $*$ and $◇$ are commutative, since $a$ and $b$ do not commute under $⋆$ .

Example 1.3.16. §

We can define operations $+$ and $\cdot$ on $ℤ ∕ 𝑛ℤ$ as follows. Let $a, b \in ℤ$ , and recall that we denote their equivalence classes under congruence modulo $n$ by $\bar{a}, \bar{b} \in ℤ ∕ 𝑛ℤ$ . We define $\bar{a} + \bar{b} = \bar{a + b}$ and $\bar{a} \cdot \bar{b} = \bar{a \cdot b}$ . These are well-defined, as if $c$ and $d$ are congruent modulo $n$ to $a$ and $b$ , respectively, then $c + d \equiv a + b mod n$ and $c \cdot d \equiv a \cdot b mod n$ .

Definition 1.3.17. §

A set $X$ together with a binary operation $⋆ : X \times X \to X$ is called a binary structure, and we write it as a pair $(X, ⋆)$ .

Remark 1.3.18. §

If $(X, ⋆)$ is a binary structure, then we often refer to $X$ as the underlying set.

Example 1.3.19. §

The pair $(ℤ ∕ 𝑛ℤ, +)$ is a binary structure, as is $(ℤ ∕ 𝑛ℤ, \cdot)$ .

Definition 1.3.20. §

Let $(X, ⋆)$ be a binary structure. A subset $A$ is said to be closed under the binary operation $⋆$ if $a ⋆ b \in A$ for all $a, b \in A$ .

Definition 1.3.21. §

Let $(X, ⋆)$ be a binary structure and $A$ a closed subset of $X$ . Then the restriction of $⋆$ to $A$ is a binary operation $⋆_{A} : A \times A \to A$ defined by $a ⋆_{A} b = a ⋆ b$ for all $a, b \in A$ . We usually denote $⋆_{A}$ more simply by $⋆$ .

Remark 1.3.22. §

If $(X, ⋆)$ is a binary operation and $A$ is a closed subset of $X$ , then $(A, ⋆)$ is a binary structure as well.

Examples 1.3.23. §

a.: The subsets $ℤ$ , $ℚ$ , and $ℝ$ of $ℂ$ are closed under the binary operation $+$ .
b.: The subset $[- 1, 1]$ of $ℝ$ is not closed under $+$ , though it is under $\cdot$ .
c.: The set of all nonempty subsets of a set $X$ is closed under the binary operation $\cup$ on $𝒫_{X}$ , but not under the operation $\cap$ (unless $X$ has fewer than two elements).
d.: The matrices in $M_{n} (ℝ)$ with determinant $1$ are closed under multiplication. The resulting binary structure is denoted ${SL}_{n} (ℝ)$ .

Remark 1.3.24. §

If $⋆ : X \times X \to X$ is a binary operation, then we can also think of it as an operation. However, the notions of a subset $A$ of $X$ being closed under $⋆$ as a binary operation and being closed under $⋆$ as an operation do not in general coincide. The first says that $⋆$ restricts to a binary operation $⋆ : A \times A \to A$ , while the second says that $⋆$ restricts to an operation $⋆ : X \times A \to A$ . In other words, the first requires only that the product of any two elements of $A$ lands in $A$ (under $⋆$ ), while the second says that the product $x ⋆ a$ lands in $A$ for any $x \in X$ and any $a \in A$ , which is a stronger condition.

Example 1.3.25. §

Consider the set $ℤ$ and the binary operation $\cdot$ of multiplication on it. The set of odd numbers $E$ is closed under multiplication thought of as a binary operation, since the product of any two odd numbers is odd. However, it is not closed $\cdot$ thought of as an operation of $ℤ$ on itself, since the product of an even number and an odd number is not odd (as in Example 1.3.5).

Look for similarities in the following tables of binary structures with underlying sets of order $3$ .

$+$	$0$	$1$	$2$



$0$	$0$	$1$	$2$

$1$	$1$	$2$	$0$

$2$	$2$	$0$	$1$

$⋆$	$a$	$b$	$c$



$a$	$a$	$b$	$c$

$b$	$b$	$c$	$a$

$c$	$c$	$a$	$b$

In fact, if we replace $+$ by $⋆$ , $0$ by $a$ , $1$ by $b$ , and $2$ by $c$ , the first table becomes the second. In a sense, these binary operations are the “same”. We give this notation of sameness a technical definition. Note that to be the same in this sense, there must exist a bijection between the sets: i.e., if they are finite, they must have the same number of elements.

Definition 1.3.26. §

Let $(X, ⋆)$ and $(Y, *)$ be binary structures. We say that they are isomorphic if there exists a bijection $f : X \to Y$ such that

f (a ⋆ b) = f (a) * f (b)

for all $a, b \in X$ . We then say that $f$ is an isomorphism.

Remark 1.3.27. §

If we remove the condition of bijectivity in Definition 1.3.26, then the map $f : X \to Y$ with $f (a ⋆ b) = f (a) * f (b)$ is called a homomorphism of binary structures.

In the above example $f (0) = a$ , $f (1) = b$ , and $f (2) = c$ , and the condition that $f (x + y) = f (x) ⋆ f (y)$ for all $x, y \in {0, 1, 2}$ is exactly that the multiplication tables match.

Examples 1.3.28. §

a.

The map $f : ℤ \to ℤ$ defined by $f (n) = - n$ defines an isomorphism from $(ℤ, +)$ to itself.

b.

The map $f : ℤ \to ℤ$ defined by $f (n) = 2 n$ is not an isomorphism from $(ℤ, +)$ to itself. It satisfies $f (m + n) = f (m) + f (n)$ , but it is not onto.

c.

Let $ℝ_{> 0} = {x \in ℝ ∣ x > 0}$ . Define $f : ℝ \to ℝ_{> 0}$ by $f (x) = e^{x}$ . This is an isomorphism from $(ℝ, +)$ to $(ℝ_{> 0}, \cdot)$ , since

e^{x + y} = e^{x} e^{y}

for all $x, y \in ℝ$ .

d.

The map $f : ℝ \to ℝ$ defined by $f (x) = x^{3}$ is not an isomorphism from $(ℝ, +)$ to itself, as

f (1 + 1) = 8 \neq 2 = f (1) + f (1) .

On the other hand, the same map does define an isomorphism from $(ℝ, \cdot)$ to $(ℝ, \cdot)$ .

We have the following lemma.

Lemma 1.3.29. §

Suppose that $f$ is an isomorphism from $(X, ⋆)$ to $(Y, *)$ . Then the inverse $f^{- 1}$ of $f$ is an isomorphism from $(Y, *)$ to $(X, ⋆)$ .

Proof.

Let $y_{1}, y_{2} \in Y$ . Then there exists $x_{1}, x_{2} \in X$ with $f (x_{1}) = y_{1}$ and $f (x_{2}) = y_{2}$ We have

f^{- 1} (y_{1}) ⋆ f^{- 1} (y_{2}) = x_{1} ⋆ x_{2},

and

f (x_{1} ⋆ x_{2}) = f (x_{1}) * f (x_{2}) = y_{1} * y_{2},

x_{1} ⋆ x_{2} = f^{- 1} (y_{1} * y_{2}),

as desired. □

Example 1.3.30. §

The inverse of $f : ℝ \to ℝ_{> 0}$ with $f (x) = e^{x}$ is $f^{- 1} (x) = \log (x)$ , which satisfies

\log (x \cdot y) = \log (x) + \log (y)

for $x, y \in ℝ_{> 0}$ .

In fact, the properties of being isomorphic puts an equivalence relation on any set of binary structures.

Example 1.3.31. §

The set of representatives for the isomorphism classes (i.e., equivalence classes under isomorphism) of binary structures on the set ${a, b}$ has $10$ elements. That is, one can construct at most 10 tables for binary operations on ${a, b}$ that give binary structures, no two of which are isomorphic, as the reader can check.