Methods of Proof — Contrapositive by Jeremy Kun.
From the post:
In this post we’ll cover the second of the “basic four” methods of proof: the contrapositive implication. We will build off our material from last time and start by defining functions on sets.
Functions as Sets
So far we have become comfortable with the definition of a set, but the most common way to use sets is to construct functions between them. As programmers we readily understand the nature of a function, but how can we define one mathematically? It turns out we can do it in terms of sets, but let us recall the desired properties of a function:
- Every input must have an output.
- Every input can only correspond to one output (the functions must be deterministic).
Jeremy continues his series on proof techniques.
Required knowledge for reading formal CS papers.