Quantifiers An important mathematical concept There exists The symbol (LaTeX: \exists) is read exists. Examples: There exists
The symbol (LaTeX: \exists) is read exists. Examples: Is this true? Yes No
Something else There exists The symbol (LaTeX: \exists) is read exists. Examples: Depends on the domain!
Over false Over , true! Is this true? Yes No Something
else There exists The symbol (LaTeX: \exists) is read exists. Examples: Depends on the domain! Over false
Over , true! Is this true? Yes No Something else
Thats why Epp always gives domain! There exists Examples: [
There exists Examples: [ True There exists Examples:
[ True There exists Examples: [ True False There exists
Examples: [ True False Is there a domain D where is true? Yes
No Something else There exists Examples: [ True
False Is there a domain D where is true? The complex numbers Yes
No Something else For all The symbol Examples:
( (LaTeX: \forall) is read for all. For all The symbol Examples: ( True
(LaTeX: \forall) is read for all. For all The symbol Examples: ( True ]
(LaTeX: \forall) is read for all. For all The symbol Examples: ( True ] True
(LaTeX: \forall) is read for all. For all Let D be the set of all students in this class who are over 8 feet tall. True False
Something else For all Let D be the set of all students in this class who are over 8 feet tall. True
False If disagree, need to find who missed a class Called vacuously true! Dr. Gasarchs wife calls it stupidly true! Something else
Nesting quantifiers Nesting quantifiers False Nesting quantifiers
False Nesting quantifiers
False True, Nesting quantifiers False
True, Common abbreviation: Generally: Alternating nested quantifiers Notice the differences between the following:
Alternating nested quantifiers Notice the differences between the following: True ( unbounded from above) False ( unbounded from below)
ORDER OF QUANTIFIERS MATTERS!!!!!!! Finding domains Give infinite sets D such that 1. Is true Finding domains Give infinite sets D such that 1. Is true ( select )
Finding domains Give infinite sets D such that 1. Is true ( select ) 2. Is false Finding domains Give infinite sets D such that 1. Is true ( select )
2. Is false (, counter-example is 0) Finding domains Give infinite sets D such that 1. Is true ( select ) 2. Is false (, counter-example is -1) Do the same thing for
Finding domains Give infinite sets D such that 1. Is true ( select ) 2. Is false (, counter-example is -1) Do the same thing for 1. True for
Finding domains Give infinite sets D such that 1. Is true ( select ) 2. Is false (, counter-example is -1) Do the same thing for 1. True for 2. False for
Some notation Examples: 12,-8, 0 Examples: 5, 13, 1031 We will be using those for our next examples.
Examples Lets define Statement: For all sufficiently large odd numbers, there exists a triplet of primes (not necessarily different) that sums to those numbers. True False
Something else Examples Lets define Statement: For all sufficiently large odd numbers, there exists a triplet of primes (not necessarily different) that sums to those numbers. (Vinogradovs Theorem)
Something True False else Examples Lets define Statement: For all sufficiently large odd numbers, there exists a triplet of primes (not necessarily different) that sums to those numbers.
(Vinogradovs Theorem) True False Something else Make sure you understand the order of parentheses ( (, ) ) and square brackets ([, ])!
Examples Statement: Every even integer above 2 can be expressed as the sum of two primes. True False
Something else Examples Statement: Every even integer above 2 can be expressed as the sum of two primes. (Goldbach conjecture, hasnt been proven yet) True
Expressed via quantifiers: False Something else Existential statements
Any statement of the form is called an existential statement. Proving Existential Statements true 1. Find a witness Example: works! So 5 is our witness
2. There are other techniques that dont require finding a witness, called non-constructive proofs of existence Proving Existential Statements false Goal: Prove that is false 1. If domain D finite, scan entire domain to show that for no does hold. 2. If domain D infinite,
Proving Existential Statements false Goal: Prove that is false 1. If domain D finite, scan entire domain to show that for no does hold. 2. If domain D infinite, this is the entire point of the course! Proving Universal Statements true or false
False: Similar to proving an existential statement true. The witness this is this case is known as the counterexample. True: Similar to proving an existential statement false. Proving universal statements true is pretty much all of math. Negated Quantifiers It is not the case that Alice comes to all office hours.
There is an office hour that Alice does not come to. Equiv. Not equiv. Something else
Negated Quantifiers It is not the case that Alice comes to all office hours. There is an office hour that Alice does not come to. Equiv. Not equiv.
Something else Negated Quantifiers We can therefore reach the following logical equivalences: ( ) [ ( ) ] ( )[ ( ) ]
( ) [ ( ) ] ( ) [ ( ) ] Negating nested quantifiers Observe how we can negate Negating nested quantifiers Observe how we can negate Negating nested quantifiers
Observe how we can negate Negating nested quantifiers Observe how we can negate Negating nested quantifiers Observe how we can negate Another example
Observe the statement A set is dense if between any two elements of it there exists another element of it. This statement says: D is dense. Another example Observe the statement
1. Give a D where the statement is true. 2. Give a D where the statement is false. 3.
Negate the statement. Another example Observe the statement 1. Give a D where the statement is true.
2. Give a D where the statement is false 3. Negate the statement
Answers: Another example Observe the statement 1. Give a D where the statement is true.
2. Give a D where the statement is false 3. Negate the statement Answers:
Another example Observe the statement 1. Give a D where the statement is true. 2.
Give a D where the statement is false 3. Negate the statement Answers:
Another example Observe the statement 1. Give a D where the statement is true. 2.
Give a D where the statement is false 3. Negate the statement Answers: 1. (See next slide)
Negating the statement How do we negate an implication? Negating implications Recall that Therefore, (by De Morgans law and double negation)
So the negation of an implication is a conjunction! Intuitive result: If all men are mortal, then we say If we want to negate this, to say that there exists some man that is immortal, then we say: Back to our example Back to our example
Back to our example Back to our example
