# Quantifiers - University Of Maryland 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