Exercise 8. We can restrict the logical connectives to {, V, A}. The set of propositional vari- ables is again P = {po,P1, P2,...}, which is countably infinite. Suppose we extend

this syntax with two new connectives, denoted W and M, each taking as a single argument a countably infinite set of previously defined wff's. The resulting syntax is one version of Infinitary PL. If I is the countably infinite set {91, 92, 93,...), then WI can be informally understood as: Wr = 41 V 4₂ V 43 V..., and similarly for Mr. Keep in mind that "41 V 42 V 43 V..." is not a legal formal expression; we use Was a unary connective, applied to a single argument which must be a set, and similarly for . There are three parts in this exercise: 1. Define the syntax of Infinitary PL, preferably in an extended BNF (Backus-Naur Form). Try to be as precise as you can, paying special attention to the presence of ellipses "..." in the definition - or can you think of a formulation that avoids any mention of ellipses? 2. Define the semantics of Infinitary PL, by structural induction on the syntax in Part 1, starting from an assignment of truth values to every member of P (for the base case of the induction). 3. Show that Theorem 2 does not hold, and therefore nor does Corollary 7, for Infinitary PL. Hint: Define a countably infinite set I of wff's such that every finite To CI is satisfiable, but I is not. Further Hint: Include wff = W{-Po: P₁, P2,...} in your proposed r. Remark 9. The infinitary propositional logic (Infinitary PL) extends finitary propositional logic, which is just what is commonly called propositional logic (our PL here). The distinction between infinitary and finitary extends to other formal logics and their proof systems besides PL. You can take the phrase "finitary proof system" to qualify a system that generates new finite expressions (e.g., the sequents of PL in natural-deduction style or the wff's of propositional logic in Hilbert- or Frege-style) from previously generated ones by means of finitely many rules that require each finitely many premises or antecedents - without using any notion of infinite sequence or any notion of infinite set.9