Evanalysis
1.3Source-backedEmbedded interactionEstimated reading time: 3 min

1.3 Quantifiers and negation

Read predicates, domains, and quantifiers carefully, then negate quantified statements without losing the scope or meaning.

Note collections

MATH1090: Set theory

Rigorous course notes on logic, sets, and number construction, written in short linked sections with careful proofs and examples.

Language

ENEnglish繁Traditional Chinese简Simplified Chinese
All note collectionsSeries overview

Chapter 1

Logic

Reasoning tools for statements, connectives, and quantifiers.

1.1

1.1 Propositional logic

1.2

1.2 Truth tables and equivalence

1.3

1.3 Quantifiers and negation

Chapter 2

Sets and relations

Basic set language, functions, and relations.

2.1

2.1 Sets and set operations

2.2

2.2 Functions and relations

Chapter 3

Numbers by construction

How natural numbers, integers, and rationals are built, and where Q still falls short.

3.1

3.1 Natural numbers and Peano axioms

3.2

3.2 Induction and recursive arithmetic

3.3

3.3 Integers from equivalence classes

3.4

3.4 Rationals and well-defined operations

3.5

3.5 Gaps in Q and why sqrt(2) is not rational

Chapter 4

Order and completeness

Total order, bounds, supremum and infimum, and the completeness gap between Q and R.

4.1

4.1 Order, bounds, and completeness

Quantifiers turn open statements into propositions. That is their main job in the course: they let us talk about every allowed object, or at least one allowed object, without writing out every case separately.

Predicates and domains

Definition

Predicate

A predicate is a statement with one or more free variables. It becomes a proposition only after every free variable has been assigned a value or bound by a quantifier.

Definition

Domain

The domain is the set of allowed values for the variables.

The domain matters every time you read ∀ or ∃. The same formal string can mean different things in different domains.

For example, the statement x2=1x^2 = 1 behaves differently over the natural numbers, integers, rationals, and reals. If you do not state the domain, you do not yet have a complete statement.

Common mistake

Do not forget the domain

∀x P(x) is incomplete unless it is clear which values x may take. In practice, the domain is either stated explicitly or understood from context.

Universal and existential quantifiers

Definition

Quantifiers

∀x P(x) means that P(x) is true for every allowed value of x.

∃x P(x) means that there is at least one allowed value of x for which P(x) is true.

If you prefer words:

  • ∀ means "for all" or "for every."
  • ∃ means "there exists."

The statement is not finished until the quantifier is attached. For that reason, P(x) alone is not a proposition, but ∀x P(x) and ∃x P(x) are.

Worked example

Read a quantified statement as English

Let P(x) mean "x is divisible by 2" and let the domain be the integers.

Then ∀x P(x) means:

"Every integer is divisible by 2."

That statement is false. By contrast, ∃x P(x) means:

"There is an integer that is divisible by 2."

That statement is true, for example x=2x = 2.

Solution

What the quantifier is doing

Negating quantified statements

Theorem

Quantifier negation

The basic negation laws are:

¬∀x P(x)≡∃x ¬P(x)¬∀x\,P(x) \equiv ∃x\,¬P(x)¬∃x P(x)≡∀x ¬P(x)¬∃x\,P(x) \equiv ∀x\,¬P(x)

Read these carefully. The negation always does two things:

  1. It flips the outer quantifier.
  2. It negates the predicate inside.

That is the whole pattern.

Worked example

Negate the definition of a prime number

The worksheet defines n to be prime by saying that, for every natural number d, if d divides n, then d=1d = 1 or d=nd = n.

In symbols:

∀d∈N,  d∣n→(d=1∨d=n).∀d ∈ N,\; d \mid n \to (d = 1 \lor d = n).

Its negation is:

∃d∈N such that d∣n and d≠1 and d≠n.∃d ∈ N \text{ such that } d \mid n \text{ and } d \neq 1 \text{ and } d \neq n.

