# Propositional Logic: Conditions for a sequence to be an element of $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in \mathbb{N}$ satisfying the following properties:

(1) For each propositional symbol $A_n$ with $n\in\mathbb{N}$, \begin{multline} A_n \in L. \end{multline}

(2) For each pair of finite sequences $s$ and $t$, if $s$ and $t$ belong to $L$, then \begin{multline} (\neg s) \in L \end{multline} and \begin{multline} (s \to t) \in L. \end{multline}

Show that $\phi$ is an element of $\mathcal{L_0}$ if and only if there is a finite sequence of sequences $\langle\phi_1,\dots,\phi_n\rangle$ such that $\phi_n = \phi$, and for each $i$ less than or equal to $n$ either there is an $m$ such that $\phi_i = \langle A_m \rangle$, or there is a $j$ less than $i$ such that $\phi_i = (\neg \phi_j)$ or there are $j_1$ and $j_2$ less than $i$ such that $\phi_i = (\phi_{j_1} \to \phi_{j_2})$.

I'm a little confused on what this sequence of sequences is.

Like for example, let $\phi = ((A_1 \to (\neg A_2)) \to A_3)$. Now when we talk about $\langle\phi_1,\dots,\phi_n\rangle$ where $\phi_n = ((A_1 \to (\neg A_2)) \to A_3)$, what are the $\phi_i$?

