Unit 3: Counting Principles and Relations

I. Foundations of Counting and Relations

Counting principles determine the size of finite sets without listing every element, while relations describe structured connections between elements of sets. The unit links combinatorial methods, especially overlap counting and distribution, with relation-based structures such as equivalence classes, ordered sets, and lattices.

• Set convention: For a finite set (A), (|A|) denotes the number of distinct elements in (A).
• Counting convention: Objects are counted exactly once; inclusion-exclusion corrects counts when sets overlap.
• Relation convention: A binary relation (R) from (A) to (B) is any subset of (A\times B).
  • (aRb) means ((a,b)\in R).
  • A relation on (A) is a subset of (A\times A).
• Representation convention: A finite relation may be expressed as ordered pairs, a Boolean matrix, or a directed graph.
• Structural progression: Equivalence relations classify elements, ordering relations compare them, and lattices provide least upper bounds and greatest lower bounds.

II. Inclusion-Exclusion — Correcting Overlapping Counts

The inclusion-exclusion method counts a union by alternately adding individual set sizes and subtracting or adding intersections.

A. Principle of Inclusion-Exclusion

The principle ensures that each element in a union contributes exactly once to the final count.

• Two-set formula: Elements in (A\cap B) are initially counted twice, so one copy is subtracted.

|A ∪ B| = |A| + |B| - |A ∩ B|

Here, (A) and (B) are finite sets, (\cup) is union, and (\cap) is intersection.

• Three-set formula: Add single sets, subtract pairwise intersections, and restore the triple intersection.

|A ∪ B ∪ C|
= |A| + |B| + |C|
- |A ∩ B| - |A ∩ C| - |B ∩ C|
+ |A ∩ B ∩ C|

• General formula: For finite sets (A_1,\ldots,A_n), intersections of odd numbers of sets are added and intersections of even numbers are subtracted.

|⋃ Aᵢ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ···

• Worked example: If 25 students study mathematics, 18 study computing, and 10 study both, then the number studying at least one subject is (25+18-10=33).

III. Basic Distribution — Guaranteed Repetition

The pigeonhole principle converts a comparison of objects and containers into a certainty about repetition.

A. Pigeonhole principle

If more objects than containers are distributed among the containers, at least one container receives more than one object.

• Formal statement: Placing (n+1) objects into (n) boxes guarantees that some box contains at least two objects.
• Logical basis: If every box contained at most one object, the boxes could hold at most (n) objects, contradicting the presence of (n+1).
• Worked example: Among 13 people, at least two were born in the same month because there are only 12 months.
• Limitation: The principle proves existence but usually does not identify the repeated objects or their container.

IV. General Distribution — Minimum Occupancy Bounds

The generalized form determines how heavily at least one container must be occupied.

A. Generalized pigeonhole principle

When (N) objects are placed into (k) boxes, some box contains at least (\lceil N/k\rceil) objects.

Maximum guaranteed occupancy = ⌈N/k⌉

Here, (N) is the number of objects, (k>0) is the number of boxes, and (\lceil x\rceil) is the least integer greater than or equal to (x).

• Equivalent condition: To guarantee at least (r) objects in one box, it is sufficient to have more than (k(r-1)) objects.
• Reasoning: If every box held at most (r-1) objects, the total could not exceed (k(r-1)).
• Worked example: Distributing 100 files among 9 folders guarantees one folder with at least (\lceil100/9\rceil=12) files.
• Exact implication: The result gives a guaranteed lower bound; a box may contain more than the stated number.

V. Binary Relations — Connections Between Elements

A binary relation records which ordered pairs satisfy a specified condition.

A. Relations and their properties

Properties of a relation on (A) describe how its ordered pairs interact.

• Reflexive: (R) is reflexive if ((a,a)\in R) for every (a\in A); equality is reflexive.
• Irreflexive: (R) is irreflexive if ((a,a)\notin R) for every (a\in A); “less than” is irreflexive.
• Symmetric: If (aRb), then (bRa); “has the same age as” is symmetric.
• Antisymmetric: If (aRb) and (bRa), then (a=b); (\leq) is antisymmetric.
• Asymmetric: If (aRb), then (bRa) is impossible; (<) is asymmetric.
• Transitive: If (aRb) and (bRc), then (aRc); divisibility on positive integers is transitive.
• Distinction: Antisymmetric does not mean “not symmetric”; equality is both symmetric and antisymmetric.

VI. Operations on Relations — Building New Connections

Relations can be combined through standard set operations because each relation is itself a set of ordered pairs.

A. Combining relation

Combining relations produces a new relation while preserving the meanings of union, intersection, difference, and complementation.

• Union: (R\cup S) contains pairs belonging to (R), (S), or both.
• Intersection: (R\cap S) contains only pairs common to both relations.
• Difference: (R-S) contains pairs in (R) but not in (S).
• Complement: For relations on (A), (\overline R=(A\times A)-R).
• Inverse: The inverse reverses every ordered pair.

R⁻¹ = {(b,a) | (a,b) ∈ R}

• Property effects: The union of two transitive relations need not be transitive, while the intersection of two transitive relations is transitive.

VII. Relational Chaining — Linking Through Intermediate Elements

Composition connects two relations whenever the second component of one pair matches the first component of another.

