Class Notes (810,970)
Canada (494,411)
Mathematics (1,874)
MATH 135 (334)

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

4 Pages
Unlock Document

University of Waterloo
MATH 135
Wentang Kuo

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

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.