Quantifiers, Domains, and Counterexamples

Propositional logic treats “Every tested unit passed” as one indivisible letter. First-order logic opens the claim. It represents objects, their properties, their relationships, and the words all and some. This lets us diagnose overgeneralization, scope shifts, and counterexamples with precision.

Domain, predicates, names, variables

A first-order translation begins with a domain: the collection of things variables may represent. If the domain is “all submitted reports,” then every x is a submitted report. If the domain is “all documents,” submission must be represented by a predicate.

Example key:

• Domain: all documents.
• S(x): x was submitted.
• C(x): x is complete.
• R(x): x was reviewed.
• a: the annual report.

A predicate such as C(x) becomes a claim when a name replaces the variable—C(a), “the annual report is complete”—or when a quantifier binds the variable.

The universal quantifier ∀ means “for every object in the domain.” The existential quantifier ∃ means “for at least one object in the domain.”

Four common claim forms

Every S is C

For every object, if it was submitted, it is complete. The conditional matters. Writing ∀x(S(x) ∧ C(x)) would claim every document in the domain was both submitted and complete.

Some S is C

At least one object is both submitted and complete. Existential statements typically use conjunction because the same witness must satisfy both predicates.

No S is C

Equivalently, ¬∃x(S(x) ∧ C(x)): there is no object that is both.

Not every S is C

Equivalently:

“Not every” means at least one exception, not “none.” This distinction prevents sweeping rebuttals.

Negate by switching the quantifier

Two rules do most of the work:

Mnemonic: push “not” through; flip ∀/∃; negate the inside.

Examples:

• Negation of “Every valve is closed”: “At least one valve is not closed.”
• Negation of “Some valve is closed”: “No valve is closed.”
• Negation of “No alert was acknowledged”: “At least one alert was acknowledged.”

This gives a proof strategy. To refute a universal, produce one valid counterexample in the domain. To establish an existential, produce one valid witness. But one positive example cannot prove a universal, and inspecting many examples without complete coverage yields at most inductive support.

Vacuous truth and existence assumptions

Suppose there are no submitted reports. Then ∀x(S(x) → C(x)) is true in classical logic: no submitted report violates the rule. This is vacuous truth. The formula does not imply that any report was submitted.

If existence matters, add it:

Policy writing often hides this issue. “All successful applicants completed training” can be true even when there were no successful applicants. A reader may hear evidence of success that the sentence does not logically provide.

Relations and order

First-order logic can represent multi-place relations:

• A(x, y): x approved y.
• W(x, y): x wrote y.

“Every report has an approver” becomes:

“There is one person who approved every report” becomes:

The quantifier order changes the claim. The first permits a different approver for each report; the second requires one universal approver. Compare “Everyone loves someone” with “Someone is loved by everyone.” Same words, different scope.

Countermodels for quantified arguments

An argument is invalid if you can describe an interpretation where all premises are true and the conclusion false.

Argument:

1. Every inspected unit passed.
2. Unit 17 passed.
3. Therefore, unit 17 was inspected.

This affirms a predicate-level consequent. Countermodel: domain contains units 17 and 18. Unit 18 was inspected and passed. Unit 17 passed but was never inspected. Premise 1 is true, premise 2 is true, conclusion false.

Draw small models. Use dots for objects and labels for predicates. Two or three objects usually suffice to expose an invalid form.

Worked translation: a compliance claim

Passage:

Every approved vendor submitted an insurance certificate. At least one vendor submitted a certificate but was not approved. No vendor lacking a tax form was approved.

Domain: all vendors.

• A(x): x was approved.
• I(x): x submitted an insurance certificate.
• T(x): x submitted a tax form.

Translations:

1. ∀x(A(x) → I(x))
2. ∃x(I(x) ∧ ¬A(x))
3. ∀x(¬T(x) → ¬A(x))

By contraposition, statement 3 is equivalent to ∀x(A(x) → T(x)): a tax form is necessary for approval. It does not state that a tax form is sufficient. Statement 2 shows insurance submission is not sufficient either. Together, the claims identify two necessary conditions without giving a complete approval rule.

“Most” is not a first-order quantifier here

Elementary first-order logic directly handles all and at least one, not statistical “most,” “usually,” or “about 60%.” Do not translate “Most users returned” as ∀x(U(x) → R(x)). That turns a probabilistic generalization into a universal.

Represent proportions with appropriate statistical language, and state the target population and time. Formal precision includes knowing when a formalism is too weak for the claim.

Practice

Domain: all devices. O(x) = x is online; E(x) = x is encrypted; M(x) = x is managed.

Translate:

1. Every managed device is encrypted.
2. Some online device is not managed.
3. No unencrypted device is managed.
4. Not every online device is encrypted.

Checks:

1. ∀x(M(x) → E(x))
2. ∃x(O(x) ∧ ¬M(x))
3. ∀x(¬E(x) → ¬M(x)), equivalent to ∀x(M(x) → E(x))
4. ∃x(O(x) ∧ ¬E(x))

Then answer: do 1 and 2 entail 4? No. The online unmanaged device in statement 2 might still be encrypted. Build that one-object witness to see why.

Rule of thumb

Universals invite counterexamples; existentials require witnesses. Always state the domain, translate “every” with a conditional, translate “some” with a conjunction, and flip the quantifier when negating. When two quantifiers occur, read them in order and ask whether the same object must work for all cases.