maths.free › Discrete Math & Logic › 2. Logic and Proofs › Mathematical Statements

Mathematical Statements

Investigation While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies.

Section Preview

Investigation

While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:

Troll 1: If I am a knave, then there are exactly two knights here.

Troll 2: Troll 1 is lying.

Troll 3: Either we are all knaves, or at least one of us is a knight.

Which troll is which?

In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding numerical answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

In fact, the primary goal of mathematics, as an academic discipline in its own right, is to establish general mathematical truths. How can we know whether these facts, perhaps called theorems or propositions, are true? We construct valid arguments, called proofs, which establish the truth of the statements. Here, an argument is not the sort of thing you have with your Mom when you disagree about what to have for dinner. Rather, we have a technical definition of the term.

Our definitions of argument, valid argument, and sound argument are the same ones used in philosophy, the other primary academic discipline concerned with logic and reasoning.

To determine whether we have a proof of a statement, we must decide both whether every premise is true, and whether the argument is valid: whether the conclusion follows from the premises. How can we do this?

Since arguments are built up of statements, we must agree on what counts as a statement.

If the sentences in an argument could not be true or false, there would be no way to determine whether the argument was valid, since validity describes a relationship between the truth values of the premises and conclusions.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Atomic and Molecular Statements

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

Example

These are statements (in fact, atomic statements):

  • Telephone numbers in the USA have 10 digits.

  • The moon is made of cheese.

  • 42 is a perfect square.

  • Every even number greater than 2 can be expressed as the sum of two primes.

  • \(3+7 = 12\)

And these are not statements:

  • Would you like some cake?

  • The sum of two squares.

  • \(1+3+5+7+\cdots+2n+1\)

  • Go to your room!

  • \(3+x = 12\)

The reason the sentence \(3 + x = 12\) is not a statement is that it contains a variable. Depending on what \(x\) is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by setting a specific substitution, for example, \(3+x = 12\) where \(x = 9\), which is a true statement. Or you could capture the free variable by quantifying over it, as in, For all values of \(x\), \(3+x = 12\), which is false. We will discuss quantifiers in more detail in the subsection below.

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Telephone numbers in the USA have 10 digits, and 42 is a perfect square.

Note that we can break this down into two smaller statements. The two shorter statements are connected by an and. We will consider 5 connectives: and (Sam is a man, and Chris is a woman), or (Sam is a man, or Chris is a woman), if, then (if Sam is a man, then Chris is a woman), if and only if (Sam is a man if and only if Chris is a woman), and not (Sam is not a man). The first four are called binary connectives (because they connect two statements) while not is an example of a unary connective (since it applies to a single statement).

These molecular statements are, of course, still statements, so they must be either true or false. The crucial observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say or whether they have some material connection to each other, only whether those parts are true or false.

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Quantifiers and Predicates

Did you know that all mammals have hair? That every integer is even or odd? That some odd numbers are not prime?

Our goal is to explore how to write statements such as these in mathematical notation to highlight the logical structure of the statements.

This will require considering a new sort of basic sentence called a predicate, which is like a statement, but contains a free variable. When you replace that variable with a constant of some sort, then the sentence becomes a statement proper. Think of a predicate as making a claim about the values that are substituted for the placeholder variable(s).

A predicate can be made into a (true or false) statement by evaluating it at some constant(s), or we can claim that some or all possible constants would make the resulting statement true or false. This is done using quantifiers.

We usually write predicates similar to how you write a function, although with capital letters. For example, we might use the predicate \(P(x)\) to represent \(x\) is prime. We can then say that \(P(7)\) is true (since 7 is prime) and that \(P(8)\) is false. Or using quantifiers, we can (falsely) claim that all numbers are prime by writing \(\forall x P(x)\) or (truthfully) claim that there is at least one prime number, by writing \(\exists x P(x)\).

Example

Translate the statement, Every number is even or odd, into symbols.

Solution

Before we even start using symbols, it is helpful to rephrase this in a way that captures the logical structure of the statement. What is the claim saying? Given any number, it will either be the case that the number is even, or that the number is odd. In particular, we are not claiming that either all numbers are even or all numbers are odd.

Let's use \(E(x)\) to say that \(x\) is even, and \(O(x)\) to say that \(x\) is odd. Then we can write, \[E(x) \vee O(x)\] to say that \(x\) is even or \(x\) is odd. Which \(x\) is that true for (according to the claim)? All of them. So we write the statement as, \[\forall x (O(x) \vee E(x))\]. We added some parentheses to emphasize that the scope of the universal quantifier includes both predicates.

