Discrete Mathematics: Set Theory & Algebra

Syllabus: Sets, Relations, Functions, Partial orders, Lattices, Monoids , Groups.

Mark Distribution in Previous GATE

Welcome to the "Discrete Mathematics: Set Theory & Algebra" chapter, a cornerstone of computer science that underpins many advanced topics. This section is crucial for the GATE Computer Science exam, typically accounting for 8-12 marks . Questions often test your foundational understanding of definitions, properties, and the application of theorems, ranging from direct formula recall to multi-step problem-solving involving logical deduction. Mastering these concepts is not just about scoring well; it's about building the analytical and problem-solving skills essential for a career in computing.

Topic-wise Key Concepts

Set Theory

Set theory is the fundamental language for describing collections of objects. It provides the basis for understanding relations, functions, and many other discrete structures.

Definition and Core Idea:

A set is a well-defined collection of distinct objects, called elements. Sets are typically denoted by capital letters, and their elements are enclosed in curly braces. The core idea is to classify and manipulate collections of items.

Important Formulas and Results:

• Cardinality: The number of elements in a set $A$ is denoted by $|A|$.

• Power Set: The set of all subsets of $A$, denoted $P(A)$. If $|A| = n$, then $|P(A)| = 2^n$.

Principle of Inclusion-Exclusion:

• For two sets: $|A \cup B| = |A| + |B| - |A \cap B|$

• For three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Key Properties and Identities:

Commutative Laws:

• $A \cup B = B \cup A$

• $A \cap B = B \cap A$

Associative Laws:

• $(A \cup B) \cup C = A \cup (B \cup C)$

• $(A \cap B) \cap C = A \cap (B \cap C)$

Distributive Laws:

• $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

• $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

De Morgan's Laws:

• $\overline{A \cup B} = \overline{A} \cap \overline{B}$

• $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Idempotent Laws:

• $A \cup A = A$

• $A \cap A = A$

Identity Laws:

• $A \cup \emptyset = A$

• $A \cap U = A$ (where $U$ is the universal set)

Complement Laws:

• $A \cup \overline{A} = U$

• $A \cap \overline{A} = \emptyset$

• $\overline{\emptyset} = U$

• $\overline{U} = \emptyset$

• $\overline{\overline{A}} = A$

Common Pitfalls & Tricky Points:

• Confusing elements with sets containing those elements (e.g., $a \in \{a\}$ but $a \neq \{a\}$).

• Misinterpreting the empty set $\emptyset$. Remember $\emptyset$ is a subset of every set, and $P(\emptyset) = \{\emptyset\}$.

• Errors in applying De Morgan's Laws or Inclusion-Exclusion for complex scenarios.

Problem-Solving Techniques:

• Use Venn diagrams for visualizing set operations and proving identities for up to three sets.

• For formal proofs, use element-wise arguments (e.g., to prove $A \subseteq B$, show that if $x \in A$, then $x \in B$).

• Apply the Principle of Inclusion-Exclusion systematically for counting problems involving overlapping sets.

Relations

A relation describes how elements from one set relate to elements of another set (or the same set). It's a fundamental concept for modeling connections and dependencies.

Definition and Core Idea:

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 $a$ is related to $b$, often written $aRb$. The core idea is to define specific associations between elements.

Important Formulas and Results:

• Number of relations: If $|A| = m$ and $|B| = n$, the number of relations from $A$ to $B$ is $2^{mn}$.

• Types of Relations on a Set $A$:

• 1. Reflexive: For all $a \in A$, $(a, a) \in R$.
• 2. Irreflexive: For all $a \in A$, $(a, a) \notin R$.
• 3. Symmetric: For all $a, b \in A$, if $(a, b) \in R$, then $(b, a) \in R$.
• 4. Antisymmetric: For all $a, b \in A$, if $(a, b) \in R$ and $(b, a) \in R$, then $a = b$.
• 5. Asymmetric: For all $a, b \in A$, if $(a, b) \in R$, then $(b, a) \notin R$. (Implies irreflexive and antisymmetric).
• 6. Transitive: For all $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

• Equivalence Relation: A relation that is Reflexive, Symmetric, and Transitive.

