Module 1: Proof Techniques & Discrete Structures

Primary text: Mathematics for Computer Science
Selective support: Discrete Mathematics and Its Applications

This guide is the primary teacher. You do not need to read either book front-to-back to complete the module, but this is an in-depth module, not a light overview. The expectation is that you will work through the concept pages carefully, write full proofs, and use the local book chunks for reinforcement when a concept is unstable.

Scope of This Module

This module is the mathematical foundation for the rest of the degree. It is where vague intuition has to become explicit reasoning.

What it covers in depth:

propositional language, quantified statements, and how scope changes meaning
proof-method selection based on the shape of a claim
direct proof, contrapositive, contradiction, proof by cases, and iff structure
sets, Cartesian products, and set equality proofs by double inclusion
functions as mappings with domain, codomain, image, preimage, and composition
relations, equivalence relations, partial orders, and composition
ordinary induction, strong induction, recursive definitions, and structural induction

What it deliberately does not try to finish here:

full formal logic as a separate subject
graph theory depth beyond relation and order language
recurrence solving as a major topic
advanced set theory or proof theory

This is a heavy textbook module. The goal is durable proof fluency, not fast exposure.

Before You Start

Use the prerequisite diagnostic for arithmetic, tracing and terminal readiness. Quantifiers and induction are learning objectives here, not assumed entry skills. Read Proof and Model Contracts alongside the lessons; use it to distinguish a theorem from an implementation check.

What This Module Is For

Later courses will ask you to prove that an algorithm terminates, justify that a data-model invariant holds, reason about equivalence classes, or explain why a recursive definition is valid. All of those tasks reuse the same foundation:

read a statement without smuggling in assumptions
separate hypotheses from conclusions
choose a proof move because it fits the statement, not because it feels familiar
model structure precisely with sets, functions, and relations
use induction when the claim is generated step by step or recursively

This module is where mathematical writing stops being decorative and becomes operational.

Concept Map

How To Use This Module

Work cluster by cluster. Do not skip from logic to induction. The order matters because later proof forms depend on earlier language precision.

Cluster 1: Logical Language

Order	Concept	Type	Focus
1	Propositions, Implication, and Equivalence	PRIMARY	What counts as a statement and how compound statements behave
2	Truth Tables, Validity, and Equivalence	SUPPORTING	Mechanical checks for logical form and equivalence
3	Predicates, Domains, and Quantified Statements	SUPPORTING	Moving from open sentences to formal claims
4	Negation and Quantifier Order	SUPPORTING	Correctly negating statements and seeing when order changes meaning

Cluster mastery check: Can you translate a statement, identify its scope, and negate it without guessing?

Cluster 2: Proof Construction

Order	Concept	Type	Focus
5	Proof Strategy Starts from Theorem Shape	PRIMARY	Matching implication, equivalence, existence, and universal claims to proof moves
6	Direct Proof and Contrapositive	SUPPORTING	Two high-frequency templates and when each is cleaner
7	Contradiction, Cases, and Iff Proofs	SUPPORTING	Multi-branch and indirect arguments
8	Counterexamples and Proof-Writing Discipline	SUPPORTING	Disproving false statements and writing proofs that another reader can follow

Cluster mastery check: Can you explain why a chosen proof method fits the theorem better than the alternatives?

Cluster 3: Sets and Functions

Order	Concept	Type	Focus
9	Sets Are Models, Not Just Containers	PRIMARY	Membership, subsets, equality, power sets, and set-builder notation
10	Set Operations, Cartesian Products, and Double Inclusion	SUPPORTING	Union, intersection, difference, products, and proof of set equality
11	Functions Are Behavior on a Domain	PRIMARY	Domain, codomain, image, and why function equality is behavioral
12	Images, Preimages, Composition, and Classification	SUPPORTING	Injective, surjective, bijective, and composition reasoning

Cluster mastery check: Can you prove set equalities and classify functions from definitions instead of intuition?

Cluster 4: Relations and Order

Order	Concept	Type	Focus
13	Relation Properties and Composition	PRIMARY	Reflexive, symmetric, antisymmetric, transitive, and relational composition
14	Equivalence Relations and Partitions	SUPPORTING	When a relation groups elements into same-kind classes
15	Partial Orders and Hasse Thinking	SUPPORTING	Comparability, minimal elements, maximal elements, and order structure

