C04: Logic, sets, relations, and constructing proofs

A. Prerequisites and observable goals#

Level: Degree core.

B. The central question: what would make this claim true or false?#

A proof is a logically justified argument from stated assumptions to a conclusion. It is not a longer example or a report that code passed tests. Before proving a claim, identify its domain, quantifiers, and conditions. “This search works” is too vague. “For every finite nondecreasing integer sequence and every integer target, this function returns the first qualifying index or the length” is a proposition with a testable meaning and a possible proof structure.

A proposition has a truth value. The operators $\neg$, $\land$, and $\lor$ mean not, and, and inclusive or. An implication $P\Rightarrow Q$ is false only when $P$ is true and $Q$ is false. When $P$ is false, the implication is true in classical propositional logic; it does not assert that $P$ occurs or causes $Q$. An equivalence $P\Leftrightarrow Q$ requires both directions. Proving one implication does not establish the converse.

C. Quantifiers and their order#

$\forall x\in D\,P(x)$ means every element of the specified domain satisfies the predicate. $\exists x\in D\,P(x)$ means at least one witness exists. Negation changes both the quantifier and predicate:

Thus disproving a universal claim needs one valid counterexample, whereas proving it needs a general argument covering the entire domain. Testing a million cases can reveal a counterexample but cannot by itself prove a claim over all integers.

The claims $\forall x\,\exists y\,(y>x)$ and $\exists y\,\forall x\,(y>x)$ over the integers differ. The first is true: choose $y=x+1$ depending on $x$. The second asks for one integer greater than every integer, which does not exist. This distinction appears in software contracts: “each request eventually gets some response” is not the same as “there is one fixed response time bound that works for every request.” Additional timing assumptions would be needed for a uniform bound.

Sets collect distinct elements without an intrinsic order. Membership $x\in A$ differs from inclusion $A\subseteq B$. Union, intersection, and complement act on sets; complements require a declared universe. De Morgan’s laws, $(A\cup B)^c=A^c\cap B^c$ and $(A\cap B)^c=A^c\cup B^c$, follow by checking membership of an arbitrary element. A list can contain duplicates and preserve order, so it is not interchangeable with a mathematical set.

D. How to build a proof#

For a direct proof of $P\Rightarrow Q$, assume $P$, unpack its definitions, and derive $Q$ with justified steps. For a contrapositive proof, prove $\neg Q\Rightarrow\neg P$, which is logically equivalent to the original implication. For a contradiction proof, assume the negation of the desired claim together with the hypotheses and derive an impossibility. These methods are choices of argument organization, not magic words that turn an unsupported calculation into a proof.

Example: if an integer $n$ has even square, then $n$ is even. The contrapositive says an odd integer has odd square. Write an arbitrary odd integer as $n=2k+1$ for an integer $k$. Then $n^2=4k^2+4k+1=2(2k^2+2k)+1$, which is odd by definition. This covers every odd integer, including negative ones. Checking $3^2=9$ and $5^2=25$ would only illustrate it.

For a contradiction example, suppose $\sqrt2=p/q$ with coprime integers $p,q$ and $q\ne0$. Then $p^2=2q^2$, so $p$ is even by the previous result. Write $p=2r$ to get $q^2=2r^2$, hence $q$ is even too. Both being even contradicts coprimality. The argument depends on choosing a reduced fraction; without that condition, discovering a common factor would not contradict the assumption.

E. Relations organize objects into classes and orders#

A binary relation on $S$ is a subset of $S\times S$. An equivalence relation is reflexive ($x\sim x$), symmetric ($x\sim y$ implies $y\sim x$), and transitive ($x\sim y$, $y\sim z$ imply $x\sim z$). It partitions the set into disjoint equivalence classes. Equality modulo $m>0$, defined by $m$ dividing $a-b$, is an example: each integer belongs to exactly one residue class.

A partial order is reflexive, antisymmetric, and transitive. Antisymmetric means $x\preceq y$ and $y\preceq x$ together imply $x=y$; it does not mean that reversing every pair makes the relation false. Set inclusion is a partial order, and some sets are incomparable. A total order additionally compares every pair. Sorting and search rely on specific ordering assumptions; a comparator that changes its answer or violates transitivity can invalidate the algorithm’s reasoning.

A function assigns exactly one output in its codomain to each input in its domain. Injectivity means distinct inputs have distinct outputs; surjectivity means every codomain element occurs; bijectivity means both. The chosen codomain matters. The map $x\mapsto x^2$ from $\R$ to $\R$ is neither injective nor surjective, but restricted from $[0,\infty)$ to $[0,\infty)$ it is bijective. This revisits calculus inverse-function conditions in a discrete language.

F. Finite logic checking is useful within a stated boundary#

A truth-table checker can enumerate all $2^n$ assignments to $n$ Boolean names and find an assignment where every premise is true but the conclusion is false. For a fixed finite propositional formula, exhaustive enumeration is complete. It is not a proof method for arbitrary quantified integer claims unless the finite reduction itself is justified. The lab imposes a 16-name bound to keep exhaustive work intentional rather than accidentally exponential.

The invalid inference “$P\Rightarrow Q$; $Q$; therefore $P$” is called affirming the consequent. Set $P$ false and $Q$ true: both premises are true and the conclusion false. The valid inference “$P\Rightarrow Q$; $P$; therefore $Q$” has no such assignment. Finding the counterexample is more informative than saying the first argument “looks wrong.”

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C04#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C04.05: finite propositional entailment, not first-order theorem proving."""
from itertools import product
from collections.abc import Callable

def counterexample(names: list[str], premises: list[Callable],
                   conclusion: Callable) -> dict[str, bool] | None:
    if len(names) != len(set(names)):
        raise ValueError("variable names must be unique")
    if len(names) > 16:
        raise ValueError("educational exhaustive limit: 16 variables")
    for bits in product((False, True), repeat=len(names)):
        env = dict(zip(names, bits))
        if all(p(env) for p in premises) and not conclusion(env):
            return env
    return None

if __name__ == "__main__":
    implication = lambda e: not e["p"] or e["q"]
    print(counterexample(["p", "q"], [implication, lambda e: e["q"]],
                         lambda e: e["p"]))

I. Retention and readiness#

Retrieve domains and inverse-function restrictions from calculus. Advance when you can negate a quantified statement, name a missing hypothesis, and produce a counterexample to a tempting converse. Do not skip proof practice merely because the corresponding code is easy to run.