Abstract Algebra/Sets

Sets

In the so-called naive set theory, which is sufficient for the purpose of studying abstract algebra, the notion of a set is not rigorously defined. We describe a set as a well-defined aggregation of objects, which are referred to as members or elements of the set. If a certain object is an element of a set, it is said to be contained in that set. The elements of a set can be anything at all, but in the study of abstract algebra, elements are most frequently numbers or mathematical structures. The elements of a set completely determine the set, and so sets with the same elements as each other are equal. Conversely, sets which are equal contain the same elements.

For an element $x$ and a set $A$, we can say either $x\in A$, that is, $x$ is contained in $A$, or $x\not \in A$, that is, $x$ is not contained in $A$. To state that multiple elements $a,b,c,\ldots ,n$ are contained in $A$, we write $a,b,c,\ldots ,n\in A$.

The axiom of extensionality

Using this notation and the symbol $\rightarrow$, which represents logical implication, we can restate the definition of equality for two sets $A$ and $B$ as follows:

$A=B$ if and only if $x\in A\rightarrow x\in B$ and $x\in B\rightarrow x\in A$.

This is known as the axiom of extensionality.

Comprehensive notation

If it is not possible to list the elements of a set, it can be defined by giving a property that its elements are sole to possess. The set of all objects $x$ with some property $Q(x)$ can be denoted by $\{x:Q(x)\}$. Similarly, the set of all elements $x$ of a set $A$ with some property $Q(x)$ can be denoted by $\{x\in A:Q(x)\}$. The colon : here is read as "such that". The vertical bar | is synonymous with the colon in similar contexts. This notation will appear quite often in the rest of this book, so it is important for the readers to familiarize themselves with this now.

As an example of this notation, the set of integers can be written as $\mathbb {Z} =\{x:x{\text{ is an integer}}\}$, and the set of even integers can be written as $\{x\in \mathbb {Z} :x{\text{ is even}}\}$.

Set inclusion

For two sets $A$ and $B$, we define set inclusion as follows: $A$ is included in, or a subset of, $B$, if and only if every member of $A$ is a member of $B$. In other words,

$A\subseteq B\Leftrightarrow x\in A\rightarrow x\in B$

where the symbol $\subseteq$ denotes "is a subset of", and $\Leftrightarrow$ denotes "if and only if".

By the aforementioned axiom of extensionality, one finds that $A=B\Leftrightarrow A\subseteq B{\mbox{ and }}B\subseteq A$.

The empty set

One can define an empty set, written $\varnothing$, such that $\forall x(x\not \in \varnothing )$, where $\forall$ denotes universal quantification (read as "for all" or "for every"). In other words, the empty set is defined as the set which contains no elements. The empty set can be shown to be unique.

Since the empty set contains no elements, it can be shown to be a subset of every set. Similarly, no set but the empty set is a subset of the empty set.

Proper set inclusion

For two sets $A$ and $B$, we can define proper set inclusion as follows: $A$ is a proper subset of $B$ if and only if $A$ is a subset of $B$, and $A$ does not equal $B$. In other words, there is at least one member in $B$ not contained in $A$

$A\subset B\Leftrightarrow (A\subseteq B\land A\neq B)$,

where the symbol $\subset$ denotes "is a proper subset of" and the symbol $\land$ denotes logical and.

Cardinality of sets

The cardinality of a set $A$, denoted by $|A|$, can be said informally to be a measure of the number of elements in $A$. However, this description is only rigorously accurate for finite sets. To find the cardinality of infinite sets, more sophisticated tools are needed.

Set intersection

For sets $A$ and $B$, we define the intersection of $A$ and $B$ by the set $A\cap B$ which contains all elements which are common to both $A$ and $B$. Symbolically, this can be stated as follows:

$A\cap B=\{x\mid x\in A{\mbox{ and }}x\in B\}$.

Because every element of $A\cap B$ is an element of $A$ and an element of $B$, $A\cap B$ is, by the definition of set inclusion, a subset of $A$ and $B$.

If the sets $A$ and $B$ have no elements in common, they are said to be disjoint sets. This is equivalent to the statement that $A$ and $B$ are disjoint if $A\cap B=\emptyset$.

Set intersection is an associative and commutative operation; that is, for any sets $A$, $B$, and $C$, $(A\cap B)\cap C=A\cap (B\cap C)$ and $A\cap B=B\cap A$.

By the definition of intersection, one can find that $A\cap \emptyset =\emptyset$ and $A\cap A=A$. Furthermore, $A\subseteq B\Leftrightarrow A\cap B=A$.

One can take the intersection of more than two sets at once; since set intersection is associative and commutative, the order in which these intersections are evaluated is irrelevant. If $A_{i}$ are sets for every $i\in I$, we can denote the intersection of all $A_{i}$ by

$\bigcap _{i\in I}A_{i}=\{x\mid (\forall i\in I)x\in A_{i}\}$

In cases like this, $I$ is called an index set, and $A_{i}$ are said to be indexed by $I$.

In the case of $I=\{1,2,...,n\}$ one can either write $A_{1}\cap A_{2}\cap A_{3}\cap \cdots \cap A_{n}$ or

$\bigcap _{i=1}^{n}A_{i}$.

Set union

For sets $A$ and $B$, we define the union of $A$ and $B$ by the set $A\cup B$ which contains all elements which are in either $A$ or $B$ or both. Symbolically,

$A\cup B=\{x\mid x\in A{\mbox{ or }}x\in B\}$.

Since the union $A\cup B$ of sets $A$ and $B$ contains the elements of $A$ and $B$, $A\subseteq A\cup B$ and $B\subseteq A\cup B$.

Like set intersection, set union is an associative and commutative operation; for any sets $A$, $B$, and $C$, $(A\cup B)\cup C=A\cup (B\cup C)$ and $A\cup B=B\cup A$.

By the definition of union, one can find that $A\cup \emptyset =A\cup A=A$. Furthermore, $A\subseteq B\Leftrightarrow A\cup B=B$.

Just as with set intersection, one can take the union of more than two sets at once; since set union is associative and commutative, the order in which these unions are evaluated is irrelevant. Let $A_{i}$ be sets for all $i\in I$. Then the union of all the $A_{i}$ is denoted by

$\bigcup _{i\in I}A_{i}=\{x\mid (\exists i\in I)x\in A_{i}\}$

(Where $\exists$ may be read as "there exists".)

For the union of a finite number of sets $A_{1},A_{2},A_{3},\ldots ,A_{n}$, that is, $I=\{1,2,...,n\}$ one can either write $A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}$ or abbreviate this as

$\bigcup _{i=1}^{n}A_{i}$.

Distributive laws

Set union and set intersection are distributive with respect to each other. That is,

$A\cap (B\cup C)=(B\cup C)\cap A=(A\cap B)\cup (A\cap C)$ and

$A\cup (B\cap C)=(B\cap C)\cup A=(A\cup B)\cap (A\cup C)$.

Cartesian product

The Cartesian product of sets $A$ and $B$, denoted by $A\times B$, is the set of all ordered pairs which can be formed with the first object in the ordered pair being an element of $A$ and the second being an element of $B$. This can be expressed symbolically as

$A\times B=\{(x,y)\mid x\in A{\mbox{ and }}y\in B\}$.

Since different ordered pairs result when one exchanges the objects in the pair, the Cartesian product is not commutative. The Cartesian product is also not associative. The following identities hold for the Cartesian product for any sets $A,B,C,D$:

$(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$,

$(A\cup B)\times (C\cup D)=(A\times C)\cup (A\times D)\cup (B\times C)\cup (B\times D)$,

$A\times (B\cap C)=(A\times B)\cap (A\times C)$,

$A\times (B\cup C)=(A\times B)\cup (A\times C)$.

The Cartesian product of any set and the empty set yields the empty set; symbolically, for any set $A$, $A\times \emptyset =\emptyset \times A=\emptyset$.

The Cartesian product can easily be generalized to the n-ary Cartesian product, which is also denoted by $\times$. The n-ary Cartesian product forms ordered n-tuples from the elements of $n$ sets. Specifically, for sets $A_{1},A_{2},A_{3},\ldots ,A_{n}$,

$A_{1}\times A_{2}\times A_{3}\times \cdots \times A_{n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in A_{i}\}$.

This can be abbreviated as

$\prod _{i=1}^{n}A_{i}$.

In the n-ary Cartesian product, each $x_{i}$ is referred to as the $i$-th coordinate of $(x_{1},\ldots ,x_{n})$.

In the special case where all the factors are the same set $A$, we can generalize even further. Let $A^{\Omega }$ be the set of all functions $f\,:\,\Omega \rightarrow A$. Then, in analogy with the above, $A^{\Omega }$ is effectively the set of "$\Omega$-tuples" of elements in $A$, and for each such function $f$ and each $i\in \Omega$, we call $f(i)$ the $i$-th coordinate of $f$. As one might expect, in the simple case when $\Omega =\{1,2,...,n\}$ for an integer $n$, this construction is equivalent to $\prod _{i=1}^{n}A$, which we can abbreviate further as $A^{n}$. We also have the important case of $\Omega =\mathbb {N}$, giving rise to the set of all infinite sequences of elements of $A$, which we can denote by $A^{\infty }$. We will need this construction later, in particular when dealing with polynomial rings.

Disjoint union

Let $A$ and $B$ be any two sets. We then define their disjoint union, denoted $A\coprod B$ to be the following: First create copies $A^{\prime }$ and $B^{\prime }$ of $A$ and $B$ such that $A^{\prime }\cap B^{\prime }=\emptyset$. Then define $A\coprod B=A^{\prime }\cup B^{\prime }$. Notice that this definition is not explicit, like the other operations defined so far. The definition does not output a single set, but rather a family of sets. However, these are all "the same" in a sense which will be defined soon. In other words, there exists bijective functions between them.

Luckily, if a disjoint union is needed for explicit computation, one can easily be constructed, for example $A\coprod B=(\{0\}\times A)\cup (\{1\}\times B)$.

Set difference

The set difference, or relative set complement, of sets $A$ and $B$, denoted by $A\setminus B$, is the set of elements contained in $A$ which are not contained in $B$. Symbolically,

$A\setminus B=\{x\mid x\in A{\mbox{ and }}x\not \in B\}$.

By the definition of set difference, $A\setminus B\subseteq A$.

The following identities hold for any sets $A,B,C$:

$A\setminus B=A\Leftrightarrow A\cap B=\emptyset$,

$A\setminus B=\emptyset \Leftrightarrow A\subseteq B$,

$A\setminus B=A\setminus C\Leftrightarrow A\cap B=A\cap C$,

$A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)$,

