Metatheory: introduction

Before starting the unit, measure your starting point. It is a short self-assessment: it is not graded and its result is stored only in your browser.

1. Question 1From earlier unitsWhat does $\Gamma \models \varphi$ mean?

   That every valuation that satisfies all the formulas of $\Gamma$ satisfies $\varphi$.

   That there is a deduction of $\varphi$ from $\Gamma$.

   That some valuation satisfies both $\Gamma$ and $\varphi$.

   That $\varphi$ is a consequence of some formula of $\Gamma$ taken alone.

2. Question 2From earlier unitsWhich of the following assertions is equivalent to $\Gamma \models \varphi$?

   That $\Gamma \cup \{\neg\varphi\}$ is unsatisfiable.

   That $\Gamma \cup \{\varphi\}$ is satisfiable.

   That $\Gamma \cup \{\neg\varphi\}$ is satisfiable.

   That $\neg\varphi$ is unsatisfiable.

3. Question 3From earlier unitsIf a valuation $v$ gives $\alpha$ the value $1$, what value does it give $(\alpha \downarrow \beta)$?

   $0$, whatever the value of $\beta$.

   It depends on $\beta$: it has the value $1$ if $\beta$ has the value $0$.

   $1 - v(\beta)$.

   $1$, because one of the components is true.

4. Question 4From earlier unitsThe variables of $\varphi$ are $v_{2}$ and $v_{7}$. Two valuations $v$ and $w$ give the same values to $v_{2}$ and to $v_{7}$, and opposite values to all the other variables. If $v(\varphi) = 1$, what can be asserted about $w(\varphi)$?

   That $w(\varphi) = 1$.

   Nothing, because $v$ and $w$ differ on infinitely many variables.

   That $w(\varphi) = 0$, because $w$ inverts almost all the values of $v$.

   That $w(\varphi) = 1$ only if $v$ and $w$ also agree on $v_{1}, \ldots, v_{6}$.

5. Question 5From earlier unitsLet $\Gamma$ be an infinite set of formulas such that $\Gamma \vdash \varphi$. What can be asserted?

   That some finite subset of $\Gamma$ deduces $\varphi$.

   That $\varphi$ is a theorem.

   That the deduction uses all the formulas of $\Gamma$.

   Nothing without the compactness theorem, because $\Gamma$ is infinite.

6. Question 6From earlier unitsIt is known that $\Gamma \cup \{p\} \vdash \chi$ and that $\Gamma \cup \{\neg p\} \vdash \chi$. What does proof by cases allow one to conclude?

   That $\Gamma \vdash \chi$.

   Nothing, as long as it is not known whether $\Gamma$ deduces $p$ or deduces $\neg p$.

   That $\Gamma \vdash (p \leftrightarrow \chi)$.

   Only that $\Gamma \cup \{p, \neg p\} \vdash \chi$.

7. Question 7The course system is sound. What does that property assert?

   That, for every set $\Gamma$, if $\Gamma \vdash \varphi$, then $\Gamma \models \varphi$.

   That if $\Gamma \models \varphi$, then $\Gamma \vdash \varphi$.

   That there is no formula $\varphi$ with $\vdash \varphi$ and $\vdash \neg\varphi$.

   That every true formula is a theorem.

8. Question 8Let $v$ be the valuation that gives $1$ to $p$ and $0$ to $q$. What does Kalmár's lemma assert, with the variables $p$ and $q$, for the formula $(p \leftrightarrow q)$?

   That $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$.

   That $\{p, \neg q\} \vdash (p \leftrightarrow q)$.

   That $\{p, q\} \vdash \neg(p \leftrightarrow q)$.

   That $\vdash \neg(p \leftrightarrow q)$.

9. Question 9Can a deductive system be sound without being complete?

   Yes: Łukasiewicz's system, without the rule RDN, is sound and does not derive the tautology $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$.

   No: soundness and completeness can be inferred from each other.

   No: a system whose axioms are tautologies derives all tautologies.

   Yes, but only if the system is inconsistent.

10. Question 10What does the compactness theorem assert?

    That a set of formulas is satisfiable if and only if every finite subset of it is satisfiable.

    That a set of formulas is satisfiable if and only if each of its formulas is satisfiable.

    That every infinite set of formulas is satisfiable.

    That a set is satisfiable if some finite subset of it is.

11. Question 11Let $\Gamma$ be an infinite set of formulas such that $\Gamma \models \varphi$. What does compactness ensure?

    That $\Gamma_{0} \models \varphi$ for some finite subset $\Gamma_{0}$ of $\Gamma$.

    That $\varphi$ is a consequence of some formula of $\Gamma$ taken alone.

    That $\varphi$ is a consequence of every finite subset of $\Gamma$.

    That $\varphi$ is valid.

12. Question 12The first lesson proves completeness for finite sets of premises. Why does the finiteness of deduction not suffice to extend it to an infinite set $\Gamma$?

    Because finiteness speaks of $\Gamma \vdash \varphi$, and what one has is $\Gamma \models \varphi$: what is needed is that consequence, not deduction, reduce to a finite part, and that is compactness.

    It does suffice: if $\Gamma \models \varphi$, finiteness gives a finite $\Gamma_{0}$ with $\Gamma_{0} \models \varphi$.

    Because Kalmár's lemma does not hold for formulas with infinitely many variables.

    Because completeness is false for infinite sets of premises.

13. Question 13What is the resolvent of the clauses $\{p, \neg q, r\}$ and $\{q, s\}$?

    $\{p, r, s\}$.

    $\{p, \neg q, r, q, s\}$.

    $\{p, r\}$.

    They have no resolvent, because they share no literal.

14. Question 14To decide by resolution whether $\{(p \vee q), \neg p\} \models q$, which set of clauses does one try to refute?

    $\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$.

    $\{\{p, q\}, \{\neg p\}, \{q\}\}$.

    $\{\{p, q\}, \{\neg p\}\}$.

    $\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$.

15. Question 15Can the empty clause $\Box$ be derived by resolution from the set $\{\{p, q\}, \{\neg p, \neg q\}\}$?

    No: the set is satisfiable, and resolution is sound.

    Yes, in a single step, eliminating both complementary pairs at once.

    Yes, in two steps: first on $p$ and then on $q$.

    No, because neither of the two clauses is a unit clause.