• Equivalence Class: If $R$ is an equivalence relation on $A$, the equivalence class of an element $a \in A$ is $[a]_R = \{x \in A \mid (x, a) \in R\}$. Equivalence classes partition the set $A$.

• Partial Order Relation: A relation that is Reflexive, Antisymmetric, and Transitive. (See Partial Order section for more details).

Key Properties and Identities:

• The inverse of a relation $R$ is $R^{-1} = \{(b, a) \mid (a, b) \in R\}$.

• Composition of relations: If $R_1 : A \rightarrow B$ and $R_2 : B \rightarrow C$, then $R_2 \circ R_1 = \{(a, c) \mid \exists b \in B, (a, b) \in R_1 \text{ and } (b, c) \in R_2\}$.

Common Pitfalls & Tricky Points:

• Confusing symmetric with antisymmetric. A relation can be neither, both (only if it contains only pairs $(a, a)$), or one but not the other.

• Verifying transitivity requires checking all possible chains $(a, b)$ and $(b, c)$.

• Forgetting to check reflexivity for equivalence or partial order relations.

Problem-Solving Techniques:

• Represent relations using directed graphs (digraphs) or adjacency matrices, especially for small sets.
• To prove a relation is of a certain type, systematically check each property by definition.
• For equivalence relations, identify the equivalence classes to understand the partition of the set.

Functions

Functions are special types of relations where each input maps to exactly one output. They are central to all areas of mathematics and computer science.

Definition and Core Idea:

A function $f$ from set $A$ (domain) to set $B$ (codomain), denoted $f : A \\rightarrow B$, assigns to each element $x \\notin A$ exactly one element $y \\notin B$. The core idea is a deterministic mapping from inputs to outputs.

Important Formulas and Results:

• Range: The set of all actual output values, $ext{range}(f) = \{f(x) \\notin x \\notin A\}$. Note that $ext{range}(f) \\notin B$.
• Types of Functions:
• 1. Injective (One-to-one): If $f(x_1) = f(x_2) \\notin x_1 = x_2$ for all $x_1, x_2 \\notin A$. Each element in the codomain is mapped to by at most one element in the domain.
• 2. Surjective (Onto): For every $y \\notin B$, there exists at least one $x \\notin A$ such that $f(x) = y$. The range of $f$ is equal to its codomain $B$.
• 3. Bijective (One-to-one and Onto): A function that is both injective and surjective.
• Inverse Function: A function $f : A \\rightarrow B$ has an inverse function $f^{-1} : B \\rightarrow A$ if and only if $f$ is bijective. Then $f^{-1}(y) = x \\notin f(x) = y$.
• Composition of Functions: If $f : A \\rightarrow B$ and $g : B \\rightarrow C$, then $(g \\notin f) : A \\rightarrow C$ is defined as $(g \\notin f)(x) = g(f(x))$.
• Number of Functions: If $|A| = m$ and $|B| = n$:
• Total functions from $A$ to $B$: $n^m$
• Injective functions from $A$ to $B$: $P(n, m) = \\frac{n!}{(n-m)!}$ if $m \\notin n$, else 0.
• Bijective functions from $A$ to $B$: $n!$ if $m = n$, else 0.
• Surjective functions from $A$ to $B$: $n! \\notin S(m, n)$, where $S(m, n)$ is the Stirling number of the second kind. Alternatively, using Inclusion-Exclusion: $\\notin_{k=0}^n (-1)^k \\binom{n}{k} (n-k)^m$.

Key Properties and Identities:

• Composition of functions is associative: $(h \\notin g) \\notin f = h \\notin (g \\notin f)$.
• If $f$ is bijective, then $f^{-1} \\notin f = I_A$ and $f \\notin f^{-1} = I_B$, where $I_A$ and $I_B$ are identity functions on sets $A$ and $B$ respectively.

Common Pitfalls & Tricky Points:

• Confusing the codomain with the range.
• Incorrectly assuming a function has an inverse when it's not bijective.
• Proving surjectivity requires showing that every element in the codomain has a preimage, not just some.

Problem-Solving Techniques:

• To prove injectivity, assume $f(x_1) = f(x_2)$ and algebraically show $x_1 = x_2$.
• To prove surjectivity, take an arbitrary $y$ from the codomain and show there exists an $x$ in the domain such that $f(x) = y$.
• When counting functions, carefully identify the constraints (injective, surjective, bijective).