$A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$,

$A\setminus (B\setminus C)=(C\cap A)\cup (A\setminus B)$,

$A\setminus \emptyset =A$,

$A\setminus A=\emptyset$,

$\emptyset \setminus A=\emptyset$.

The set difference of two Cartesian products can be found as $(A\times B)\setminus (C\times D)=[A\times (B\setminus D)]\cup [(A\setminus C)\times B]$.

The universal set and set complements

We define some arbitrary set $U$ for which every set under consideration is a subset of $U$ as the universal set, or universe. The complement of any set is then defined to be the set difference of the universal set and that set. That is, for any set $A\subseteq U$, the complement of $A$ is given by $A^{C}=U\setminus A$. The following identities involving set complements hold true for any sets $A$ and $B$:

De Morgan's laws for sets:

$(A\cup B)^{C}=A^{C}\cap B^{C}$,

$(A\cap B)^{C}=A^{C}\cup B^{C}$,

Double complement law:

$A^{CC}=A$,

Complement properties:

$A\cup A^{C}=U$,

$A\cap A^{C}=\emptyset$,

$\emptyset ^{C}=U$,

$U^{C}=\emptyset$,

$A\subseteq B\rightarrow B^{C}\subseteq A^{C}$.

The set complement can be related to the set difference with the identities $A\setminus B=A\cap B^{C}$ and $(A\setminus B)^{C}=A^{C}\cup B$.

Symmetric difference

For sets $A$ and $B$, the symmetric set difference of $A$ and $B$, denoted by $A\bigtriangleup B$ or by $A\ominus B$, is the set of elements which are contained either in $A$ or in $B$ but not in both of them. Symbolically, it can be defined as

$A\bigtriangleup B=\{x:(x\in A)\oplus (x\in B)\}.$

More commonly, it is represented as

$A\bigtriangleup B=(A\setminus B)\cup (B\setminus A)$ or as

$A\bigtriangleup B=(A\cup B)\setminus (A\cap B)$.

The symmetric difference is commutative and associative so that $A\bigtriangleup B=B\bigtriangleup A$ and $(A\bigtriangleup B)\bigtriangleup C=A\bigtriangleup (B\bigtriangleup C)$. Every set is its own symmetric-difference inverse, and the empty set functions as an identity element for the symmetric difference, that is, $A\bigtriangleup A=\emptyset$ and $A\bigtriangleup \emptyset =A$. Furthermore, $A\bigtriangleup B=\emptyset$ if and only if $A=B$.

Set intersection is distributive over the symmetric difference operation. In other words, $A\cap (B\bigtriangleup C)=(A\cap B)\bigtriangleup (A\cap C)$.

The symmetric difference of two set complements is the same as the symmetric difference of the two sets: $A^{C}\bigtriangleup B^{C}=A\bigtriangleup B$.

Notation for specific sets

Commonly-used sets of numbers in mathematics are often denoted by special symbols. The conventional notations used in this book are given below.

Natural numbers with 0: $\mathbb {N} _{0}=\{0,1,2,\ldots \}$ or $\mathbb {N} =\{0,1,2,\ldots \}$
Natural numbers without 0: $\mathbb {N} ^{*}=\{1,2,3,\ldots \}$
Integers: $\mathbb {Z} =\{0,\pm 1,\pm 2,\ldots \}$
Rational numbers: $\mathbb {Q} =\left\{{\frac {p}{q}}:p\in \mathbb {Z} {\mbox{ and }}q\in \mathbb {N} ^{*}\right\}$
Real numbers: $\mathbb {R}$
Complex numbers: $\mathbb {C}$