A. Composition

For (R\subseteq A\times B) and (S\subseteq B\times C), the composition (S\circ R) relates (A) directly to (C).

S ○ R = {(a,c) | there exists b ∈ B such that aRb and bSc}

• Order: (R) is applied first and (S) second, so composition order matters.
• Associativity: For compatible relations, (T\circ(S\circ R)=(T\circ S)\circ R).
• Non-commutativity: Generally, (S\circ R\neq R\circ S); one expression may even be undefined.
• Relation powers: For a relation on (A), (R^2=R\circ R); a transitive relation satisfies (R^2\subseteq R).

VIII. Finite Representation — Matrices and Directed Graphs

Finite relations can be encoded visually or algebraically without changing their ordered pairs.

A. Representing relation using matrices and graph

A relation on a finite set is represented by Boolean entries in a matrix or directed edges in a graph.

• Matrix form: For (A={a_1,\ldots,a_n}), define (MR=[m{ij}]), where (m_{ij}=1) if (a_iRa_j), and (0) otherwise.
• Graph form: Each element is a vertex, and (a_iRa_j) creates a directed edge (a_i\to a_j).
• Visible properties:
  • Reflexivity gives all diagonal entries (1), or a loop at every vertex.
  • Symmetry makes (M_R=M_R^T), or gives reverse edges.
  • Antisymmetry forbids opposite edges between distinct vertices.
• Composition: Boolean matrix multiplication represents composition, using AND for multiplication and OR for addition.

IX. Classification — Partitioning by Sameness

An equivalence relation formalizes when elements should be treated as belonging to the same category.

A. Equivalence relations

A relation (R) on (A) is an equivalence relation exactly when it is reflexive, symmetric, and transitive.

• Equivalence class: The class of (a\in A) is

[a] = {x ∈ A | xRa}

• Partition property: Equivalence classes are nonempty, pairwise disjoint or identical, and their union is (A).
• Reverse construction: Every partition of (A) defines an equivalence relation by relating elements in the same block.
• Example: Congruence modulo (n), written (a\equiv b\pmod n), holds when (n\mid(a-b)); its classes group integers with the same remainder.

X. Ordered Sets — Partial and Complete Comparability

Ordering relations arrange elements consistently, although not every pair must necessarily be comparable.

A. Partial and total ordering relations

A partial order is reflexive, antisymmetric, and transitive; a total order additionally compares every pair.

1. Partial ordering: In a poset ((A,\preceq)), some distinct (a,b\in A) may satisfy neither (a\preceq b) nor (b\preceq a).
   • Divisibility on positive integers is partial because neither (2\mid3) nor (3\mid2).
2. Total ordering: For every (a,b\in A), either (a\preceq b) or (b\preceq a).
   • The usual (\leq) relation on integers is total.

• Extremal elements: Minimal and maximal elements need not be unique; a least or greatest element, when present, is unique.

XI. Lattice Structures — Bounds for Every Pair

A lattice is a partially ordered set in which each pair has both a unique greatest lower bound and a unique least upper bound.

A. Lattice

For (a,b) in a lattice, their meet is (a\wedge b), and their join is (a\vee b).

• Meet: (a\wedge b) is the greatest element less than or equal to both (a) and (b).
• Join: (a\vee b) is the least element greater than or equal to both.
• Core laws: Meet and join are commutative, associative, and idempotent.
• Absorption laws:

a ∧ (a ∨ b) = a
a ∨ (a ∧ b) = a

• Example: In the power set ((\mathcal P(S),\subseteq)), meet is intersection and join is union.

XII. Contained Lattices — Preserving Operations

A subset of a lattice forms a sublattice when it remains closed under the parent lattice’s meet and join operations.

A. Sub lattice

For a lattice (L), a nonempty subset (S\subseteq L) is a sublattice if (a\wedge b\in S) and (a\vee b\in S) for all (a,b\in S).

• Closure requirement: Merely being a subset or sub-poset is insufficient; both lattice operations must stay inside (S).
• Inherited order: The ordering on (S) is the restriction of the ordering on (L).
• Example: Under divisibility, ({1,2,6}) is a sublattice of the positive divisors of (6), because every gcd and lcm of its elements remains in the subset.
• Boundary note: A sublattice need not contain the least or greatest element of the original lattice.

XIII. Order Visualization — Cover Relations

A Hasse diagram simplifies a finite poset by displaying only immediate ordering relationships.

A. Hasse diagram and its components

A Hasse diagram represents a finite partially ordered set through vertices, vertical placement, and cover edges.

• Vertices: Each vertex corresponds to one element of the poset.
• Cover relation: (y) covers (x) when (x\prec y) and no (z) satisfies (x\prec z\prec y).
• Edges: Connect (x) to (y) only when (y) covers (x); reflexive loops and transitive edges are omitted.
• Direction: Larger elements are placed above smaller elements, so arrowheads are normally unnecessary.
• Components: Minimal elements have nothing below them; maximal elements have nothing above them. Least and greatest elements, if present, are unique.
• Interpretation: An upward path from (x) to (y) indicates (x\preceq y); disconnected vertical branches often represent incomparable elements.
• Lattice test: A finite poset diagram represents a lattice only if every pair of vertices has a unique meet and a unique join.