This is exactly the meaning of "n is not prime": there is a divisor other than the trivial ones.

Solution

Why the negation is right

Worked example

Negate a statement about students

Suppose Student(x) means "x is a student" and Submitted(x) means "x has submitted the form."

The statement

∃x (Student(x)∧Submitted(x))∃x\,(Student(x) \land Submitted(x))

means that at least one student has submitted the form.

Its negation is

∀x (¬Student(x)∨¬Submitted(x)).∀x\,(\neg Student(x) \lor \neg Submitted(x)).

In words: every allowed object fails at least one of the two properties.

Solution

How to read the negation

Why quantifier order matters

The order of quantifiers is part of the meaning.

∀x ∃y P(x, y) says that for each x, there is a possibly different y that works.

∃y ∀x P(x, y) says that one single y works for every x.

Those are very different statements. The first allows the choice of y to depend on x. The second does not.

Worked example

One borrower per book is not the same as one person for all books

Let Book(b) mean that b is a book, and Borrows(x, b) mean that x borrows b.

The statement

∀b (Book(b)→∃x Borrows(x,b))∀b\,(Book(b) \to ∃x\,Borrows(x, b))

means that every book is borrowed by at least one person.

The statement

∃x ∀b (Book(b)→Borrows(x,b))∃x\,∀b\,(Book(b) \to Borrows(x, b))

means that one person borrows every book.

The first statement can be true even when the second is false.

Solution

What the example teaches

Common incorrect formalizations

Common mistake

Implication is not conjunction

If the intended meaning is "for every student, if the student enrolls, then the student satisfies the prerequisite," then the correct shape is

∀x (Student(x)→(Enrolls(x)→Prereq(x)))∀x\,(Student(x) \to (Enrolls(x) \to Prereq(x)))

or, more naturally,

∀x ((Student(x)∧Enrolls(x))→Prereq(x)).∀x\,((Student(x) \land Enrolls(x)) \to Prereq(x)).

Writing Student(x)∧Enrolls(x)Student(x) \land Enrolls(x) without the implication would state a very different and much stronger claim.

Worked example

Formalize a course requirement

Say that Taken(x, m) means "student x has taken mathematics course m." Then the statement "Every student has taken at least one mathematics course" can be written as

∀x (Student(x)→∃m (MathCourse(m)∧Taken(x,m))).∀x\,(Student(x) \to ∃m\,(MathCourse(m) \land Taken(x, m))).

This is stronger and clearer than trying to compress the meaning into a single unstructured sentence.

Solution

Why the nested quantifier is necessary

Quick checks

Quick check

Write the negation of ∀x P(x) and simplify it.

Flip the quantifier and negate the predicate.

Solution

Answer

Quick check

What is the negation of ∃x (x is a student and x has submitted the form)?

Use De Morgan's law inside the predicate.

Solution

Answer

Quick check

Which statement is stronger: ∀x∃y P(x,y) or ∃y∀x P(x,y)?

Ask whether one witness must work for all x.

Solution

Answer

Quick check

Translate ∀b(Book(b)→∃xBorrows(x,b))∀b(Book(b) → ∃x Borrows(x,b)) into English.

Read the quantifiers from the outside in.

Solution

Answer

Embedded check

Use the stepper to practice moving between a quantified statement and its negation.

Read and try

Negate one quantified statement carefully

The live stepper reveals one quantifier-negation move at a time.

Example

For every real number x, x^2 >= 0.

  1. 1. Start with the outer quantifier: “for every x.”

Read this first

For the propositional version of these ideas, review 1.1 Propositional logic.

Section mastery checkpoint

Complete the questions below to run a final section checkpoint. Progress: 0%.

Skills: quantifiers, negation, logic-equivalence

Fill in the blank: The negation of "for all x, P(x)" is "there exists x such that ____".

Prerequisites

1.1

1.1 Propositional logic

Key terms in this unit

More notes in this series

Previous section

1.2 Truth tables and equivalence

Next section

2.1 Sets and set operations