Someone claims that ∃x P(x) semantically entails ∀x P(x). What is the most direct way to show this claim is FALSE?
AProve that ∀x P(x) is not a tautology using a truth table
BConstruct a structure with a domain where ∃x P(x) is true and ∀x P(x) is false
CShow that the inference violates a rule of the formal deduction system
DDemonstrate that ∃x P(x) is satisfiable but not valid
To refute a claimed entailment Γ ⊭ φ, you construct a countermodel: a specific structure M in which every formula of Γ is true and φ is false. For this case: take a domain {a, b} where P holds of a but not of b. Then ∃x P(x) is true (a witnesses it) but ∀x P(x) is false (b fails it). One countermodel suffices. Option A (truth table) applies to propositional logic, not FOL. Option C is a syntactic approach — the task asks for semantic refutation. Option D is true but doesn't directly refute the entailment claim.
Question 2 Multiple Choice
Which of the following correctly describes a valid formula in first-order logic?
AA formula that is true in some structure under some assignment
BA formula that is provable from at least one consistent set of premises
CA formula that is true in every structure under every variable assignment
DA formula whose negation is unsatisfiable in standard models only
A valid formula (also called a logical truth or tautology in FOL) is one that is true in every structure under every assignment — there is no possible counterexample. Option A describes satisfiability, not validity. Option B is weaker than validity and misdescribes it — a formula provable from some premises need not be valid. Option D is almost right (a formula is valid iff its negation is unsatisfiable), but the qualifier 'in standard models only' makes it incorrect. Validity has no model-theoretic restrictions of that kind in standard FOL semantics.
Question 3 True / False
If Γ semantically entails φ, then φ should itself be a valid formula — true in most structure.
TTrue
FFalse
Answer: False
This is a subtle but important error. Γ ⊨ φ means every model of Γ is also a model of φ — but φ might only be true in models where Γ holds. φ need not be true in all structures. For example: {∀x P(x)} ⊨ P(a) — if everything has P, then a has P. But P(a) is not valid — there are structures where a does not have P (specifically, any structure where P(a) is false, which also fails to satisfy the premise ∀x P(x)). Validity requires truth in every structure with no premises; entailment only requires truth in every structure that satisfies the premises.
Question 4 True / False
A formula φ is valid if and only if the empty set of premises semantically entails it (∅ ⊨ φ).
TTrue
FFalse
Answer: True
This biconditional captures the relationship between validity and entailment precisely. ∅ ⊨ φ means every structure satisfying all formulas in the empty set also satisfies φ. But every structure vacuously satisfies the empty set of premises (there are no conditions to fail). So ∅ ⊨ φ holds exactly when φ is true in every structure under every assignment — which is the definition of validity. This shows that validity is a special case of entailment: entailment from nothing at all.
Question 5 Short Answer
What does Gödel's Completeness Theorem establish about first-order logic, and why is this result surprising or non-trivial?
Think about your answer, then reveal below.
Model answer: Gödel's Completeness Theorem (1930) establishes that syntactic provability (Γ ⊢ φ) and semantic consequence (Γ ⊨ φ) coincide for first-order logic: Γ ⊨ φ if and only if Γ ⊢ φ. Soundness (⊢ implies ⊨) is relatively straightforward — each inference rule preserves truth. The deep direction is completeness (⊨ implies ⊢): if φ is semantically entailed by Γ, then there exists a finite formal proof of φ from Γ. This is non-trivial because semantic consequence is defined over all possible structures — an infinite, uncountable class — while a formal proof is a finite syntactic object. The theorem says these two independently defined notions leave no gaps between them in FOL.
The theorem fails for higher-order logics (second-order logic is not complete), which is why FOL occupies a privileged position in mathematical logic. In second-order logic, there are semantic consequences that cannot be captured by any finite proof system. Completeness for FOL means that proof systems are not merely convenient tools — they are provably adequate for all semantic reasoning in that logic.