Interpret propositions and quantifiers

Statements, predicates and domains

A proposition is a statement with a definite truth value. “9 is even” is a proposition, although it is false. A question or an instruction is not a proposition. “x + 2 = 7” is an open sentence: it is true at x = 5 but false at x = 0. Assigning x, or quantifying over a stated domain, produces a proposition. A statement can have a definite truth value even when we do not yet know it

1. 1State the domain A proposition has a definite truth value, true or false. A predicate such as x² = 4 is open until x is assigned or quantified over a stated domain

Which is a proposition?

For every and there exists

For every means each member of the specified domain must satisfy the predicate. There exists means at least one member does. It does not say that the witness is unique. Here both 3 and −3 witness the existential statement. In this course N means the positive integers unless another convention is stated

1. 1Every and at least one The universal quantifier means every member of the domain. The existential quantifier means at least one member, not exactly one. A witness must belong to the domain \(\displaystyle \begin{gathered}\forall x\in D,\ P(x)\\\exists x\in D,\ P(x)\end{gathered}\)

An existential statement has two different witnesses. What follows?

Verify a witness in the domain

To establish an existential statement, exhibit an allowed value and verify the complete predicate. For “there exists an integer n with n² = 25”, n = −5 is in Z and its square is 25, so the statement is true. A proposed square root of 2 cannot witness an integer statement, even though its square is 2.

Why is the positive square root of 2 not a witness for “there exists an integer n with n² = 2”?

Negate a quantified statement

The negation must be true exactly when the original is false. To deny that every member works, assert that at least one member fails. To deny the existence of a witness, assert that every member fails. Keep the domain unchanged. For real inequalities, not greater than becomes less than or equal to, and not less than or equal to becomes greater than

1. 1Negate both the quantifier and the predicate Not every means at least one failure. There does not exist means every member fails. Keep the same domain and include the correct inequality boundary \(\displaystyle \begin{gathered}\neg(\forall x\in D, P(x))\\\iff\exists x\in D,\neg P(x)\\\neg(\exists x\in D, P(x))\\\iff\forall x\in D,\neg P(x)\end{gathered}\)

What is the exact negation of “every real x satisfies x > −1”?

For real x, what is the exact negation of x ≤ 4?

Read an implication

In if P then Q, P is the hypothesis and Q is the conclusion. The conditional is false only when P is true and Q is false. If P is false, the conditional is true in the logical sense: that case does not break its promise. This does not assert that Q is true, or describe a causal relationship. For a universal conditional, every allowed value must avoid the failure case

1. 1A conditional has one failure case To disprove if P then Q, make P true and Q false. A false hypothesis is not a counterexample. The negation of the conditional is P and not Q. \(\displaystyle \begin{gathered}\neg(P\implies Q)\\\iff P\land\neg Q\end{gathered}\)

Which truth values disprove P implies Q?

Converse and contrapositive

If an integer is divisible by 8, then it is divisible by 4. Its converse says that divisibility by 4 implies divisibility by 8; n = 4 disproves that. The contrapositive says that an integer not divisible by 4 is not divisible by 8. It is equivalent to the original. The inverse, not P implies not Q, is equivalent to the converse, not generally to the original. We use the contrapositive as a proof method in the next section

1. 1Distinguish the related conditionals The converse reverses the direction and need not be equivalent. The contrapositive reverses the direction and negates both statements; it is equivalent to the original \(\displaystyle \begin{gathered}\text{original: }P\implies Q\\\text{converse: }Q\implies P\\\text{contrapositive: }\neg Q\implies\neg P\end{gathered}\)

Which is the contrapositive of “if x > 2, then x² > 4”, for real x?

Necessary, sufficient and equivalent

Divisibility by 8 is sufficient for divisibility by 4: it guarantees it. Divisibility by 4 is necessary for divisibility by 8: a multiple of 8 cannot lack it. These are not equivalent conditions, because the reverse direction fails at 4. To assert if and only if, both implications must hold

1. 1Sufficient and necessary In P implies Q, P is sufficient for Q, while Q is necessary for P. An equivalence, written if and only if, requires both directions \(\displaystyle P\iff Q\)

In a true implication P implies Q, which description is correct?

Build a counterexample, not just an example

Consider the claim that for every real x, x² > 9 implies x > 3. Choose x = −4. It belongs to R, its square is 16 > 9, but −4 > 3 is false. This one case refutes the universal claim. At x = 2 the hypothesis fails, so it cannot refute the conditional. At x = 4 both parts hold, which is only one successful example

1. 1Use examples for the right purpose One verified witness proves existence. One valid counterexample refutes a universal claim. Successful examples do not prove an infinite universal claim; a finite domain can be proved by checking every member

A counterexample to “for every x in D, P(x) implies Q(x)” must satisfy which conditions?

What checking examples can establish

One verified example proves an existential claim. Checking every member of a finite domain can prove a universal claim on that domain. Checking 50 or 5,000 cases does not prove a claim over all integers. A program can help discover a counterexample or a conjecture, but its finite search is not automatically a general proof. Failure to find a counterexample does not prove truth, and lack of a proof does not prove falsity

All members of A = {−2, 0, 2} have been checked and satisfy x² ≤ 4. What is proved?

Keep the order of quantifiers

For every real x, there exists a real y greater than x is true: after x is given, choose y = x + 1. There exists one real y greater than every real x is false: for any proposed fixed y, x = y + 1 is larger. In negating a statement with two quantifiers, change each quantifier in place and negate the final predicate. Do not reorder the variables

1. 1Quantifier order matters In for every x there exists y, y may depend on x. In there exists y for every x, one fixed y must work for all x. Negation changes each quantifier in place; it does not reorder them

In “for every real x there exists a real y with y > x”, may y depend on x?

An empty domain

If A is empty, “every x in A satisfies P(x)” is true because no member violates it. “There exists x in A satisfying P(x)” is false because there is no possible witness. This is called vacuous truth for the universal statement. It does not assert that a member of A exists

Written statement practice, ungraded

On paper, translate “every integer has a square greater than 2” into symbols, then write its exact negation in symbols and words. Preserve the domain and inequality boundary. Decide which statement is true and justify that decision. This written construction is not automatically marked. The next screen gives a model

Model statement and negation

The original statement is false. Its negation says there exists an integer whose square is less than or equal to 2. The integer 0 is a witness: it belongs to Z and its square is 0 ≤ 2. This proves the existential negation and refutes the original universal statement

Written counterexample practice, ungraded

Refute the claim: for every real x, if x² > 16 then x > 4. Write a counterexample with all three checks: it lies in the domain, satisfies the hypothesis and fails the conclusion. Then write the converse and contrapositive of the claim. These written responses are ungraded; the next screen gives a model

Model counterexample and related statements

Take x = −5, which is real. Its square is 25 > 16, but −5 > 4 is false, so the universal claim is false. The converse is: if x > 4, then x² > 16. The contrapositive is: if x ≤ 4, then x² ≤ 16. The original and its contrapositive are equivalent and both false, while the converse is true. Equivalence does not mean that the statements must be true