maths.free › Abstract Algebra › 1. Preliminaries › Sets and Equivalence Relations
Sets and Equivalence Relations
A set is a well-defined collection of objects; that is, it is defined in such a manner that we can determine for any given object x whether or not x belongs to the set.
Set Theory
A set is a well-defined collection of objects; that is, it is defined in such a manner that we can determine for any given object \(x\) whether or not \(x\) belongs to the set. The objects that belong to a set are called its elements or members. We will denote sets by capital letters, such as \(A\) or \(X\); if \(a\) is an element of the set \(A\), we write \(a \in A\). \(a \in A\) \(a\) is in the set \(A\)
A set is usually specified either by listing all of its elements inside a pair of braces or by stating the property that determines whether or not an object \(x\) belongs to the set. We might write \[\begin{aligned}\end{aligned}\] for a set containing elements \(x_1, x_2, \ldots, x_n\) or \[\begin{aligned}\end{aligned}\] if each \(x\) in \(X\) satisfies a certain property \({\mathcal P}\). For example, if \(E\) is the set of even positive integers, we can describe \(E\) by writing either \[\begin{aligned}\end{aligned}\]. We write \(2 \in E\) when we want to say that 2 is in the set \(E\), and \(-3 \notin E\) to say that \(-3\) is not in the set \(E\).
Some of the more important sets that we will consider are the following: \[\begin{aligned}{\mathbb N} = \{n: n \text{ is a natural number}\} = \{1, 2, 3, \ldots \}; \\ {\mathbb Z} = \{n : n \text{ is an integer} \} = \{\ldots, -1, 0, 1, 2, \ldots \}; \\ {\mathbb Q} = \{r : r \text{ is a rational number}\} = \{p/q : p, q \in {\mathbb Z} \text{ where } q \neq 0\}; \\ {\mathbb R} = \{ x : x \text{ is a real number} \}; \\ {\mathbb C} = \{z : z \text{ is a complex number}\}\end{aligned}\]. \({\mathbb N}\) the natural numbers \({\mathbb Z}\) the integers \({\mathbb Q}\) the rational numbers \({\mathbb R}\) the real numbers \({\mathbb C}\) the complex numbers
It is convenient to have a set with no elements in it. This set is called the empty set and is denoted by \(\emptyset\). Note that the empty set is a subset of every set. \(\emptyset\) the empty set
When two sets have no elements in common, they are said to be disjoint; for example, if \(E\) is the set of even integers and \(O\) is the set of odd integers, then \(E\) and \(O\) are disjoint. Two sets \(A\) and \(B\) are disjoint exactly when \(A \cap B = \emptyset\).
Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.
Cartesian Products and Mappings
Given sets \(A\) and \(B\), we can define a new set \(A \times B\), called the Cartesian product of \(A\) and \(B\), as a set of ordered pairs. That is, \(A \times B\) Cartesian product of sets \(A\) and \(B\) \[\begin{aligned}\end{aligned}\].
Example
If \(A = \{ x, y \}\), \(B = \{ 1, 2, 3 \}\), and \(C = \emptyset\), then \(A \times B\) is the set \[\begin{aligned}\end{aligned}\] and \[\begin{aligned}\end{aligned}\].
We define the Cartesian product of \(n\) sets to be \[\begin{aligned}\end{aligned}\]. If \(A = A_1 = A_2 = \cdots = A_n\), we often write \(A^n\) for \(A \times \cdots \times A\) (where \(A\) would be written \(n\) times). \(A^n\) \(A \times \cdots \times A\) (\(n\) times) For example, the set \({\mathbb R}^3\) consists of all of 3-tuples of real numbers.
Subsets of \(A \times B\) are called relations. We will define a mapping or function \(f \subset A \times B\) from a set \(A\) to a set \(B\) to be the special type of relation where each element \(a \in A\) has a unique element \(b \in B\) such that \((a, b) \in f\). Another way of saying this is that for every element in \(A\), \(f\) assigns a unique element in \(B\). We usually write \(f:A \rightarrow B\) or \(A \stackrel{f}{\rightarrow} B\). Instead of writing down ordered pairs \((a,b) \in A \times B\), we write \(f(a) = b\) or \(f : a \mapsto b\). The set \(A\) is called the domain of \(f\) and \[\begin{aligned}\end{aligned}\] is called the range or image of \(f\). We can think of the elements in the function's domain as input values and the elements in the function's range as output values.
Example
Suppose \(A = \{1, 2, 3 \}\) and \(B = \{a, b, c \}\). In we define relations \(f\) and \(g\) from \(A\) to \(B\). The relation \(f\) is a mapping, but \(g\) is not because \(1 \in A\) is not assigned to a unique element in \(B\); that is, \(g(1) = a\) and \(g(1) = b\).
Given a function \(f : A \rightarrow B\), it is often possible to write a list describing what the function does to each specific element in the domain. However, not all functions can be described in this manner. For example, the function \(f: {\mathbb R} \rightarrow {\mathbb R}\) that sends each real number to its cube is a mapping that must be described by writing \(f(x) = x^3\) or \(f:x \mapsto x^3\).
Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.
Equivalence Relations and Partitions
A fundamental notion in mathematics is that of equality. We can generalize equality with equivalence relations and equivalence classes. An equivalence relation on a set \(X\) is a relation \(R \subset X \times X\) such that
\((x, x) \in R\) for all \(x \in X\) (reflexive property);
\((x, y) \in R\) implies \((y, x) \in R\) (symmetric property);
\((x, y)\) and \((y, z) \in R\) imply \((x, z) \in R\) (transitive property).
Example
Let \(p\), \(q\), \(r\), and \(s\) be integers, where \(q\) and \(s\) are nonzero. Define \(p/q \sim r/s\) if \(ps = qr\). Clearly \(\sim\) is reflexive and symmetric. To show that it is also transitive, suppose that \(p/q \sim r/s\) and \(r/s \sim t/u\), with \(q\), \(s\), and \(u\) all nonzero. Then \(ps = qr\) and \(ru = st\). Therefore, \[\begin{aligned}\end{aligned}\]. Since \(s \neq 0\), \(pu = qt\). Consequently, \(p/q \sim t/u\).
Example
Suppose that \(f\) and \(g\) are differentiable functions on \({\mathbb R}\). We can define an equivalence relation on such functions by letting \(f(x) \sim g(x)\) if \(f'(x) = g'(x)\). It is clear that \(\sim\) is both reflexive and symmetric. To demonstrate transitivity, suppose that \(f(x) \sim g(x)\) and \(g(x) \sim h(x)\). From calculus we know that \(f(x) - g(x) = c_1\) and \(g(x)- h(x) = c_2\), where \(c_1\) and \(c_2\) are both constants. Hence, \[\begin{aligned}\end{aligned}\] and \(f'(x) - h'(x) = 0\). Therefore, \(f(x) \sim h(x)\).
Example
For \((x_1, y_1 )\) and \((x_2, y_2)\) in \({\mathbb R}^2\), define \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\). Then \(\sim\) is an equivalence relation on \({\mathbb R}^2\).
Let us examine some of the partitions given by the equivalence classes in the last set of examples.
Example
In the equivalence relation in , two functions \(f(x)\) and \(g(x)\) are in the same partition when they differ by a constant.
Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.
Symbols used here
n divides a − b; a and b have the same remainder.
x belongs to A; every element of A is in B.
In either; in both; in A but not B.
The two sides are different.
Naturals, integers, rationals, reals, complex numbers.
Marks the point where the statement has been established.
b is a multiple of a; the largest number dividing both.
A set with an operation; the do-nothing element; the element that undoes g.
Same structure; the group of cosets of a normal subgroup N.
The remainders 0…n−1 with clock arithmetic.
The set of morphisms; do g then f.
Questions people ask
What is a group, in plain words?
A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.
What is the difference between a ring and a field?
A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.
Tente o seu próprio
Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.
Mais em Abstract Algebra
GroupsSubgroups, cosets and Lagrange's theoremCyclic groups and permutation groupsHomomorphisms, normal subgroups and quotient groupsRings and fieldsGalois theory: why the quintic has no formula