Quantifiers - University Of Maryland

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

Recently Viewed Presentations

  • IUSE Reviewer Orientation Improving Undergraduate STEM Education Program

    IUSE Reviewer Orientation Improving Undergraduate STEM Education Program

    Implicit bias toward a group ("schemas") Non-conscious hypotheses/stereotypes, often about competence. Implicit institutional or geographic bias. Lack of critical mass leads to greater reliance on schemas. Fewer women and minorities in sciences.
  • Anemia an enigma in chronic kidney disease Mohammad

    Anemia an enigma in chronic kidney disease Mohammad

    hyporesponsive to ESA therapy? A. The primary cause of the hyporesponsiveness to ESA therapy is. overt iron deficiency. B. The chronic inflammation associated with his osteomyelitis has. produced a deficiency in H1Fα resulting in anemia resistant to ESA. therapy. C....
  • Theory-Based Inference

    Theory-Based Inference

    introduce statistical inference in week 1 or 2 of a 10-week quarter in a calculus-based introductory statistics course. Malone et al. (2010) discuss reordering of topics such that inference methods for one categorical variable are introduced in week 3 of...
  • Simbol Transistor

    Simbol Transistor

    Trebuchet MS MS Pゴシック Arial Comic Sans MS Wingdings Verdana Times New Roman Symbol Default Design Orbit Network Blitz Profile 1_Orbit 1_Network Blitz 1_Profile Equation JFET Introduction (FET) BJT is Current-controlled FET is Voltage-controlled Types of Field Effect Transistors (The...
  • BIOL 100L Microscope & Cells Microscope, Cells &

    BIOL 100L Microscope & Cells Microscope, Cells &

    BIOL 100L Microscope & Cells Microscope, Cells & Mitosis Lab Prelab Quiz Models: cells Prepared slides in order Crossed threads- just focus Letter "e"- draw at 4, 10, 40x mag 6 slides- draw at best mag include sperm and blood...
  • Kein Folientitel - Indico for IAEA Conferences (Indico)

    Kein Folientitel - Indico for IAEA Conferences (Indico)

    Recent ASDEX Upgrade Research in. Support of ITER and DEMO. Hartmut Zohm. forthe ASDEX Upgrade /EUROfusion MST1 Team* MPI für Plasmaphysik, Garching, Germany
  • Chapter 8 : Approximation Algorithms

    Chapter 8 : Approximation Algorithms

    Young CS 530 Ad. Algo. D&A Approximation Algorithms * The decision PS problem is NPC PARTITION PS (you should try this!) Approximation PS Algorithm // assume programs are sorted in nondecreasing order of program size, // i.e. s1 s2 …...
  • Electron Configurations & Quantum Numbers

    Electron Configurations & Quantum Numbers

    Electrons and Their Energies. Bohr model was a one dimensional model describing the structure of the atom. Atoms are 3 dimensional. Quantum numbers describe the orientation of electrons in atoms.