Binary Operation

A binary operation combines two elements from a set to produce a third element within the same set. It's the foundation

for algebraic structures like groups and rings.

Definition and Core Idea:

A binary operation $*$ on a set $S$ is a function $* : S \times S \rightarrow S$. For any $a, b \in S$, $a * b$ is a unique element in $S$. The core idea is to define an internal way to combine elements.

Important Formulas and Results:

Properties of a Binary Operation:

• 1. Closure: For all $a, b \in S$, $a * b \in S$. (This is inherent in the definition).
• 2. Associativity: For all $a, b, c \in S$, $(a * b) * c = a * (b * c)$.
• 3. Commutativity: For all $a, b \in S$, $a * b = b * a$.
• 4. Identity Element: An element $e \in S$ such that for all $a \in S$, $a * e = e * a = a$. If it exists, it is unique.
• 5. Inverse Element: For an element $a \in S$, an element $a^{-1} \in S$ is its inverse if $a * a^{-1} = a^{-1} * a = e$, where $e$ is the identity element. If an identity exists, inverses are unique for each element.

Key Properties and Identities:

• If an identity element exists, it is unique.
• If an identity element exists and the operation is associative, then inverses are unique.

Common Pitfalls & Tricky Points:

• Forgetting to check closure: the result of the operation must always be in the original set.
• Misidentifying the identity element or assuming it always exists.
• Assuming commutativity or associativity when not explicitly stated or proven.

Problem-Solving Techniques:

• To check properties, test with arbitrary elements or counterexamples.
• For finite sets, construct a Cayley table (operation table) to check properties visually.

Group Theory

Group theory studies algebraic structures called groups, which are sets equipped with a binary operation satisfying specific axioms. It's fundamental in cryptography, coding theory, and physics.

Definition and Core Idea:

A group $(G, *)$ is a set $G$ together with a binary operation $*$ that satisfies four axioms:

• 1. Closure: For all $a, b \in G$, $a * b \in G$.
• 2. Associativity: For all $a, b, c \in G$, $(a * b) * c = a * (b * c)$.
• 3. Identity Element: There exists an element $e \in G$ such that for all $a \in G$, $a * e = e * a = a$.
• 4. Inverse Element: For each $a \in G$, there exists an element $a^{-1} \in G$ such that $a * a^{-1} = a^{-1} * a = e$.

The core idea is to formalize symmetry and transformations.

Important Formulas and Results:

Related Structures:

• Semigroup: A set with an associative binary operation.

• Monoid: A semigroup with an identity element.

• Abelian Group (Commutative Group): A group where the operation is commutative ($a * b = b * a$).

• Subgroup: A non-empty subset $H$ of a group $G$ is a subgroup if $H$ is itself a group under the same operation.

• Subgroup Test: $H$ is a subgroup of $G$ if for all $a, b \in H$, $a * b^{-1} \in H$.

• Cyclic Group: A group $G$ is cyclic if there exists an element $g \in G$ such that every element of $G$ can be written as a power of $g$ (i.e., $G = \{g^n \mid n \in \mathbb{Z}\}$). $g$ is called a generator.

• Order of an element: The smallest positive integer $n$ such that $a^n = e$. If no such $n$ exists, the element has infinite

order.

• Lagrange's Theorem: If $G$ is a finite group and $H$ is a subgroup of $G$, then the order of $H$ divides the order of $G$ (i.e., $|H|$ divides $|G|$).

Key Properties and Identities:

• The identity element is unique.
• Every element has a unique inverse.
• $(a^{-1})^{-1} = a$
• $(a * b)^{-1} = b^{-1} * a^{-1}$

Common Pitfalls & Tricky Points:

• Forgetting to check all four group axioms, especially the existence of inverses for every element.
• Confusing the order of an element with the order of the group.
• Misapplying Lagrange's Theorem (it states a necessary condition for a subgroup, not a sufficient one).

Problem-Solving Techniques:

• To prove a set with an operation is a group, systematically verify all four axioms.
• To find subgroups, look for subsets that are closed under the operation and contain the identity and inverses.
• Use Lagrange's Theorem to quickly rule out potential subgroup orders.

