Skip to main content

Subsection 6.2.2 Mathematical Statements

Mathematical statements are formal claims. The logical language that we’ve developed is exactly what we need to encode them in a way that is unambiguous and that enables us to reason with what we know.

Let’s look at how we can do two important things:

  • Define concepts. We do this with the logical notion of equivalence.

  • Assert properties and relationships of the objects that we’ve defined. We do this with our full arsenal of logical tools.

We derive a good deal of power from the fact that this approach lets us easily build new concepts on top of simpler ones. Let’s see how this works.

Recall that we’ve already defined two useful predicates on the integers:

[1] Div(x, y) ≡ ∃z (x = y⋅z) Div(x, y) is true iff x is evenly divisible by y.

[2] Even(x) ≡ Div(x, 2) Even(x) is true iff x is divisible by 2.

Now we can exploit them to define new useful concepts:

Definition of Prime Numbers

A prime number is an integer greater than 1 whose only divisors are itself and 1. We’ve already seen that we can write this definition formally. In fact, we gave two equivalent definitions (read them carefully to see what they are saying):

[3] ∀x (Prime(x) ≡ ( (x > 1) ∧ ∀y (Div(x, y) → ((x = y) ∨ (y = 1)))))

[4] ∀x (Prime(x) ≡ ( (x > 1) ∧ ¬∃y (Div(x, y) ∧ ¬(x = y) ∧ ¬(y = 1))))

Definition of Composite Numbers

A composite number is an integer greater than 1 that isn’t prime. Here’s a definition stated in terms of our basic predicate Div:

[5] ∀x (Composite(x) ≡ ( (x > 1) ∧ ∃y (Div(x, y) ∧ ¬(x = y) ∧ ¬(y = 1) ) ) )

Exercises Exercises

1.

We want to encode the fact that there is no largest integer. Another way to say this is that every integer has another one that is bigger than it is.

Which (one or more) of the following statements correctly encode(s) our claim:

I. ¬∃i (∀j (i ≥ j))

II. ∀i (∃j (j > i))

III. ∃i (∀j (j > i))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. II and III.

Answer.
Correct answer is D.
Solution.
Explanation: I says that there doesn’t exist any i that’s greater than or equal to everything else. II says that for every i, there’s something else that is greater than it. Those two are correct. But III says that there exists an i such that everything is greater than it. This would be true of the positive integers. That smallest number would be 1. It isn’t true of all the integers.

2.

2. We want to encode the fact that, for any nonzero integer, there’s a different integer with the same absolute value. So, for example, consider 2. Another integer, namely -2, has the same absolute value as 2.

Let |x| stand for the absolute value of x. Which (one or more) of the following statements correctly encode(s) our claim:

I. ∀x (∀y ((x = y) → ((¬(x = 0) ∧ (|x| = |y|))))

II. ∃y ((¬(y = 0)) → ∃x (|x| = |y|))

III. ∀x ((¬(x = 0)) → ∃y (¬(x = y) ∧ (|x| = |y|)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. II and III.

Answer.
Correct answer is C
Solution.
Explanation: III says that, if x isn’t 0, then there exists a different y with the same absolute value. This is correct. I says that, for any two integers, if they are equal then the first one isn’t 0 and their absolute values are the same. Of course, if they’re equal, their absolute values are the same. But it isn’t true that any x must be 0. Thus this claim cannot be equivalent to III, since III is true. It’s hard to make sense of II when it’s written this way. Let’s use Disjunctive Syllogism and Double Negation to get rid of the implies. We get:
y ((y = 0)  x (|x| = |y|))
This claim is true (since there clearly exists a y that is equal to 0), but it’s different from the one we are trying to make.