Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Kaye's Mathematics Logic, about notation for propositional logic:

Another place where we relax notation is in the notation on the left hand side of a turnstile symbol $\vdash$. Instead of using set theory notation with $\{\ldots\}, \cup, ∅$, etc., it is traditional to list formulas and sets of formulas, separating them with commas, and regard the list as a single set of formulas, so the order of formulas in the list and any repetitions in it is ignored. This applies to both the turnstile $\vdash$ of this chapter and the turnstile that will be introduced in the next. Thus, with all the conventions in place, the previous example would be written as $a ∧ b \vdash ¬(¬ a ∨ ¬ b)$. The empty set is written as an empty list, as in $\vdash (a ∨ ¬ a)$.

  1. Does "separating them with commas" mean to represent $a ∧ b \vdash ¬(¬ a ∨ ¬ b)$ as $a, b \vdash ¬(¬ a ∨ ¬ b)$ ? Then what is the difference between $a ∧ b$ and $a, b$ ?

    I can't figure out what the paragraph is saying from the two examples.

  2. Also a propositional language doesn't have comma as a punctuation symbol, while a first order language does. Is it true?

Thanks.

share|improve this question
1  
Well, I think in this case it turns out that $\{a \land b\}$ and $\{a,b\}$ are equivalent, but I imagine the author meant that you write $a \land b \vdash ...$ instead of $\{ a \land b \} \vdash ...$? –  copper.hat Jul 23 at 18:10
    
(1) First of all, by $\{a∧b\}$ do you mean it is a set? why is the LHS a set? Isn't it a boolean term? (2) WHere is "comma"? –  Tim Jul 23 at 18:13
    
I think this was very badly explained. I agree with copper.at, the author means that instead of writing $\{\varphi _1, \ldots ,\varphi_n\}\vdash \text{Whatever}$, you can write $\varphi _1, \ldots ,\varphi_n\vdash \text{Whatever}$. –  Git Gud Jul 23 at 18:13
    
I mean a set of formulae. If the author's example was $a \lor b$ then you would write $a \lor b \vdash ...$. It just so happens that in this particular example we have $a \land b \vdash ...$ is equivalent to $a,b \vdash ...$. –  copper.hat Jul 23 at 18:14
    
@Git: (1) why is the LHS a set? I think it is a boolean term, not a set. (2)since we have $∧$, why do we need comma? –  Tim Jul 23 at 18:15

1 Answer 1

up vote 4 down vote accepted

The "official" notation is :

$\Gamma \vdash \varphi$

where :

$\Gamma = \{ φ_1,\ldots,φ_n \}$.

The "abbreviation" licenses us to write it as :

$φ_1,\ldots,φ_n \vdash φ$.

Also, when $\Gamma = \emptyset$, instead of :

$\emptyset \vdash \varphi$

we will write :

$\vdash \varphi$.

Another abbreviation is the following :

$\Gamma, \alpha \vdash \varphi$

in place of the "official" :

$\Gamma \cup \{ \alpha \} \vdash \varphi$.


Comment

Regarding the example discussed, it must be :

$\{ a∧b \} \vdash a$

abbreviated as :

$a∧b \vdash a$

and not : $a, b \vdash a$.

We have to note an important distinction: that between object language and meta-language.

In the formal system of propositional logic, assuming that the propositional letters are the $p_i$'s, we have that e.g. $p_1 \land p_2$ is a formula.

The symbol :

$\Gamma \vdash \varphi$

is not part of the formal system. It is part of the meta-language, and says that there is a derivation (i.e.a sequence of formulae of the system satisfying certain rules) of the formula $\varphi$ from the assumptions in $\Gamma$.

Thus, when we license ourselves to "abbreviate" :

$\{p \rightarrow q, q \rightarrow r \} \vdash p \rightarrow r$

as :

$p \rightarrow q, q \rightarrow r \vdash p \rightarrow r$

we are introducing an abbreviation in the metalanguage.


Added

About commas in f-o logic : yes, we need it for terms, written as :

$f_i(x_1, \ldots, x_n)$

where $f_i$ is the $i$-th function letter (in the enumeration of the alphabet) and has $n$ argument-places.

If we choose to make explicit the number of arguments, writing : $f_i^n$, we can avoid comma and parentheses, writing terms as :

$f_i^nx_1 \ldots x_n$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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