Is $\phi_{n-1} = ((A_1 \to (\neg A_2)) \to A_3$? Is $\phi_{n-2} = ((A_1 \to (\neg A_2)) \to$? At this point, formulas have not yet been defined. What are the $\phi_i$?

How can we prove that any sequence must be such a sequence of sequences to be in $\mathcal{L_0}$?

Like for example, let $\phi = ((A_1 \to (\neg A_2)) \to A_3)$. Now when we talk about $\langle\phi_1,\dots,\phi_n\rangle$ where $\phi_n = ((A_1 \to (\neg A_2)) \to A_3)$, what are the $\phi_i$?

Is $\phi_{n-1} = ((A_1 \to (\neg A_2)) \to A_3$? Is $\phi_{n-2} = ((A_1 \to (\neg A_2)) \to$? At this point, formulas have not yet been defined. What are the $\phi_i$?

One important thing to note on the statement on the RHS of the equivalence is that it is of the form 'there exists a natural number $n$ and there exists a sequence of sequences of propositional and symbols with length $n$ and other certain properties'.

So in your example you should first specify what $n$ is. There are infinite possibilities for $n$, to help you through this example I'll choose $n=6$.

Set \begin{align} &\phi _1=A_1,\\ &\phi_2=A_2,\\ &\phi _3=\neg (A_2),\\ &\phi _4=(A_1\to (\neg A_2)),\\ &\phi_5=A_3,\\ &\phi _6=((A_1 \to (\neg A_2)) \to A_3) \end{align} and consider the finite sequence $\langle \phi_1, \phi_2, \phi_3, \phi_4, \phi_5, \phi_6\rangle$.

Let's check if $\langle \phi_1, \phi_2, \phi_3, \phi_4, \phi_5, \phi_6\rangle$ satisfies what it is asked of you to prove.

So $i\in \{1,2,3,4,5,6\}$.
If $i=1$, set $m=1$ to get $\phi _1=A_1$ (by the way, I believe the $\langle \rangle$ enclosing $A_1$ in the first paragraph of this answer are not meant to be there).
If $i=2$, set $m=2$ to get $\phi _2=A_2$.
If $i=3$, set $j=2$ to get $\phi _3=(\neg \phi_2)=(\neg A_2)$.
If $i=4$, set $j_1=1$ and $j_2=3$ to get $\phi _4=(\phi _1\to \phi _3)=(A_1\to (\neg A_2))$.
If $i=5$, set $m=3$ to get $\phi _5=A_3$.
If $i=6$, set $j_1=4$ and $j_2=5$ to get $\phi=\phi _5=(\phi _4\to \phi_5)=((A_1\to (\neg A_2))\to A_3)$.

Formulas have been defined, maybe they haven't been named, but formulas are the names one gives to the elements of $\mathcal L_0$.

How can we prove that any sequence must be such a sequence of sequences to be in $\mathcal{L_0}$?

A couple of remarks.

I said there were infinite possibilities for $n$, that's because you can add superfluous $\phi _k$ as you please. You can add them and not use them, nothing wrong with that.

What the problem is asking of you is basically to prove that every element of $\mathcal L_0$ exists by being built from previously defined elements.

Edit:

I said that formulas are what one calls the elements of $\mathcal L_0$. There is a 'but'. Formulas are any finite sequences of propositional and logical symbols. The elements of $\mathcal L_0$ are often called well-formed formulas or wffs, but most of the time in logic we're interested only in wffs, so the term formula is often used to refer to wff after the audience is past the introduction to this sort of thing.

Now regarding the problem itself.

Given a formula (not necessarily a wff) $\phi$, abbreviate $\phi\in \mathcal L_0$ by $P(\phi)$ and let $Q(\phi)$ abbreviate "there exists a positive natural number $n$ and a finite sequence $s$ of elements propositional and logical symbols such that $s=\langle\phi_1,\dots,\phi_n\rangle, \phi_n=\phi$ and $\forall i\in \mathbb N\left(0<i\leq n\implies R(i,n)\right)$", where $R(i,n)$ is the predicate $$\exists m\in \mathbb N(\phi _i=A_m)\lor \exists j\in \mathbb N(j<i\land \phi_i=(\neg \phi_j))\lor \exists j_1, j_2\in \mathbb N(\phi_i=(\phi_{j_1}\to \phi_{j_2})).$$

The statement to prove is 'for all formulas $\phi$ the equivalence $P(\phi)\iff Q(\phi)$ holds'.

I'd rather reformulate this a bit. Let $\mathcal F$ be the set of formulas that satisfy $Q$. You want to prove that $\mathcal L_0=\mathcal F$

$\boxed{\subseteq}$

For this inclusion, prove that $\mathcal F$ satisfies (1) and (2). Since $\mathcal L_0$ is the smallest set of formulas that does this, the inclusion follows.

$\boxed{\supseteq}$

Prove by complete induction on $m$ the following statement $\forall m\in \mathbb N\forall \phi\in \mathcal F\left(\langle \phi_1, \ldots ,\phi_m\rangle\text{ 'generates' }\phi \implies \phi\in \mathcal L_0\right)$, (I suppose you can guess that I mean with 'generating' here).

• I was basically asking how one would approach the proof in generality, besides my example, meaning the approach of: "Show that $\phi$ is an element of $\mathcal{L_0}$ if and only if there is a finite sequence of sequences $\langle\phi_1,\dots,\phi_n\rangle$ such that $\phi_n = \phi$, and for each $i$ less than or equal to $n$ either there is an $m$ such that $\phi_i = \langle A_m \rangle$, or there is a $j$ less than $i$ such that $\phi_i = (\neg \phi_j)$ or there are $j_1$ and $j_2$ less than $i$ such that $\phi_i = (\phi_{j_1} \to \phi_{j_2})$." – Kevin Carroll Oct 11 '14 at 1:20
• @KevinCarroll Oh, you were asking how to prove the problem, OK. I'm off to bed now. Maybe you can handle it now that I've broken down the example. Let me know 'tomorrow' if you still need help. – Git Gud Oct 11 '14 at 1:22
• Thank you, I'll try to prove in the next day. I'll post my answer when I'm done. That last sentence you wrote in your answer is insightful. I get kind of bogged down by notation sometimes. – Kevin Carroll Oct 11 '14 at 1:24
• @KevinCarroll No problem. Let me ask you something, though. Did you accept this answer of mine? I ask because on my my profile's summary it shows the answer was accepted. However in my reputation tab the acceptance doesn't come up. Furthermore,on my screen I don't see a $\color{green}{\large \checkmark}$ by my answer, so there seems to be a bug – Git Gud Oct 11 '14 at 1:28
• I'm not asking you to accept my answer. Just want to understand what's going on. – Git Gud Oct 11 '14 at 1:28