Class Notes (810,970)
Mathematics (1,874)
MATH 135 (334)
Lecture

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

4 Pages
197 Views

School
University of Waterloo
Department
Mathematics
Course
MATH 135
Professor
Wentang Kuo
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.