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