# Quantifiers: For All and There Exists

In Phase 1 you met predicates - statements with a hole in them, like `P(x): x is even`. A
predicate isn't true or false on its own; it's waiting for an `x`. This phase covers the two
words that fill that hole all at once and turn a predicate into a real claim: **for all** and
**there exists**. Once you can read them like a sentence, a huge amount of formal writing stops
looking like hieroglyphics.

## First, what's a domain again?

Every quantified claim lives inside a **domain**: the collection of things `x` is allowed to be.
Without a domain, "for all x" means nothing - all *what*? People? Numbers? Files on disk? For
most of this phase the domain is the **natural numbers**: `0, 1, 2, 3, …`. When you read a
quantifier, whisper the domain to yourself - "for all `x`" really means "for all `x` *in this
collection*." (The [Sets, Relations & Functions](/guides/sets-relations-and-functions) guide
builds domains up properly, but "the bag of things `x` ranges over" is enough for now.)

## The universal quantifier: ∀ ("for all")

The symbol `∀` is an upside-down A (think **A** for "All"). You write:

```text
∀x P(x)
```

and you read it: **"for all x in the domain, P(x) is true."** `∀x P(x)` is a single statement -
true or false, no leftover hole - and it's true under exactly one condition:

> `∀x P(x)` is **true** only when *every single element* of the domain makes `P` true.
> If even one element fails, the whole statement is **false**.

A "for all" claim is a promise about the entire collection at once. It's a big bet:
*no exceptions, anywhere.*

Concrete example, domain = natural numbers:

```text
∀n (n + 1 > n)        "every natural number is smaller than its successor"
```

Pick any `n` - `0`, `7`, `1000000`. Adding 1 always lands you somewhere bigger. There's no number
where this breaks. So `∀n (n + 1 > n)` is **true**.

Now a false one:

```text
∀n (n is even)        "every natural number is even"
```

This bets that *nothing* is odd. But `1` is right there. One number wrecks it. So `∀n (n is even)`
is **false** - and the number that wrecks it has a name.

## The existential quantifier: ∃ ("there exists")

The symbol `∃` is a backwards E (think **E** for "Exists"). You write:

```text
∃x P(x)
```

and you read it: **"there exists an x in the domain such that P(x) is true."** This is a much
humbler claim - it promises nothing about the whole collection, only that *somewhere in here, at
least one thing works.*

> `∃x P(x)` is **true** as soon as *at least one* element makes `P` true.
> It's **false** only when *nothing at all* in the domain works.

Concrete example, domain = natural numbers:

```text
∃n (n is even)        "some natural number is even"
```

Is there even one even number? Yes - `2` works. (So do `0`, `4`, `100`.) You only needed one. So
`∃n (n is even)` is **true**.

Notice we did *not* check every number. The moment we found `2`, we were done. That "one is enough"
feeling is the whole personality of `∃`.

## Quantifier scope: how far does the claim reach?

A quantifier's **scope** is the part of the statement it controls. When you write
`∀x (P(x) → Q(x))`, the quantifier reaches across the whole parentheses. When you
nest quantifiers, the order changes what's claimed:

```mermaid
flowchart LR
    subgraph Outer[∀x outer]
        subgraph Inner[∃y inner]
            P[P x y]
        end
    end
    Outer --> Result["For every x, there is SOME y"]
```

```mermaid
flowchart LR
    subgraph Outer2[∃y outer]
        subgraph Inner2[∀x inner]
            P2[P x y]
        end
    end
    Outer2 --> Result2["There is ONE y that works for ALL x"]
```

Same letters, opposite meaning. Swapping them is not a style choice - it changes the claim.

## The asymmetry that matters most

Here is the single most useful idea in this entire guide. Read it twice.

- To **disprove** a `∀` claim, you need exactly **one counterexample** - one element where
  the predicate fails.
- To **prove** an `∃` claim, you need exactly **one witness** - one element where the
  predicate holds.

That's it. The two quantifiers are mirror images:

```text
∀x P(x)   →  one FAILING element makes it FALSE   (a counterexample)
∃x P(x)   →  one PASSING element makes it TRUE    (a witness)
```

This asymmetry is *why* the symbols are worth learning. It tells you how to argue about collections
you could never fully inspect - even infinite ones.

Think about `∀n (n is even)` over the natural numbers. You can't check infinitely many numbers. But
you don't have to. You produce `n = 1`, point at it, and say "this is odd, so the claim that *all*
numbers are even is false." Done. One counterexample beats an infinite "for all."

The same trick runs the other way. To show `∃n (n + n = 6)` is true, you don't search the whole
number line. You hand over `n = 3` and say "there's your witness." One example beats an infinite
"there exists" search.

⚠️ **Watch the direction.** One example does *not* prove a `∀`. Showing that `2` is even tells you
*nothing* about whether *all* numbers are even. And one example does not *disprove* an `∃` - finding
one odd number doesn't mean no even number exists. Examples prove `∃` and kill `∀`; they do not
prove `∀` or kill `∃`. Getting this backwards is the classic mistake.

## Why "for all" is the fragile one

A `∀` claim is *strong* - it says a lot - which is exactly why it's *fragile*. It has to be right
about everything, so one overlooked case brings it all down. "All swans are white" survives
thousands of white swans and dies the instant one black swan walks in. A `∃` claim is *weak* - it
says very little - which is exactly why it's *sturdy*: it needs one thing to go right, and that
one thing is usually easy to point at.

So when someone makes a sweeping "every… / all… / always…" statement, the experienced move is to
hunt for the one case that breaks it. And when someone says "that can never happen / no input ever
does X," they've made a `∀` in disguise (for all x, *not* X) - so again, one example settles it.
[Phase 3](03-negating-and-nesting-quantifiers.md) shows exactly how "never" becomes a hidden `∀`.

## For builders

If you write code, you use both quantifiers constantly under different names. A quantifier ranges
over a domain; a loop or a collection method ranges over a list.

- `∀x P(x)` is **`all(...)`** in Python, **`.every(...)`** in JavaScript - true only if the
  predicate holds for *every* element.
- `∃x P(x)` is **`any(...)`** in Python, **`.some(...)`** in JavaScript - true if the predicate
  holds for *at least one* element.

```text
∀n (n > 0)   ≈   all(n > 0 for n in nums)     # all() / .every()
∃n (n > 0)   ≈   any(n > 0 for n in nums)     # any()  / .some()
```

And the asymmetry shows up as a real optimization: these functions **short-circuit**.

- `all()` / `.every()` stops at the **first element that fails** - that failing element is
  your counterexample. (`all` over an empty list is `true`: there's no failure to find.)
- `any()` / `.some()` stops at the **first element that passes** - that passing element is
  your witness. (`any` over an empty list is `false`: there's nothing to witness.)

So "falsify a `∀`" and "find the first failing element" are *literally the same operation*. The
logic you learned is the control flow your language already implements.

## Recap

- **`∀x P(x)`** - "for all x, P(x)." True only when **every** element of the domain
  satisfies `P`. The upside-down A is for **A**ll.
- **`∃x P(x)`** - "there exists an x such that P(x)." True when **at least one** element
  satisfies `P`. The backwards E is for **E**xists.
- The key asymmetry: **one counterexample** makes a `∀` false; **one witness** makes an `∃`
  true. This is how you reason about whole collections - even infinite ones - without
  inspecting them all.
- Examples *prove* `∃` and *kill* `∀`. They do **not** prove `∀` or kill `∃`. Don't mix up
  the direction.
- In code: `∀` is `all()` / `.every()`, `∃` is `any()` / `.some()`, and short-circuiting is
  the counterexample/witness idea in action.

If predicates still feel fuzzy, revisit
[Predicates](01-predicates-statements-with-variables.md). For the bigger picture of what
formal claims even are, [What Logic Actually Is](/guides/what-logic-actually-is) and
[Propositional Logic](/guides/propositional-logic) sit underneath everything here. And if the
symbols still trigger a flinch, [Why Math Isn't Your Enemy](/guides/why-math-isnt-your-enemy)
is a gentler on-ramp.

## Open-ended exercise

A database query returns 10,000 rows. A teammate says: "All of them have a non-null email
address." Is this a `∀` claim or an `∃` claim? What would it take to *prove* it versus
what would it take to *disprove* it? Now suppose the teammate instead says: "At least one
row has a non-null email address." How does the burden of proof flip?

Quick check before you move on:

```quiz
[
  {
    "q": "Over the natural numbers, what does ∀n (n + 1 > n) claim?",
    "choices": [
      "Every natural number is smaller than its successor",
      "Some natural number is smaller than its successor",
      "There is a natural number with no successor",
      "Exactly one natural number satisfies n + 1 > n"
    ],
    "answer": 0,
    "explain": "∀ means 'for all.' ∀n (n + 1 > n) says that for every n in the domain, n + 1 > n holds - every number is smaller than the next."
  },
  {
    "q": "What is the minimum you need to show that ∀x P(x) is FALSE?",
    "choices": [
      "Show P fails for every element",
      "Show P holds for at least one element",
      "Find a single element where P fails (one counterexample)",
      "Check half of the domain"
    ],
    "answer": 2,
    "explain": "A 'for all' claim is fragile: one counterexample - a single element where the predicate fails - makes the whole statement false. You never need more than one."
  },
  {
    "q": "Which statement correctly describes ∃x P(x)?",
    "choices": [
      "It is true only if P holds for every element of the domain",
      "It is true if P holds for at least one element of the domain",
      "It is false if P holds for exactly one element",
      "It says nothing unless the domain is infinite"
    ],
    "answer": 1,
    "explain": "∃ means 'there exists.' ∃x P(x) is true the moment one element (a witness) satisfies P; it's false only when nothing in the domain works."
  }
]
```