BII Algebra: Lecture 1

Equivalence relation on a set

Let A be a set. A binary relation on A is a

subset R of A × A.

We write a ∼ b (a is related to b) if (a, b) ∈ R.

We shall be interested in a special type of

relation called the equivalence relation.

A relation ∼ on A is called an equivalence relation

if the following three conditions hold:

1. x ∼ x for all x ∈ A.

2. For x, y ∈ A, if x ∼ y, then y ∼ x.

3. For x, y, z ∈ A if x ∼ y and y ∼ z hold, then

x ∼ z.

1
One of the most important results in this con-
text:

Theorem. Let A be a set. An equivalence re-

lation ∼ on A partitions A into disjoint subsets.
(Converse is also true.)

Proof. For a ∈ A, write

[a] := {x ∈ A | x ∼ a},
called the equivalence class of a.

Clearly,
[
A= [a]
a∈A

Check that the equivalence classes are either

equal or disjoint.

Conversely, let
[
A= Aα ,
α∈I
2
be a partition of A into disjoint subsets.

Define: a ∼ b if and only if there is some α ∈

I such that a, b ∈ Aα. Check that this is an
equivalence relation.
 A construction

For any set A, define S(A) = A ∪ {A}. This

is called the successor operation. Let us now
apply this operation repeatedly, starting from:

The empty set!

3
Starting point: ∅.

S(∅) = ∅ ∪ {∅} = {∅}.

S({∅}) = {∅} ∪ {{∅}} = {∅, {∅}}.

S({∅, {∅}}) = {∅, {∅}}∪{{∅, {∅}}} = {∅, {∅}, {∅, {∅}}}.

S(−) = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}.

... and so on...

4
Let us give those sets from the last page some
names (rather symbols).

Write:

0 for ∅.

1 for {∅} (= {0}).

2 for {∅, {∅}} (= {0, 1}).

3 for {∅, {∅}, {∅, {∅}}} (= {0, 1, 2}).

4 for {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}} (= {0, 1, 2, 3}).

... and so on ...

5
The system of symbols {0, 1, 2, 3, 4, 5, · · · } thus
obtained is the set of natural numbers, denoted
by N.

Remark 1: Each natural number is a set.

Remark 2: A natural number is the set of its

preceding natural numbers.

The set N satisfies the so called Peano Axioms:

• 0 is a natural number.

• Every natural number has a successor which

is also a natural number.

• 0 is not the successor of any natural num-

ber.
6
• If the successor of x equals the successor
of y, then x equals y.

• (Axiom of Induction) If a statement is true

for 0, and if the truth of that statement for
a number implies its truth for the successor
of that number, then the statement is true
for every natural number.
 Addition.

Define n + 0 = n for all n. Then go on recur-

sively as follows:

n + S(m) = S(n + m)

Illustration:

1 + 1 = 1 + S(0) := S(1 + 0) = S(1) = 2

2 + 1 = 2 + S(0) := S(2 + 0) = S(2) = 3

n + 1 = n + S(0) := S(n + 0) = S(n)

Remark: Note that n + 1 is the successor of n.

7
The set N, together with addition + satisfies:

1. n + (m + p) = (n + m) + p for all m, n, p ∈ N.

2. n + m = m + n for all m, n ∈ N.

3. n + 0 = n for all n ∈ N.

Exercise: Prove the above properties!

8
In an algebraic system as above we would like
to solve equations.

While the equation X + 1 = 2 has a solution

in N, the following

X +2=1
does not (why?).

Question. Can we embed N in a bigger sys-

tem, retaining all its properties, so that the
equation as above has a solution (in the big-
ger system)?

So we have to bring in the “negatives”. We

only have (N, +) and basic set theory at our
disposal. This will be our focus now.

9
 Construction of Integers

Consider the set X = N × N. On X, define the

relation:
(a, b) ∼ (c, d) if a + d = c + b

Example. (1, 3) ∼ (5, 7), (11, 5) ∼ (100, 94)

etc.

Exercise. Check that ∼ is an equivalence re-

lation.

Write Z = set of all equivalence classes.

Notation: [(a, b)] for the equivalence class con-

taining (a, b).

Now define addition on these equivalence classes:

[(a, b)] ⊕ [(m, n)] := [(a + m, b + n)]

(note that + is from N)
10
Remark. What if [(a, b)] = [(c, d)] and [(m, n)] =
[(p, q)]? Do we have

[(a, b)] ⊕ [(m, n)] = [(c, d)] ⊕ [(p, q)]?

Let us check.
[(a, b)] = [(c, d)] ⇒ (a, b) ∼ (c, d)
(a, b) ∼ (c, d) ⇒ a + d = c + b
[(m, n)] = [(p, q)] ⇒ (m, n) ∼ (p, q)
(m, n) ∼ (p, q) ⇒ m + q = p + n

Then, a+d+m+q = c+b+p+n and therefore,

a + m + d + q = c + p + b + n, implying (a +
m, b + n) ∼ (c + p, d + q). In other words,

[(a, b)] ⊕ [(m, n)] = [(c, d)] ⊕ [(p, q)],

and the definition is consistent.

11
What is the “zero” in Z?

It is the class of (0, 0) (which is the same as

[(1, 1)], [(2, 2)], [(3, 3)], · · · ).

The natural numbers are embedded in Z as

follows:
f : N −→ Z by

n 7→ [(n, 0)]

Exercise: Prove that f is injective.

Do we have some [(a, b)] ∈ Z such that

[(a, b)] ⊕ [(1, 0)] = [(0, 0)] ?

Yes, [(0, 1)] ⊕ [(1, 0)] = [(1, 1)] = [(0, 0)].

In general, [(0, n)]⊕[(n, 0)] = [(n, n)] = [(0, 0)].

Let us call [(n, 0)] as n and [(0, n)] as −n.

These are the negatives.
12
Let us now drop the ⊕ notation. Also, write n
for [(n, 0)] and −n for [(0, n)].

Take any integer [(a, b)] ∈ Z.

Then

[(a, b)] = [(a, 0)] + [(0, b)] = a − b

Thus, we realized integers as difference of nat-

ural numbers.

13
On N. we can also define multiplication.

Define n × 0 = 0 for all n.

Then,
n × S(m) = n × m + n

You can easily check the properties of multi-

plication and the distributive law.

You can extend this definition to Z.

14
Now that we have addition and multiplication
on Z, consider the equation:

2x = 3

It has no solution in Z.

Again, can we embed Z into some bigger struc-

ture where we have a solution?

If we can accommodate reciprocals of

n ∈ Z r {0}, we shall be done.

15
Almost a similar construction as before.

Take
X = {(a, b) ∈ Z × Z |b 6= 0}

Define a relation ∼ on X by:

(a, b) ∼ (c, d) iff ad = bc

Check that this is an equivalence relation.

Define Q = X/ ∼ (the set of equivlence classes).

16
Notation: write [(a, b)] for the equivalence class
of (a, b).

Define:

[(a, b)] + [(c, d)] = [(ad + bc, bd)]

[(a, b)] × [(c, d)] = [(ac, bd)]

Exercise: Check that the above operations are

well-defined.

17
Take any [(a, b)] ∈ Q, with a 6= 0. Then

[(a, b)] × [(b, a)] = [(ab, ab)] = [(1, 1)]

Let us keep this in mind.

For convenience, we write [(a, b)] as ab .

We have an injective map

φ : Z −→ Q
n
n 7→
1

Therefore, we can identify n

1 of Q with n.

18
Let n(6= 0) ∈ Z. Note that, in Q we have
n 1 1
× =
1 n 1

In other words, n has reciprocal in Q.

19
Now consider the equation:

x2 = 2

This has no solution in Q.

One then constructs R to tackle this problem.

But this construction is not an algebraic one

as the above two.

That’s analysis.

20
Again, another equation! Consider

x2 + 1 = 0
This has no solution in R.

How do we embed R into a bigger structure?

We shall take
R[X]
2
,
hX + 1i

where

hX 2 + 1i = {(X 2 + 1)f (X) | f (X) ∈ R[X]}

(i.e. all multiples of X 2 + 1).

Let us call hXR2[X]

+1i
as C.

21
We shall see later that:

• there is a natural injection ϕ : R −→ C;

• −1 has a square root in C.

And this construction of C would be the model

for various such general constructions.

22