Back To Top

Unit-3: Counting Principles and Relations

1. Principle of Inclusion-Exclusion, Pigeonhole Principle, and Generalized Pigeonhole Principle

1. Principle of Inclusion-Exclusion (PIE)

The Principle of Inclusion-Exclusion helps count elements in the union of multiple sets, accounting for overlaps.

For Two Sets:

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

For Three Sets:

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

Example:

In a class of 40 students:

How many study Math or Physics?

|Math ∪ Physics| = |Math| + |Physics| - |Math ∩ Physics|

= 25 + 20 - 10 = 35

2. Pigeonhole Principle

The Pigeonhole Principle states that if you have more items than containers, at least one container must hold more than one item.

Formal Statement:

If n items are put into m containers, and n > m, then at least one container must contain more than one item.

Example:

If there are 13 pairs of shoes in a closet, at least one pair must share the same month of purchase (12 months, 13 pairs).

3. Generalized Pigeonhole Principle

The Generalized Pigeonhole Principle extends the basic principle:

Formal Statement:

If n items are distributed across m containers, at least one container must contain at least ⌈n/m⌉ items.

Example:

If 50 students are placed into 10 groups, at least one group must have ⌈50/10⌉ = 5 students.

4. Key Takeaways

2. Relations and Their Properties

1. What is a Relation?

A relation is a subset of the Cartesian product of two sets. It defines a connection between elements of one set with elements of another (or the same) set.

Formally, a relation R from set A to set B is a subset of A × B:

R ⊆ A × B

If (a, b) ∈ R, we write aRb, meaning "a is related to b".

Example:

Let A = {1, 2, 3} and B = {2, 3}. A relation R could be:

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

2. Types of Relations

3. Properties of Relations

1. Reflexive

A relation R on set A is reflexive if (a, a) ∈ R for all a ∈ A.

Example: R = {(1, 1), (2, 2), (3, 3)} is reflexive.

2. Symmetric

R is symmetric if (a, b) ∈ R ⇒ (b, a) ∈ R.

Example: R = {(1, 2), (2, 1)} is symmetric.

3. Antisymmetric

R is antisymmetric if (a, b) ∈ R and (b, a) ∈ R ⇒ a = b.

Example: R = {(1, 1), (2, 3)} is antisymmetric.

4. Transitive

R is transitive if (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R.

Example: R = {(1, 2), (2, 3), (1, 3)} is transitive.

4. Types of Special Relations

Example:

The "divides" relation (|) on integers is a partial order.

5. Matrix Representation of Relations

A relation can be represented by a matrix M, where:

M[i][j] = 1 if (aᵢ, aⱼ) ∈ R, otherwise 0.

Example:

A = {1, 2, 3}, R = {(1, 2), (2, 3)}

123
1010
2001
3000

6. Closure of Relations

A closure of a relation is the smallest relation containing R with a specific property:

Example:

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

Transitive closure: R⁺ = {(1, 2), (2, 3), (1, 3)}

7. Key Takeaways

3. Combining Relations

1. What Does It Mean to Combine Relations?

Given two relations on a set, you can combine them in various ways to create new relations. The main ways to combine relations are:

2. Union of Relations (R ∪ S)

The union of two relations R and S on set A is the set of pairs that belong to either R or S (or both):

R ∪ S = {(a, b) | (a, b) ∈ R or (a, b) ∈ S}

Example:

A = {1, 2, 3}

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

S = {(2, 1), (3, 3)}

R ∪ S = {(1, 2), (2, 3), (2, 1), (3, 3)}

3. Intersection of Relations (R ∩ S)

The intersection of two relations is the set of pairs that belong to both R and S:

R ∩ S = {(a, b) | (a, b) ∈ R and (a, b) ∈ S}

Example:

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

S = {(2, 3), (3, 3)}

R ∩ S = {(2, 3)}

4. Composition of Relations (R ∘ S)

The composition of relations R and S combines pairs through an intermediate element:

R ∘ S = {(a, c) | ∃b ∈ A such that (a, b) ∈ R and (b, c) ∈ S}

Example:

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

S = {(3, 4), (2, 5)}

R ∘ S = {(1, 5)}

5. Inverse of a Relation (R⁻¹)

The inverse of a relation R swaps each pair:

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

Example:

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

R⁻¹ = {(2, 1), (4, 3)}

6. Properties of Combined Relations

7. Matrix Representation of Combined Relations

Relations can be represented as adjacency matrices, and combination operations can be translated to matrix operations:

8. Key Takeaways

4. Representing Relations Using Matrices and Graphs

1. What is a Relation?

A relation R on a set A is a subset of the Cartesian product A × A. It pairs elements of the set based on a certain condition.

Example:

Set A = {1, 2, 3}

Relation R = {(1, 2), (2, 3), (3, 1)}

2. Matrix Representation of a Relation

A relation can be represented using a square matrix, where rows and columns represent elements of the set. The matrix entry is either 0 or 1:

Matrix Definition:

If A has n elements, the matrix M of relation R is an n × n matrix, where:

M[i][j] = 1 if (aᵢ, aⱼ) ∈ R, else M[i][j] = 0

Example:

Set A = {1, 2, 3}

Relation R = {(1, 2), (2, 3), (3, 1)}

Matrix M(R):

123
1010
2001
3100

3. Graph Representation of a Relation

A relation can also be represented as a directed graph, where:

Example:

For the same relation R = {(1, 2), (2, 3), (3, 1)}:

This forms a cycle in the graph!

4. Key Insights

5. Quick Example for Properties

Relation R = {(1, 1), (2, 2), (1, 2), (2, 1)}

Matrix M(R):

12
111
211

Graph:

1 ↔ 2 (Bidirectional) and self-loops at 1 and 2.

Properties:

6. Why Use Matrices and Graphs?

7. Conclusion

Relations can be represented as matrices or graphs, each offering unique advantages for analysis and visualization. Whether you want to prove properties or model real-world systems, these representations are powerful tools!

5. Equivalence Relations

1. What is an Equivalence Relation?

An equivalence relation is a special type of relation that groups elements into subsets, where elements in the same subset are related to each other in a meaningful way.

A relation R on a set A is an equivalence relation if it satisfies three properties:

2. Example of an Equivalence Relation

Set A = {1, 2, 3, 4}

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

Checking Properties:

This is an equivalence relation!

3. Equivalence Classes

An equivalence class of an element a is the set of all elements related to a:

[a] = {x ∈ A | (a, x) ∈ R}

Example:

For the relation above:

The set of all equivalence classes forms a partition of A.

4. Matrix Representation

You can represent an equivalence relation with a matrix where M[i][j] = 1 if (aᵢ, aⱼ) ∈ R, and 0 otherwise.

Matrix for the Relation:

1234
11010
20100
31010
40001

5. Graph Representation

In a graph, elements are vertices, and an edge exists between a and b if (a, b) ∈ R.

6. Real-World Examples of Equivalence Relations

6. Partial and Total Ordering Relations

1. What is a Partial Ordering Relation?

A relation R on a set A is a partial order if it is:

If a relation satisfies these three properties, it's called a partial order, and the set A with the relation R is called a partially ordered set (poset).

Example:

Set A = {1, 2, 3}

Relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}

