Propositions and Truth Values

Propositional truth values underlie the entire architecture of formal mathematics: every axiom, lemma, and theorem is, at bottom, asserted to be a true proposition, and every proof is a demonstration that a proposition's truth value is T given the truth of the hypotheses. In computer science, Boolean-valued propositions are the literal semantic content of `bool` types, and every `if` statement, database query condition, and hardware logic gate is evaluating a proposition's truth value in exactly the sense defined here — digital circuit design is propositional logic realized in silicon. Cryptographic protocols and formal verification tools (model checkers, SAT/SMT solvers) treat enormous propositional formulas built from millions of atomic propositions, relying on precisely the well-definedness guaranteed by the theorem above to make automated truth-value computation meaningful at scale. In statistics and the philosophy of science, the question of whether a hypothesis is a genuine testable proposition (falsifiable, with a determinate truth status) versus an unfalsifiable or ill-formed claim echoes the same distinction drawn here between propositions and non-propositions. And in everyday mathematical writing, the discipline of distinguishing a proposition from an open sentence is exactly what makes quantifiers (Logical Connectives and later quantified statements) necessary: without it, "$x^2 \ge 0$" would be meaningless as a claim rather than the true universal statement "for all real $x$, $x^2 \ge 0$."

Ask the tutor: How do quantifiers formally convert an open sentence into a genuine proposition, and why does the order of "for all" and "there exists" matter?

Think of the collection of all propositions as a giant filing cabinet with exactly two drawers, labeled T and F. Every proposition must be filed in exactly one drawer — never left in the hallway, never stuffed into both. The job of logic is not to figure out which drawer any particular proposition belongs in (that is the job of mathematics, science, or ordinary investigation) but to study how the drawer-assignment behaves when propositions are combined: if $P$ is in drawer T and $Q$ is in drawer F, which drawer does "$P$ and $Q$" belong in? This separation of concerns — content lives outside logic, form lives inside it — is what makes propositional logic simultaneously so simple and so universally applicable. The reason "declarative sentence" is not quite the right criterion becomes clear once you meet sentences that are grammatically declarative yet resist filing. "$x + 2 = 5$" looks like a statement, but until $x$ is specified it names no single truth value — it is true for $x=3$ and false otherwise, so it is an open sentence, not a proposition, and only becomes one once $x$ is bound by quantification or substitution. Even worse, "This sentence is false" is declarative and has no free variables, yet trying to file it produces a contradiction whichever drawer you choose. The definition above handles the first problem by requiring a unique, context-independent value, and handles the second by simply declining to admit self-referential sentences of that pathological form into the language $\mathcal{L}$ in the first place — a move that is made rigorous in the counterexample discussion below.

The corollary is immediate from the theorem: existence of the extension is the content of the recursive construction just verified, and uniqueness follows because the value at each stage was shown to be forced — not chosen — by the values of $\mathcal{L}_0$ together with the connectives' truth tables, leaving no freedom in how the extension could otherwise be defined.

