help with abstract math

`Produced by Charles Wells.  Home    Website TOC    Website Index   Blog`

Posted 21 May 2009

EQUIVALENCE RELATIONS

A partition  of a set S is a set of nonempty subsets of S which are pairwise disjoint and whose union is all of S.  An equivalence relation on a set S is a reflexive, symmetric, transitive relation on S.  Both of these structures is motivated by the idea of grouping objects that are alike in some respect.  Partition and equivalence relation provide exactly the same class of structures.  Each definition is a different way of presenting the same type of structure.  This chapter spells this out in detail.

# Abstraction of similarity

This section concerns the idea of objects being alike in some respect.

¨  With poker chips, some are red, some are white and some are blue.  You can group them into three subsets  the red ones, the white ones, and the blue ones.  You can say two red chips are alike in having the same color, and a red and a blue chip are not alike because they have different colors.

¨  With natural numbers, some are divisible by 2 and some are not.  You can group them into even ones and odd ones.  We can say 4 and 10 are alike in that they are both even, and 5 and 11 are alike in that they are both odd.  However, 4 and 5 are not alike in that respect.

In both these examples, we can abstract the idea of being alike in some respect by grouping the like objects together (clumping) or by making a statement that two given objects are alike or different.  (See two.)  These two ideas can be abstracted into the idea of partition and of equivalence relation.

# Partitions

## Definitions

### Definition:  Partition

If S is a set, a family  of subsets of S (called the blocks or  equivalence classes of  )  is a partition of S if it satisfies the following axioms:

PAR.1   Every block of  is nonempty.

PAR.2   Every element of S is an element of exactly one block of .

#### Alternative Definition:  Partition

If S is a set, a family  of subsets of S is a partition of S if

APAR.1   Every block of  is nonempty.

APAR.2   S is the union of all the blocks in .

APAR.3   If B and C are blocks in  and , then .

### Remarks

¨   is the Greek letter capital pi.

¨  The word “partition” has several other meanings in math.

¨  In everyday English, the word “partition” can refer to the division of something into pieces, but it can also refer to a wall that divides a room in two.  Don’t let this mess with your mind: the mathematical idea has nothing to do with walls.

¨  A partition is a set of blocks.  Don’t refer to one block as a partition.

¨  APAR.3 means by definition that  is pairwise disjoint.

## Simple examples

Here are four partitions of the set {1, 2, 3, 4, 5}:

¨

¨

¨

¨

### Remarks

Think about the remarks below until you see why they are correct:

¨   and  are the same partition (see here).

¨   and  are different partitions, because they have different blocks.

¨  In , as in any partition with two blocks, each block is the complement of the other one.

¨   is the only partition of {1, 2, 3, 4, 5} with exactly one block.  Every nonempty set has a partition consisting of the whole set as the only block.

¨   is the only partition with five blocks.  Every nonempty set has a partition whose blocks are all the singleton subsets of the set.

¨  The empty set has just one partition, whose set of blocks is empty.

### Non-examples

¨    is not a partition of the set {1, 2, 3, 4, 5} because the element 4 is not in any block.  It is, however, a partition of the set {1, 2, 3, 5}.

¨   is not a partition (of any set) because 4 is in two different blocks, violating PAR.1.   It violates APAR.3, too, because  but .

¨   is not a partition because one of its blocks is empty.

## Representing partitions

Small finite partitions can be represented by diagrams like the following, which represents :

In this diagram, the circles are merely for grouping.  The fact that they are circles has no significance.  All that matters is which elements are in which circles.

## Counting Partitions

The functions that count partitions are the Bell numbers and the Stirling numbers of the second kind

¨  The set {1, 2, 3, 4, 5} has 52 different partitions altogether.   The Bell number B5  = 52.

¨  There are 25 different partitions of the set {1, 2, 3, 4, 5} that have three blocks each (  is one of them).  The Stirling number S(5,3) = 25.

## Notation

### Blocks

If  is a partition of a set S and , then there is a unique block of  that contains x as an element.  This block is denoted by .  For example, ,  and  .

### Sequence notation

It may happen that an author refers to a partition as if it were a sequence of sets.  For example, they might say  is the partition , where ,  and .   Be warned: the order the blocks are listed in doesn’t matter, even though in sequence notation it usually does matter.

### Exercise PAR

Provide an example with the given property of a partition  of the set  of real numbersAnswers.

a)   has at least one block with exactly three elements.

b)   {1,2} and {3} are blocks of .

c)    has at least one finite block and at least one infinite block.

d)    has an infinite number of finite blocks.

e)    has an infinite number of infinite blocks.

### Exercise IIZ

Find a partition of  that has an infinite number of infinite blocks.  Answer.

# Equivalence relations

The concept of equivalence relation is an abstraction of the idea of two math objects being like each other in some respect.

¨  If an object a is like an object b in some specified way, then b is like a in that respect.

¨  a is like itself in every respect!

So if you want to give an abstract definition of a type of relation intended to capture the idea of being alike in some respect, two of the properties you could require are reflexivity and symmetry.  The nearness relations are reflexive and symmetric.  Relations with those two properties are studied in applied math NEED REFERENCE  but here we are going to require the additional property of transitivity, which roughly speaking forces the objects to fall into discrete types, making a partition of the set of objects being studied.

### Definition: Equivalence relation

An equivalence relation on a set S is a reflexive, symmetric, transitive relation on S.

Note This definition is an abstraction of the idea of “being like each other”. You don’t have to have some property or mode of similarity in mind to define an equivalence relation.

### Examples

¨  The relation “equals” on any set is an equivalence relation.  On the set {1, 2, 3}, “equals” is the relation {(1,1),(2,2),(3,3)}.

¨  The relation E on the real numbers defined by  if and only if  is an equivalence relation.  In this case, x and y are like each other in this respect:  They have the same square.

¨  Let A = {1, 2, 3, 4, 5}  and let .  Then  is an equivalence relation on A. You can define this relation more easily by saying:  “  if and only if x and y are in the same block of  (above).”  This is the key to the relationship between equivalence relations and partitions.

¨  For any integer k, congruence (mod k) is an equivalence relation, discussed here.

### Non-examples

¨  The relation “  ” on the set of real numbers is not an equivalence relation.  It is reflexive and transitive but not symmetric:  For example,  is true but  is false.  This relation is an example of an ordering.

¨  The relation E defined on the real numbers by  if and only if  and  is not an equivalence relation.   It is symmetric and transitive but not reflexive.  It is a partial equivalence relation.

¨  The relation D defined on a set of sets by x D y if and only if x and y are disjoint is not an equivalence relation.  It is reflexive and symmetric but not transitive.

# Equivalence relations and partitions

This is the fundamental fact connecting equivalence relations and partitions

Every equivalence relation on a set S determines a specific partition of S and every partition of S determines a specific equivalence relation on S.   These operations are inverse to each other.

This statement is not a theorem because I haven’t told you how each equivalence relation induces a partition and vice versa.  The proper statement is the Fundamental Theorem on Equivalence Relations below, but to state it requires several definitions.  A more detailed explanation with proofs is given here.

## An equivalence relation determines a partition

If an equivalence relation E is given on a set S, the elements of S can be collected together into subsets, with two elements in the same subset if and only if they are related by E. This collection of subsets of S is a set denoted S/E, the quotient set of S by E. Here is the formal definition of S/E:

### Definition: quotient set of an equivalence relation

Let E be an equivalence relation on a set S. For each , the equivalence class of x mod E, denoted by , is the subset  of S.  The quotient set  of E is the set of equivalence classes of x mod E for all .

#### Warning

I have now defined two notations that look like  for some symbol s.  If s denotes a partition,  is the block of the partition that contains x.  If s denotes an equivalence relation,  denotes the set .   Thus the notation “  ” is overloaded.  However, the fundamental theorem below says don’t worry, be happy about this.

### Example

Let A = {1, 2, 3, 4, 5}  and let

(We looked at this example before.)   Notice that , because by definition

and you can see that the only three pairs in  whose second coordinate is 2 are (1,2), (2,2) and (5,2).  Reasoning in the same way, we have

and

so by definition the quotient set of  is the partition , which I called  above.  In other words, .

The fact that the quotient set is a partition is always true:

### Theorem

If S is a set and E is an equivalence relation on S, then the quotient set S/E is a partition of S

### Proof

¨  Proof of Par.1:  Any block of S/E is of the form  for some .  By definition, .  Since E is reflexive, x E x, so  is nonempty because it contains x.

¨ Proof of Par.2:  We know that x is in at least one set because  by reflexivity.  Suppose  and .  We must show that  as sets.  That means by definition of set equality we must show that for any element w,  if and only if .  Suppose (modus ponens) that .  Then by comprehensionw E y.  Then , so x E y.  By symmetry, y E x.  So by transitivity, w E x.  Since , we know x E z.  So by transitivity, w E z, which means .  That is half the proof.  You do the other half.

### How to think about S/E

If E is an equivalence relation on S, you can think of the quotient set S/E  as obtained by merging equivalent elements of S.   In the example above, 3 and 4 are equivalent so they are merged into the equivalence class {3, 4}, which is both  and .

One often says that one identifies equivalent elements. Here, “identify” means “make identical” rather than “discover the identity of”. Mathematicians may also say we glue equivalent elements together.  Thus we form the Möbius strip by gluing the left and right edge of the unit square together in a certain way.

### Exercises

BTWO Let S = {1, 2, 3, 4}.   Find two different equivalence relations E and E' with the property that the subset {1, 2} is a block of both S/E and S/E'.  Answer.

INTB Give an example of an equivalence relation E on the set  of real numbers with the property that the interval [0, 1] is one of the equivalence classes of EAnswer

## A partition determines an equivalence relation

Given a partition , you get an equivalence relation  by the definition:

In other words,  if and only if x and y are in the same block of .  The relation   is well-defined because each element is in exactly one block of  by PAR.2.

### Theorem

For a partition  of S, the relation  is an equivalence relation on S.

### Proof

All three steps in this proof depend on the fact that each element of S is in exactly one block (Par.2).

¨  Since x is in the same block as itself, , so  is reflexive.

¨  If , then x and y are in the same one and only block, which is the same thing as saying that y and x are in the same block, so .  So  is symmetric.

¨  If  and , then  x is in the same block as y and z is in the same block as y.  By Par.2, x and z must be in the same block, so   Hence  is transitive.

## The fundamental theorem on equivalence relations

### One way to state the fundamental theorem

Above we showed how to take an equivalence relation E and construct a partition S/E.  Then we showed how to take a partition  of a set S and construct an equivalence relation .

The fundamental theorem on equivalence relations says that if you perform one construction and then the other you get back what you started with.  In other words:

¨  If you have an equivalence relation E, construct the quotient set S/E, which is a partition, and then construct the equivalence relation  corresponding to that partition, you get the equivalence relation E you started with.

¨  If you have a partition  of S, construct the corresponding equivalence relation  and then construct the quotient set  of , you get the partition  back again.

In short:

and

##### Note  This pair of equations condenses the information down to two cryptic statements.It is worthwhile spending a few minutes trying to spell out to yourself in detail just what they say.

Lots of math in research papers is excruciatingly succinct.

You need to practice unwinding what they say.

The proof of the fundamental theorem involves the same sort of arguments given above.

### Another way to state the fundamental theorem

Let S be a set, let  be the set of all partitions of S, and let E(S) be the set of all equivalence relations on S.  The fundamental theorem says that the two constructions given above produce a function  and a function  that are inverses to each other.  This means they are bijections.  In fact, E and  are functors that are naturally isomorphic by these bijections.

#### Example

If S = {1, 2}, then

¨   is the set {{{1}, {2}}, {{1, 2}}}.   It has two elements, the partition {{1}, {2}} and the partition {{1, 2}}.

¨  E(S)  is the set {{1, 1), (2, 2)}, {(1, 1), (2, 2), (1, 2), (2, 1)}}.  It contains the two equivalence relations {1, 1), (2, 2)} and {(1, 1), (2, 2), (1, 2), (2, 1)}.

¨  R[{{1}, {2}}] = {(1, 1), (2, 2)} and R[{{1, 2}}] = {(1, 1), (2, 2), (1, 2), (2, 1)}.

¨  Q[ {(1, 1), (2, 2)} ] = {{1}, {2}}  and Q[ {(1, 1), (2, 2), (1, 2), (2, 1)}] = {{1, 2}}.

According to the fundamental theorem,

An equivalence relation is the same thing as a partition

Of course, they are described differently, but once you have an equivalence relation you have a partition and vice versa.   All you know about the partition is determined by the data of the equivalence relation and all you know about the equivalence relation is determined by the data of the partition.

The relationship between equivalence relations and partitions is a basic and important example of the fact that two different looking kinds of structures can actually be two different descriptions of the same kind of structure.

# Consciousness-raising examples

### The quotient of the squaring function

Let  be the partition of  whose blocks are all subsets of the form  for all .    is the quotient set of the squaring function  defined by . Observe that:

¨   has an infinite number of blocks.

¨  ,  and  are blocks of .

¨  Every block of  except  has exactly two elements.

### A foliation of the real plane

For any given real number c, let .  This defines an infinite family of functions .  For a given c, the graph of  is the subset , which I will denote by , of the real plane .  You can check that these subsets  are a partition of .  The picture below shows some of the blocks.

¨  These blocks are dense in , meaning that between any two of them there is an infinite number of others.  There is no block next to a given block.  They are dense in  just like the points on the real line are dense.

¨  This is a baby example of a foliation (Wikipedia, MathWorld).

Answers to Exercise PAR.   Each problem has many possible answers.  I give only one for each.

a)   Let  and  the set of all real numbers except 1, 3 and 5.

b)   Let .  and  the set of all real numbers except 1, 2 and 3.

c)   The answers to a) and to b) also work for this one.

d)   For each positive integer n, let , and let  the set of all real numbers that are not integers.

e)   For each integer n, let .  Can you think of a partition of the integers  that has an infinite number of infinite blocks?

For each prime p, let .  Let .  (See set subtraction).  Then set .  Then  is a partition of  with an infinite number of infinite blocks.  Note:  I have deliberately used succinct notation that you may have to unwind extensively before you understand it.  (Pretend you are a kitten attacking a ball of yarn.)