CMSC 250: First Order Logic and Associated
Proof Methods
Justin Wyss-Gallifent
October 7, 2021
1 A Tiny Bit of Set Notation . . . . . . . . . . . . . . . . . . . . . 2
2 Quantifying Variables . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Universal; For All . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Existential; There Exists . . . . . . . . . . . . . . . . . . . 4
2.4 Multiple Quantifiers . . . . . . . . . . . . . . . . . . . . . 5
2.5 Informality and Implicit Quantification . . . . . . . . . . 7
2.6 Revisiting Parity Etc. . . . . . . . . . . . . . . . . . . . . 8
2.7 Unbound Variables . . . . . . . . . . . . . . . . . . . . . . 8
3 Negating Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Contrapositive, Converse and Inverse Revisited . . . . . . . . . . 10
5 Proofs Involving Statements with Quantifiers . . . . . . . . . . . 11
5.1 Proving Existential and Disproving Universal; Counterex-
amples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2 Proving Universal and Disproving Existential . . . . . . . 13
6 What’s a Formal Proof? . . . . . . . . . . . . . . . . . . . . . . . 14
7 Basic Proof Type Overview . . . . . . . . . . . . . . . . . . . . . 15
7.1 Direct Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.2 Proof by Contrapositive . . . . . . . . . . . . . . . . . . . 17
7.3 Proof by Contradiction . . . . . . . . . . . . . . . . . . . 18
1
1 A Tiny Bit of Set Notation
Even though we’ll discuss set notation at length later there is a small collection
of symbols which will make our life easier right now.
Definition 1.0.1. The symbol ∈ means “is an element in the set of (whatever
follows)”
�
Here are some examples:
Example 1.1. We would write:
(a) x ∈ {1, 2, 3} to say that x is one of the three numbers 1,2, or 3.
(b) x ∈ {primes} to say that x is a prime number.
�
Definition 1.0.2. The symbol Z means the set of all integers and the symbol
R means the set of all real numbers.
�
Thus:
Example 1.2. We would write:
(a) x ∈ Z to say that x is an integer.
(b) x ∈ R to say that x is a real number.
�
Definition 1.0.3. The list goes on; We also have Q for rational numbers, C for
complex numbers, 2Z for even integers, and lots more.
�
2 Quantifying Variables
2.1 Introduction
We saw in propositional logic that we cannot have variables in our statements
unless we clarify what they are, otherwise it’s impossible to assign a truth value.
Example 2.1. The sentence “p is an odd prime number” is not a statement
because don’t know the value of p. It might be p = 2, in which case the
statement is false, otherwise the statement is true.
�
There are two classic ways to take a sentence which includes one or more vari-
ables and turn it into a statement.
2
2.2 Universal; For All
Suppose P (x) is some sentence which involves a variable x such that when a
particular x is plugged in, P (x) becomes a statement. That x could be a number
or even a more abstract thing.
For example, suppose P (x) is the sentence “x weighs less than one ton”. Then
for example, if x is “Justin” then the statement is true, whereas if x is “A Boeing
737” then the statement is false.
Consider now the sentence:
For all humans x, x weighs less than one ton.
We can see that this sentence is actually a statement and it is true. On the
other hand consider the sentence:
For all airplanes x, x weighs less than one ton.
This sentence is also a statement and it is false, since some airplanes weigh a
ton or more.
What we’ll do now is introduce some notation.
Definition 2.2.1. The quantifier ∀ is read “for all”.
�
Using this notation, then our previous examples become:
• The statement
∀x ∈ {humans}, x weighs less than one ton
is true.
• The statement
∀x ∈ {airplanes}, x weighs less than one ton
is false.
Here are some more:
Example 2.2. The statement:
∀x ∈ R, x2 ≥ 0
is true.
�
Example 2.3. The statement:
∀x ∈ R, x2 > 0
is false, since x = 0 makes it false, so it’s not true for all reals.
3
�
Example 2.4. If D = {2, 3, 5, 7} then the statement:
∀x ∈ D,x is prime
is true.
�
2.3 Existential; There Exists
To balance this out we’ll also have the notation:
Definition 2.3.1. The quantifier ∃ is read “there exists” and will make the
statement true if there is at least one value of the variable which makes it true.
�
Note 2.3.1. The comma used is then often read as “such that”. For example
�
Using this notation, here are examples similar to our previous.
• The statement
∃x ∈ {humans}, x weighs less than 100 pounds
is true. This is read as:
“There is an x in the set of humans such that x weighs less than 100
pounds.”
or “There is a human who weighs less than 100 pounds.”
• The statement
∃x ∈ {humans}, x weighs more than one ton
is false.
Here are some more:
Example 2.5. The statement:
∃x ∈ Z, x is prime
is true.
�
4
Example 2.6. The statement:
∃x ∈ Z, 3x = 12
is true.
�
Example 2.7. The statement:
∃x ∈ Z, 3x = 7
is false.
�
However:
Example 2.8. The statement:
∃x ∈ R, 3x = 7
is true, as the integer x = 7
3
works.
�
2.4 Multiple Quantifiers
It’s certainly possible to have a sentence which involves more than one variable.
In such a case we may introduce one quantifier for each variable.
When the quantifiers are the same the order does not matter and the statement
is usually fairly easy to understand.
Example 2.9. Consider the statement:
∀x ∈ Z,∀y ∈ Z, x + y = 100
This statement is saying that when x and y are integers the sum is always 100.
This statement is clearly false. Moreover we could have written ∀y ∈ Z,∀x ∈ Z
instead with no difference.
�
Example 2.10. Consider the statement:
∃x ∈ Z,∃y ∈ Z, y = x2
This statement is saying that it’s possible to find integers x and y which satisfy
y = x2. This statement is clearly true, for example x = 5 and y = 25. Moreover
we could have written ∃y ∈ Z,∃x ∈ Z instead with no difference.
�
5
Example 2.11. Consider the statement:
∀x ∈ Z,∀y ∈ Z, x2 + y2 ≥ 0
This statement is saying that when x and y are integers the sum of the squares
is always greater than or equal to 0. This statement is clearly true. Moreover
we could have written ∀y ∈ Z,∀x ∈ Z instead with no difference.
�
Example 2.12. Consider the statement:
∃x ∈ Z,∃y ∈ Z, x + y =
1
2
This statement is saying that it’s possible to find integers x and y whose sum is 1
2
.
This statement is clearly false. Moreover we could have written ∃y ∈ Z,∃x ∈ Z
instead with no difference.
�
Note 2.4.1. When the quantifiers and the sets are the same we can shorthand
the notation. For example instead of writing ∀x ∈ Z,∀y ∈ Z we can simply
write ∀x, y ∈ Z.
�
However when the quantifers are different then the sentences will generally mean
entirely different things.
Consider the following real-world examples. For the sake of argument we’re only
considering regular currencies here, not things like Bitcoin.
Example 2.13. Consider the statement:
For every country, there is a currency such that the currency works in the
country.
More formally we might write:
∀x ∈ {countries},∃y ∈ {currencies}, y works in x
�
Example 2.14. Consider the statement:
There is a currency, for every country such that the currency works in the
country.
More formally we might write:
∃y ∈ {currencies},∀x ∈ {countries}, y works in x
6
�
Stop and really think about the difference between these. The first one is saying
that if you choose a country, any country, there is a currency which works in in
that country. This is clearly true. On the other hand the second one is saying
that there is a currency that works in every country. This is clearly false.
Consider now a mathematical pair:
Example 2.15. The statement:
∀x ∈ Z,∃y ∈ Z, x + y = 2
This is clearly true, since y = 2− x will work for any x that’s given.
�
Example 2.16. The statement:
∃y ∈ Z,∀x ∈ Z, x + y = 2
This is clearly false. The claim here that there is one single y ∈ Z which will
work for every x ∈ Z.
�
2.5 Informality and Implicit Quantification
It’s not at all uncommon for us to be informal and/or implicit with our quan-
tification.
An example of informality would be:
Example 2.17. Consider the statement:
Squaring a real number yields a result which is greater than or equal to zero.
This would be more formally put as:
∀x ∈ R, x2 ≥ 0
�
Likewise when the context is clear we assume that it’s understood.
Example 2.18. Suppose you’re a number theorist communicating with another
number theorist and you know for a fact that you only ever discuss integers.
You might write something like:
∀n, 2n is even
It’s understood that n ∈ Z and the statement is true. You would never write this
to some general mathematician who would answer “No, it’s false, for example
n = 1
2
.
�
We strongly recommend making it clear!
7
2.6 Revisiting Parity Etc.
Just to close this section let’s revisit our definitions related to parity, primes,
divisibility, and modular arithmetic, using these quantifiers.
Definition 2.6.1. We say that an integer x is even iff ∃k ∈ Z, x = 2k.
�
Definition 2.6.2. We say that an integer x is odd iff ∃k ∈ Z, x = 2k + 1.
�
Definition 2.6.3. Given integers a, b with a 6= 0 we say that a | b iff ∃c ∈
Z, ac = b.
�
In the next definition, Z+ denotes the set of positive integers.
Definition 2.6.4. Given an integer n ≥ 2 we say that n is prime iff ∀d ∈
Z+, (d|n)→ ((d = 1) ∨ (d = n)).
�
Definition 2.6.5. Given an integer n ≥ 2 we say that n is composite iff ∃d ∈
Z+, (d|n) ∧ (1 < d < n).
�
Definition 2.6.6. Given integers a, b,m with m ≥ 2 we say that a mod m = b
iff (0 ≤ b < m) ∧ ∃q ∈ Z, a = qm + b.
�
Definition 2.6.7. Given integers a, b,m with m ≥ 2 we say that a ≡ b mod m
iff m | (a− b) iff ∃k ∈ Z, km = a− b
�
2.7 Unbound Variables
Definition 2.7.1. When we have a variable which is not bound, we say it is
unbound.
Unbound variables are not really something we will work with, except when you
forget to bind your variables and we say “Hey, this variable is unbound!”
8
3 Negating Quantifiers
Suppose I said to you:
Every human is under six feet tall!
You would probably tell me I’m false by arguing:
There is a human who is six feet tall or taller!
What happened here? You negated my statement, but let’s look at a more
formal version of this:
I said:
∀x ∈ D,P (x)
You replied:
∃x ∈ D,∼P (x)
In essence we have:
∼
[
∀x ∈ D,P (x)
]
≡ ∃x ∈ D,∼P (x)
Notice what happened here. The general rule is as follows:
Rule: When negating a quantified statement, switch the quantifer from ∀ to ∃
or ∃ to ∀ and push the negation inside.
Note 3.0.1. Once the negation is inside it can be beneficial to do more tidying
up inside.
�
Here are some abstract examples:
Example 3.1. Here is a negation involving a conjunction inside:
∼
[
∃x, P (x) ∧Q(x)
]
≡ ∀x,∼(P (x) ∧Q(x))
≡ ∀x,∼P (x) ∨ ∼Q(x)
�
Example 3.2. Here is a negation involving an implication inside:
∼
[
∀x, P (x)→ Q(x)
]
≡ ∃x,∼(P (x)→ Q(x))
≡ ∃x, P (x) ∧ ∼Q(x)
�
Example 3.3. Here is a negation involving two quantifiers and some stuff
inside:
∼
[
∃x,∀y, P (x) ∨ (Q(x)→ ∼R(x))
]
≡ ∀x∃y,∼(P (x) ∨ (Q(x)→ ∼R(x)))
≡ ∀x∃y,∼P (x) ∧ ∼(Q(x)→ ∼R(x))
≡ ∀x∃y,∼P (x) ∧ (Q(x) ∧R(x))
9
�
Here are some more concrete ones. You can think about whether they’re true
or false but that’s not really the issue here.
Example 3.4. We have:
∼
[
∃x ∈ Z, x2 = 20
]
≡ ∀x ∈ Z,∼(x2 = 20)
≡ ∀x ∈ Z, x2 6= 20
�
Example 3.5. We have:
∼
[
∀n ∈ Z, if n is odd then n is prime
]
≡ ∃n ∈ Z,∼(if n is odd then n is prime)
≡ ∃n ∈ Z, n is odd and n is not prime
�
4 Contrapositive, Converse and Inverse Revis-
ited
Let’s revisit the contrapositive, converse and inverse once more:
• The contrapositive of P → Q is ∼Q→ ∼P .
• The converse of P → Q is Q→ P .
• The inverse of P → Q is ∼P → ∼Q
Since these are things which apply to implications, not to quantifiers per se,
when we discuss these terms the quantifiers remain unchanged. For example:
• The contrapositive of ∀x(P (x)→ Q(x)) is ∀x(∼Q→ ∼P (x)).
• The converse of ∃x(P (x)→ Q(x)) is ∃x(Q(x)→ P (x)).
• The inverse of ∀x(P (x)→ Q(x)) is ∀x(∼P (x)→ ∼Q(x))
Here are some more specific examples:
Example 4.1. The contrapositive of:
∀p ∈ {primes}∀a ∈ Z, if a | p then (a = 1 or a = p)
would be (note DeMorgan’s Law):
∀p ∈ {primes}∀a ∈ Z, If (a 6= 1 and a 6= p) then a - p
Remember from earlier that the contrapositive of a statement is equivalent to
the statement. In this case both of these are true.
10
�
Example 4.2. The converse of:
For all a, b,m ∈ Z with m ≥ 2, if a ≡ b mod m then a2 ≡ b2 mod m
would be:
For all a, b,m ∈ Z with m ≥ 2, if a2 ≡ b2 mod m then a ≡ b mod m
Remember from earlier that the converse of a statement is not equivalent to the
statement. In this case the original statement is true but the converse is false.
�
Example 4.3. The inverse of:
∀a ∈ Z, if a > 3 then a2 > 100
would be:
∀a ∈ Z, if a 6> 3 then a2 6> 100
or, better:
∀a ∈ Z, if a ≤ 3 then a2 ≤ 100
Remember from earlier that the inverse of a statement is not equivalent to the
statement. In this case the original statement is false but the converse is true.
�
5 Proofs Involving Statements with Quantifiers
5.1 Proving Existential and Disproving Universal; Coun-
terexamples
Suppose we wish to prove an existential statement, meaning one of the form:
∃x, P (x)
To prove that such a statement is true, often we can simply find a specific
example. Please note that P (x) itself might be its own fairly complex expression.
Example 5.1. Consider the statement:
There is some integer x ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9} which is a perfect square
or more formally:
∃x ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9},∃y ∈ Z, x = y2
11
To prove this statement is true, we simply identify such an integer. A proof
could simply stating that x = 4 (or x = 9) is a perfect square.
�
Example 5.2. Consider the statement
∃n ∈ Z, n is even and n is prime
To prove this statement is true, we simply identify such an integer. A proof
could simply be stating that n = 2 is even and is prime.
�
Suppose now we wish to disprove a universal statement ∀x, P (x).
Definition 5.1.1. To disprove a statement means to prove its negation.
This means we are trying to prove:
∼ [∀x, P (x)]
However this is equivalent to:
∃x,∼P (x)
This means that disproving a universal statement is the same as proving a
related existential statement.
Example 5.3. To disprove:
∀x ∈ {primes}, x is odd.
We instead prove the negation:
∼ [∀x ∈ {primes}, x is odd.]
This is equivalent to:
∃x ∈ {primes}, x is not odd.
As a proof we present the prime x = 2, which is not odd.
�
Definition 5.1.2. When we disprove a universal statement by presenting a
specific example which proves the existential negation of that universal we say
we have found a counterexample to the universal statement.
�
Example 5.4. A counterexample to:
∀x ∈ {primes}, x is odd.
12
is x = 2, since x is a prime which is not odd.
�
Example 5.5. A counterexample to:
∀a ∈ Z, a – (a + 1)
Is a = 1, since a is an integer and 1 | (1 + 1).
�
Example 5.6. A counterexample to:
∀a, b, c,m ∈ Z with m ≥ 2, (ac ≡ bc mod m)→ (a ≡ b mod m)
Is a = 1, b = 2, c = 2, m = 2, since 1 · 2 ≡ 2 · 2 mod 2 but 2 6≡ 2 mod 2.
�
5.2 Proving Universal and Disproving Existential
Suppose we wish to prove a universal statement, meaning one of the form:
∀x ∈ D,P (x)
Since we wish to prove it’s always true we cannot show it’s true for just one
specific example. The approach here will be to start with a general x in D and
show that P (x) is true. We will have a more organized way soon but for now,
a simple example:
Example 5.7. To prove:
∀x ∈ R, if x > 3 then x2 + 2x + 2 > 17
To prove this, we start with an unknown x ∈ R. We take this x and then prove:
If x > 3 then x2 + 2x + 2 > 17. To do this we observe:
x2 + 2x + 2 > (3)2 + 2(3) + 2 = 9 + 6 + 2 = 17
Then we are done.
�
Suppose now we wish to disprove an existential statement ∃x, P (x). To disprove
an existential statement means to prove its negation. This means we’re trying
to prove:
∼ [∃x, P (x)]
However this is equivalent to:
∀x,∼P (x)
This means that disproving an existential statement is equivalent to proving a
related universal statement.
13
Example 5.8. To disprove:
∃x ∈ R, x2 + 2x < −1 We instead prove the negation: ∼ [ ∃x ∈ R, x2 + 2x < −1 ] This is equivalent to: ∀x ∈ R, x2 + 2x ≥ −1 Since x2 + 2x + 1 = (x + 1)2 ≥ 0 we know x2 + 2x ≥ −1. � Example 5.9. To disprove: ∃a ∈ Z, x is even and a is odd We instead prove the negation: ∼ [∃a ∈ Z, a is even and a is odd] This is equivalent to: ∀a ∈ Z, either a is not even or a is not odd We’ll talk about how to do this later. � 6 What’s a Formal Proof? Just to be honest and open, there is no “official” definition of a formal proof nor is there a hard line between “formal” and “informal”. Rather there is a relatively large grey area and it’s best to stay on the right side of this grey area. To that note, here are some guidelines to help you know if your proofs are “formal enough”. This is not comprehensive, it’s just a list of things that can help guide you! 1. Your proof should flow when the reader reads it. This means sentences and connecting words like “therefore” and “from here we can see” and so on. 2. Equations should be contextualized, meaning there should be words to clarify their existence and the role they play in the greater context. 3. Variables should not be introduced without explanation as to why they are there. 4. Lead the reader into the process at the beginning by making sure they know where you’re starting and why. 14 5. Make sure the reader knows why you have achieved the goal. 6. It’s standard to use the third person when writing proofs. That is, “we” and “us” and so on. You don’t have to but the entire mathematical community will think you’re strange if you don’t. 7 Basic Proof Type Overview 7.1 Direct Proofs Suppose we are trying to prove an implication of the form P → Q. Definition 7.1.1. A direct proof of P → Q involves assuming P and finding a series of steps, each of which introduces new facts which follow logically from previous facts, until we obtain Q. � Direct proofs are exactly what we were doing when we proved the validity of arguments. Example 7.1. Let’s prove the statement: ∀x ∈ Z, if x is even then 3x + 7 is odd Because this is a ∀ statement we start with a general and unknown x ∈ Z. For a direct proof we assume that x is even. Since x is even, x = 2k for some integer k. Then 3x + 7 = 3(2k) + 7 = 6k + 7 = 2(3k + 2) + 1. Since we have written 3k + 7 as 2(integer) + 1 we have proven that 3k + 7 is odd. � Let’s pause for a second and reflect on the previous section regarding informality. Here is the exact same proof as above but devoid of any clarification: Example 7.2. Proof: x = 2k, 3x + 7 = 2(3k + 2) + 1, done. Notice that the following questions arise for someone new to the problem: • Q: Where did that x = 2k come from? • Q: What is k? • Q: Where did the 3x + 7 come from? • Q: In what way are we done? Answering these simple questions leads to a nice, readable proof: • Q: Where did that x = 2k come from? A: Since x is even. • Q: What is k? A: It’s an integer. 15 • Q: Where did the 3x + 7 come from? A: It’s the thing we want to prove is odd. • Q: In what way are we done? A: Well 3x + 7 now has the form of an odd number. Filling this in: Proof: Since x is even x = 2k for some integer k. Then look at 3x+ 7 and note that 3x+ 7 = 3(2k) + 7 = 6k + 7 = 2(3k + 2) + 1. Since 3k + 7 = 2(integer) + 1 we know that 3k + 7 is odd. Much nicer! � Example 7.3. Let’s prove the statement: ∀x ∈ R, if x > 5 then x2 − x− 10 > 10.
Because this is a ∀ statement we start with a general and unknown x ∈ R.
For a direct proof we assume that x > 5. Then observe that:
x2 − x− 10 = x(x− 1)− 10 > 5(5− 1)− 10 = 10
�
Example 7.4. Let’s prove the following statement. Notice that the nature of
a, b, and c is implied.
If a|b and b|c then a|c.
Because this is a ∀ statement we start with general and unknown a, b, and c.
Proof: We assume that a|b and b|c. Then ak = b and bl = c for integers k, l.
Then c = bl = (ak)l = (kl)a and since kl is an integer we have proved a|c.
�
We can often prove a direct proof by exhaustion.
Definition 7.1.2. A direct proof by exhaustion of a universal statement is a
proof where we show that the statement is true for all possible values. This only
works when there are finitely many values.
�
Example 7.5. Let’s prove the statement:
∀n ∈ 1, 2, 4, 6, n2 + 1 is prime.
Proof: Observe that 12 + 1 = 2, 22 + 1 = 5, 42 + 1 = 17, and 62 + 1 = 37 are all
prime.
�
16
7.2 Proof by Contrapositive
Suppose we are trying to prove an implication of the form P → Q. We know
that a statement is logically equivalent to its contrapositive:
P → Q ≡ ∼Q→ ∼P
We can thus instead prove ∼Q→ ∼P directly.
Definition 7.2.1. A proof by contrapositive of P → Q involves assuming ∼Q
and finding a series of steps, each of which introduces new facts which follow
logically from previous facts, until we obtain ∼P .
�
We might want to do this when assuming P gives us little to work with or when
assuming ∼Q gives us a lot to work with.
Note 7.2.1. Recall that the contrapositive of a statement wrapped in a quan-
tifer is just the contrapositive of the statement. The quantifier doesn’t change.
So the contrapositive of ∀x, (P (x)→ Q(x)) is ∀x, (∼Q(x)→ ∼P (x)).
�
Example 7.6. Let’s prove the statement:
∀a, b ∈ Z, if a – (2b) then a – b
Because this is a ∀ statement we start with general and unknown a, b ∈ Z.
If we were to approach this as a direct proof we would assume a – (2b) but this
doesn’t give us much to work with. After all, this just means that there isn’t
some k ∈ Z with ak = 2b, and what do we do with that?
For a proof by contrapositive we assume ∼(a – b), which is a | b, and we attempt
to prove ∼a – (2b), which is a | (2b). These are easier to work with.
Proof: If a | b then there is some k ∈ Z with ak = b. From here we can put
a(2k) = 2b and since we have written a(integer) = 2b we have proven that
a | (2b).
�
Example 7.7. Let’s prove the statement:
If the square of an integer is even, then the integer is even.
Because this is a ∀ statement we start with general and unknown x ∈ Z.
If we were to approach this as a direct proof we would assume that x2 is even,
meaning x2 = 2k for some integer k. But this doesn’t give us much. We can
say x = ±
√
2k but this isn’t particularly helpful.
For a proof by contradiction we assume x is not even and attempt to prove x2
is not even.
17
Proof: Assume x is odd and so x = 2k + 1 for some integer k. Then we have
x2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 which tells us that x2 is odd,
and hence not even.
�
7.3 Proof by Contradiction
Suppose we are trying to prove an implication of the form P . This might be of
the form P → Q but not necessarily.
Definition 7.3.1. A proof by contradiction of P involves assuming the negation
∼P and finding a series of steps, each of which introduces new facts which
follow logically from previous facts, until we obtain some (any) contradiction
at all. This contradiction could be two facts with disagree with one another or
something which is simply untrue.
�
Example 7.8. Let’s prove:
∀x ∈ R, x 6= x + 1
Proof: We assume the negation:
∼ [∀x ∈ R, x 6= x + 1]
This is equivalent to:
∃x ∈ R x = x + 1
Since we are assuming such an x exists, we know x = x + 1 and then 0 = 1.
Since this is impossible, we have our contradiction and our assumption is false
and so our original assertion is true.
�
Example 7.9. Let’s prove the statement:
There is no greatest integer.
Proof: We assume the negation, that there is a greatest integer. Let’s call it N .
But then notice that N + 1 is also an integer and N + 1 > N . This contradicts
the assumption that N is greatest. Thus our original assertion is true.
�
Note 7.3.1. When the implication we wish to prove is of the form P → Q then
assuming the negation ∼(P → Q) means assumign P ∧∼Q. This means we get
to assume both P and ∼Q. This is very much the best of both worlds since we
get more things to chew on in our hunt for a contradiction. This is why proofs
by contradiction are extremely common and powerful.
18
�
Example 7.10. Let’s prove that an even integer is not odd. This means we
are proving:
∀x ∈ Z, if x is even then x is not odd
Proof: We assume the negation:
∼ [∀x ∈ Z, if x is even then x is not odd]
This is equivalent to:
∃x ∈ Z, ∼ [if x is even then x is not odd]
And to:
∃x ∈ Z, x is even and x is odd
So we assume this is true. Since we are assuming such an x exists, we know
x = 2k and x = 2l + 1 for k, l ∈ Z.
But then 2k = 2l + 1 and so 2(k − l) = 1 and so k − l = 1
2
which is impossible
since k, l ∈ Z.
This is our contradiction, and therefore our hypothesis is false and so our original
assertion is true.
�
Generally we won’t write so much detail:
Example 7.11. Let’s prove the statement:
∀a ∈ Z, if a mod 6 = 3 then a mod 3 6= 2.
Proof: We assume, by way of contradiction, that there is some a ∈ Z with a
mod 6 = 3 and a mod 3 = 2.
The first tells us a = 6q1 + 3 and the second tells us a = 3q2 + 2, where q1, q2
are integers. Then we have:
6q1 + 3 = 3q2 + 2
6q1 − 3q2 = −1
3(2q1 − q2) = −1
2q1 − q2 = −
1
2
Since 2q1 − q2 is an integer, this is a contradiction and our original assertion is
true.
�
19
A Tiny Bit of Set Notation
Quantifying Variables
Introduction
Universal; For All
Existential; There Exists
Multiple Quantifiers
Informality and Implicit Quantification
Revisiting Parity Etc.
Unbound Variables
Negating Quantifiers
Contrapositive, Converse and Inverse Revisited
Proofs Involving Statements with Quantifiers
Proving Existential and Disproving Universal; Counterexamples
Proving Universal and Disproving Existential
What’s a Formal Proof?
Basic Proof Type Overview
Direct Proofs
Proof by Contrapositive
Proof by Contradiction