Logic with Quantified Statements

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic

Arguments and Proof

Verifying Mathematical Arguments in Maple

Set Theory

Set Theory in Maple

Logic with Quantified Statements

What can we deduce knowing that a universally quantified open statement is true? What can we deduce knowing that an existentially quantified statement is true? How are universally quantified statements and existentially quantified statements related? In this section, we delve deeper into quantifiers and explore propositional logic involving quantifiers.

A Simple Logical Implication

Suppose we have some open statement p(x) with some non-empty universe 𝒰 (non-empty just means 𝒰 contains at least one element, which we can refer to as α.)

What can we conclude if we happened to know that the statement ∀x [p(x)] was true? That is to say, we know that

∀x [p(x)] = 1.

One thing we can conclude is that if α ∈ 𝒰 (meaning that α is some element that can be found within universe 𝒰), then p(α) = 1. As such, since some value of x exists that makes p(x) = 1, we can thus conclude that

∃x [p(x)] = 1.

Example 1.9.1

Let our universe, denoted Ν, consist of the integers 1, 2, 3, 4, 5, 6, 7, 8, and 9.

Now consider the open statement

ℓ(n):

n² < 100

defined on N.

We know that ∀n [ℓ(n)] is a true statement because

1² = 1 < 100	4² = 16 < 100	7² = 49 < 100
2² = 4 < 100	5² = 25 < 100	8² = 64 < 100
3² = 9 < 100	6² = 36 < 100	9² = 81 < 100

As such, we know that ∃n [ℓ(n)] is also a true statement because we know that 1² = 1 < 100, and as such there exists some value (n = 1) such that ℓ(n) = 1.

Does this work the other way? That is, does know that ∃x [p(x)] is a true statement mean that ∀x [p(x)] is a true statement? Certainly not, because knowing that some value exists that makes p(x) = 1 is not the same thing as knowing that every value of x within 𝒰 makes p(x) = 1.

Example 1.9.2

Consider the universe, which we’ll denote R, consisting of all the real numbers. On that universe, consider the open statement

r(x):

1 – x² = 0

We know that ∃x [r(x)] = 1. For example, r(1) = 1. We even have that r(-1) = 1, for a total of two values that make r(x) true.

However, notice that

1 – (2)² = -3.

Thus, r(2) = 0. Since not every value of x makes r(x) = 1, we have that

∀x [r(x)] = 0.

This leads us to our first logical implication:

∀x [p(x)] ⟹ ∃x [p(x)].

Let’s break this down to make it easier. We start by color-coding the actual statements in this logical implication:

∀x [p(x)] ⟹ ∃x [p(x)]

As a reminder, all of ∀x [p(x)] is a single statement with a definite truth value (it is not an open statement or propositional function.) The statement being expressed here is that “every value of x within 𝒰 makes p(x) a true statement.” Furthermore, all of ∃x [p(x)] is a single statement as well, which can be translated as “there exists at least one value of x that makes p(x) a true statement.”

Another way to break this down is by saying that

∀x [p(x)] → ∃x [p(x)] is a tautology

where ∀x [p(x)] is the hypothesis of the implication, and ∃x [p(x)] is the conclusion of the implication.

Two Simple Definitions

Just like with non-open statement, we can ask whether two open statements are logically equivalent, or if one open statement logically implies another open statement.

Logically Equivalent

Consider some open statements p(x) and q(x) defined on some universe 𝒰.

When p(a) ↔ q(a) = 1 for each value a within 𝒰 (in other words, when p(a) ↔ q(a) is a tautology), we say that p(x) and q(x) are logically equivalent open statements, and we write

∀x [p(x) ⟺ q(x)]

Example 1.9.3

Consider the universe of all planar triangles. Along with this universe, consider the following open statements:

a(t):	All three angles of triangle t are 60°
s(t):	All three sides of triangle t have equal measure

From classical geometry, we know that for any particular triangle △ABC, we have that

a(△ABC) ⟺ s(△ABC).

As such, we have that

∀t [a(t) ⟺ s(t)].

Logically Implies

Consider some open statements p(x) and q(x) defined on some universe 𝒰.

