Table of Contents
In this chapter we focus on propositions as the basic building blocks of mathematical logic and proofs. The broader idea of logic and proof is handled in the parent chapter; here we sharpen the notion of what counts as a proposition, how we name and combine propositions, and how this connects to truth values.
What a Proposition Is
A proposition is a declarative statement that is either true or false, but not both.
Key points:
- It must be a statement (not a question, command, or exclamation).
- It must have a definite truth value: there is a fact of the matter about whether it is true or false (even if we do not know which).
- It cannot be both true and false at the same time.
Examples of propositions:
- “$2+3=5$.” (True)
- “Every prime number greater than 2 is odd.” (True)
- “There is a largest prime number.” (False)
- “$x^2\ge 0$ for all real numbers $x$.” (True)
Non-examples (not propositions):
- “What time is it?” (Question)
- “Close the door.” (Command)
- “Wow!” (Exclamation)
- “This sentence is false.” (Self-contradictory, paradoxical)
- “$x>3$.” (Open sentence; its truth depends on which value of $x$ we mean)
The last kind (“$x>3$”) becomes a proposition only after a value is specified, such as “$5>3$” (true) or “$1>3$” (false), or after we say something like “For all real numbers $x$, $x>3$” (which is then a false proposition). The handling of variables and quantifiers is developed in other chapters; here we simply note that bare expressions with free variables are not propositions.
Truth Values
Each proposition has one of two truth values:
- True, often denoted by $T$, or $1$
- False, often denoted by $F$, or $0$
In basic (classical) propositional logic, we work only with these two values. We do not distinguish different “degrees” of truth here; other systems (such as fuzzy logic) are outside our current scope.
While the truth value is always conceptually fixed, we may not always know it:
- “There are infinitely many twin primes.”
Mathematically, this is either true or false, but as of now it is an open problem: we do not know which truth value it has.
The important point in propositional logic is that such a sentence still counts as a proposition because it is in principle either true or false.
Atomic and Compound Propositions
A useful distinction is between atomic and compound propositions.
- An atomic proposition (or simple proposition) does not contain smaller propositions as parts.
- Example: “$5$ is an odd number.”
- Example: “The graph $G$ is connected.”
- A compound proposition is built from one or more propositions by using logical connectives (such as “and”, “or”, “not”, “if … then …”). The details of these connectives are covered in the “Logical operators” chapter; here we only emphasize that such constructions are still propositions.
- “$5$ is odd and $8$ is even.”
- “If $n$ is even, then $n^2$ is even.”
- “Either $n$ is prime or $n$ is composite, but not both.”
Each whole compound sentence also has a truth value, determined by the truth values of its parts and the meaning of the connectives.
Propositional Variables and Symbolic Representation
To reason abstractly about propositions, we often name them with single letters called propositional variables.
Typical letters are $p, q, r, s$, etc.
Examples:
- Let $p$ be the proposition “$2+2=4$”.
- Let $q$ be the proposition “$5$ is an even number.”
Then we can refer to these sentences compactly as $p$ and $q$ instead of repeatedly writing the full English statements.
This symbolic approach is especially useful when we form compound propositions:
- $p\land q$ could stand for “$2+2=4$ and $5$ is an even number”.
- $p\lor q$ could stand for “$2+2=4$ or $5$ is an even number”.
- $\neg p$ could stand for “It is not the case that $2+2=4$”.
The specific symbols $\land,\lor,\neg,\to,\leftrightarrow$ and their meanings belong to the “Logical operators” chapter; here we only note that propositional variables are placeholders for entire propositions.
Distinguishing Propositions from Other Statements
It is easy to misclassify sentences. Here are some typical borderline cases.
- Sentences with pronouns or vague references
- “She is tall.”
- “It is raining.”
As written, these are not precise enough for mathematical logic: “she” and “it” are not defined. In a formal context, we either clarify them or treat them as propositional variables:
- Let $p$ be “It is raining in Paris at noon on January 1, 2020.”
Now $p$ is a definite proposition.
- Open sentences with variables
- “$n$ is even.”
- “$x^2 > 4$.”
Without specifying what $n$ or $x$ refers to, these are not propositions in the strict sense. They become propositions only when the variable is given a specific value or is bound by a quantifier (handled in other chapters).
- Self-referential or paradoxical sentences
- “This sentence is false.”
If it were true, it would be false; if it were false, it would be true. Such a sentence does not fit neatly into the “true or false, but not both” requirement and is excluded from ordinary propositional logic.
For the purpose of mathematical proof, we typically restrict our attention to clear, unambiguous, non-self-referential propositions.
Propositions in Mathematical Reasoning
In the context of proofs, propositions appear in two main roles:
- Premises (assumptions): propositions we start with or are allowed to use.
- Example: “Assume $n$ is an even integer.”
This assumption can be summarized as a proposition $p$: “$n$ is even.” - Conclusions: propositions we aim to show follow logically from the premises.
- Example: “Then $n^2$ is even.”
This might be recorded as a proposition $q$: “$n^2$ is even.”
A correct proof shows that, under the rules of logic, whenever $p$ is true, $q$ must also be true. Symbolically, this is the claim that the implication $p\to q$ is itself a true proposition (or at least true under the given assumptions about $n$).
How exactly we move from premises to conclusions (e.g., via direct proof, contradiction, or induction) is developed in later chapters on proof techniques. Here it is enough to see that the objects we reason about step by step are propositions and relationships between their truth values.
Summary
- A proposition is a declarative sentence with a definite truth value (true or false, but not both).
- Questions, commands, exclamations, vague statements, open sentences with free variables, and paradoxical self-referential sentences are not propositions in standard propositional logic.
- Atomic propositions are indivisible; compound propositions are built from simpler ones with logical connectives.
- Propositional variables ($p,q,r,\dots$) serve as abstract names for whole propositions, enabling symbolic reasoning.
- In proofs, we treat assumptions and conclusions as propositions and use logical rules (studied elsewhere) to relate their truth values.