1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ See this very similar post $\endgroup$ – Mauro ALLEGRANZA Oct 3 '20 at 8:39
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Oct 3 '20 at 8:41
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Oct 3 '20 at 8:44
  • $\begingroup$ 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 ? $\endgroup$ – F. Zer Oct 4 '20 at 12:11
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Mauro ALLEGRANZA Oct 4 '20 at 15:23
3
$\begingroup$

$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$).
$\endgroup$
11
  • $\begingroup$ 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))". $\endgroup$ – F. Zer Oct 3 '20 at 1:57
  • $\begingroup$ 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. $\endgroup$ – lemontree Oct 3 '20 at 11:44
  • $\begingroup$ 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). $\endgroup$ – lemontree Oct 3 '20 at 11:46
  • 1
    $\begingroup$ Yes, that was a typo; fixed it. $\endgroup$ – lemontree Oct 4 '20 at 18:47
  • 1
    $\begingroup$ Yes, that's right. $\endgroup$ – lemontree Oct 4 '20 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.