3
$\begingroup$

First question :

Is the following formula a valid MSO formula?

$\theta(S, r) = \exists (e_1, t_1), ... ,(e_h, t_h) \bigwedge\limits_{(e_i, e_j) \in \rho(S,r)} \mathcal{R}((e_i, t_i), (e_j, t_j))$

So my main concern here is the fact one states there exists $e_1, t_1$ etc. but then goes on to not use these in the actual formula (only using $e_i$ and $e_j$). Is this correct?

Second question :

While browsing around, I found the following :

enter image description here

(found in this post : MSO (Monadic second-order logic) Logic On Words)

My question here is, in MSO, how come one can still use 2-ary relations, such as $S(x,y)$ (as well as $\mathcal{R}((e_i, t_i), (e_j, t_j))$ from the first question), since I thought MSO is supposed to use only 1-ary relations, i.e. sets?

I think I might have found the answer myself, but I would like to verify : is this allowed because one does not quantify over these 2-ary relations?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think your thoughts are right. The explanation of "monadic" restriction of "second order" is given in the first paragraphs of wikipedia's page on MSO logic . $\endgroup$
    – Hendrik Jan
    Commented May 16, 2019 at 10:24

1 Answer 1

Reset to default
3
$\begingroup$

You are asking two questions. The first question is about logic more generally. You are wondering whether a statement of the form $$ \exists x \, \mathrm{True} $$ is valid, although $\mathrm{True}$ doesn't mention $x$. There is absolutely no requirement in the syntax of logical formulas that you use all the variables you quantify over. This similar to functions which don't depend on all of their arguments. Do you object to the function $f(x) = 1$?

As for your second question, monadic refers to the fact that you are only allowed to quantify over unary predicates. The language itself can freely contain $k$-ary predicates for any $k$. Compare this to first-order logic, in which you are not allowed to quantify over any predicates. Would that mean that first-order logic only allows for 0-ary predicates?

Improve this answer
$\endgroup$
6
  • $\begingroup$ for your answer to the first question : but why would one quantify over variables that have no impact whatsoever on the formula? Is it not recommended to remove such "useless" variables? It appears to be a nonsense sentence such as "there exists some banana such that all apples are green." $\endgroup$
    – J. Schmidt
    Commented May 16, 2019 at 17:26
  • $\begingroup$ Why would one have constant functions? $\endgroup$
    – Yuval Filmus
    Commented May 16, 2019 at 17:27
  • $\begingroup$ Constant functions don't seem to be the same thing. I see constant functions as "for all x, the function f binds x to 1", whereas the mentioned logic formula doesn't seem to bind the x to anything, hence its uselessness in the formula. Do correct me if I'm not seeing something here. $\endgroup$
    – J. Schmidt
    Commented May 16, 2019 at 17:47
  • $\begingroup$ Consider the induction scheme, $P(0) \land (\forall n P(n) \to P(n+1)) \to \forall n P(n)$. Are you suggesting it doesn't apply to constant predicates? $\endgroup$
    – Yuval Filmus
    Commented May 16, 2019 at 18:09
  • $\begingroup$ Another example: a language $L$ is r.e. if there is a computable predicate $P$ such that $x \in L$ iff $\exists y \, P(x,y)$. Must $P$ depend on $y$? What if $L$ itself is computable? $\endgroup$
    – Yuval Filmus
    Commented May 16, 2019 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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