When p(a) → q(a) = 1 for each value a within 𝒰 (in other words, when p(a) → q(a) is a tautology), we say that p(x) logically implies q(x), and we write

∀x [p(x) ⟹ q(x)]

Example 1.9.4

Consider the universe of all planar quadrilaterals along with the following open statements:

s(q):	Quadrilateral q is a square
r(q):	Quadrilateral q is a rectangle

Again, from classical geometry, we know that all squares are rectangles, but not all rectangles are squares.

Thus for every planar quadrilateral q₀, we have that

s(q₀) ⟹ r(q₀)

but

r(q₀) ⇏ s(q₀)

and so

∀q [s(q) ⟹ r(q)].

The Converse, Inverse, and Contrapositive of Quantifiers

Just like how the statement

p → q

has a converse, inverse, and contrapositive, so too does the universally quantified statement

∀x [p(x) → q(x)].

Converse, Inverse, Contrapositive

Consider the open statements p(x) and q(x) defined on some universe 𝒰.

The converse of the statement ∀x [p(x) → q(x)] is

∀x [q(x) → p(x)].

The inverse of the statement ∀x [p(x) → q(x)] is

∀x [¬p(x) → ¬q(x)].

The contrapositive of the statement ∀x [p(x) → q(x)] is

∀x [¬q(x) → ¬p(x)].

Just like how a normal implication is logically equivalent with it’s contrapositive, so too is a quantified implication logically equivalent with its contrapositive.

Furthermore, the converse and inverse of a quantified implication are logically equivalent to each other.

Example 1.9.5

Consider the universe of all planar quadrilaterals along with the following open statements:

s(q):	Quadrilateral q is a square
e(q):	Quadrilateral q is equilateral

From classical geometry, we know that if a quadrilateral is a square, then it is equilateral, so we know that the statement

∀q [s(q) → e(q)]

is a tautology. In other words, ∀q [s(q) ⟹ e(q)].

The contrapositive of the above statement is

∀q [¬e(q) → ¬s(q)].

The contrapositive is saying that if a quadrilateral is not equilateral, then it is not a square. Since the implication is a logical implication, so is the contrapositive, and so we can write

∀q [s(q) → e(q)] ⟺ ∀q [¬e(q) → ¬s(q)].

Now let’s consider the converse

∀q [e(q) → s(q)].

This statement is saying that if a quadrilateral is equilateral, then it is a square. This is not necessarily true, as every rhombus is equilateral, but not every rhombus is a square. As such, we have that

∀q [e(q) ⇏ s(q)].

The inverse can be written as

∀q [¬s(q) → ¬e(q)].

The inverse is saying that if a quadrilateral is not a square, then it is not equilateral, but again, we know that any non-square rhombus is equilateral. As such we have that

∀q [¬s(q) ⇏ ¬e(q)].

Example 1.9.6

Consider the universe of all real numbers along with the following open statements:

f(x):	x² – 1 ≥ 0
α(x):	x ≤ -1

Now consider the following quantified statements:

Statement:	∀x [f(x) → α(x)]
Contrapositive:	∀x [¬α(x) → ¬f(x)]
Converse:	∀x [α(x) → f(x)]
Inverse	∀x [¬f(x) → ¬α(x)]

Consider a value of x = 5. We have that f(5) = 1, and α(5) = 0. Since 1 → 0 = 0, we have that 5 is a counter-example to our statement, and so

∀x [f(x) → α(x)] = 0.

Furthermore, since ∀x [f(x) → α(x)] ⟺ ∀x [¬α(x) → ¬f(x)], we also have that

∀x [¬α(x) → ¬f(x)] = 0.

We know that the converse is true, since when x ≤ -1, we would have that x² ≥ 1, giving us that x² -1 ≥ 0. Thus, we can write

∀x [α(x) → f(x)] = 1,

and since ∀x [α(x) → f(x)] ⟺ ∀x [¬f(x) → ¬α(x)], we also have that

∀x [¬f(x) → ¬α(x)] = 1.

Example 1.9.7

Consider the universe of all real numbers along with the following open statements:

f(x):	x² – 1 ≥ 0
α(x):	x ≤ -1
β(x):	x ≥ 1

This is a repeat of Example 1.9.6, along with a new open statement β(x). Now consider the following quantified statements:

Statement:	∀x [f(x) → ( α(x) ∨ β(x) )]
Contrapositive:	∀x [¬( α(x) ∨ β(x) ) → ¬f(x)]
Converse:	∀x [( α(x) ∨ β(x) ) → f(x)]
Inverse	∀x [¬f(x) → ¬( α(x) ∨ β(x) )]

The converse and inverse both remain true since all we did was use a disjunction. However, now we have a true original statement. As such, we have that

∀x [f(x) → ( α(x) ∨ β(x) )] = ∀x [¬( α(x) ∨ β(x) ) → ¬f(x)] = 1.

Furthermore, since we know that the original statement and the converse are true, we can write

∀x [f(x) ↔ ( α(x) ∨ β(x) )] = 1,

or equivalently,

∀x [f(x) ⟺ ( α(x) ∨ β(x) )].

Conjunctions and Disjunctions with Quantifiers

Example 1.9.8

Consider the universe of all integers along with the following two open statements:

q₁(x):	x² – 3x + 2 = 0
q₂(x):	-x² – 3x – 2 = 0

For q₁(x), we have that q₁(1) = 1 and q₁(2) = 1. All other values of x yield q₁(x) = 0.

For q₂(x), we have that q₂(-1) = 1 and q₂(-2) = 1. All other values of x yield q₂(x) = 0.

As such, no value of x makes q₁(x) ∧ q₂(x) true. This means that

∃x [q₁(x)] ∧ ∃x [q₂(x)] = 1

whereas

∃x [q₁(x) ∧ q₂(x)] = 0.

It’s worth pointing out that we have both

∃x [q₁(x)] ∨ ∃x [q₂(x)] = 1,

and

∃x [q₁(x)] ∨ ∃x [q₂(x)] = 1.

Example 1.9.8 shows that the existential quantifier does not distribute over the conjunction operator ∧. In other words, for general open statements p(x) and q(x), Example 1.9.8 gives us a counter-example revealing that

∃x [p(x) ∧ q(x)] ⇐/⇒ ∃x [p(x)] ∧ ∃x [q(x)].

Instead, what we have is

∃x [p(x) ∧ q(x)] ⟹ ∃x [p(x)] ∧ ∃x [q(x)].

In general, we do have that

∃x [p(x) ∨ q(x)] ⟺ ∃x [p(x)] ∨ ∃x [q(x)]

because if a value of x within the universe exists that satisfies the disjunction, then one of the statements within the disjunction must be true. So, the existential quantifier distributes over disjunction.

Example 1.9.9

Consider the universe of all positive integers with the following two propositional functions:

s₁(n):	n > 9
s₂(n):	n² < 100

The positive integers where s₂(n) = 1 are the integers 1, 2, 3, 4, 5, 6, 7, 8 and 9. The positive integers where s₂(n) = 1 are all those integers larger than or equal to 10. Thus, we can say that

∀n [s₁(n) ∨ s₂(n)] = 1.

Of course, we have that both ∀n [s₁(n)] = 0 and ∀n [s₂(n)] = 0, and so

∀n [s₁(n)] ∨ ∀n [s₂(n)] = 0.

It’s also worth pointing out that we have

∀n [s₁(n) ∧ s₂(n)] = (∀n [s₁(n)] ∧ ∀n [s₂(n)]) = 0

According to Example 1.9.9, for any two open statements p(x) and q(x), it looks like

∀x [p(x)] ∨ ∀x [q(x)] ⇐/⇒ ∀x [p(x) ∨ q(x)],

and instead, we have that

∀x [p(x)] ∨ ∀x [q(x)] ⟹ ∀x [p(x) ∨ q(x)].

On the other hand, it appears that we have

∀x [p(x) ∧ q(x)] ⟺ (∀x [p(x)] ∧ ∀n [q(x)]).

So it looks like the universal quantifier distributes over conjunction, but not disjunction.

We summarize the above results here.

Logical Distribution of Quantifiers Over Logical Operators

Let p(x) and q(x) be any propositional functions defined on some universe 𝒰.

∃x [p(x) ∧ q(x)]	⟹	∃x [p(x)] ∧ ∃x [q(x)]
∃x [p(x) ∨ q(x)]	⟺	∃x [p(x)] ∨ ∃x [q(x)]
∀x [p(x)] ∨ ∀x [q(x)]	⟹	∀x [p(x) ∨ q(x)]
∀x [p(x)] ∧ ∀n [q(x)]	⟺	∀x [p(x) ∧ q(x)]

Negating Quantified Statements

For some open statement p(x) and universe 𝒰, what do ¬∃x [p(x)] and ¬∀x [p(x)] mean exactly?

Focusing on ¬∃x [p(x)], remember that the statement ∃x [p(x)] asserts that at least one value of x makes p(x) a true statement. As such, if we negate the statement ∃x [p(x)], what we’re saying is that zero values of x make p(x) a true statement (it’s nonsensical to talk about a negative number or a fractional number of values that make p(x) a true statement, so such scenarios are ignored.)

Thus, the statement ¬∃x [p(x)] asserts that no value of x makes p(x) a true statement. In other words, every value of x makes p(x) a false statement. This is equivalent to the statement ∀x [¬p(x)]. As such, we have that

¬∃x [p(x)] ⟺ ∀x [¬p(x)].

Now we turn our focus to the statement ¬∀x [p(x)]. Remember that the statement ∀x [p(x)] is asserting that every value of x makes p(x) a true proposition. So, naturally, the negation of ∀x [p(x)] means that not every value of x makes p(x) a true statement. Hence, there must exist at least one value of x that makes p(x) a false statement. This is equivalent to the statement ∃x [¬p(x)]. And so we have that

¬∀x [p(x)] ⟺ ∃x [¬p(x)].

Let us quickly summarize our finding regarding quantified statements.

Summarizing Quantifiers

Consider a propositional function p(x) with some universe 𝒰.

We have the following logical equivalencies:

¬∀x [p(x)] ⟺ ∃x [¬p(x)]
¬∃x [p(x)] ⟺ ∀x [¬p(x)]

Example 1.9.10

Reconsider Example 1.9.5 where we consider the universe of all planar quadrilaterals with

s(q):	Quadrilateral q is a square
e(q):	Quadrilateral q is equilateral

From classical geometry, we know that some equilateral quadrilaterals are not squares, hence, we have that

∀q [e(q) → s(q)] = 0.

Thus, we have that

¬∀q [e(q) → s(q)] = 1.

Using the above highlighted logical equivalencies for negating quantifiers, we have that

∃q [¬(e(q) → s(q))] = 1.

We could negate the inner implication by the following steps:

	∃q [¬(e(q) → s(q))]	Law of Logic Used
⟺	∃q [¬(¬e(q) ∨ s(q))]	p→q ⇔ ¬p∨q
⟺	∃q [¬¬e(q) ∧ ¬s(q)]	DeMorgan’s Law
⟺	∃q [e(q) ∧ ¬s(q)]	Law of Double Negation

Thus, we know that

∃q [e(q) ∧ ¬s(q)] = 1,

meaning there exists some planar polygon that is equilateral and not a square. One such example is a rhombus with opposite angle measures of 60° and 120°.

The Book ofFoundational Mathematics

Logic with Quantified Statements

A Simple Logical Implication

Example 1.9.1

Example 1.9.2

Two Simple Definitions

Logically Equivalent

Example 1.9.3

Logically Implies

Example 1.9.4

The Converse, Inverse, and Contrapositive of Quantifiers

Converse, Inverse, Contrapositive

Example 1.9.5

Example 1.9.6

Example 1.9.7

Conjunctions and Disjunctions with Quantifiers

Example 1.9.8

Example 1.9.9

Logical Distribution of Quantifiers Over Logical Operators

Negating Quantified Statements

Summarizing Quantifiers

Example 1.9.10

The Book of
Foundational Mathematics