Checking the properties:

This is a partial order!

2. What is a Total (or Linear) Ordering Relation?

A relation R on a set A is a total order if it is a partial order and has the property of comparability:

This means every pair of elements is related.

Example:

Set A = {1, 2, 3}

Relation R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3)}

Checking the properties:

This is a total order!

3. Visualizing Orders with Hasse Diagrams

A Hasse diagram is a graph that visually represents a partial order:

Example:

For the relation R = {(1, 2), (2, 3)}:

This is a simple chain representing a total order.

4. Key Differences Between Partial and Total Orders

Property Partial Order Total Order
Reflexive Yes Yes
Antisymmetric Yes Yes
Transitive Yes Yes
Comparability Not required Required
Example Subset relation (⊆) ≤ on real numbers

5. Real-World Examples

7. Lattices and Sublattices

1. What is a Lattice?

A lattice is a partially ordered set (poset) in which every pair of elements has both a:

In simpler terms, a lattice is a poset where we can always "join" and "meet" elements!

Example:

Set A = {1, 2, 3, 6}

Relation: Divides ( | )

Join and Meet:

This is a lattice!

2. Types of Lattices

3. Hasse Diagram of a Lattice

A Hasse diagram can visually represent a lattice, where elements are connected if one covers the other.

Example:

Set: {1, 2, 3, 6}

Diagram:

      6
     / \
    2   3
     \ /
      1

4. What is a Sublattice?

A sublattice is a subset of a lattice that is itself a lattice under the same meet and join operations.

Example:

Lattice: {1, 2, 3, 6}

Subset: {1, 2, 6}

Checking Sublattice Conditions:

This is a sublattice!

5. Real-World Examples

8. Hasse Diagram and Its Components

1. What is a Hasse Diagram?

A Hasse diagram is a graphical representation of a finite partially ordered set (poset). It visually shows the elements and their order relations without displaying reflexive or transitive edges explicitly.

Key Points:

2. Components of a Hasse Diagram

3. Example of a Hasse Diagram

Set: A = {1, 2, 3, 6}

Relation: Divides ( | )

Diagram:

      6
     / \
    2   3
     \ /
      1

Explanation:

4. How to Draw a Hasse Diagram

Follow these steps to construct a Hasse diagram:

  1. Identify the Set and Relation: Choose a set and a partial order relation.
  2. Create the Poset: List all pairs (a, b) where a ≤ b.
  3. Remove Reflexive Pairs: Eliminate pairs like (a, a).
  4. Remove Transitive Pairs: If (a, b) and (b, c) exist, remove (a, c).
  5. Draw the Graph: Place elements as points and connect them with lines.
  6. Arrange Vertically: Place lower elements below higher elements.

5. Real-World Examples

6. Practice Problem

Set: B = {1, 2, 4, 8}

Relation: Divides ( | )

Question: