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

Answer these closed-book before beginning the main path:

What is the negation of "for every integer n, P(n)"?
Why is checking many examples not enough to prove a universal statement?
What is the difference between x in A and A subseteq B?
When are two functions different: when they use different formulas, or when they disagree on at least one input from the domain?
Why does an induction proof need both a base case and an inductive step?

Diagnostic Interpretation

4-5 solid answers

You are ready for the main path.

2-3 solid answers

You can continue, but expect to spend more time on the logic and proof-construction clusters.

0-1 solid answers

Do not rush. Work the module slowly and write out every example by hand.

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, support, 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

a proof notebook containing at least 12 fully written proofs
one translation-and-negation sheet with corrected quantified statements
one set/function/relation sheet with your own examples and non-examples
one counterexample log for false universal statements
at least 4 induction proofs written in complete sentences
one structural induction proof on a recursively defined object
one flashcard deck for theorem shapes, relation properties, and induction templates
one short memo explaining how Module 1 proof habits carry into algorithm correctness

Completion Standard

You have completed Module 1 when all of these are true:

you can parse and negate quantified statements reliably
you can explain why a selected proof method fits the theorem shape
you can prove set equality by double inclusion without handwaving
you can classify functions and relations from definitions and justify the result
you can finish at least one clean proof each of direct, contrapositive, contradiction, and induction style
your proofs are readable enough that another learner could follow the plan without filling in missing logic

If the ideas feel familiar but you still cannot produce the arguments yourself, the module is not complete.

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.

Suggested Weekly Flow

Day	Work
1	Cluster 1 and one page of translation and negation drills
2	Cluster 2 and two short proofs written in full sentences
3	Cluster 3 and one set-equality proof plus one function-classification sheet
4	Cluster 4 and one relation-property analysis with counterexamples
5	Cluster 5 and at least one ordinary induction proof
6	Practice pages 1-2 and targeted book reinforcement
7	Practice pages 3-4, quiz, and proof cleanup pass

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​

Diagnostic Interpretation​

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​

Completion Standard​

Reading Policy​

Suggested Weekly Flow​

Reference​

Rich Learning Pages​

Model Artifact Calibration​