Unit 1: Discrete Mathematics

I. Foundations and Conventions

Discrete mathematics studies finite or countable structures whose elements are distinct rather than continuously varying. Its central method is deductive reasoning: definitions establish mathematical objects, axioms specify assumptions, and valid inference produces conclusions.

• Objects of study: Propositions, sets, mappings, ordered structures, and algebraic systems provide models for computation and combinatorial reasoning.
• Logical foundation: A proof begins with premises and uses valid rules to derive a conclusion; validity concerns the form of an argument, while truth concerns its statements.
• Set-theoretic language: Most discrete structures consist of a set together with operations or relations defined on that set.
• Standard notation:
  • ∀ means “for every,” and ∃ means “there exists.”
  • ∈ denotes membership, while ⊆ denotes the subset relation.
  • |A| denotes the cardinality of a finite set (A).
  • ℕ, ℤ, ℚ, and ℝ denote the natural numbers, integers, rational numbers, and real numbers.
• Closure principle: An operation on a set must produce an element of that set; for example, integer addition is closed because (a+b\in\mathbb Z) whenever (a,b\in\mathbb Z).
• Proof methods: Direct proof, contrapositive proof, contradiction, case analysis, and mathematical induction are recurring techniques throughout the unit.

II. Propositional Logic — Reasoning with Truth-Valued Statements

A. propositional logic

Propositional logic studies declarative statements that have exactly one of two truth values: true or false.

• Proposition: A proposition is a sentence with a definite truth value; “(7) is prime” is true, whereas a command or open expression such as “(x>3)” is not itself a proposition.
• Logical connectives:
  • Negation (\neg p) is true exactly when (p) is false.
  • Conjunction (p\land q) is true only when both operands are true.
  • Disjunction (p\lor q) is true when at least one operand is true.
  • Implication (p\to q) is false only when (p) is true and (q) is false.
  • Biconditional (p\leftrightarrow q) is true when (p) and (q) have equal truth values.
• Logical equivalence: Formulas (P) and (Q) are equivalent, written (P\equiv Q), when their truth values agree under every assignment. Important laws include:

p → q ≡ ¬p ∨ q
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Here (p) and (q) are propositions, and ≡ denotes logical equivalence.

• Special formulas: A tautology is always true, a contradiction is always false, and a contingency is true under some assignments and false under others.
• Inference: Modus ponens derives (q) from (p) and (p\to q); modus tollens derives (\neg p) from (\neg q) and (p\to q).
• Normal forms: Conjunctive normal form is a conjunction of disjunctions, while disjunctive normal form is a disjunction of conjunctions.
• Worked example: If (p) means “the input is valid” and (q) means “processing begins,” then (p\to q) permits (q) when (p) is established, but it does not permit (p) to be inferred from (q).

B. Applications and Limitations

Propositional logic provides a precise framework for validating arguments and representing binary conditions.

• Applications: Truth tables support digital circuit design, program conditions, and verification of finite logical formulas.
• Limitation: It treats whole propositions as indivisible units and cannot directly express properties such as “every integer has a successor.”

III. First Order Logic — Predicates, Variables, and Quantification

A. first order logic

First order logic extends propositional logic by describing objects, their properties, and relations among them.

• Predicate: A predicate (P(x)) becomes a proposition when the variable (x) receives a value; for example, (P(x): x>0).
• Domain: The domain is the collection over which variables range; (\forall x(x^2\geq0)) is true over (\mathbb R).
• Quantifiers:
  • (\forall x\,P(x)) states that (P) holds for every (x).
  • (\exists x\,P(x)) states that (P) holds for at least one (x).
• Negation rules:

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

Here (x) is a variable and (P(x)) is a predicate.

• Free and bound variables: In (P(x)), (x) is free; in (\forall x\,P(x)), the quantifier binds (x). A formula with no free variables is a sentence.
• Order of quantifiers: Quantifiers generally cannot be interchanged. Over the integers, (\forall x\exists y(y>x)) is true, but (\exists y\forall x(y>x)) is false.
• Inference: Universal instantiation obtains (P(a)) from (\forall xP(x)); existential generalization obtains (\exists xP(x)) from (P(a)).

B. Expressive Scope

First order logic formalizes mathematical definitions and arguments involving arbitrary objects.

