Unit 2: Set Theory and Ordered Sets

Table of Contents

2.1 Basic Concept of Set Theory

A set is a well-defined, unordered collection of distinct objects, called elements or members.

2.2 Operations with Sets

  • Union: A ∪ B = \{x \mid x ∈ A or x ∈ B\}
  • Intersection: A ∩ B = \{x \mid x ∈ A and x ∈ B\}
  • Difference: A - B = \{x \mid x ∈ A and x ∉ B\}
  • Complement: A' = \{x \mid x ∈ U and x ∉ A\} (This is U - A)
  • Principle of Inclusion-Exclusion (for two sets): |A ∪ B| = |A| + |B| - |A ∩ B|

2.3 Functions

A function f from a set A (domain) to a set B (codomain), written f: A \to B, is an assignment of exactly one element of B to each element of A.
  • Range: The set of all actual output values \{f(a) \mid a ∈ A\}. The range is a subset of the codomain.
  • Injective (One-to-One): f(a) = f(b) implies a = b. Different inputs map to different outputs.
  • Surjective (Onto): For every y ∈ B, there exists an x ∈ A such that f(x) = y. The range equals the codomain.
  • Bijective (One-to-One and Onto): The function is both injective and surjective.

2.4 Relations

A binary relation R from A to B is a subset of the Cartesian Product A × B = \{(a, b) \mid a ∈ A, b ∈ B\}. If A=B, we say R is a relation on A.

Example: If A = \{1, 2, 3\}, R = \{(a, b) \mid a < b\} would be R = \{(1, 2), (1, 3), (2, 3)\}.

2.5 Properties of Relations

Let R be a relation on a set A.

  • Reflexive: (a, a) ∈ R for every a ∈ A.
  • Irreflexive: (a, a) ∉ R for every a ∈ A.
  • Symmetric: If (a, b) ∈ R, then (b, a) ∈ R.
  • Anti-symmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b.
  • Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
Equivalence Relation: A relation that is Reflexive, Symmetric, and Transitive. Partial Order: A relation that is Reflexive, Anti-symmetric, and Transitive.

2.6 Representing Relations

  • Zero-One Matrix (MR): Let A=\{a1, ..., am\} and B=\{b1, ..., bn\}. The m × n matrix MR is defined by: MR[i, j] = 1 if (ai, bj) ∈ R, and 0 otherwise.
    • Reflexive: Main diagonal is all 1s.
    • Symmetric: MR = MRT (Matrix is symmetric).
    • Anti-symmetric: If MR[i, j] = 1 and i \ne j, then MR[j, i] = 0.
  • Directed Graph (Digraph): Draw a dot (vertex) for each element in A. Draw a directed arrow from a to b if (a, b) ∈ R. A loop from a to a represents (a, a) ∈ R.

2.7 Composition of Relations

Let R be a relation from A to B, and S be a relation from B to C. The composition S ° R is a relation from A to C defined as:

S ° R = \{(a, c) \mid there exists some b ∈ B such that (a, b) ∈ R and (b, c) ∈ S\}

If using matrices, MS ° R = MR · MS (using Boolean matrix multiplication, where 1+1=1).

Powers of a relation: R2 = R ° R, R3 = R2 ° R, etc.

2.8 Closures of Relations

The closure of a relation R with respect to a property P is the smallest relation R* that contains R and has property P.

  • Reflexive Closure: R ∪ Δ, where Δ = \{(a, a) \mid a ∈ A\} is the diagonal relation.
  • Symmetric Closure: R ∪ R-1, where R-1 = \{(b, a) \mid (a, b) ∈ R\} is the inverse relation.
  • Transitive Closure (R*): R* = R ∪ R2 ∪ R3 ∪ ... ∪ Rn (where n is the number of elements in the set). It can be found efficiently using Warshall's Algorithm.

2.9 Ordered Sets

A set S with a partial ordering relation R (must be reflexive, anti-symmetric, transitive) is called a partially ordered set or poset, denoted (S, R).

  • Total Order (Linear Order): A partial order where every pair of elements is comparable (i.e., for any a, b ∈ S, either (a, b) ∈ R or (b, a) ∈ R).
  • Example: (ℤ, ≤) is a total order. The "subset" relation (⊂eq) on a power set P(A) is a partial order, but not a total order (e.g., \{a\} and \{b\} are incomparable).

2.10 Hasse Diagrams of Partially Ordered Sets

A Hasse diagram is a simplified way to draw a finite poset.

  1. Start with the digraph of the partial order.
  2. Remove all loops (reflexivity is assumed).
  3. Remove all edges that are implied by transitivity (e.g., if a \to b and b \to c, remove the direct edge a \to c).
  4. Arrange all vertices so that all arrows point upwards, then remove the arrowheads (direction is implied to be up).

In a Hasse diagram, a is "below" b and connected by a line if a is related to b and there is no c such that a is related to c and c is related to b (i.e., b *covers* a).