Metatheory and Logical Consequence

Diagnostic lens 1: Assumptions and meaning

Diagnostic lens 2: What an exact test establishes

Diagnostic lens 3: Constructing a counterexample

Soundness is a preservation property of the rules. A sound calculus cannot derive a sentence that fails in some model of its premises. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

Completeness of first-order logic links validity and derivability. It does not provide a procedure that always declares every invalid input invalid after finite time. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

A theory can be consistent but have several models. A second model may refute a proposed extra axiom while a first model supports it; model comparison helps study independence. A responsible solution states a semantic domain, separates definitions from empirical observations, and identifies the particular output that would refute the assertion. The student should carry this distinction forward to the worked cases rather than substitute confidence for a visible check.

Begin with the following problem: A rule engine returns a conclusion for a database. Determine whether that is a statement about one finite model, an instance of a sound rule, or a general completeness claim. Write the problem in ordinary language first. Identify which words introduce conjunctions, alternatives, negations, quantifiers, or claims of necessity. Then separate object-level statements from the evaluator's assumptions. State a proposed formalization and one plausible alternative. For each, ask what observation or interpretation would distinguish them. Finally, explain which parts can be checked by logic alone and which require additional factual or policy evidence. A correct formal answer must be precise enough for another student to reproduce without guessing the intended meanings.

1. Central idea and precise vocabulary

The object language contains the propositions or formulas under study; the metalanguage describes their syntax, models and derivations. Conflating levels creates circular explanations. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: Γ ⊨ φ is metalogical notation; φ is an object formula.

Worked example: “P is true in model M” is not identical to the symbol P appearing within the object language. Record the interpretation and valuation used to assess truth. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Do not use a theorem about proof systems as an extra axiom inside the object system without explicit formalization. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: Could two distinct metalanguages express equivalent descriptions of one formal calculus? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Annotate a verification report to distinguish claims and checks. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Annotate a verification report to distinguish claims and checks.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object Γ ⊨ φ is metalogical notation; φ is an object formula. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Do not use a theorem about proof systems as an extra axiom inside the object system without explicit formalization.” and the question “Could two distinct metalanguages express equivalent descriptions of one formal calculus?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

A proof system is sound when every provable consequence is semantically valid. Typically a proof proceeds by induction on the length or structure of derivations, checking each inference rule. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: Γ ⊢ φ ⇒ Γ ⊨ φ.

Worked example: For modus ponens, assume P and P→Q are both true under any valuation. By the truth table for →, Q must then be true. This establishes preservation for the rule. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Checking a few example proofs does not prove soundness of the entire rule system. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: What could happen if an unsound extra inference rule were added to an otherwise sound calculus? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Audit a rule engine against connective semantics. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Audit a rule engine against connective semantics.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object Γ ⊢ φ ⇒ Γ ⊨ φ. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Checking a few example proofs does not prove soundness of the entire rule system.” and the question “What could happen if an unsound extra inference rule were added to an otherwise sound calculus?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

Semantic completeness means every valid consequence has a derivation in a specified system. The classical first-order completeness theorem is about provability, not algorithmic runtime. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: Γ ⊨ φ ⇒ Γ ⊢ φ.

Worked example: A search for a proof may discover one when φ follows from Γ. If it does not halt quickly, that fact alone does not establish invalidity. For propositional logic, finite truth tables give a decision method. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Completeness must not be confused with categoricity, consistency or the Gödel incompleteness theorems. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: Why is a general first-order validity checker not guaranteed to terminate on every invalid formula? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Separate proof search from finite model evaluation in a logic service. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Separate proof search from finite model evaluation in a logic service.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object Γ ⊨ φ ⇒ Γ ⊢ φ. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Completeness must not be confused with categoricity, consistency or the Gödel incompleteness theorems.” and the question “Why is a general first-order validity checker not guaranteed to terminate on every invalid formula?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

A theory is consistent if it cannot derive contradiction in the intended proof system. A proposed axiom is independent when neither it nor its negation follows from the other assumptions, relative to those assumptions. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: Consistency of Γ: Γ ⊬ ⊥.

Worked example: The pair {P,¬P} is classically inconsistent. The single assumption {P} is satisfiable and therefore consistent in any sound and complete classical propositional calculus. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Failure to find a proof with limited resources is not proof of independence. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: Give two models of an independent proposition under a simple background theory. The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Test whether policy constraints conflict before deployment. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Test whether policy constraints conflict before deployment.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object Consistency of Γ: Γ ⊬ ⊥. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Failure to find a proof with limited resources is not proof of independence.” and the question “Give two models of an independent proposition under a simple background theory.”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

1. Central idea and precise vocabulary

A decision procedure returns a correct yes or no and halts for every input. Propositional validity is decidable through finite enumeration. First-order validity is recursively enumerable but undecidable in general. In this lesson, write down the syntax separately from the semantic interpretation. A notation choice should simplify comparison, not hide an extra premise. When a variable occurs more than once, keep its interpretation fixed within the test. If ordinary-language content is underspecified, state a working definition explicitly and report how a different definition could change the result. This practice matters most when a formula is later embedded in software and readers can no longer see the designer’s intention.

