# Understanding $PROP$ set in the book Logic and Structure (Van Dalen).

Working on the book: Dirk van Dalen. "Logic and Structure (Universitext)" (p. 18)

Definition 1.1.2 The set PROP of propositions is the smallest set X with the properties

$$\begin{array}{rl} \rm(i)&p_i\in X(i\in N),\bot\in X,\\ \rm(ii)&\varphi,\psi\in X\Rightarrow(\varphi\wedge\psi),(\varphi\vee\psi),(\varphi\to\psi),(\varphi\leftrightarrow\psi)\in X,\\ \rm(iii)&\varphi\in X\Rightarrow(\neg\varphi)\in X.\\ \end{array}$$

I would like to know:

$$p_i\in X(i\in N),\bot\in X$$

• How can I instantiate this statement when verifiyng a string of symbols belongs to PROP ?
• Is the comma an and connective ?
• What is $$N$$?
• Why is bottom symbol there ?

$$((p \land q) \to p)$$

• How can I show this statement belongs to PROP ?

P.S.: I am already aware of similar questions but they do not address my questions, I think.

• – Mauro ALLEGRANZA Oct 3 '20 at 8:39
• The def is a "recipe" to build complex formulas. Start from basic symbols: $p_i$ and $\bot$ and apply the rules (i)) and (iii) to produce new members of $\text {PROP}$: $(\lnot p_1), ( \lnot \bot), ((\lnot p_1) \land \bot)$ and so on. – Mauro ALLEGRANZA Oct 3 '20 at 8:41
• How can check if a string of symbols is in $\text {PROP}$ ? Decompose it, starting from the innermost connective (count parenthesis): $\to$. It is of the form $(\varphi \to \psi)$ ? If yes, repeat the procedure with $\varphi$ and $\psi$ until you arrive to the atoms ($p_i$ and $\bot$) or stop when you find that some rules are not satisfied. – Mauro ALLEGRANZA Oct 3 '20 at 8:44
• Thanks for your input, @Mauro Allegranza. I appreciate it. I see now this is a "recipe". However, I saw the post you linked. I am not clear on how to show a specific string of symbols does not belong to PROP. Suppose I want to show $\lnot \bot \notin PROP$, I am not sure it suffices to show I cannot construct it using rules of formation. There is something regarding a smaller set that I am not sure I grasp. Could you give some insight ? – F. Zer Oct 4 '20 at 12:11
• It's the same; according to the construction recipe a correct formula must be: either (i) a single symbol, in which case it is one of $p_i$'s or $\bot$, and this is not the case; or (ii) a complex formula, in which case it must be enclosed between a pair of parentheses: the left one "(" and the right one ")", and this is not the case. Thus, it is not an element of $\text {PROP}$. – Mauro ALLEGRANZA Oct 4 '20 at 15:23

$$p_i\in X(i\in N),\bot\in X$$

• How can I instantiate this statement when verifiyng a string of symbols belongs to PROP ?

You can instantiate any propositional symbol or $$\bot$$: $$p_1$$ is $$\in PROP$$ according to this clause, $$p_{354}$$ is $$\in PROP$$ according to this clause, $$\bot$$ is $$\in PROP$$ according to this clause.

• Is the comma an and connective ?

Yes.

• What is $$N$$?

It should be $$\mathbb{N}$$. The $$(i \in N)$$ just indicates that the $$i$$'s are running indices to number the propositional symbols.

• Why is bottom symbol there ?

Because it is an atomic formula. Unlike the other connectives, it does not take any other formulas to form a new formula, and thus belongs in the base case together with the propositional symbols.

$$((p \land q) \to p)$$

• How can I show this statement belongs to PROP ?

Strictly speaking you can't, because according to the definition introduced up to this point, there exist only indexed propositional symbols starting iwth $$p$$. But it is customary to use $$p, q, r$$ in practice; if we incoporate these into clause (i), one can prove by induction on the structure of the formula:

1. $$p \in PROP$$ (by (i), with $$p_i = p$$).
2. $$q \in PROP$$ (by (i), with $$p_i = q$$).
3. Since $$p \in PROP$$ and $$q$$ in $$PROP$$, $$(p \land q) \in PROP$$ (by (ii), with $$\phi = p$$ and $$\psi = q$$).
4. Since $$(p \land q) \in PROP$$ and $$p \in PROP$$, $$((p \land q) \to p) \in PROP$$ (by (ii), with $$\phi$$ = $$(p \land q)$$ and $$\psi = p$$).
• I can't thank you enough, @lemontree. I hope you can clarify some points. When you say: "$p \in PROP$ (by (i))", are you instantiating set $X$ to $PROP$ ? Are there implicit Universal Quantifiers in front of those conditions ? Is there some ND rule that allows one to conclude "$p \in PROP$ (by (i))". – F. Zer Oct 3 '20 at 1:57
• 1) No. I am instantiating the meta-variable $p_i$ with the concrete propositional symbol $p$. The distinction between $X$ and $PROP$ is just that $X$ can be any set in which at least all of these elements are contained, but possibly additional stuff not part of the inductive clauses, whereas $PROP$ is the restriction to only these elements specified by the clauses. Yes, this looks a bit clumsy, and often this restriction is made implicitly. 2) Yes, the $i$, $\phi$'s and $\psi$'s are implicitly universally quantified. – lemontree Oct 3 '20 at 11:44
• 3) No. The reasoning about which strings are part of the language takes place not in some formal proof system like ND, but informally in the meta langugae (mathematical English). – lemontree Oct 3 '20 at 11:46
• Yes, that was a typo; fixed it. – lemontree Oct 4 '20 at 18:47
• Yes, that's right. – lemontree Oct 4 '20 at 19:40