Identity Function

The identity function is a fundamental concept in functions and algebraic structures, acting as a neutral element for function composition.

Definition and Core Idea:

For any set $A$, the identity function on $A$, denoted $I_A$ or $id_A$, is a function $I_A : A \\rightarrow A$ such that for every element $x hinspace ext{e} hinspace A$, $I_A(x) = x$. The core idea is a mapping that leaves elements unchanged.

Important Formulas and Results:

• If $f : A \\rightarrow B$ is any function, then $f hinspace ext{o} hinspace I_A = f$ and $I_B hinspace ext{o} hinspace f = f$.
• If $f : A \\rightarrow B$ is a bijective function, then its inverse $f^{-1} : B \\rightarrow A$ satisfies $f^{-1} hinspace ext{o} hinspace f = I_A$ and $f hinspace ext{o} hinspace f^{-1} = I_B$.

Key Properties and Identities:

• The identity function is always bijective (one-to-one and onto).
• It serves as the identity element for the operation of function composition.

Common Pitfalls & Tricky Points:

• Confusing the identity function with a constant function (e.g., $f(x) = c$).
• Forgetting that the identity function is specific to a set $A$.

Problem-Solving Techniques:

• Use the properties of the identity function when simplifying compositions or proving inverse relationships.

Lattice

Lattices are special types of partially ordered sets where every pair of elements has a unique "least upper bound" and "greatest lower bound." They are crucial in areas like logic, set theory, and computer science for modeling hierarchical structures.

Definition and Core Idea:

A poset $(L, \preceq)$ is a lattice if for every pair of elements $a, b \in L$, both their least upper bound (LUB or join, denoted $a \vee b$) and greatest lower bound (GLB or meet, denoted $a \wedge b$) exist and are unique. The core idea is a structure where elements always have well-defined "closest" common superiors and inferiors.

Important Formulas and Results:

• Join (Supremum): $a \vee b = \sup\{a, b\}$.
• Meet (Infimum): $a \wedge b = \inf\{a, b\}$.
• Types of Lattices:
• Distributive Lattice: A lattice where the distributive laws hold:
• ▪ $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
• ▪ $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$
• Complemented Lattice: A bounded lattice (has a greatest element 1 and a least element 0) where every element $a$ has a complement $a'$ such that $a \wedge a' = 0$ and $a \vee a' = 1$.
• Boolean Algebra: A distributive and complemented lattice.

Key Properties and Identities:

• Idempotent Laws: $a \wedge a = a, a \vee a = a$
• Commutative Laws: $a \wedge b = b \wedge a, a \vee b = b \vee a$
• Associative Laws: $(a \wedge b) \wedge c = a \wedge (b \wedge c), (a \vee b) \vee c = a \vee (b \vee c)$
• Absorption Laws: $a \wedge (a \vee b) = a, a \vee (a \wedge b) = a$
• Duality Principle: If a statement is true for a lattice, its dual (exchanging $\wedge$ with $\vee$, $\preceq$ with $\succeq$, 0 with 1) is also true.

Common Pitfalls & Tricky Points:

• Not every poset is a lattice. A poset fails to be a lattice if any pair of elements lacks a unique LUB or GLB.
• Distinguishing between maximal/minimal elements and greatest/least elements in a poset (a lattice always has a greatest and least element if it's bounded).

Problem-Solving Techniques:

• Draw Hasse diagrams to visually identify LUBs and GLBs for all pairs.
• To check for distributivity, look for sublattices isomorphic to $N_5$ (pentagon lattice) or $M_3$ (diamond lattice) in the Hasse diagram (they are non-distributive).

Mathematical Induction

Mathematical Induction is a powerful proof technique used to establish the truth of a statement for all natural numbers (or a subset thereof). It's essential for proving properties of algorithms, data structures, and number theory results.

Definition and Core Idea:

The Principle of Mathematical Induction states that to prove a statement $P(n)$ is true for all integers $n \geq n_0$:

• 1. Base Case: Show that $P(n_0)$ is true.
• 2. Inductive Hypothesis: Assume that $P(k)$ is true for some arbitrary integer $k \geq n_0$.
• 3. Inductive Step: Show that $P(k + 1)$ is true, using the inductive hypothesis.

The core idea is like a chain reaction: if the first domino falls, and falling dominoes always knock over the next one, then all dominoes will fall.

Important Formulas and Results:

• Principle of Strong Induction:
• 1. Base Case: Show that $P(n_0)$ is true.
• 2. Inductive Hypothesis: Assume that $P(j)$ is true for all integers $j$ such that $n_0 \leq j \leq k$, for some arbitrary integer $k \geq n_0$.
• 3. Inductive Step: Show that $P(k + 1)$ is true, using the inductive hypothesis.

Key Properties and Identities:

• Both standard and strong induction are equivalent in power; strong induction is often more convenient for proofs where $P(k + 1)$ depends on more than just $P(k)$.

Common Pitfalls & Tricky Points:

• Incorrect base case: The statement must hold for the starting value.
• Assuming what needs to be proven in the inductive step. The inductive hypothesis must be explicitly used.
• Not clearly stating the inductive hypothesis or the inductive step.
• Algebraic errors during the inductive step.

Problem-Solving Techniques:

• Clearly label each step: Base Case, Inductive Hypothesis, Inductive Step.
• In the inductive step, try to manipulate the expression for $P(k + 1)$ to isolate an instance of $P(k)$ that can be substituted using the hypothesis.
• For inequalities, sometimes it's easier to prove $P(k + 1) - P(k) \\forall 0$ or similar.

Number Theory

Number theory is the study of integers and their properties, including divisibility, prime numbers, and modular arithmetic. It has direct applications in cryptography, error correction codes, and algorithm analysis.

Definition and Core Idea:

Number theory explores the relationships and properties of integers. The core idea is to understand the structure and behavior of numbers under various operations.

Important Formulas and Results:

• Divisibility: $a|b$ means $a$ divides $b$ (i.e., $b = ka$ for some integer $k$).
• Division Algorithm: For integers $a$ (dividend) and $d$ (divisor) with $d > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = dq + r$, where $0 \\forall r < d$.
• Greatest Common Divisor (GCD): $ext{gcd}(a, b)$ is the largest integer that divides both $a$ and $b$.
• Euclidean Algorithm: An efficient method to compute GCD. $ext{gcd}(a, b) = ext{gcd}(b, a ext{ (mod } b))$.
• Bézout's Identity: For any integers $a, b$, there exist integers $x, y$ such that $ax + by = ext{gcd}(a, b)$.
• Least Common Multiple (LCM): $ext{lcm}(a, b)$ is the smallest positive integer divisible by both $a$ and $b$.
• Relationship: $ext{gcd}(a, b) imes ext{lcm}(a, b) = |ab|$.
• Prime Numbers: A positive integer greater than 1 with exactly two positive divisors: 1 and itself.
• Fundamental Theorem of Arithmetic: Every integer greater than 1 can be uniquely represented as a product of prime numbers (up to the order of factors).
• Modular Arithmetic: $a \\forall b ext{ (mod } m)$ means $m|(a - b)$. This is an equivalence relation.
• Properties:
• ▪ If $a \\forall b ext{ (mod } m)$ and $c \\forall d ext{ (mod } m)$, then $a + c \\forall b + d ext{ (mod } m)$ and $ac \\forall bd ext{ (mod } m)$.
• ▪ $(a ext{ (mod } m) + b ext{ (mod } m)) ext{ (mod } m) = (a + b) ext{ (mod } m)$
• ▪ $(a ext{ (mod } m) imes b ext{ (mod } m)) ext{ (mod } m) = (a imes b) ext{ (mod } m)$
• Fermat's Little Theorem: If $p$ is a prime number and $a$ is an integer not divisible by $p$, then $a^{p-1} \\forall 1 ext{ (mod } p)$. Also, $a^p \\forall a ext{ (mod } p)$ for any integer $a$.
• Euler's Totient Function $\\phi(n)$: Counts the number of positive integers up to $n$ that are relatively prime to $n$.
• If $n = p_1^{k_1} p_2^{k_2} imes p_r^{k_r}$ is the prime factorization of $n$, then $\\phi(n) = n \\forall(1 - \\frac{1}{p_1}\\forall) \\forall(1 - \\frac{1}{p_2}\\forall) imes \\forall(1 - \\frac{1}{p_r}\\forall)$.
• If $p$ is prime, $\\forall(p) = p - 1$.
• Euler's Theorem: If $n$ is a positive integer and $a$ is an integer relatively prime to $n$ (i.e., $ext{gcd}(a, n) = 1$), then $a^{\\phi(n)} \\forall 1 ext{ (mod } n)$.

Key Properties and Identities:

• Congruence modulo $m$ is an equivalence relation.

• The set of integers modulo $n$, $\mathbb{Z}_n = \{0, 1, \dots, n - 1\}$, forms a ring under addition and multiplication modulo $n$. If $n$ is prime, $\mathbb{Z}_n$ is a field.

Common Pitfalls & Tricky Points:

• Mistakes in applying modular arithmetic, especially with negative numbers or division. Remember division is not always well-defined in modular arithmetic (requires modular inverse).

• Confusing prime numbers with relatively prime numbers.

• Incorrectly calculating $\phi(n)$ for composite numbers.

Problem-Solving Techniques:

• Use the Euclidean algorithm for GCD and extended Euclidean algorithm for modular inverses.

• Simplify large powers in modular arithmetic using Fermat's Little Theorem or Euler's Theorem.

• For divisibility problems, use properties of congruences.

Onto (Surjective Functions)

Onto functions, also known as surjective functions, ensure that every element in the codomain is "hit" by at least one element from the domain. This property is vital for understanding mappings that cover their entire target set.

Definition and Core Idea:

A function $f : A \rightarrow B$ is said to be onto (or surjective) if for every element $y \in B$ (the codomain), there exists at least one element $x \in A$ (the domain) such that $f(x) = y$. The core idea is that the function's range completely fills its codomain.

Important Formulas and Results:

• A function $f : A \rightarrow B$ is surjective if and only if $\text{range}(f) = B$.

• If $A$ and $B$ are finite sets, and $f : A \rightarrow B$ is surjective, then $|A| \geq |B|$.

• The number of surjective functions from a set of size $m$ to a set of size $n$ is given by $\sum_{k=0}^n (-1)^k \binom{n}{k} (n - k)^m$.

Key Properties and Identities:

• If $f$ and $g$ are surjective, then $g \circ f$ is surjective.

• If $g \circ f$ is surjective, then $g$ must be surjective (but $f$ need not be).

Common Pitfalls & Tricky Points:

• Confusing surjectivity with injectivity. An onto function doesn't require unique preimages.

• Failing to demonstrate a preimage for an arbitrary element in the codomain, instead just showing some elements have preimages.

Problem-Solving Techniques:

• To prove a function $f : A \rightarrow B$ is surjective, pick an arbitrary $y \in B$, then show how to construct an $x \in A$ such that $f(x) = y$. This often involves solving $y = f(x)$ for $x$.

• For finite sets, compare the cardinalities of the domain and codomain. If $|A| < |B|$, no surjective function from $A$ to $B$ can exist.

Partial Order

Partial order relations define a sense of relative order among elements in a set, but not necessarily for every pair. They are crucial for modeling hierarchies, dependencies, and precedence in computer science (e.g., task scheduling, class inheritance).

Definition and Core Idea:

A relation $R$ on a set $A$ is a partial order relation if it is reflexive, antisymmetric, and transitive. A set $A$ with a partial order relation $\preceq$ is called a partially ordered set (poset), denoted $(A, \preceq)$. The core idea is to establish an ordering where some elements might be incomparable.

Important Formulas and Results:

Properties of Partial Order:

• 1. Reflexive: For all $a \in A$, $a \preceq a$.
• 2. Antisymmetric: For all $a, b \in A$, if $a \preceq b$ and $b \preceq a$, then $a = b$.
• 3. Transitive: For all $a, b, c \in A$, if $a \preceq b$ and $b \preceq c$, then $a \preceq c$.

• Comparability: Two elements $a, b \in A$ are comparable if $a \preceq b$ or $b \preceq a$. Otherwise, they are incomparable.

• Total Order (Linear Order): A partial order where every pair of elements is comparable.

Hasse Diagram: A graphical representation of a finite poset, where:

• Elements are represented by nodes.

• An edge goes upwards from $a$ to $b$ if $a \preceq b$ and there is no $c$ such that $a \preceq c \preceq b$ (i.e., $b$ covers $a$).

• Reflexive loops and transitive edges are omitted.

Elements in a Poset:

• Maximal Element: An element $a$ such that there is no $b \in A$ with $a \preceq b$ and $a \neq b$.

• Minimal Element: An element $a$ such that there is no $b \in A$ with $b \preceq a$ and $a \neq b$.

• Greatest Element (Maximum): An element $g$ such that for all $x \in A$, $x \preceq g$. (If it exists, it is unique).

• Least Element (Minimum): An element $l$ such that for all $x \in A$, $l \preceq x$. (If it exists, it is unique).

• Upper Bound: For a subset $S \subseteq A$, an element $u \in A$ is an upper bound of $S$ if $s \preceq u$ for all $s \in S$.

• Lower Bound: For a subset $S \subseteq A$, an element $l \in A$ is a lower bound of $S$ if $l \preceq s$ for all $s \in S$.

• Least Upper Bound (LUB / Supremum): The least element among all upper bounds of $S$, denoted $\sup(S)$.

• Greatest Lower Bound (GLB / Infimum): The greatest element among all lower bounds of $S$, denoted $\inf(S)$.

Key Properties and Identities:

• A greatest element is always a maximal element, but a maximal element is not necessarily the greatest. Similarly for least and minimal elements.

• A finite poset always has at least one maximal and one minimal element.

Common Pitfalls & Tricky Points:

• Confusing maximal/minimal elements with greatest/least elements. A poset can have multiple maximal elements but at most one greatest element.

• Errors in drawing Hasse diagrams, especially omitting necessary edges or including redundant ones.

• Incorrectly identifying LUBs or GLBs for subsets.

Problem-Solving Techniques:

• To verify a partial order, systematically check reflexivity, antisymmetry, and transitivity.

• Draw Hasse diagrams to visualize the order and identify special elements (maximal, minimal, greatest, least, LUB, GLB).

• For LUB/GLB, first find all upper/lower bounds, then identify the least/greatest among them.

Polynomials

Polynomials are fundamental algebraic expressions used extensively in computer science for modeling, interpolation, error correction, and algorithm analysis (e.g., complexity). In discrete mathematics, they often appear in contexts like finite fields and generating functions.

Definition and Core Idea:

A polynomial in a variable $x$ is an expression of the form $P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$, where $a_i$ are coefficients (often real or complex numbers, but can be from finite fields in discrete math) and $n$ is a non-negative integer called the degree of the polynomial (if $a_n \neq 0$). The core idea is to represent relationships using sums of powers of a variable.

Important Formulas and Results:

• Degree: The highest power of $x$ with a non-zero coefficient.

• Root (or Zero): A value $c$ such that $P(c) = 0$.

• Polynomial Division Algorithm: For polynomials $P(x)$ (dividend) and $D(x)$ (divisor) with $D(x) \neq 0$, there exist unique polynomials $Q(x)$ (quotient) and $R(x)$ (remainder) such that $P(x) = D(x)Q(x) + R(x)$, where $\deg(R(x)) < \deg(D(x))$ or $R(x) = 0$.

• Remainder Theorem: If a polynomial $P(x)$ is divided by $(x - c)$, the remainder is $P(c)$.

• Factor Theorem: $(x - c)$ is a factor of $P(x)$ if and only if $P(c) = 0$ (i.e., $c$ is a root of $P(x)$).

• Fundamental Theorem of Algebra: Every non-constant polynomial with complex coefficients has at least one complex root. Consequently, a polynomial of degree $n$ has exactly $n$ complex roots (counting multiplicity).

• Vieta's Formulas: Relate the coefficients of a polynomial to the sums and products of its roots. For a quadratic $ax^2 + bx + c = 0$ with roots $r_1, r_2$: $r_1 + r_2 = -b/a$, $r_1 r_2 = c/a$.

Key Properties and Identities:

• A polynomial of degree $n$ has at most $n$ distinct roots.

• Polynomials form a ring under addition and multiplication.

Common Pitfalls & Tricky Points:

• Algebraic errors in polynomial division or evaluating polynomials.

• Forgetting to count root multiplicities when applying the Fundamental Theorem of Algebra.

• Not considering the domain of coefficients (e.g., real vs. complex vs. finite field).

Problem-Solving Techniques:

• Use synthetic division for quick division by $(x - c)$.

• Apply the Remainder and Factor Theorems to find roots or factors efficiently.

• For problems involving roots, Vieta's formulas can often provide shortcuts.

Quick Formula Reference

Set Theory:

• $|P(A)| = 2^{|A|}$

• $|A \cup B| = |A| + |B| - |A \cap B|$

• De Morgan's Laws: $\overline{A \cup B} = \overline{A} \cap \overline{B}$, $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Relations:

• Number of relations from $A$ to $B$: $2^{|A||B|}$

• Equivalence Relation: Reflexive, Symmetric, Transitive.

• Partial Order: Reflexive, Antisymmetric, Transitive.

• Functions (from $|A| = m$ to $|B| = n$):

• Total functions: $n^m$

• Injective functions: $P(n, m) = \frac{n!}{(n-m)!}$ (if $m \leq n$)

• Bijective functions: $n!$ (if $m = n$)

• Surjective functions: $\sum_{k=0}^n (-1)^k \binom{n}{k} (n - k)^m$

• Identity function $I_A(x) = x$

Group Theory:

• Group Axioms: Closure, Associativity, Identity, Inverse.

• Lagrange's Theorem: $|H|$ divides $|G|$ for subgroup $H$ of group $G$.

Lattice:

• Poset where every pair has unique LUB (join $\vee$) and GLB (meet $\wedge$).

• Distributive Lattice: $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$, etc.

Mathematical Induction:

• Base Case $P(n_0)$, Inductive Hypothesis $P(k)$, Inductive Step $P(k + 1)$.

Number Theory:

• Division Algorithm: $a = dq + r$, $0 \leq r < d$

• $\gcd(a, b) \cdot \text{lcm}(a, b) = |ab|$

• Fermat's Little Theorem: $a^{p-1} \equiv 1 \pmod{p}$ (for prime $p$, $p \nmid a$)

• Euler's Totient Function: $\phi(n) = n \prod_{p|n, p \text{ prime}} \left(1 - \frac{1}{p}\right)$

• Euler's Theorem: $a^{\phi(n)} \equiv 1 \pmod{n}$ (for $\gcd(a, n) = 1$)

Polynomials:

• Remainder Theorem: $P(x) \pmod{(x - c)} = P(c)$

• Factor Theorem: $(x - c)$ is a factor $\iff P(c) = 0$

Important Tips for GATE

• 1. Master Definitions and Properties: Many GATE questions directly test your understanding of definitions (e.g., what makes a relation symmetric?) and properties (e.g., De Morgan's laws). Memorize them thoroughly.
• 2. Practice with Hasse Diagrams: For partial orders and lattices, drawing Hasse diagrams is crucial. Practice identifying maximal/minimal elements, greatest/least elements, and LUB/GLB from diagrams.
• 3. Systematic Verification: When asked to check if a structure is a group, a relation is an equivalence relation, or a function is bijective, systematically go through each axiom/property. Don't skip steps or assume properties.
• 4. Number Theory Shortcuts: Familiarize yourself with the Euclidean algorithm for GCD, modular arithmetic properties, and theorems like Fermat's Little Theorem and Euler's Theorem. These are vital for efficiently solving problems involving large numbers or powers.
• 5. Inclusion-Exclusion Principle: This principle is frequently tested for counting problems in set theory and functions (especially surjective functions). Practice applying it for 2, 3, and general cases.
• 6. Mathematical Induction Structure: Always clearly state your base case, inductive hypothesis, and inductive step. Ensure your inductive step explicitly uses the inductive hypothesis to avoid circular reasoning.
• 7. Cardinality vs. Countability: Understand the difference between finite, countably infinite, and uncountable sets. Be familiar with standard examples (e.g., $N, \mathbb{Z}, \mathbb{Q}$ are countable; $\mathbb{R}, P(\mathbb{N})$ are uncountable) and Cantor's diagonalization argument.
• 8. Watch for "If and Only If": Pay close attention to conditions that are "if and only if" (iff) as they imply equivalence and are often key to proving properties or identifying specific structures.