Logical Statements

Section 1.2 Logical Statements

By a statement, we mean a sentence that asserts that something is the case. Here are some statements:

“2 is even.”
“937 is prime.”
“57 is prime.”
“The only subset of the empty set is the empty set itself.”
“There are two points on opposite sides of the equator of the Earth where the temperatures are identical.”

Sentences like “go to bed” or “what's that growing out of your ear?” are not statements, because they don't assert that something is the case.

Every statement is either true or false. That is, to every statement \(\phi\) there is one and only one corresponding element of the set \(\{\text{ true }, \text{ false }\}\text{.}\) This is called the truth-value of \(\phi\text{.}\) Thus the truth value of “2 is even” is true; the truth-value of “937 is prime” is true; the truth-value of “57 is prime” is false; and the truth-value of “the only subset of \(\varnothing\) is \(\varnothing\) itself” is true.

Let's emphasize that there are plenty of statements whose truth-value is unknown to us. That is, we just don't know whether they are true or false. For instance, “Every even integer greater than \(2\) can be written as the sum of exactly two primes” is a statement, but we don't know whether this sentence is True or False. (This particular statement is known as the Goldbach Conjecture.)

We can also speak of a statements that contain a free variable. These are useful in describing subsets of existing sets. For example, let's say we write down the set of integer multiples of \(5\text{.}\) If \(n\) is an integer, then we can let \(\phi(n)\) be the statement

“\(n\) is divisible by \(5\text{.}\)”

Here, \(n\) is a free variable in the statement \(\phi(n)\text{.}\) Thus \(\phi(n)\) will have a truth-value once we know what \(n\) is. The statement \(\phi(6)\) is false, but the statement \(\phi(10)\) is true. Now we can contemplate the set of natural numbers \(n\) such that \(\phi(n)\) holds. This is a subset of the set \(\NN_0\) of natural numbers; here's how we write it:

\begin{equation*} S = \{n \in \NN_0 : \phi(n)\} = \{n \in \NN_0 : n \text{ is divisible by 5 } \} \subseteq \NN_0\text{.} \end{equation*}

The axiom schema of set theory that allows us to define new sets in this way is called the Axiom Schema of Bounded Comprehension. It says that if you have any statement \(\phi(x)\) of set theory containing a free variable \(x\text{,}\) and if you have a set \(S\text{,}\) then you are entitled to form the set \(\{x \in S : \phi(x)\}\) whose elements are precisely those elements of \(S\) such that \(\phi(x)\) holds. The “boundedness” is the presence of the ambient set \(S\text{.}\) Bertrand Russell noticed that if you have an Axiom Schema of Unbounded Replacement, then you can generate contradictions: he suggested that we consider the set \(R = \{ S : S \notin S \} \text{,}\) which you'd have to allow if you have Unbounded Comprehension. The set \(R\) the set of all sets that are not elements of themselves. Is \(R\) an element of itself? If it isn't, then it is, and if it is, then it isn't! The solution is reject the possibility that \(R\) is a set, and along with it, you'll have to reject Unbounded Comprehension!

This reads “\(S\) is the set of natural numbers \(n\) such that \(n\) is divisible by \(5\text{.}\)” This is called set-builder notation. The colon \(:\) reads as “such that;” some authors use a vertical bar \(|\) for this, so that the sentence above could be rewritten

\begin{equation*} S=\{n\; |\; n \text{ is divisible by 5 } \}\text{.} \end{equation*}

Informally, \(S\) is the set

\begin{equation*} \{ 0, 5, 10, 15, \dots \}\text{,} \end{equation*}

but the set-builder notation above is generally preferable to this informal description, because it isn't always clear what the pattern is. For example: if we write

\begin{equation*} \{3, 5, 7, \dots \}\text{,} \end{equation*}

is that the set of odd numbers greater than \(1\text{,}\) or the set of odd prime numbers? That ellipsis isn't telling!

Example 1.2.1. Natural numbers bigger than \(10\).

For every natural number \(n\text{,}\) let \(\phi(n)\) be the statement “\(n>10\text{.}\)” Now we can look at the subset

\begin{equation*} \{n \in \NN_0 : \phi(n)\} = \{n \in \NN_0 : n > 10 \} \subseteq \NN_0 \end{equation*}

That's the set of natural numbers strictly greater than \(10\text{.}\)

Example 1.2.2. Solving equations as equalities of sets.

Consider the sets

\begin{equation*} A=\{n\in\NN_0 : (n-8)^2= 4\} \text{ and } B=\{6,10\}\text{.} \end{equation*}

These are two subsets of \(\NN_0\text{.}\) In fact, we claim \(A=B\text{.}\) To prove this, we will first prove that \(A \subseteq B\) and then that \(B \subseteq A\text{:}\)

If \(n\in A\text{,}\) then \((n-8)^2=4\text{,}\) so \(0=n^2-16n+60=(n-6)(n-10)\text{.}\) The only way the product of two natural numbers is zero is if at least one of them is zero, so \(n-6=0\) or \(n-10=0\text{,}\) i.e. \(n=6\) or \(n=10\text{,}\) hence \(n\in B\text{.}\) This shows that \(A \subseteq B\text{.}\)
If \(n\in B\text{,}\) then either \(n=6\) or \(n=10\text{,}\) and in either case \((n-8)^2=4\text{,}\) so \(x\in A\text{.}\) This shows that \(B \subseteq A \text{.}\)

The statement “\(A=B\)” here makes the sentence “the only solutions of the equation \((n-8)^2=4\) in \(\NN_0\) are \(6\) and \(10\)” precise.

Example 1.2.3. An equation with no solutions.

Let \(S=\{n\in\NN_0 : 2n=1\}\text{.}\) The sentence “\(2n=1\) has no solutions in \(\NN_0\)” is the natural language translation of the sentence “\(S=\varnothing\text{.}\)”

Warning 1.2.4.

In order for set-builder notation \(\{x \in S : \phi(x)\}\) to be meaningful, it has to be the case that the statement \(\phi(x)\) makes sense for all elements \(x \in S\text{.}\) For example, if \(S\) is the set of all fir trees, then the set

\begin{equation*} \{ x \in S : x^2 = 1\} \end{equation*}

doesn't make any sense, because we don't know how to take the square of a fir tree, nor what it means for such a square to be equal to \(1\text{.}\) That may seem like a silly point, but this basic error leads to lots of mistakes!

In fully formalized set theory, this issue is avoided by introducing a rule that says that all mathematical objects are sets, and the only statements we're permitted to contemplate are statements about sets. Telling this story would be the subject of a first course on mathematical logic or set theory.