propositional language. don't understand the definition?

Question

I'm taking a mathematical logic class, and I don't understand this definition of the $propositional$ $language$, as given by my book:

"The propositional language $\mathscr{L}_0$ is the smallest set $L$ of finite sequences of the above symbols satisfying the following properties.

(1) For each propositional symbol $A_n$ with $n\in$ $0, 1, 2, ... $, we have

$A_n \in L$

(2) For each pair of finite sequences $s$ and $t$, if $s$ and $t$ belong to $L$, then

$(\neg s) \in L$

and

$(s \implies t) \in L$.

I tried to find other sources online, but the notation is so varied... I'd greatly appreciate some help understanding what this means.

Answer 1

I am sure $(1)$ and $(2)$ are explained clearly enough in the answers below. You also need to properly grasp the first sentence of the definition. I'm assuming you've already defined $\{A_n\}$ the set of propositional symbols.

The definition first says that all elements in $ \mathscr L_{\circ} $ are strings of symbols from $\{A_n\}$ or $ \{ \lnot, \implies , (, )\} $. So the alphabet of your language has been specified.

Next it says only finite strings can be considered. This is very important when constructing formulas. So infinite strings are not "words" in the Language of Propositions.

Finally it says this is the smallest set $L$ such that $(1)$ and $(2)$ hold. This too is very important. It says no other string containing letters from $\{A_n , \lnot, \implies , (, )\} $ is a grammatical word in $ \mathscr L_{\circ} $ unless they are necessitated to be so by conditions $(1)$ and $(2)$. That is if $\alpha \in \mathscr L_{\circ} $ then either $\alpha$ is a propositional symbol OR $\alpha $ is identical to $ (\lnot \beta) $ where $ \beta \in \mathscr L_{\circ} $ OR $\alpha$ is identical to $ \beta \implies \gamma $ where $ \beta, \gamma \in \mathscr L_{\circ} $

These definitions must be grasped properly. The phrase "smallest set" can be interpreted as either

• The intersection of all sets for which $(1)$ and $(2)$ are satisfied OR
• As the set of all words constructed from the Propositional Symbols (and them only) using the operations $\lnot$ and $\implies$.

See A Mathematical Introduction to Logic by Enderton for a proof that the two sets are actually equal. Hope this helped.

Answer 2

Well, it would be good to have some additional context for this question, but let me try to answer (what I understood from your short version):

Apparently the example is about building a language that mimics logical negation $\neg$ and implication $\Rightarrow$.

So in your language there are some symbols $A_n$ ($n=1,2,3,4,\ldots$) which are like variables and then there are two "operations" between those symbols. The first one is "negation" $\neg$, which is a unitary operator, i.e. it takes a single variable or string and is put in front of it (to negate what follows). The second is a binary operator $\Rightarrow$, which usually means that if the string to its left is true, the one to its right has to be true as well.

So this seems to be the "sense" (intention) behind the example of this language. However what the language really does is form all finite strings which correspond to logical formulas in the variables and those two operators. What you describe is just a formal way to build a set of all strings from those symbols and "connecting" operators. Not sure what you (or the book) intends to do with this later.

If you are looking for more examples of this type, try to build a language from symbols $A_n$ and operators like $\mathsf C$, $\cap$ and $\cup$ (which could be interpreted as set theoretic complement, intersection and union) or from $\neg$, $\wedge$, $\vee$ (which would correspond to negation, logical AND and logical OR) etc. Try to write down the axioms (rules) for those languages to see whether you understood what the formal concept is about.

Answer 3

Here is a slides presentation about such languages with some additional background and some examples/exercises:

http://www3.cs.stonybrook.edu/~pfodor/courses/CSE371/slides03/3slides.pdf