Cluster mastery check: Can you test a relation property with definitions and counterexamples rather than pattern recognition alone?

Cluster 5: Induction and Recursion

Order	Concept	Type	Focus
16	Ordinary Induction Is Sequential Closure	PRIMARY	Base case, inductive hypothesis, inductive step, and proof shape
17	Strong Induction and Well-Ordering	SUPPORTING	When a proof needs all earlier cases, not only the previous one
18	Recursive Definitions and Structural Induction	PRIMARY	Proving properties of recursively generated objects

Cluster mastery check: Can you explain why the proof structure mirrors the way the objects or numbers are generated?

Then work these practice pages:

Order	Practice path	Focus
1	Logic and Proof Method Diagnostics	Translation, negation, theorem shape, and proof-method choice
2	Sets, Functions, and Relations Lab	Modeling, classification, and proof from definitions
3	Induction and Recursion Clinic	Ordinary induction, strong induction, recursive objects, and proof repair
4	Code Katas	Small computational drills that reinforce truth tables, relations, and recursion

Use Module Quiz after the concept and practice path. Use Reference and Selective Reading and Learning Resources only when targeted reinforcement is needed.

Learning Objectives

By the end of this module you should be able to:

Translate mathematical or CS statements into propositions, predicates, and quantified claims.
Negate quantified and conditional statements correctly.
Choose among direct proof, contrapositive, contradiction, cases, and iff proof with a reason.
Prove or disprove statements about sets by definition rather than diagram intuition alone.
Reason about functions using domain, codomain, image, preimage, injective, surjective, bijective, and composition.
Test relations for reflexivity, symmetry, antisymmetry, and transitivity with small examples and counterexamples.
Explain equivalence relations and partial orders as structure, not just vocabulary.
Write ordinary induction, strong induction, and structural induction proofs with all required logical parts visible.

Outputs and Completion

Submit P1–P20 with corrected reasoning, the four runnable labs, an independent eight-part checkpoint, and the workflow model/proof notebook. Save first attempts, assistance, counterexamples and revisions. Use the per-competency rubric: each of C1–C8 needs level 2 independently. An aggregate score or a completed reading list cannot replace a missing skill.

Practice feedback and assessment solutions are separate from their questions. Recheck selected competencies after 7–14 days and record reviewer status honestly.

Reading Policy

Concept pages are the main path.
Book chunks are selective reinforcement, not the default path.
Read only if stuck means open the linked chunk after trying the concept page and drill first.
Optional deep dive means extra nuance, not required progression.
Because this is an in-depth module, written proof work is mandatory, not optional enrichment.

Workload and Progression

Work	Estimated hours
Diagnostic, lessons and bounded reading	25–35
Four guided implementation/proof labs	14–20
Independent practice and revision	18–26
Assessment, feedback and remediation	7–10
Workflow capstone	6–9
Total	70–100

These are planning estimates pending learner pilots. At 10 hours/week, allow roughly 7–10 weeks. Prerequisite repair and optional depth add time. Work in cluster order, using each cluster's practice before moving on. Lab work is counted once; do not add the code-kata page as a second implementation workload.

Diagnostic · Model contracts · Runnable labs · Practice feedback · Independent checkpoint · Assessment rubric · Assessment key · Workflow capstone · Instructor review record

Authored candidate: independent mathematical/code review and learner pilots remain pending. This module supports rigorous practice; no elite-percentile outcome has been demonstrated.

Reference

If you need exact chunk links into the local books, use Reference and Selective Reading.

Rich Learning Pages

Model Artifact Calibration

For an example of learner-quality proof evidence, compare your work to the proof notebook model artifact.

Scope of This Module​

Before You Start​

What This Module Is For​

Concept Map​

How To Use This Module​

Cluster 1: Logical Language​

Cluster 2: Proof Construction​

Cluster 3: Sets and Functions​

Cluster 4: Relations and Order​

Cluster 5: Induction and Recursion​

Learning Objectives​

Outputs and Completion​

Reading Policy​

Workload and Progression​

Evidence and Feedback Navigation​

Reference​

Rich Learning Pages​

Model Artifact Calibration​