Two permutations ±, β ∈ Sn are conjugate iff ∃π ∈ Sn such that ± = πβπ ’1 .

Theorem 3.4. Two permutations are conjugate iff they have the same cycle type.

This theorem is proved in the Algebra and Geometry course. We note the corollary

that the number of conjugacy classes in Sn equals the number of partitions of n.

Determinants of an n — n matrix

3.3.5

In the Linear Maths course you will prove that if A = (aij ) is an n — n matrix then

n

det A = sign π aj π(j) .

j=1

π∈Sn

3.4. BINARY RELATIONS 29

3.4 Binary Relations

A binary relation on a set S is a property that any pair of elements of S may or may

not have. More precisely:

Write S —S, the Cartesian square of S for the set of pairs of elements of S, S —S =

{(a, b) : a, b ∈ S}. A binary relation R on S is a subset of S — S. We write a R b iff

(a, b) ∈ R. We can think of R as a directed graph with an edge from a to b iff a R b.

A relation R is:

• re¬‚exive iff a R a ∀a ∈ S,

• symmetric iff a R b ’ b R a ∀a, b ∈ S,

• transitive iff a R b, b R c ’ a R c ∀a, b, c ∈ S,

• antisymmetric iff a R b, b R a ’ a = b ∀a, b ∈ S.

The relation R on S is an equivalence relation if it is re¬‚exive, symmetric and

transitive. These are “nice” properties designed to make R behave something like =.

De¬nition. If R is a relation on S, then

[a]R = [a] = {b ∈ S : a R b}.

If R is an equivalence then these are the equivalence classes.

Theorem 3.5. If R is an equivalence relation then the equivalence classes form a par-

tition of S.

Proof. If a ∈ S then a ∈ [a], so the classes cover all of S. If [a] © [b] = … then

∃c ∈ [a] © [b]. Now a R c and b R c ’ c R b. Thus a R b and b ∈ [a]. If d ∈ [b]

then b R d so a R d and thus [b] ⊆ [a]. We can similarly show that [a] ⊆ [b] and thus

[a] = [b].

The converse of this is true: if we have a partition of S we can de¬ne an equivalence

relation on S by a R b iff a and b are in the same part.

An application of this is the proof of Lagrange™s Theorem. The idea is to show that

being in the same (left/right) coset is an equivalence relation.

Given an equivalence class on S the quotient set is S/R, the set of all equivalence

classes. For instance if S = R and a R b iff a ’ b ∈ Z then S/R is (topologically) a

circle. If S = R2 and (a1 , b1 ) R (a2 , b2 ) iff a1 ’ a2 ∈ Z and b1 ’ b2 ∈ Z the quotient

set is a torus.

Returning to a general relation R, for each k ∈ N we de¬ne

R(k) = {(a, b) : there is a path of length at k from a to b}.

R(1) = R and R(∞) = t(R), the transitive closure of R. R(∞) is de¬ned as

(i)

i≥1 R .

CHAPTER 3. SETS, FUNCTIONS AND RELATIONS

30

3.5 Posets

R is a (partial) order on S if it is re¬‚exive, anti-symmetric and transitive. The set S is

a poset (partially ordered set) if there is an order R on S.

We generally write a ¤ b iff (a, b) ∈ R, and a < b iff a ¤ b and a = b.

Consider Dn , the set of divisors of n. Dn is partially ordered by division, a ¤ b if

a | b. We have the Hasse diagram, in this case for D36 :

A descending chain is a sequence a1 > a2 > a3 > . . . . An antichain is a subset of

S with no two elements directly comparable, for instance {4, 6, 9} in D36 .

Proposition. If S is a poset with no chains of length > n then S can be covered by at

most n antichains.

Proof. Induction on n. Take n > 1 and let M be the set of all maximal elements in S.

Now S \ M has no chains of length > n ’ 1 and M is an antichain.

3.5.1 Products of posets

Suppose A and B are posets. Then A — B has various orders; two of them being

• product order: (a1 , b1 ) ¤ (a2 , b2 ) iff a1 ¤ a2 and b1 ¤ b2 ,

• lexicographic order: (a1 , b1 ) ¤ (a2 , b2 ) if either a1 ¤ a2 or if a1 = a2 then

b1 ¤ b2 .

Exercise: check that these are orders.

Note that there are no in¬nite descending chains in N — N under lexicographic

order. Such posets are said to be well ordered. The principle of induction follows from

well-ordering as discussed earlier.

3.5.2 Eulerian Digraphs

A digraph is Eulerian if there is a closed path covering all the edges. A necessary

condition is: the graph is connected and even (each vertex has an equal number of “in”

and “out” edges). This is in fact suf¬cient.

Proposition. The set of such digraphs is well-ordered under containment.

3.6. COUNTABILITY 31

Proof. Assume proposition is false and let G be a minimal counterexample. Let T be

a non-trivial closed path in G, for instance the longest closed path. Now T must be

even, so G \ T is even. Hence each connected component of G \ T is Eulerian as G

is minimal. But then G is Eulerian: you can walk along T and include all edges of

connected components of G \ T when encountered ” giving a contradiction. Hence

there are no minimal counterexamples.

3.6 Countability

De¬nition. A set S is countable if either |S| < ∞ or ∃ a bijection f : S ’ N.

The countable sets can be equivalently thought of as those that can be listed on a

line.

Lemma 3.3. Any subset S ‚ N is countable.

Proof. For: map the smallest element of S to 1, the next smallest to 2 and so on.

Lemma 3.4. A set S is countable iff ∃ an injection f : S ’ N.

Proof. This is clear for ¬nite S. Hence assume S is in¬nite. If f : S ’ N is an

injection then f (S) is an in¬nite subset of N. Hence ∃ a bijection g : f (S) ’ N. Thus

gf : S ’ N is a bijection.

An obvious result is that if S is countable and ∃ an injection f : S ’ S then S is

countable.

Proposition. Z is countable.

Proof. Consider f : Z ’ N,

2x + 1 if x ≥ 0

f: x’

’2x if x < 0.

This is clearly a bijection.

Proposition. Nk is countable for k ∈ N.

Proof. The map (i1 , . . . , ik ) ’ 2i1 3i2 . . . pik (pj is the j th prime) is an injection by

k

uniqueness of prime factorisation.

Lemma 3.5. If A1 , . . . , Ak are countable with k ∈ N, then so is A1 — · · · — Ak .

Proof. Since Ai is countable there exists an injection fi : Ai ’ N. Hence the function

g : A1 , . . . , Ak ’ Nk de¬ned by g(a1 , . . . , ak ) = (f1 (a1 ), . . . , fk (ak )) is an injection.

Proposition. Q is countable.

Proof. De¬ne f : Q ’ N by