Reasoning: An Introduction to Logic, Sets, and Functions

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.

Divisibility

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:

[1] \(\forall \) x, y (Div(x, y) \(\equiv \) ((y \(\neq \) 0) \(\wedge \) \(\exists \) z (x = yz)))

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.”

Even numbers

Next, we can use our definition of Div to define what it means for an integer to be even:

[2] \(\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”.

Big Idea

Mathematical definitions are written as logical statements that exploit an equivalence statement.

Prime Numbers

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:

[3] \(\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:

[4] \(\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.

Nifty Aside

If you want to experiment with finding prime numbers, visit http://mathforsmartypants.com/resources/primecheck.php¹ 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:

[5] \(\forall \) x ((Even(x) \(\wedge \) Prime(x)) \(\rightarrow \) (x = 2))