Plain propositional logic can only juggle whole sentences that are already true or false — "it is raining", "7 is prime". But almost everything worth saying in mathematics is a claim about objects: every even number is a sum of two odd numbers, some equation has no real root, no prime bigger than 2 is even. To say "every" and "some" precisely, propositions are not enough. We need predicate logic — also called first-order logic — the language that lets us talk about variables, properties, and relations, and that quietly underlies every theorem, every database query, and every type checker you will ever meet.

A predicate is a statement with a blank in it: write P(x) for "x is prime". On its own P(x) is neither true nor false — it is an open sentence, waiting for an x. Feed it a value and it snaps into a genuine proposition: P(7) is true, P(9) is false. The blank is a free variable, and the collection of things we are allowed to drop into it is the domain of discourse — the numbers, people, or shapes we have agreed to talk about. Change the domain and the same predicate can change its verdict.

The two quantifiers

A quantifier is a word that turns an open sentence into a closed claim by saying how many things in the domain make it true. There are two of them, and everything in first-order logic is built from these two symbols.

• The universal quantifier \forall ("for all"): \forall x\, P(x) reads "for every x in the domain, P(x) is true". It is a giant AND over the whole domain.
• The existential quantifier \exists ("there exists"): \exists x\, P(x) reads "there is at least one x with P(x) true". It is a giant OR over the whole domain.

Once a variable is captured by a quantifier it is bound: the whole formula \forall x\, P(x) is a finished statement with a definite truth value, and the name x is now internal plumbing — you could rename it to t without changing a thing (just as \sum_{k} a_k and \sum_{i} a_i mean the same sum). A variable that is not caught by any quantifier stays free, and a formula with a free variable is still just an open sentence. In \exists y\,(x < y) the y is bound but the x is free, so the whole thing depends on x.

Translating English into logic

The everyday words "every", "some", and "no" map onto a small handful of patterns. The trick is that \forall almost always pairs with an implication (\Rightarrow), while \exists almost always pairs with an AND (\wedge). Let the domain be all animals, with predicates D(x) ("x is a dog") and B(x) ("x barks").

• "Every dog barks": \forall x\,\bigl(D(x) \Rightarrow B(x)\bigr) — if it is a dog, then it barks. (Writing \forall x\,(D(x)\wedge B(x)) would wrongly claim everything is a barking dog.)
• "Some dog barks": \exists x\,\bigl(D(x) \wedge B(x)\bigr) — there is something that is a dog and barks.
• "No dog barks": \neg\exists x\,\bigl(D(x) \wedge B(x)\bigr), equivalently \forall x\,\bigl(D(x) \Rightarrow \neg B(x)\bigr) — the two forms say the same thing, and the equivalence is exactly a negation rule (below).

The domain matters. Over the integers, "every number has an additive inverse" is \forall x\, \exists y\,(x + y = 0) and it is true (take y = -x). Over the positive integers it is false — there is no positive y undoing x. Same formula, different universe, different answer. Predicates and quantifiers are, at bottom, a way of talking about relations and functions as sets: P(x) picks out a subset of the domain, and a two-place predicate R(x,y) is just a set of ordered pairs.

Negating a quantified statement

Pushing a "not" through a quantifier is one of the most useful moves in all of mathematics — it is how you state precisely what it means for a claim to fail. The rule is beautifully simple: a negation flips the quantifier and moves inward.

In words: "not everything has P" means "something lacks P" (a counterexample), and "nothing has P" means "everything lacks P". The \forall and \exists trade places; they never stay put.

Worked example — negate step by step. Start from "every student passed the exam", with domain the students and \mathrm{Pass}(x):

Reading the right-hand side back into English: "there is a student who did not pass". Notice the negation is not "no student passed" — that would be far too strong. To refute "everyone passed" you only need one failure.

A nested one. Negate \forall x\,\exists y\,(x + y = 0). Flip each quantifier as the \neg travels through it, and negate the core last:

"There is an x such that no y makes x+y=0" — a single element with no inverse. Each quantifier flipped exactly once; the inner equality became an inequality.

Order matters: \forall\exists versus \exists\forall

When two quantifiers of different kinds sit next to each other, swapping their order can completely change the meaning. This is the single most important — and most error-prone — idea in the whole topic. Let M(x,y) mean "y is a mother of x", over a domain of people.

• \forall x\,\exists y\,M(x,y) — "everyone has a mother". For each person we may pick a different y. True.
• \exists y\,\forall x\,M(x,y) — "there is one person who is everyone's mother". Now a single y must work for all x at once. Wildly false.

In \forall x\,\exists y the choice of y is allowed to depend on x; in \exists y\,\forall x one y must serve everybody. Reading the diagram left to right: each child in the top band has its own arrow, while the bottom band funnels every arrow into one node.

Same two quantifiers, same predicate, opposite order — and one claim is true while the other is absurd. The logician's rule of thumb: you may always weaken \exists y\,\forall x to \forall x\,\exists y, but never the other way round.

Relations: predicates with more than one blank

A predicate can have several slots. L(x, y) for "x loves y", x < y for the order relation, B(x, y, z) for "y is between x and z" — these are multi-place predicates, and each one is nothing more than a set of tuples: a relation. That is the bridge back to set theory — a two-place relation R on a domain A is a subset of A \times A, and R(x,y) is true exactly when the pair (x,y) lives in that subset.

Multi-place predicates are where quantifier order earns its keep. Over the real numbers, \forall x\,\exists y\,(y > x) ("every number has a bigger one") is true, but the swapped \exists y\,\forall x\,(y > x) ("some number beats them all") is false — there is no largest real. First-order logic is precisely the language rich enough to spot that difference.