Note that if we incorrectly interpreted the statement as claiming that either all numbers are even or all numbers are odd, we could write that as \(\forall x O(x) \vee \forall x E(x)\). This is not the same!

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (15)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Spend a few minutes thinking about the Investigate problem above. What could you conclude if you knew Troll 1 really was a knave (i.e., their statement was false)? Share your initial thoughts on this.

  2. Which of the following sentences should count as statements? That is, for which of the sentences below could you potentially claim the sentence was either true or false? Select all that apply.

  3. You and your roommate are arguing, and they make the audacious claim that pineapple is good both on pizza and in smoothies. Which of the following are reasonable responses to this claim, from a logical point of view?

  4. Your roommate now makes an even more outrageous claim: If a superhero movie is part of the Marvel Cinematic Universe, then it is good. Which of the following are reasonable responses to this claim, from a logical point of view?

  5. Your roommate just won't let up with their outrageous claims. Now they claim that either every troll is a knave, or there is at least one troll that is a knight. What can you say to this?

  6. Match each statement in symbols with its type of statement.

  7. Consider the sentence, If \(x \gt 3\), then \(x\) is even.

    Which of the following statements are true about the sentence? Select all that apply.

  8. What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

  9. Let \(P(x,y)\) be the predicate, person \(x\) can be fooled at time \(y\).

    Match each statement with its representation in symbols.

  10. Your friend believes that you cannot fool everyone at the same time. What is another way of saying this, and how would you write that in symbols (using \(P(x,y)\) to say you can fool \(x\) at time \(y\)).

  11. Regardless of your beliefs of how many people can be fooled at various times, what could you conclude if we reinterpret \(P(x,y)\) to mean \(x \lt y\) and only quantify over the natural numbers (so \(\forall x\) means For all natural numbers, and \(\exists x\) means There exists a natural number)? Select all of the following that apply.

  12. Consider the sentence, \(\exists x P(x,y) \imp \forall x P(x,y)\). What can we say about this sentence? Select all that apply.

  13. Suppose \(P\) and \(Q\) are the statements: \(P\): Jack passed math. \(Q\): Jill passed math.

    1. Translate Jack and Jill both passed math into symbols.

    2. Translate If Jack passed math, then Jill did not into symbols.

    3. Translate \(P \vee Q\) into English.

    4. Translate \(\neg(P \wedge Q) \imp Q\) into English.

    5. Suppose you know that if Jack passed math, then so did Jill. What can you conclude if you know that:

      1. Jill passed math?
      2. Jill did not pass math?

    Revelar la respuesta

    1. \(P \wedge Q\)
    2. \(P \imp \neg Q\)

    3. Jack passed math or Jill passed math (or both).

    4. If Jack and Jill did not both pass math, then Jill did.

      1. Nothing else.
      2. Jack did not pass math either.

  14. Translate into symbols. Use \(E(x)\) for \(x\) is even and \(O(x)\) for \(x\) is odd.

    1. No number is both even and odd.

    2. One more than any even number is an odd number.

    3. There is a prime number that is even.

    4. Between any two numbers there is a third number.

    5. There is no number between a number and one more than that number.

    Revelar la respuesta

    1. \(\neg \exists x (E(x) \wedge O(x))\)
    2. \(\forall x (E(x) \imp O(x+1))\)
    3. \(\exists x(P(x) \wedge E(x))\)\(P(x)\)\(x\) is prime
    4. \(\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\)
    5. \(\forall x \neg \exists y (x \lt y \lt x+1)\)

  15. For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false.

    1. \(\forall x \exists y (y^2 = x)\)
    2. \(\forall x \forall y (x \lt y \imp \exists z (x \lt z \lt y))\)
    3. \(\exists x \forall y \forall z (y \lt z \imp y \le x \le z)\)

    Revelar la respuesta

    Hint:

    First figure out what each statement is saying. For part (c), you don't need to assume the domain is an infinite set.

Symbols used here

\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
\neq
not equal
The two sides are different.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
a \bmod n
remainder
What is left after dividing a by n.

How to: Mathematical Statements

  1. Identify the logical structure of statements to determine their truth value in terms of the truth values of their parts.
  2. Identify the use of quantifiers in a statement, and determine the truth value of the statement based on those quantifiers.
  3. Translate between statements in natural language and logical symbols.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Prueba tu propio

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Más en Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions