Class Notes
(810,970)

Canada
(494,411)

University of Waterloo
(18,179)

Mathematics
(1,874)

MATH 135
(334)

Wentang Kuo
(7)

Lecture

# MATH 135 Algebra Notes II (Sept 16 - Sept 20 ): Quantifiers/Nested Quantifiers, Methods of Proofs

Unlock Document

University of Waterloo

Mathematics

MATH 135

Wentang Kuo

Fall

Description

MATH 135: Algebra for Honours Mathematics
Notes II
Michael Brock Li
Computational Mathematics IA
September MXIII
Concordia Cum Veritate
I: Quanti▯ers/Nested Quanti▯ers
Objective: Learn the basic structure of quanti▯ers, and how to use Object,
Construct, Select Methods.
Basics
Existential Quanti▯er: There is, there are, there exists, it has, et cetera.
Universial Quanti▯er: For all, for each, for every, for any, et cetera.
The word existence is to emphasize that we are looking for a particular math-
ematical object. The word universal is to emphasize that we are looking for a
set of mathematical objects.
Example I:
There exists an x in the set T such that F(x) is false.
For every x in the set R, G(x) is false.
In general, mathematicians prefer symbols rather than writing out existence
and universal. Thus, the symbol 9 stands for "there exists." The symbol 8
stands for "for every."
Example II:
9 x 2 T;F(x)
8 x 2 R;G(x)
Important Side Note:
{A quanti▯er can be either existential or universal
{A variable can be any mathematical interpretation
{A set contains the domain of the variable
1 {An open sentence that is involved with the variable
Example I:
There exists an integer c so that n = cm
Solution:
Quanti▯er: 9
Variable: c
Domain: R
Open sentence: n = cm
Example II:
8 x 2 R; 9 y 2 R; y ▯ x
True
Proof: Let x 2 R. Choose y = x ▯ 1.
Then y = x ▯ 1 ▯ x. Thus, the statement is true.
The order of the quanti▯ers in a nested quanti▯er statement matters. Here
the nested quanti▯er statement means in a statement, we have more than one
quanti▯er.
Example III:
9 y 2 N; 8 x 2 N; y ▯ x
On the side note, N is the set of all natural numbers where
x 2 Z x > 0
Proof: Let y = 1. Then every natural number x is greater or equal to y = 1.
Thus x ▯ y = 1.
Contradiction:
To prove the statement P is true, it is the same to prove :P is false. Similarly,
to prove P is false, it is the same to prove :P is true.
Example IV:
9 y 2 R; 8 x 2 R; y ▯ x
The prove for the above statement is false. We use the method called proof
by contradiction. Assume that statement is true. However, we can choose x =
y ▯ 1 < y
2 II: Methods of Proofs
Counter-examples:
Generally, if we wish to prove that a universal quanti▯er statement A is false,
we show that its negation, which is an existential quanti▯er, is true.
Remark:
:(:A) ▯ A
:(

More
Less
Related notes for MATH 135