Propositions and Axiomatic Systems

This note addresses how to make a mathematical statement precise and how to justify a conclusion from stated assumptions. These ideas will recur in direct proofs, proofs by contrapositive, and induction. MIT’s introductory proof notes provide a useful companion for the organization of mathematical arguments [1][1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf.

We use classical logic and take $\mathbb N=\{0,1,2,\ldots\}$. Truth and falsity are understood relative to a specified domain and interpretation. This does not mean that an algorithm can always determine which one applies.

From sentences to propositions

DefinitionPropositions and domains

A proposition is a meaningful assertion with a truth value under a given interpretation. A domain specifies the objects that variables may range over. Having a definite truth value is different from our knowing or having proved that truth value.

“Every prime number is even” is a false proposition, with $3$ as a counterexample. “Find a prime number” is a command rather than an assertion to classify as true or false. “This proof is beautiful” does not specify a criterion precise enough to serve as a mathematical proposition here.

Other sentences leave their setting unstated. “The angles of a triangle sum to $180^\circ$” needs the assumption of Euclidean plane geometry. Changing the geometric setting can change the conclusion. Before proving something, check that its objects, operations, and background have been specified.

DefinitionPredicates and free variables

A formula containing free variables that have not been assigned values can be treated as a predicate. Let $P(x)$ mean $x>2$, with $x\in\mathbb Z$. Its truth depends on $x$: $P(3)$ is true and $P(1)$ is false. Assigning values, or binding all free variables with quantifiers, produces a statement that no longer depends on those unassigned values.

For example, $x^2=2$ leaves $x$ unspecified. “There exists a real number $x$ such that $x^2=2$” is a true proposition. Replacing “real” with “rational” gives a false one. The same symbolic expression can make different claims when its domain changes.

RemarkA definite truth value need not be known

Our inability to prove an assertion does not stop it from being a proposition. Conversely, knowing that an assertion is true in an intended mathematical structure does not establish that it is provable in any chosen axiom system. Keep the chosen assumptions in view when deciding what a proof has established.

Combining statements with logical connectives

Let $P,Q$ be propositions. The negation $\neg P$ says that $P$ does not hold. The conjunction $P\land Q$ requires both propositions to hold. The disjunction $P\lor Q$ requires at least one to hold, allowing both. Unless stated otherwise, mathematical “or” is inclusive.

The conditional $P\to Q$ reads “if $P$, then $Q$.” It excludes exactly one situation: a true premise with a false conclusion. The biconditional $P\leftrightarrow Q$ requires both directions and reads “$P$ if and only if $Q$.”

$P$	$Q$	$P\to Q$	$P\leftrightarrow Q$
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

ExampleWhy a false premise is not a counterexample

Consider “For every integer $n$, if $4$ divides $n$, then $n$ is even.” At $n=6$, the premise fails, so this value does not refute the claim. A counterexample would have to be divisible by $4$ without being even. The conditional constrains objects that satisfy its premise.

A true conditional does not necessarily describe causation. It specifies a logical condition. Reversing it to “if $Q$, then $P$” can change its truth value; see Converse, Inverse, and Contrapositive for the comparison.

Quantifiers determine the proof task

Universal and existential claims

The universal quantifier $\forall$ means “for every object,” while the existential quantifier $\exists$ means “for at least one object.” For a domain $D$, the usual notation is

$$\forall x\in D,\ P(x),$$

and

$$\exists x\in D,\ P(x).$$

To prove a universal claim, take an arbitrary object satisfying the stated conditions and avoid relying on any special feature of that choice. Checking a few examples generally supports a conjecture rather than a proof. One counterexample refutes a universal claim. An existential claim can be proved by supplying a witness; the witness need not be unique.

Quantifier order and dependencies

ExampleA larger integer for each integer, or one larger than all of them?

These statements differ only in quantifier order:

$$\forall x\in\mathbb Z,\ \exists y\in\mathbb Z,\ y>x,$$$$\exists y\in\mathbb Z,\ \forall x\in\mathbb Z,\ y>x.$$

The first is true: after receiving an arbitrary integer $x$, choose $y=x+1$. The choice of $y$ may depend on $x$. The second is false: it requires fixing one $y$ that exceeds every integer. Choosing $x=y$ would then require $y>y$.

Read nested quantifiers from left to right, asking which objects have already been given and which earlier objects a new choice may depend on. This habit will be useful for limit definitions, algorithmic guarantees, and properties of functions.

Negating quantified statements

A universal claim fails when some object fails its condition. An existential claim fails when every object fails its condition. Thus,

$$\neg\bigl(\forall x\in D,\ P(x)\bigr) \iff \exists x\in D,\ \neg P(x),$$ $$\neg\bigl(\exists x\in D,\ P(x)\bigr) \iff \forall x\in D,\ \neg P(x).$$

For example, the negation of “every integer has a larger integer” is “there is an integer with no larger integer.” Negating the quantifiers and the innermost condition gives

$$\exists x\in\mathbb Z,\ \forall y\in\mathbb Z,\ y\le x.$$

RemarkEmpty sets and vacuous truth

For quantifiers restricted to the empty set $D=\varnothing$, “every $x\in D$ satisfies $P(x)$” is true because there is no counterexample. “Some $x\in D$ satisfies $P(x)$” is false because there is no witness. This concerns restricted quantification over an empty set; standard first-order logic still takes a model’s entire domain to be nonempty.

Axioms, definitions, and inference rules

A formal language specifies legal symbols and expressions. Axioms are sentences chosen as starting points. Inference rules specify how accepted statements support a next statement. Once a set $T$ of nonlogical axioms and a background logic are fixed, we can ask what follows from $T$.

Mathematical writing also uses the following names:

• A definition introduces a term or notation. For example, an integer $n$ is even when there is an integer $k$ such that $n=2k$. A definition is usually an explicit abbreviation in an existing language, rather than a pattern guessed from examples.
• A theorem is a result for which a proof has been supplied. The assumptions and background theory must be clear.
• A lemma is also a theorem, used mainly to help prove another result.
• A corollary is a proved result that follows relatively directly from an earlier theorem.

These names describe roles in an exposition, not different levels of correctness. A statement adopted as an axiom in one axiomatization may be proved as a theorem in another.

ExampleDefinitions still need meaningful conditions

A real function defined by $f(x)=1/x$ cannot have $0$ in its domain. Saying “let $r$ be the real number satisfying $r^2=2$” does not uniquely determine $r$ unless a sign is specified. To define the usual square root, require $r\ge 0$ and prove or invoke the relevant existence and uniqueness result. We may choose notation freely, but cannot omit conditions needed for an object to make sense.

ExampleAn inference rule is different from a proposition

Modus ponens allows us to infer $Q$ from the two premises $P$ and $P\to Q$:

$$\frac{P\qquad P\to Q}{Q}.$$

The premises appear above the line and the conclusion below. The conditional $P\to Q$ alone is insufficient to infer $Q$: we may have no proof of $P$.

ProofUsing the rule in a short derivation

Assume $P\to Q$, $Q\to R$, and $P$. Apply modus ponens to the first conditional and $P$ to obtain $Q$. Then apply it to $Q\to R$ and $Q$ to obtain $R$. Each step identifies both the premises used and the rule that permits the inference.

A derivation involving powers also needs a domain. Take a positive real number $a$ and integers $m,n$, so that every integer power involved is defined. Once the exponent law and commutativity of integer addition have been established, we may write

$$\begin{aligned} a^m a^n &= a^{m+n}\\ &=a^{n+m}\\ &=a^n a^m. \end{aligned}$$

This derivation shows how to use earlier results. It does not prove the exponent law from scratch and must not quietly assume a result that remains to be established.

What the axioms justify

Truth concerns the interpretation of a statement; provability concerns what follows from stated axioms and rules. Writing $T\vdash\varphi$ means that $\varphi$ has a derivation from the assumptions in $T$. A proof must identify enough of that background to justify its steps.

For example, if the only assumption is $P$, nothing in that assumption determines an unrelated statement $Q$. Both $Q$ true and $Q$ false can coexist with $P$ true. This is why a fact that holds in one chosen example is not automatically a consequence of the assumptions.

For now, the practical task is to distinguish assumptions, definitions, inference steps, and conclusions. Formal Logic and Natural Deduction develops models, consistency, independence, and the two meanings of completeness after these proof habits are in place.

Exercises: make the conditions and reasons explicit

These exercises revisit the main distinctions in the note. Try each before opening its solution; none requires the more advanced proof techniques introduced later.

ExerciseSentences, assignments, and domains

With $x\in\mathbb R$, compare $x^2\ge 0$, $\forall x\in\mathbb R,\ x^2\ge 0$, and $\exists x\in\mathbb R,\ x^2=-1$. Which are closed sentences, and what are their truth values? If the first expression appears in a proof, what should its author specify?

Show solution

Solution

The first expression has a free variable $x$ and is an open formula. It holds under every real assignment, but the author should still say that $x$ is an arbitrary real number or supply the universal quantifier. The second expression is a true closed sentence. The third is a false closed sentence because real squares are nonnegative. Being open and being false are different conditions.

ExerciseSwapping quantifiers

In $\mathbb N$, determine the truth of these statements and negate the first:

$$\forall n\in\mathbb N,\ \exists m\in\mathbb N,\ m>n,$$$$\exists m\in\mathbb N,\ \forall n\in\mathbb N,\ m>n.$$

Show solution

Solution

The first is true: after receiving $n$, choose $m=n+1$. The second is false: for any proposed $m$, choose $n=m$. Negating the first statement gives

$$\exists n\in\mathbb N,\ \forall m\in\mathbb N,\ m\le n.$$

Negation swaps the quantifiers as well as negating the innermost inequality. Changing only $>$ to $\le$ would be insufficient.

ExerciseDoes a true conclusion establish the premise?

Let $P$ mean “$4$ divides $n$” and $Q$ mean “$n$ is even.” Someone infers $P$ from $P\to Q$ and $Q$. Give an integer counterexample and explain why this is not modus ponens.

Show solution

Solution

Take $n=6$. Then $Q$ is true, $P$ is false, and $P\to Q$ is true. Both proposed premises hold while the conclusion fails. Modus ponens requires $P$ and $P\to Q$; this argument supplies $Q$ and $P\to Q$ instead.

ExerciseUsing models to test redundancy

In classical propositional logic, take $T=\{P\lor Q,\neg P\}$. Prove $T\vdash Q$. Does adding $Q$ as an axiom increase what can be derived? If $\neg P$ is removed, can the remaining axiom still derive $Q$?

Show solution

Solution

$P\lor Q$ requires at least one to hold, and $\neg P$ excludes $P$, leaving $Q$. Formally, use the two branches of the disjunction: in the $P$ branch, combine $P$ with $\neg P$ to get a contradiction and infer $Q$; in the $Q$ branch, the conclusion is already given.

Since $Q$ already has a proof from $T$, listing it as an axiom adds no derivable conclusions: any use of the new axiom can be replaced by that proof. After removing $\neg P$, the assignment $P=\mathrm T,Q=\mathrm F$ satisfies the remaining axiom but falsifies $Q$, so $Q$ no longer follows.

What to read next

You should now be able to specify domains and quantifiers before distinguishing a statement’s meaning, truth, evidence, and derivability. Continue with Converse, Inverse, and Contrapositive to practice rewriting conditionals, then Direct Proof to organize definitions, assumptions, and rules into complete arguments.

References

1. [1] T. Leighton and R. Rubinfeld, “What Is a Proof?,” 2006. MIT 6.042/18.062J lecture notes, September 7, 2006. https://web.mit.edu/neboat/Public/6.042/proofs.pdf ↩