Subsection 4.3.4 Definitions
Mathematics seeks to provide a basis for rigorous and insightful arguments. No surprise then that mathematicians make use of the logical tools we’ve described. They start with definitions, then assert axioms, and move on to claims that they can show to be theorems. We too will start with definitions.
A definition (like this one) is a claim that one thing (the thing being defined) is equivalent to some other thing (typically described in terms that we’ve already defined). So definitions generally take the form of logical equivalence statements.
Let’s do a simple definition first. Our domain is the set of integers (including zero and the negative integers). We will say that Div(x, y) is true if x is evenly divisible by nonzero y:
 \(\forall \) x, y (Div(x, y) \(\equiv \) ((y \(\neq \) 0) \(\wedge \) \(\exists \) z (x = yz)))
We can read this as, “Saying that x is divisible by nonzero y is equivalent to saying that x is the product of y and some integer z.”
Next, we can use our definition of Div to define what it means for an integer to be even:
 \(\forall \) x (Even(x) \(\equiv \) Div(x, 2) )
We can read this as, “Saying that an integer x is even is equivalent to saying that it is divisible by 2.”
In these last two examples, you saw that we read our definitions as:
Saying that <one thing > is equivalent to saying <something else>.
It’s more common to read ≡ as “if and only if”. So we can read our second definition as:
x is even if and only if …
Since “if and only if” gets a bit cumbersome, it can be abbreviated iff.
Finally, we should probably warn you here: Mathematicians tend, in definitions, to say:
x is <something significant> if <certain significant things are true>.
Note that we’ve written just “if” when we actually meant “if and only if”. You may have noticed that we’ve been using this convention also (including in our definition of Div in this very example). It’s very common. Just keep in mind that the English word “if”, when used in a definition, generally means “if and only if”.
Mathematical definitions are written as logical statements that exploit an equivalence statement.
Now let’s define what it means to be a prime number. We’ll consider the domain of positive integers. Recall that a prime number is a positive integer greater than 1 that is not evenly divisible by any positive integer except itself and 1. So, for example:
Some prime numbers are: 2, 3, 5, 7, 11, 257, 463, and 997.
Some nonprime numbers are: 4, 6, 8, 9, 10, 12, 15, 27, 201, 403, 819, and 931.
We can now state clearly what it means to be a prime. We’ll use the Div predicate that we defined above and we’ll exploit the notion of equality that we’ve already described.
Assume that the universe is the positive integers. Here’s one definition:
 \(\forall \) x (Prime(x) \(\equiv \) ( (x > 1) \(\wedge \) \(\forall \) y (Div(x, y) \(\rightarrow \) ((x = y) \(\vee \) (y = 1)))))
We can read what we’ve written as: x is Prime if and only if:
x is greater than 1, and
For any y that evenly divides x, y is 1 or it is x itself.
So, for example, 6 isn’t prime because it’s divisible by 2, which is not equal to 6 and not equal to 1.
Here’s another, equivalent definition:
 \(\forall \) x (Prime(x) \(\equiv \) ( (x > 1) \(\wedge \) \(\neg \) \(\exists \) y (Div(x, y) \(\wedge \) \(\neg \) (x = y) \(\wedge \) \(\neg \) (y = 1))))
Now we can read what we’ve written as: x is prime if and only if:
x is greater than 1, and
There exists no y that has all three of these properties:
It evenly divides x.
It isn’t equal to x.
It isn’t 1.
If you want to experiment with finding prime numbers, visit http://mathforsmartypants.com/resources/primecheck.php 1 for a nice primality checking app.
Of course, once we’ve defined predicates, like Prime and Even, we can use them to make formal claims that we can then set about to prove.
Let’s write a logical expression that corresponds to the claim that the only even prime number is 2 (a true claim that is quite easy to see: No prime number is less than 2. And any larger even number has 2 has a divisor and so is not prime.)
We state our claim as:
 \(\forall \) x ((Even(x) \(\wedge \) Prime(x)) \(\rightarrow \) (x = 2))
1. We wish to assert the claim that there is no prime number strictly between 317 and 337. (Note that “strictly between” means that the required number may not be either 317 or 337.)
(Part 1) Which one or more of the following correctly asserts this claim:
I. ∀x (Prime(x) → ¬( (x < 317) ∧ (x > 337)))
II. ∀x (Prime(x) → ( (x ≤ 317) ∧ (x ≥ 337)))
III. ∀x (Prime(x) → ( (x ≤ 317) ∨ (x ≥ 337)))
Just I and II.
Just II and III.
(Part 2) Is this claim true?
2. Composite Numbers A composite number is an integer, greater than 1, that is not prime. Without using the predicate Prime that we’ve already defined (because the point here is to get practice at the definition process), we want to give a formal definition of what it means to be composite. Call our new predicate Composite. Assume the domain of positive integers. Which one or more of the following correctly defines Composite:
I. ∀x (Composite(x) ≡ (¬(x = 1) ∧ ∀y (Div(x, y) ∧ ¬(x = y) ∧ ¬(y = 1) ) ) )
II. ∀x (Composite(x) ≡ (¬(x = 1) ∧ ∃y (Div(x, y) ∧ ¬(x = y) ∧ ¬(y = 1) ) ) )
III. ∀x (Composite(x) ≡ (¬(x = 1) ∧ ∃y (Div(x, y) ∨ ¬(x = y) ∨ ¬(y = 1) ) ) )
Just I and II.