• Strength: It represents internal structure, including equality, membership, order, and multi-place relations.
• Limitation: Ordinary first order quantifiers range over individual objects, not directly over every subset, predicate, or function.

IV. Sets — Collections and Set Operations

A. sets

A set is a well-defined collection of distinct objects called elements.

• Representation: Roster notation lists elements, as in (A={1,2,3}); set-builder notation specifies a property, as in (A={x\in\mathbb N:x\leq3}).
• Equality and inclusion: (A=B) exactly when they have the same elements; (A\subseteq B) means every element of (A) belongs to (B).
• Special sets: (\varnothing) is the empty set, and a universal set (U) contains all objects currently under consideration.
• Operations:

A ∪ B = {x : x ∈ A or x ∈ B}
A ∩ B = {x : x ∈ A and x ∈ B}
A − B = {x : x ∈ A and x ∉ B}
Aᶜ    = {x ∈ U : x ∉ A}

Here (A) and (B) are sets, (U) is the universal set, and (A^c) is the complement of (A).

• Power set: (\mathcal P(A)) is the set of all subsets of (A); if (|A|=n), then (|\mathcal P(A)|=2^n).
• Cartesian product: (A\times B={(a,b):a\in A,\ b\in B}); for finite sets, (|A\times B|=|A||B|).
• Counting union: For finite sets,

|A ∪ B| = |A| + |B| − |A ∩ B|

The subtraction removes elements counted twice.

B. Structural Significance

Sets provide the common language in which discrete mathematical objects are constructed.

• Foundation: Relations are sets of ordered pairs, functions are specialized relations, and algebraic structures combine sets with operations.
• Identities: Union and intersection satisfy commutative, associative, distributive, identity, and De Morgan laws.

V. Relations — Connections Between Elements

A. relations

A binary relation from (A) to (B) is any subset of the Cartesian product (A\times B).

• Notation: (aRb) means ((a,b)\in R); a relation on (A) is a subset of (A\times A).
• Core properties:
  • Reflexive: (aRa) for every (a\in A).
  • Symmetric: (aRb\Rightarrow bRa).
  • Antisymmetric: (aRb\land bRa\Rightarrow a=b).
  • Transitive: (aRb\land bRc\Rightarrow aRc).
• Equivalence relation: A relation that is reflexive, symmetric, and transitive partitions (A) into disjoint equivalence classes.
• Equivalence class: For (a\in A),

[a] = {x ∈ A : xRa}

Here ([a]) contains precisely the elements related to (a).

• Composition: If (R\subseteq A\times B) and (S\subseteq B\times C), then (S\circ R) relates (a) to (c) when some (b\in B) satisfies (aRb) and (bSc).
• Representation: Finite relations may be represented by ordered-pair lists, zero-one matrices, or directed graphs.
• Worked example: Congruence modulo (3), defined by (aRb) when (3\mid(a-b)), is an equivalence relation on (\mathbb Z) with classes ([0]), ([1]), and ([2]).

B. Applications and Distinctions

Relations model classifications, dependencies, transitions, and comparisons.

• Classification: Equivalence relations group elements that share a specified property.
• Distinction: Symmetry and antisymmetry are not opposites; equality satisfies both properties.

VI. Functions — Mappings Between Sets

A. functions

A function (f:A\to B) assigns each element of domain (A) exactly one element of codomain (B).

• Value and range: If (f(a)=b), then (b) is the image of (a); the range is (f(A)={f(a):a\in A}\subseteq B).
• Types:
  • Injective: (f(a_1)=f(a_2)\Rightarrow a_1=a_2).
  • Surjective: for every (b\in B), some (a\in A) satisfies (f(a)=b).
  • Bijective: both injective and surjective.
• Composition: For (f:A\to B) and (g:B\to C),

(g ∘ f)(a) = g(f(a))

Here (g\circ f:A\to C) applies (f) first and (g) second.

• Inverse: A function has an inverse (f^{-1}:B\to A) exactly when it is bijective.
• Identity: The identity function (I_A:A\to A) satisfies (I_A(a)=a) and (f\circ I_A=f).
• Finite cardinality: If finite sets (A) and (B) contain (m) and (n) elements, respectively, then exactly (n^m) functions exist from (A) to (B).

B. Applications and Limitations

Functions represent deterministic dependence between inputs and outputs.

• Applications: They model algorithms, sequences, permutations, encodings, and state transformations.
• Restriction: A function may not assign multiple outputs to one input, although different inputs may share an output unless injectivity is required.

VII. Partial Orders — Consistent but Incomplete Comparison

A. partial orders

A partial order is a reflexive, antisymmetric, and transitive relation (\preceq) on a set (P); the pair ((P,\preceq)) is a partially ordered set, or poset.

• Comparability: Elements (a,b\in P) are comparable when (a\preceq b) or (b\preceq a); otherwise they are incomparable.
• Total order: A partial order is total when every pair of elements is comparable, as with (\leq) on (\mathbb Z).
• Strict order: (a\prec b) means (a\preceq b) and (a\neq b).
• Extremal elements: A least element lies below every element, while a minimal element has no strictly smaller element. Least elements are unique; several minimal elements may exist.
• Bounds: An upper bound of (S\subseteq P) lies above every member of (S); the least such bound is the supremum. Lower bounds and infima are dual notions.
• Hasse diagram: A finite poset is drawn using cover relations, omitting loops, arrowheads, and edges implied by transitivity.
• Worked example: Under divisibility, (({1,2,3,6},\mid)) has least element (1), greatest element (6), and incomparable elements (2) and (3).

B. Structural Role

Partial orders describe hierarchy without requiring every pair to be ranked.

• Applications: Examples include subset inclusion, divisibility, task dependencies, inheritance structures, and refinement of information.
• Duality: Reversing every order relation exchanges least with greatest, minimal with maximal, and upper bounds with lower bounds.

VIII. Lattices — Posets with Canonical Bounds

A. lattices

A lattice is a poset in which every pair of elements has both a greatest lower bound and a least upper bound.

• Meet and join: For (a,b\in L), the meet (a\wedge b) is their greatest lower bound, and the join (a\vee b) is their least upper bound.
• Algebraic laws:

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

Here (a,b,c\in L); the equations express commutativity, associativity, and absorption.

• Bounded lattice: A bounded lattice contains a least element (0) and greatest element (1), satisfying (a\vee0=a) and (a\wedge1=a).
• Distributive lattice: Meet distributes over join and join distributes over meet.
• Complemented lattice: In a bounded lattice, a complement (b) of (a) satisfies (a\wedge b=0) and (a\vee b=1).
• Worked example: ((\mathcal P(S),\subseteq)) is a bounded distributive lattice: meet is intersection, join is union, (0=\varnothing), (1=S), and the complement of (A) is (S-A).

B. Significance

Lattices connect order theory with algebraic operations.

• Applications: They organize subsets, divisors, logical propositions, access permissions, and data-flow information.
• Limitation: A poset is not a lattice if even one pair lacks a unique meet or join.

IX. Groups — Algebraic Structures of Symmetry

A. groups

A group is a set (G) equipped with a binary operation (*) satisfying closure, associativity, identity, and inverse axioms.

• Axioms:

a * b ∈ G
(a * b) * c = a * (b * c)
e * a = a * e = a
a * a⁻¹ = a⁻¹ * a = e

Here (a,b,c\in G), (e) is the identity, and (a^{-1}) is the inverse of (a).

• Abelian group: A group is Abelian when (ab=ba) for all (a,b\in G); commutativity is not required in a general group.
• Order: The order of a finite group is (|G|); the order of (a\in G) is the least positive integer (n) satisfying (a^n=e).
• Subgroup: A nonempty subset (H\subseteq G) is a subgroup when (ab^{-1}\in H) for all (a,b\in H).
• Cyclic group: If every element has the form (a^n) for one (a\in G), then (G=\langle a\rangle).
• Homomorphism: A map (\phi:G\to K) preserves the operation when (\phi(a*b)=\phi(a)\circ\phi(b)), where (\circ) is the operation on (K).
• Worked example: ((\mathbb Z_4,+)) is an Abelian group with identity (0); the inverse of (1) is (3), since (1+3\equiv0\pmod4).

B. Structural Significance

Groups isolate the essential algebraic behavior of reversible operations and symmetries.

• Applications: Permutation groups describe rearrangements, symmetry groups describe invariant geometric transformations, and modular groups support number theory and cryptography.
• Consequences of axioms: The identity and each inverse are unique, cancellation is valid, and equations such as (a*x=b) have unique solutions in (G).