Glossary

The hypothesis (the "if" part) of a conditional statement.

The starting value where an induction proof verifies the claim directly.

Symbol \leftrightarrow -- true exactly when both sides match.

p\implies q -- false only when p is true and q is false.

Symbol \wedge -- true only when both sides are true.

The conclusion (the "then" part) of a conditional statement.

An existence proof that exhibits and verifies a specific witness.

A compound proposition false on every row of its truth table.

Swapping and negating both pieces -- the one rewrite guaranteed equivalent to the original.

Swapping the two pieces of a conditional -- q\implies p from p\implies q.

A single object disproving a universal claim.

Negating AND or OR swaps the connective -- never distributes unchanged.

A statement fixing the exact meaning of a term, with no ambiguity left.

Fix an arbitrary object satisfying the hypothesis, then chain justified steps to the conclusion.

Symbol \vee -- true when at least one side is true.

Symbol \mid -- b \mid a means a=bk for some integer k.

For a and positive b, unique q,r exist with a=bq+r and 0\le r<b.

The set a quantified variable ranges over -- must be fixed before evaluating a quantified statement.

Symbol \oplus -- true when exactly one side is true.

A proof establishing \exists x, P(x) -- constructively (naming a witness) or nonconstructively.

Symbol \exists -- "there exists an x" -- true when at least one domain element satisfies the predicate.

The assumption P(k), trusted and reused inside the inductive step.

Proving P(k)\implies P(k+1) for an arbitrary k.

Negating both pieces of a conditional -- \neg p\implies\neg q from p\implies q.

A real number that cannot be written as a ratio of two integers.

Symbol \equiv -- two formulas with identical truth tables.

A base case plus an inductive step, establishing a claim for every n from the base case onward.

From p\implies q and p, conclude q.

From p\implies q and \neg q, conclude \neg p.

p is necessary for q means q\implies p -- q cannot hold without p.

Symbol \neg -- flips a proposition's truth value.

More than one quantifier in a statement, read and evaluated from the outside in.

An existence proof that argues a witness must exist without ever naming one.

A sentence containing an unfixed variable, with no truth value until the variable is given one.

A sentence with variables that becomes a proposition once every variable is fixed.

A finite chain of justified claims establishing a conclusion, not a pile of checked examples.

Split the domain into exhaustive cases, and prove the claim within each one.

Assume the claim's negation, then derive an impossibility of the form R\wedge\neg R.

Prove the contrapositive instead, then invoke its guaranteed equivalence to the original.

A declarative sentence with a fixed truth value, usually named with a letter like p or q.

A number expressible as \frac{a}{b} for integers a,b with b\neq0.

A declarative sentence with a fixed truth value -- true or false, never both.

An inductive step allowed to assume every earlier case, not just the immediately preceding one.

p is sufficient for q means p\implies q -- having p guarantees q.

A compound proposition true on every row of its truth table.

A claim, provable from definitions and earlier results, true for every object satisfying some condition.

The subset of a domain where a predicate is actually true.

A proof that any two objects satisfying a property must be equal.

Symbol \forall -- "for all x" -- true when the predicate holds for every domain element.

An argument whose conclusion is guaranteed true whenever every premise is true.

Every nonempty subset of the natural numbers has a least element.

A specific object satisfying a predicate, enough to prove an existential claim true.