Giving a Name to an Open Condition
In What Is a Mathematical Statement?, we distinguished a definite assertion from an equation whose variable has not been specified. The equation \(x+2=5\), written without context for \(x\), did not yet give us a complete claim. Substituting \(3\) or \(1\) produced different statements.
Such an equation is not defective mathematics. It is useful precisely because it describes a condition that different numbers may or may not satisfy. We now give this kind of condition a name: a predicate. We also introduce proposition, the standard logical term for a statement with a definite truth value.
Propositions Are Complete Claims
Thus \(3+2=5\) and \(1+2=5\) are both propositions. The first is true and the second is false. As established in the previous tutorial, being false does not prevent an assertion from being a statement.
A proposition need not be written with numerals alone. “Every even integer is the sum of two integers” is a proposition, as is “There is an integer \(n\) such that \(n+2=5\).” The surrounding words specify what is being asserted about the integers.
In mathematical writing, Proposition is also used as a heading for a proved result, much like Theorem. That use of the word should not obscure its logical meaning here: calling a sentence a proposition does not, by itself, claim that the sentence is true or has been proved.
Predicates and Their Domains
A formula expressing such a condition is often called an open sentence. For a one-variable predicate, we can write \(P(x)\), read “\(P\) of \(x\),” to name the condition. For example, let the domain be the integers and define
The colon introduces the meaning of \(P(x)\). The letter \(P\) names the predicate; it is not a number being multiplied by \(x\). Writing \(P(3)\) means the proposition obtained by replacing \(x\) with \(3\).
We say that an allowed value satisfies a predicate when the proposition obtained by substitution is true. Thus \(3\) satisfies \(P(x)\), whereas \(1\) does not.
| Form | Example | Role |
|---|---|---|
| Expression | \(x+2\) | Represents a number once \(x\) is assigned. |
| Predicate | \(P(x): x+2=5\), for integer \(x\) | Gives a condition on an allowed input. |
| Proposition | \(P(3)\), meaning \(3+2=5\) | Makes a definite claim, which is true. |
| Proposition | \(P(1)\), meaning \(1+2=5\) | Makes a definite claim, which is false. |
A domain does not specify a particular input. Saying “\(x\) is an integer” tells us which values are allowed, but it does not tell us whether \(x\) is \(3\), \(1\), or another integer.
Substitution Must Be Consistent
When a variable appears more than once, every occurrence of that variable represents the same input. To evaluate a predicate at a given input, replace all of those occurrences consistently.
Worked Example: One Input, Several Occurrences
For real numbers \(x\), define
For \(Q(2)\), both occurrences of \(x\) are replaced with \(2\). The resulting proposition is \(2^2=2+2\), which is true because both sides equal \(4\).
For \(Q(-1)\), the proposition is \((-1)^2=(-1)+2\). Both sides equal \(1\), so it is also true. The parentheses matter: the input being squared is the entire number \(-1\).
For \(Q(0)\), the proposition is \(0^2=0+2\). This is false because \(0\ne 2\). Thus the same predicate produces true propositions at some inputs and false propositions at others.
These calculations evaluate three instances of \(Q\). They do not, on their own, establish which other real numbers satisfy it. Evaluating particular inputs and describing all satisfying inputs are different tasks.
The Domain Is Part of the Meaning
A predicate must give a definite proposition for each allowed input. The domain therefore cannot be chosen without checking that the condition makes sense there.
For example, consider the proposed condition
With domain the nonzero real numbers, this is a well-defined predicate: each allowed input has a reciprocal. Then \(H(2)\) is true because \(1/2>0\), and \(H(-2)\) is false because \(-1/2<0\).
If we instead announce that every real number is allowed, the formula has a problem at \(0\). Division by zero is undefined in the real numbers. We cannot treat \(H(0)\) as an ordinary false instance; it is not an allowed substitution for the predicate as properly defined.
Even when a formula is meaningful on two different domains, the choice of domain affects what general claims about it say. For example, \(x+2=5\) is meaningful both for integers and for even integers. It has the satisfying input \(3\) among the integers. It has no satisfying input among the even integers: the equation requires \(x=3\), and \(3\) is not even, since \(3=2k\) would require the noninteger value \(k=3/2\).
Predicates with More Than One Variable
A predicate can describe a relationship between several inputs. For integers \(x\) and \(y\), define
To obtain a proposition by substitution, we must supply both inputs. Their order matters: the first replaces \(x\), and the second replaces \(y\).
| Substitution | Resulting assertion | Truth value |
|---|---|---|
| \(R(3,5)\) | \(3+2=5\) | True |
| \(R(5,3)\) | \(5+2=3\) | False |
| \(R(-2,0)\) | \(-2+2=0\) | True |
| \(R(0,0)\) | \(0+2=0\) | False |
Substituting only the first input gives \(R(3,y)\), meaning \(5=y\). This remains a condition on the integer \(y\). It becomes true when \(y=5\) and false when, for example, \(y=4\).
A variable whose value has not been assigned and which is not governed by words such as “for every” or “there is” is called a free variable. In \(R(3,y)\), \(y\) remains free. A partial substitution generally leaves an open sentence rather than a complete proposition.
From a Predicate to a General Proposition
Substitution is one way to obtain a proposition from a predicate. Another is to state how broadly the condition is claimed to hold, using wording already encountered in the previous tutorial.
For \(P(x): x+2=5\) on the integers, compare:
- \(P(3)\): the condition holds at the specified input \(3\).
- There is an integer \(x\) for which \(P(x)\) holds: at least one allowed input satisfies the condition.
- For every integer \(x\), \(P(x)\) holds: each allowed input satisfies the condition.
All three are propositions. The first is true by addition. The second is true because \(3\) supplies an allowed input that works. The third is false because the allowed input \(1\) does not work.
The phrases “there is” and “for every” are called quantifiers. Here their ordinary mathematical wording is enough: they turn a condition on a variable into a claim about some or all of its allowed values.
Nor must a predicate change truth value as its input changes. For real numbers \(x\), the predicate \(x+0=x\) is satisfied by every input. The open formula still displays a free variable; “For every real number \(x\), \(x+0=x\)” makes the corresponding general proposition explicit.
Comparing Two Predicates by a Proof
Predicates give us a precise way to compare conditions. Consider these two predicates, both with domain the integers:
They describe different expressions, but they are satisfied by exactly the same inputs. This is a general proposition, and checking a few integers would not prove it.
The words “if and only if” require both directions: every input satisfying the first condition must satisfy the second, and every input satisfying the second must satisfy the first.
Proof. Let \(n\) be an arbitrary integer. First suppose that \(n\) is even. The integer \(2\) is even because \(2=2\cdot1\). By the earlier result that the sum of two even integers is even, \(n+2\) is even.
For the other direction, suppose that \(n+2\) is even. By the definition of evenness given earlier, there is an integer \(k\) such that \(n+2=2k\). Subtracting \(2\) gives
Since \(k-1\) is an integer, the definition of evenness shows that \(n\) is even. Both directions hold for an arbitrary integer \(n\), so the theorem follows.
No positivity assumption was used. The proof includes zero and negative integers. The two directions also ensure agreement on false instances: if \(E(n)\) were false but \(S(n)\) true, the second direction would force \(E(n)\) to be true, a contradiction. The first direction rules out the opposite mismatch.
The theorem does not say that \(E(n)\) and \(S(n)\) are always true. For example, both are false at \(n=1\): neither \(1\) nor \(3\) is twice an integer. It says that the two conditions agree at each allowed input.
A Method for Reading Predicates
Separate the assertion being tested from expressions that merely represent numbers.
Determine the allowed values of each variable and check that the condition is meaningful for all allowed inputs.
Check which variables have assigned values, which are governed by “every” or “there is,” and which remain free.
Substitute consistently for a particular instance, or give a general argument when the proposition concerns all allowed inputs.
The central distinction is between a condition on inputs and a complete claim. A predicate describes what an input must satisfy. A proposition asserts something definite, whether about one input or an entire domain.
Check Your Understanding
Give a reason for each answer, and state the domain whenever you introduce a predicate.
- For integers \(n\), let \(P(n)\) mean \(n+4=1\). Write out \(P(-3)\) and \(P(0)\), and determine their truth values. How does \(P(n)\), with \(n\) free, differ from these propositions?
- For real numbers \(x\), let \(Q(x)\) mean \(x^2=x+2\). Write out \(Q(-2)\) with parentheses and evaluate it. Why must both occurrences of \(x\) receive the same value?
- For integers \(x\) and \(y\), let \(R(x,y)\) mean \(x+2=y\). Evaluate \(R(4,6)\) and \(R(6,4)\). What variable remains free in \(R(x,6)\)?
- Why does the condition \(1/x>0\) require a domain restriction? Explain the difference between substituting \(-1\) and attempting to substitute \(0\).
- Let \(E(n)\) mean “\(n\) is even,” with integer domain. Compare \(E(2)\), “There is an integer \(n\) for which \(E(n)\) holds,” and “For every integer \(n\), \(E(n)\) holds.” Which are propositions, and what does each assert?
- Prove that, for every integer \(n\), \(n\) is even if and only if \(n+4\) is even. Explain why proving only one direction would not establish that the two predicates agree at every input.