2. Formal object and worked walkthrough

Canonical object: 2^n assignments for n atoms.

Worked example: A propositional truth table over 10 atoms has 1024 assignments; over 30 atoms it has more than a billion. Finite does not mean computationally cheap. Start by naming the starting assumptions and the intended result. If this is an entailment claim, try to build an assignment or structure satisfying every premise while falsifying the conclusion. If this is a transformation, calculate both sides under an informative assignment before claiming equivalence, and give a general reason for all remaining cases. If this is a proof step, cite its legitimate introduction or elimination rule and keep the scope of assumptions visible. If it is an application rule, distinguish necessary from sufficient conditions. The same disciplined workflow should be usable by a reader who rejects the story but accepts the formal assumptions.

3. Analysis of the countercase

Common failure: Do not infer that a web-based finite explorer implements complete automated first-order theorem proving. Examine this failure in two deliberately separate ways. Semantically, ask whether an exact interpretation can expose the defect. Syntactically, ask whether the proposed step is a member of the permitted rule set. These answers are not always interchangeable: a specific valuation refutes an entailment, while a missing proof does not generally refute it. Do not count merely repeated numerical trials as a universal demonstration. Write a minimal countercase and then test it against each premise independently. If the attempt fails, explain which premise blocked the counterexample and whether it suggests a valid result or merely a poor choice of model.

Boundary question: What resource guarantee would be required before calling a solver a decision procedure? The answer should identify the exact condition being changed and the conclusion that may or may not survive. Consider domain restrictions, unavailable evidence, ambiguity of language, and the distinction between a pedagogical finite model and a theorem over all interpretations. Many logic mistakes are failures to track one of these four changes, even when every displayed formula looks plausible.

4. Transfer to a real reasoning workflow

Applied scenario: Evaluate a solver promise on a set of policy formulas. Draft a tiny audit trail containing a domain declaration, a glossary of symbols, the input facts, the inference or semantic test, and the final classification. State one observable that the formal tool does not calculate. For a database example, do not silently treat absence of a row as a false statement unless a closed-world convention has been adopted. For a scientific claim, distinguish the fact that a sentence was supplied as a premise from the independent evidence needed to establish it. For a system rule, show the outcome of an edge case and identify who is responsible for resolving the specification if two interpretations conflict.

5. Guided exercises with solution guidance

Exercise A — identification and translation. For the situation “Evaluate a solver promise on a set of policy formulas.”, write the assumptions as short declarative propositions or predicates. Include at least two alternative translations if the original wording is ambiguous. Solution guidance: first list the relevant people or system states and any excluded cases; next choose atomic predicates before adding connectives; finally identify what additional evidence would decide between rival translations. There may not be a unique answer until the context is fixed.

Exercise B — exact check. Analyze the displayed object 2^n assignments for n atoms. Show a complete derivation if it is a consequence, an exhaustive valuation table if it has only a few propositional atoms, or a fully specified small structure when a semantic countermodel is more appropriate. Solution guidance: state which kind of claim is being assessed first. Then justify each inference, assignment, or interpretation. A correct table row must satisfy the stipulated meanings of each connective; a correct proof must not cross a discharged-assumption boundary.

Exercise C — controlled perturbation. Consider the error “Do not infer that a web-based finite explorer implements complete automated first-order theorem proving.” and the question “What resource guarantee would be required before calling a solver a decision procedure?”. Change exactly one assumption, connective, quantifier dependency, or rule of inference. Determine whether the original conclusion still holds. Solution guidance: make the changed hypothesis visible; compute the new test rather than assuming the old verdict transfers; explain why the result is sensitive or insensitive to the change. Where the statement becomes untestable from provided information, write undetermined, not true or false by guesswork.

Challenge. A rule engine returns a conclusion for a database. Determine whether that is a statement about one finite model, an instance of a sound rule, or a general completeness claim. Develop a short technical note with an exact formal statement, one chosen method of evaluation, and a counterexample search. The note should make at least one original decision-table row or proof trace available for checking. Explain why the result would be insufficient to justify a real-world institutional or engineering decision without premise validation. Attach a paragraph comparing the method used in this unit with a method from an earlier unit, or with a possible method to be learned later.

Scoring rubric. Allocate 20 points to definitions and domain, 25 to formalization, 25 to correct derivation or model checking, 15 to counterexamples and limitations, and 15 to clarity and reproducibility. A solution that asserts validity without a general argument or a complete finite enumeration receives at most partial credit. For a claim of invalidity, one genuine countermodel with all premise evaluations shown is decisive. For an application claim, assess the formal result and the evidence for inputs separately.

Instructor follow-up. Ask each student to change one premise and predict whether the final judgment flips. Comparison of predictions with actual outputs identifies memorization without semantic understanding. Archive the original translation, the revised translation, and the reason for revision; these form a transparent record of how the claim was sharpened.