Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic
  1. Propositions
  2. Modeling Logic with Truth Tables
  3. Logical Equivalence
  4. The Laws of Logic
  5. Application: Switching Networks
  6. Logical Implications
  7. Propositions with Variables
  8. Quantifiers
  9. Logic with Quantified Statements
  10. Nested Quantifiers
  11. Application: Logic Puzzles
  12. A Primer on Fuzzy Logic
  1. Mathematical Logic with Maple
  2. Defining Propositions with Maple
Arguments and Proof
  1. The Structure of Basic Arguments
  2. Rules of Inference
  3. Using the Rules of Inference
  4. Logically Equivalent Arguments
  5. Invalid Arguments
  6. Universal Specification
  7. Universal Generalization
  8. Axioms, Definitions, Theorems, and Proofs
  9. Proof Technique: Direct Proofs
  10. Proof Technique: Indirect Proofs
  11. Proof Technique: Contradiction
  12. Mistakes in Proofs
  13. Proof Technique: Equivalence
  1. Verifying Mathematical Arguments in Maple
Set Theory
  1. Sets
  2. Subsets
  3. Proof Technique: Element Arguments
  4. A Set of Operations on Sets
  5. The Laws of Set Theory
  6. Proof Technique: Exhaustion
  1. Set Theory in Maple

Quantifiers

Consider the following propositional functions:

s(n):The number n2 is an even.
t(m, n):The number m2 – n2 is even.

For both propositional functions, let the universe 𝒰 be all integers.

We can find values of n to make s(n) true, such as n = -4. We can also find values of n to make s(n) false, such as n = 13. The same thing can be said of t(m, n). The values m = 3 and n = -7 make t(m, n) a true statement. The values m = 4 and n = -1 make t(m, n) false. Both s(n) and t(m, n) are examples of open statements, so this was perhaps not surprising.

Now consider the following statements:

α:For some n, s(n) is true.
β:For all m and all n, t(m, n) is true.

α and β are not open statements, even with the presence of variables. The difference here is that each statement is making a specific claim, and the truth values of these statements do not depend on the values taken by the variables.

Statement α is making the claim that some specific integer exists that makes s(n) a true proposition. As we saw earlier in this paragraph, one such value is n = -4. As such it is true that some value exists, so α is a true proposition. It doesn’t matter that n = 13 makes s(n) a false statement because α is making a claim about the existence of some satisfying value, one example of which was found earlier.

Likewise, β is also making a specific claim. The claim is that every single value of m and every single value of n makes t(m , n) a true statement. We saw that t(m, n) is a false statement when m = 4 and n = -1. Because it is not true that all m and all n make t(m, n) true, we have that β is a false statement regardless of the fact that some values of m and n do make t(m, n) a true statement.

We explore these kinds of statements here, and in the next couple of sections.

The Existential Quantifier

The phrases “For some n” used in statement α, and “For all m and all n” used in statement β are said to quantify the propositional functions s(n) and t(m, n).

  • “for some x”
  • “for at least one value of x”
  • “a value of x exists such that”
  • “an x exists such that”

Figure 1.8.1: The above phrases are all equivalent and specify the existential quantifier.

Existential Quantifier

The phrase “for some x” specifying that at least one value of x exists that satisfies some condition is called the existential quantifier.

The existential quantifier can be expressed symbolically as

∃x

For any propositional function p(n), we can consider the statement

∃n p(n)

which is equivalent to the statement

For some n, p(n)

which in turn is equivalent to saying

For some n, p(n) is true.

Note that in the first two phrasings, we omit the “is true” part. It is assumed that we are considering existence of values of n that make p(n) true. We could also consider existence of values of n that make p(n) false by considering the statement

∃n ¬p(n).

Similarly, we can use logical connectives along with the existential quantifier. So for propositional functions x(n) and y(n), we consider the statements

∃n [x(n) ∧ y(n)]
∃n [x(n) ∨ y(n)]
∃n [x(n) ⊻ y(n)]
∃n [x(n) → y(n)]
∃n [x(n) ↔ y(n)]

where we enclose the propositional functions within [] to specify that the existential quantifier is being applied to the logical connectives. This is different to the statements

∃n [x(n)] ∧ y(n)
∃n [x(n)] ∨ y(n)
∃n [x(n)] ⊻ y(n)
∃n [x(n)] → y(n)
∃n [x(n)] ↔ y(n)

where the existential quantifier is only being applied to the propositional function x(n). In general, it’s usually a good idea to enclose whatever statement you want the quantifier to be applied to within [].

At this point, it’s worth pointing out that

p(x)

is an open statement whose truth value can only be determined after substituting in a value for x from some universe of discourse, whereas

∃n p(n)

is not an open statement. It has a definite truth value (either some value of x from the universe exists such that p(x) = 1, or no such value exists.)

It’s also worth pointing out that when we say something like

∃n p(n) = 1,

what we mean is that the statement ∃n p(n) is equal to one, we are not simply saying that p(n) is equal to 1 (again because p(n) is an open statement, we would have to substitute a value in for n before we know whether p(n) = 0 or p(n) = 1.)

Remember that, by definition, a statement such as ∃n p(n) is true if we can find at least one value of n that makes p(n) = 1. There could infinitely many such values, 1000 values, 10 values, or even exactly 1 value. The existence of at least one such value makes ∃n p(n) a true statement.

Example 1.8.1

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

p(x):x ≥ 0
q(x):x2 ≥ 0
r(x):1 – x2 = 0
s(x):x2 – 3x + 2 > 0

The statement

∃x [p(x) ∧ r(x)]

is true because there exists at least one value of x (x = 1) that makes both p(x) = 1 and r(x) = 1. We can translate this statement as “There exists a value of x such that x > 0 and 1 – x2 = 0.”

The statement

∃x [p(x) → q(x)]

is true because there exists at least one value of x (x = -1) such that p(x) = 0, q(x) = 1, and 0 → 1 is true. Another value that makes this statement true is x = 5 since p(5) = 1, q(5) = 1, and 1 → 1 is true. We can translate this statement into English as “There exists at least one value of x such that if x ≥ 0, then x2 ≥ 0.”

The statement

∃x [r(x) ∨ s(x)]

is true because there does exist a value of x (such as x = 4) where r(x) ∨ s(x) = 1 because r(4) = 0 and s(4) = 1. We can translate this statement as “There exists a value of x such 1 – x2 = 0 or x2 – 3x + 2 > 0.”

Showing that a statement quantified by the existential quantifier is false is harder because it’s not enough to simply come up with a counter-example. To show that such a statement is false, it must be demonstrated that every single value within the universe of discourse yields a false statement. To be clear, when discussing an open statement such as p(x), what we’re talking about is showing that the statement

¬∃x p(x)

is true by showing that ∃x p(x) is false. This is different than inquiring about the truth value of ∃x [¬p(x)].

Example 1.8.2

For the universe of discourse of all natural numbers (integers larger than 0, but not including 0) consider the following open propositions:

a(n):n2 + 1 = 1
b(n):2n + 1 is an even number
c(n):n2 + 2 is a perfect square

The statement

∃n [a(n)]

is false because the only integer where n2 + 1 = 1 is n = 0. But remember that 0 is not in our universe of discourse, meaning a(0) is undefined. As such, ∃n [a(n)] is false. Thus, we have that ¬∃n [a(n)] is true.

The statement

∃n [b(n)]

is false because 1 more than any multiple of 2 is by definition odd. Hence, no integer exists such that doubling it, then adding 1 will result in an even integer. As such, ¬∃n [b(n)] is a true statement.

The statement

∃n [c(n)]

is false. Consider the difference between n2 and (n + 1)2 = n2 + 2n + 1. For any integer greater than 0, the value 2n + 1 is larger than 2. Hence it is not possible to form a perfect square by adding 2 to a previous perfect square. Hence, ¬∃n [c(n)].

The Universal Quantifier

  • “for all x”
  • “for any x”
  • “for each x”
  • “for every x”

Figure 1.8.2: The above phrases are all equivalent and specify the universal quantifier.

Universal Quantifier

The phrase “for all x” specifying that every value of x satisfies some condition is called the universal quantifier.

The universal quantifier can be expressed symbolically as

∀x

The statement

∀x p(x)

asserts that all values of x make p(x) a true statement. The statement

∀x ¬p(x)

is asserting that all values of x make p(x) a false statement. Again, it’s advisable to use [] to specify how the quantifier is being used, as in

∀x [p(x)], and ∀x [¬p(x)].

Example 1.8.3

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

p(x):x ≥ 0
q(x):x2 ≥ 0
r(x):1 – x2 = 0
s(x):x2 – 3x + 2 > 0

The statement

∀x [q(x)]

is true because no matter what real number we square, it will always be greater than or equal to 0.

As such, the statement

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

is also true because squaring a positive number always yields a positive number.

The statement

∀x [p(x) ∧ s(x)]

is false because p(1.5) ∨ s(1.5) = 1 ∧ 0 = 0. Thus, x = 1.5 is a counter-example.

The statement

∀x [¬(p(x)) ∨ r(x)]

is false because ¬(p(0)) ∨ r(0) = ¬(1) ∨ 0 = 0 ∨ 0 = 0. As such, x = 0 is a counter-example which proves that ∀x [¬(p(x)) ∨ r(x)] is a false statement.

Explicit and Implicit Quantification

Some open propositions may not be as explicitly stated as we may desire. Determining if a statement uses an existential or universal quantifier may require a close look at the wording used, or some a priori knowledge.

Example 1.8.4

Consider a universe A consisting of all animal species (sponges, ants, kangaroos, elephants, etc) along with the two following sentences:

  • If an animal flies, then it has wings.
  • If x is a flying animal, then x has wings.

Both sentences express the same idea, but are they open statements? The second sentence does have a variable, but neither sentence uses any construct similar to “All x”, “For all x”, “Every x”, “Some x”, or even “An x exists such that…”.

The presence of the indefinite articles “a” and “an” suggest that these statements use the universal quantifier because the sentences are imposing conditions, and because every animal within the universe can be examined for said condition. Hence, we would say that the use of the universal quantifer is implicit, not explicit.

Let’s introduce the following propositional functions:

f(x):x is a flying animal
w(x):x is an animal with wings

We can rewrite both bulleted statements above in a more mathematically precise way using the universal quantifier as

∀n [f(x) → w(x)]

Example 1.8.5

Consider a universe Q consisting of all planar quadrilaterals along with the following sentence:

“The opposite angles of a cyclic quadrilateral are supplementary, and conversely.”

Again, this sentence lacks any of the usual linguistic constructs that explicitly determine which quantifier is used. The only clue we have that the universal quantifier is used is the indefinite article “a”.

Using the propositional functions

c(q):q is a cyclic quadrilateral
s(q):The opposite angles of q are supplementary

we can rewrite the above sentence in a mathematically precise way as

∀q [c(q) ↔ s(q)]

(The use of the word “conversely” means that the converse of the statement is also true. We could rewrite the above sentence as “If the opposite angles of a quadrilateral are supplementary, then that quadrilateral is cyclical, and conversely” or as “The opposite angles of a quadrilateral are supplementary if and only if the quadrilateral is cyclic.”)

Example 1.8.6

Consider the universe I consisting of all the integers along with the statement

“The polynomial x3 – 6x2 + 11x – 6 has positive roots.”

For this implicitly quantified statement, the word “has” suggests that we are dealing with the existential quantifier. As such, we rewrite this statement as

∃x [x3 – 6x2 + 11x – 6 = 0]

A Quick Word on Notation

In each example presented so far, we’ve always specified a universe of discourse. It was then implicitly understood that all substitutions for variables would come from that universe. We can make this more explicit.

For example, up to now, we would say something like

“For some universe 𝒰, consider the statements ∀x [p(x)] and ∃x [p(x)]”

where we substitute values from the universe 𝒰 in for variable x. We can instead write

“Consider the statements ∀x∈𝒰 [p(x)] and ∃x∈𝒰 [p(x)]”

where we use the ∈ symbol (a stylized Greek letter epsilon) to indicate that x represents some value from collection 𝒰. So, a construct such as “x∈𝒰” would be read as “x is an element residing in universe 𝒰.”

By extension then, when we say something like

“∀x∈Ψ [p(x)]”

what we are saying is that for all values x to be found within a universe, which we are denoting with Ψ (a capital Greek letter psi), p(x) is a true statement.

Alternatively, when we write something like

“∃x∈Ψ [p(x)]”,

this is equivalent to saying that there exists some value, which we’ll refer to as x, that resides in a universe, denoted by the Greek letter Ψ, such that p(x) is a true statement.