Discrete Math › Section B · Logic and proofs › Topic B.5
Proofs about sets, functions, and graphs
The proof skeletons of the previous topic work on any mathematical object. Applied to sets, functions, relations and graphs, they produce short, reliable proofs, and writing them is a good way to understand what the definitions really say.
In this topic
- Definitions drive the proof
- Subsets as implications
- Worked example: an element-chasing proof
- Worked example: proving two sets equal
- Injective functions
- Worked example: the pigeonhole principle
- Images of sets
- Relations and transitivity
- Graphs and degrees
- Worked example: an impossible party
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…