Example 1 — Sorting sentences into propositions and non-propositions. Classify each of the following, and justify the classification using the definition above. 1. "$17$ is a prime number." 2. "The $10^{100}$-th digit of $\pi$'s decimal expansion is $7$." 3. "$n^2 - n$ is even, for $n$ a positive integer." 4. "Is $17$ a prime number?" 5. "$x^2 = 9$." 6. "For every integer $x$, $x^2 = 9$." 7. "Every even number greater than $2$ is the sum of two primes." Solution. (1) is a proposition: it is declarative, and $17$ is in fact prime (its only divisors are $1$ and $17$, verified by checking that no integer from $2$ to $\lfloor\sqrt{17}\rfloor = 4$ divides it), so its truth value is T. Note carefully: being a proposition does not require us to know the value easily — it only requires the value to be determinate. That leads into (2). (2) is a proposition even though, at the time of writing, essentially no one has computed that specific digit of $\pi$. The decimal expansion of $\pi$ is a fixed, well-defined mathematical object (it is the unique real number satisfying certain analytic characterizations, and each of its digits is uniquely determined), so the sentence has a definite, unique truth value — T or F — even though that value is (currently) epistemically inaccessible to us. This is the crucial distinction between a proposition's having a truth value and our knowing that value: the definition requires only the former. (3) as written, with "$n$" appearing free and unquantified in the phrase "for $n$ a positive integer" attached loosely, is best read as a universally quantified statement: "for all positive integers $n$, $n^2 - n$ is even." Once properly quantified, this is a proposition. We can verify it is true: $n^2 - n = n(n-1)$ is a product of two consecutive integers, one of which must be even (in any two consecutive integers, exactly one is even), so the product is even. Hence this proposition has truth value T. Note that without the quantifier, "$n^2-n$ is even" alone is an open sentence (free variable $n$) and is not a proposition — it is true for some values of $n$ (indeed all, as just shown) and the sentence's truth cannot be assessed without first fixing or quantifying $n$; formally it fails the definition because $v$ is not defined on it without further specification. (4) is a question, not declarative, hence not a proposition — the definition explicitly requires a declarative sentence, and grammatically interrogative sentences are excluded from $\mathcal{L}$ by convention from the outset. (5) "$x^2 = 9$" is an open sentence: $x$ is free. It is true when $x = 3$ or $x=-3$, false otherwise, so no single truth value can be assigned without specifying $x$. Not a proposition. (6) "For every integer $x$, $x^2 = 9$" is a proposition (the quantifier binds $x$, leaving no free variables), and it is false: taking $x = 1$ gives $1^2 = 1 \neq 9$, a counterexample within the proposition's own universe of discourse. Truth value F. (7) is the Goldbach Conjecture. It is a proposition: it is declarative, has no free variables, and (assuming bivalence) has a definite truth value — either every even number greater than $2$ is a sum of two primes, or some even number greater than $2$ is not. As of this writing it is unproven in either direction, yet — exactly as in example (2) — unprovenness (or even unknowability by current methods) does not prevent it from being a proposition; it only means we do not currently know which truth value it has. This is one of the most important distinctions the definition is designed to capture: being a proposition is a semantic/ontological property, not an epistemic one.

Example 2 — Building a compound proposition and computing its value via the theorem. Let $P_0$ = "$12$ is divisible by $4$" and $Q_0$ = "$12$ is divisible by $5$" be atomic propositions. First establish their truth values directly: $v_0(P_0) = T$, since $12 = 4 \times 3$, an exact factorization with no remainder. $v_0(Q_0) = F$, since $12 = 5\times 2 + 2$, a nonzero remainder upon division by $5$. Now form the compound proposition

using connectives whose truth tables (to be studied fully in Logical Connectives) are: "or" is true when at least one argument is true; "and" is true only when both arguments are true; "not" flips T to F and F to T. By the theorem, $R$ is a proposition with a well-defined truth value computable purely from $v_0(P_0)=T$ and $v_0(Q_0)=F$, in two steps corresponding to $R$'s two connective applications (structural induction with $k=2$): Step 1 (innermost/sibling sub-formulas, order-independent by the theorem):

• $v(P_0 \text{ or } Q_0) =$ "or" applied to $(T, F)$ $= T$ (at least one is T).
• $v(\text{not } Q_0) =$ "not" applied to $F$ $= T$.

Step 2 (outermost connective):

So $R$ is true. Notice this matches direct verification: $R$ literally asserts "$12$ is divisible by $4$ or by $5$, and $12$ is not divisible by $5$," which simplifies (since $12$ is divisible by $4$, the "or" clause holds regardless of the second disjunct, and indeed $12$ is not divisible by $5$) to a true compound claim — confirming the theorem's guarantee that the recursively computed value agrees with direct semantic evaluation, and illustrating that we never needed to re-examine the content "12," "4," "5" once we had the atomic truth values $T$ and $F$ in hand.