Relations, Closures, Equivalence Partitions & Counting

A binary relation R from set A to set B is a subset of the Cartesian product A times B. When A = B, R is a relation on A.

For a set A with |A| = n elements, the product A times A has n^2 ordered pairs.

Core Properties:

1. Reflexive: forall a in A, (a, a) in R.

2. Irreflexive: forall a in A, (a, a) notin R.

3. Symmetric: forall a, b in A, (a, b) in R implies (b, a) in R.

4. Anti-Symmetric: forall a, b in A, [ (a, b) in R land (b, a) in R ] implies a = b.

5. Asymmetric: forall a, b in A, (a, b) in R implies (b, a) notin R (implies irreflexive).

6. Transitive: forall a, b, c in A, [ (a, b) in R land (b, c) in R ] implies (a, c) in R.

Represent R as an n times n Boolean adjacency matrix:

- There are n main diagonal entries (a_i, a_i).

- There are n^2 - n = n(n - 1) off-diagonal entries, forming n(n - 1) / 2 symmetric pairs { (a_i, a_j), (a_j, a_i) } with i < j.

Derivations:

- Reflexive: Diagonal entries are fixed to 1 (1 choice). The n(n - 1) off-diagonal entries can each be 0 or 1 (2 choices). Total = 2^{n(n - 1)} = 2^{n^2 - n}.

- Symmetric: Diagonal entries can each be 0 or 1 (2^n choices). For each of the n(n - 1)/2 off-diagonal pairs, both must be 0 or both must be 1 (2 choices). Total = 2^n * 2^{n(n - 1)/2} = 2^{n(n + 1)/2}.

- Anti-Symmetric: Diagonal entries can be 0 or 1 (2^n choices). For each of the n(n - 1)/2 pairs, we cannot have both equal 1. Possible choices: (0, 0), (1, 0), (0, 1) (3 choices). Total = 2^n * 3^{n(n - 1)/2}.