The number of equivalence relations of the set {1, 2, 3, 4} is

The number of equivalence relations on a set of n elements is equal to the number of ways the set can be partitioned. This is because every equivalence relation corresponds to exactly one partition, and every partition corresponds to exactly one equivalence relation.

For the set {1, 2, 3, 4}, we count the partitions by the sizes of the blocks:

• One block of 4 (i.e. {1,2,3,4}): 1 partition

• Blocks of size 3 and 1 (e.g. {1,2,3},{4}): 4 partitions

• Two blocks of size 2 (e.g. {1,2},{3,4}): 3 partitions

• Blocks of size 2, 1 and 1 (e.g. {1,2},{3},{4}): 6 partitions

• Four blocks of size 1 (i.e. {1},{2},{3},{4}): 1 partition

Total = 1 + 4 + 3 + 6 + 1 = 15. This is the 4th Bell number, B4 = 15.

B4 = 15

How to write the equivalence relation from a partition:

Each partition tells you which elements are 'related'. Two elements are related under the relation if and only if they lie in the SAME block of the partition. So you form the relation by taking, within each block, every ordered pair (a, b) where a and b are both in that block (including a related to itself).

Example 1 — the partition {1,2},{3,4} gives the relation:

R = {(1,1),(2,2),(1,2),(2,1), (3,3),(4,4),(3,4),(4,3)}.

Here 1 and 2 are in one block, so we include (1,1),(2,2),(1,2),(2,1); 3 and 4 are in the other block, so we include (3,3),(4,4),(3,4),(4,3). Notice it is reflexive (every element related to itself), symmetric (if (a,b) then (b,a)), and transitive — exactly the equivalence-relation properties.

Example 2 — the partition {1,2,3},{4} gives:

R = {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2), (4,4)}.

Every pair from within {1,2,3} is included, and 4 is related only to itself.

Doing this for each of the 15 partitions produces all 15 equivalence relations. So the correct answer is 15.