Set theory, relations, functions and lattices notes — Unit 1

A Set is a well-defined collection of distinct objects, considered as an object in its own right. The objects in a set are called its elements or members.

⇒1.1 Representation of Sets

• Roster (Tabular) Form: Listing all elements inside braces. e.g., $A = \{1, 2, 3, 4\}$
• Set-Builder Form: Stating the properties that its members must satisfy. e.g., $A = \{x \mid x \text{ is an even integer and } 0 < x < 10\}$

⇒1.2 Types of Sets

• Null/Empty Set: A set with no elements. Denoted by $\emptyset$ or $\{\}$.
• Singleton Set: A set with exactly one element.
• Finite and Infinite Sets: Sets with a countable vs uncountable number of elements.
• Universal Set: The set containing all objects or elements and of which all other sets are subsets. Denoted by $U$ or $S$.
• Power Set: The set of all subsets of a set $A$, denoted by $P(A)$. If $|A| = n$, then $|P(A)| = 2^n$.

Fundamental operations can be performed on sets to construct new sets.

⇒2.1 Basic Operations

• Union ($A \cup B$): The set of all elements that are in $A$, or in $B$, or in both.
• Intersection ($A \cap B$): The set of all elements that are in both $A$ and $B$.
• Difference ($A - B$): The set of all elements that are in $A$ but not in $B$. Note that $A - B \neq B - A$.
• Symmetric Difference ($A \oplus B$ or $A \triangle B$): The set of elements that are in $A$ or $B$, but not in both. $(A - B) \cup (B - A)$.
• Complement ($A'$ or $A^c$): The set of all elements in the universal set $U$ that are not in $A$.

⇒2.2 Laws of Set Algebra

Sets obey specific algebraic laws, which are heavily used in proofs:

• Idempotent Laws: $A \cup A = A$ and $A \cap A = A$
• Commutative Laws: $A \cup B = B \cup A$ and $A \cap B = B \cap A$
• Associative Laws: $(A \cup B) \cup C = A \cup (B \cup C)$
• Distributive Laws: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• De Morgan's Laws: $(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$

The Cartesian Product of two sets $A$ and $B$, denoted by $A \times B$, is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$.

$A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$

⇒3.1 Definition of a Relation

A Relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A \times B$. If $(a, b) \in R$, we say that $a$ is related to $b$ under $R$, denoted as $aRb$.

⇒3.2 Domain and Range

• Domain: The set of all first elements of the ordered pairs in a relation $R$.
• Range: The set of all second elements of the ordered pairs in a relation $R$.
• Inverse Relation ($R^{-1}$): If $R$ is a relation from $A$ to $B$, then $R^{-1}$ is a relation from $B$ to $A$ defined by $R^{-1} = \{(b, a) \mid (a, b) \in R\}$.

A relation $R$ defined on a single set $A$ (i.e., $R \subseteq A \times A$) can have the following properties:

• Reflexive: Every element is related to itself. For all $a \in A$, $(a, a) \in R$.
• Irreflexive: No element is related to itself. For all $a \in A$, $(a, a) \notin R$.
• Symmetric: If $a$ is related to $b$, then $b$ is related to $a$. If $(a, b) \in R$, then $(b, a) \in R$.
• Asymmetric: If $(a, b) \in R$, then $(b, a) \notin R$.
• Antisymmetric: If $(a, b) \in R$ and $(b, a) \in R$, then it must be that $a = b$.
• Transitive: If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

⇒4.1 Equivalence Relation

A relation $R$ on a set $A$ is an Equivalence Relation if it is strictly:

• 1. Reflexive
• 2. Symmetric
• 3. Transitive

Example: The relation "is equal to" (=) on the set of real numbers.

⇒5.1 Equivalence Classes

Let $R$ be an equivalence relation on a set $A$. The equivalence class of an element $a \in A$, denoted by $[a]$, is the set of all elements in $A$ that are related to $a$ by $R$.

$[a] = \{x \in A \mid (x, a) \in R\}$

⇒5.2 Partitions of a Set

A Partition of a set $A$ is a collection of mutually disjoint, non-empty subsets of $A$ whose union is exactly $A$.

Fundamental Theorem of Equivalence Relations: An equivalence relation on a set partitions the set into disjoint equivalence classes. Conversely, any partition of a set induces an equivalence relation.

A Function $f$ from set $A$ to set $B$ is a special type of relation where every element in $A$ is assigned to exactly one element in $B$.

• Domain: Set $A$.
• Codomain: Set $B$.
• Image: If $f(a) = b$, then $b$ is the image of $a$.
• Pre-image: $a$ is the pre-image of $b$.
• Range: The set of all actual images. Range $\subseteq$ Codomain.

⇒6.1 Types of Functions

• Injective (One-to-One): Every element in the codomain is mapped to by at most one element in the domain. If $f(x) = f(y)$, then $x = y$.
• Surjective (Onto): Every element in the codomain is mapped to by at least one element in the domain. Range $=$ Codomain.
• Bijective (One-to-One and Onto): A function that is both injective and surjective. Only bijective functions have an inverse.

Let $f: A \to B$ and $g: B \to C$ be two functions. The Composition of $f$ and $g$, denoted by $g \circ f$, is the function from $A$ to $C$ defined by:

$(g \circ f)(x) = g(f(x))$ for all $x \in A$.

⇒7.1 Properties of Composition

• Composition is not commutative: generally, $f \circ g \neq g \circ f$.
• Composition is associative: $(f \circ g) \circ h = f \circ (g \circ h)$.
• If $f$ and $g$ are both injective, then $g \circ f$ is injective.
• If $f$ and $g$ are both surjective, then $g \circ f$ is surjective.
• If $f$ and $g$ are both bijective, then $g \circ f$ is bijective.

⇒7.2 Inverse Functions

If $f: A \to B$ is bijective, its inverse $f^{-1}: B \to A$ exists such that $f^{-1}(b) = a$ if and only if $f(a) = b$. Note that $(f^{-1})^{-1} = f$, and $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

A relation $R$ on a set $A$ is a Partial Order if it is:

• 1. Reflexive
• 2. Antisymmetric
• 3. Transitive

A set $A$ together with a partial order relation $\le$ is called a Partially Ordered Set or POSET, denoted as $(A, \le)$.

⇒8.1 Why 'Partial'?

It is called 'partial' because not every pair of elements in the set needs to be comparable. If $a \le b$ or $b \le a$, they are comparable. If neither is true, they are incomparable.

Example: The set of positive integers under the relation "divides" ($a|b$). $2|4$, so 2 and 4 are comparable. However, neither $2|3$ nor $3|2$ is true, so 2 and 3 are incomparable.

A Hasse Diagram is a graphical representation of a finite POSET that strips away redundant information (reflexivity and transitivity) to make the hierarchy clear.

⇒9.1 How to construct a Hasse Diagram

• Start with the directed graph of the relation.
• Remove all self-loops (because reflexivity is implied).
• Remove all transitive edges (if $A \to B$ and $B \to C$, remove the direct edge $A \to C$).
• Arrange the nodes so that if $A \le B$, node $B$ is placed physically higher than node $A$.
• Remove the arrows (direction is implied to be upwards).

The Hasse Diagram is critical for visually identifying the maximal, minimal, greatest, and least elements of a POSET.

By analysing the Hasse diagram, we can identify various extremal elements.

• Maximal Element: An element $a$ in $A$ is maximal if there is no $x \in A$ such that $a < x$. (It is at the top of a chain in the Hasse diagram).
• Minimal Element: An element $a$ in $A$ is minimal if there is no $x \in A$ such that $x < a$. (It is at the bottom of a chain).
• Greatest Element (Maximum): An element $a$ is the greatest element if $x \le a$ for all $x \in A$. There can be at most one greatest element.
• Least Element (Minimum): An element $a$ is the least element if $a \le x$ for all $x \in A$. There can be at most one least element.

Note: A POSET can have multiple maximal/minimal elements, but it can have at most one greatest/least element. If a greatest element exists, it is the unique maximal element.

Let $S$ be a subset of a POSET $(A, \le)$.

⇒11.1 Upper Bound and Supremum (LUB)

• Upper Bound: An element $u \in A$ is an upper bound of $S$ if $x \le u$ for all $x \in S$.
• Least Upper Bound (LUB) / Supremum: The smallest of all the upper bounds of $S$. If it exists, it is unique.

⇒11.2 Lower Bound and Infimum (GLB)

• Lower Bound: An element $l \in A$ is a lower bound of $S$ if $l \le x$ for all $x \in S$.
• Greatest Lower Bound (GLB) / Infimum: The largest of all the lower bounds of $S$. If it exists, it is unique.

A Lattice is a specific type of POSET in which every pair of elements has a unique Least Upper Bound (LUB) and a unique Greatest Lower Bound (GLB).

Notation:

⇒12.1 Properties of Lattices

Because a Lattice is an algebraic structure, the Join and Meet operations satisfy several laws:

• Commutative: $a \lor b = b \lor a$ and $a \land b = b \land a$
• Associative: $a \lor (b \lor c) = (a \lor b) \lor c$ and $a \land (b \land c) = (a \land b) \land c$
• Absorption: $a \lor (a \land b) = a$ and $a \land (a \lor b) = a$
• Idempotent: $a \lor a = a$ and $a \land a = a$

⇒13.1 Bounded Lattice

A lattice that has both a greatest element (denoted by $I$ or $1$) and a least element (denoted by $O$ or $0$). Every finite lattice is a bounded lattice.

⇒13.2 Distributive Lattice

A lattice is distributive if the operations of Join and Meet distribute over each other.
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$

⇒13.3 Complemented Lattice

A bounded lattice where every element $a$ has at least one complement $a'$, such that:
$a \lor a' = I$ (Join is the greatest element)
$a \land a' = O$ (Meet is the least element)

⇒13.4 Boolean Algebra (Boolean Lattice)

A lattice that is both Distributive and Complemented is called a Boolean Lattice or Boolean Algebra. In a Boolean Lattice, the complement of every element is unique.

Set theory and Lattices form the structural backbone of Discrete Mathematics.

⇒14.1 University Exam Checklist

• Prove De Morgan’s laws using set builder notation and Venn diagrams.
• Define an Equivalence Relation and prove that a given relation is an equivalence relation.
• Explain the difference between Injective, Surjective, and Bijective functions.
• Given a relation matrix or set of pairs, draw the corresponding Hasse Diagram.
• From a Hasse Diagram, identify the maximal, minimal, greatest, and least elements.
• Define a Lattice. State the absorption laws of a lattice.

⇒14.2 Technical Interview & Application Focus

• How do Equivalence Classes relate to consistent hashing in distributed systems?
• How are POSETs and Hasse Diagrams used to model dependency resolution (e.g., package managers like npm/pip)?
• Why is a Boolean Lattice significant in the design of digital logic circuits?