I'm learning about monadic second order logic and I have this problem to solve. I've been trying to figure it out for a while now, but I'm finding it very difficult to discern what the question is even asking, let alone how to find the answer. Any help at all would be appreciated.

Here's the question:

Give an MSO{Z}-formula ψ(x, y) with first-order variables x, y and no second-order quantifiers such that x < y is equivalent to (∃Z)ψ(x, y) (treating Z as a second-order variable).

EDIT - If it helps, the previous questions had us working with the language {a, b} and the strings a*b.

  • $\begingroup$ What language / signature can the formula use? Otherwise, the naive answer is to let $\psi$ be "$x < y$". $\endgroup$ Commented Nov 29, 2015 at 23:29
  • $\begingroup$ @CarlMummert Sorry, edited my post. This is all the information I have. $\endgroup$
    – EmmetOT
    Commented Nov 29, 2015 at 23:31
  • $\begingroup$ It might be easier to figure out with more context, or a source for the question. I suppose this is about logic on words - is that right? It seems odd to ask about $x < y$ in that case, though. $\endgroup$ Commented Nov 29, 2015 at 23:42
  • $\begingroup$ @Carl Unfortunately the lack of context is the source of my problem! I can say that x and y refer to the positions of symbols. Here are the prior 2 questions: 1. List the MSO{a,b}-models corresponding to the strings in a∗b. 2. Give an MSO{a,b}-sentence whose models are exactly those in question 1. $\endgroup$
    – EmmetOT
    Commented Nov 29, 2015 at 23:49
  • 1
    $\begingroup$ @Mauro ALLEGRANZA: if there are no second-order quantifiers, doesn't that guarantee $\psi$ is monadic? Perhaps this is another difference of definition. $\endgroup$ Commented Nov 30, 2015 at 12:34

1 Answer 1


Long Comment (to be beneficial for someone clever than me)

From : Leonid Libkin, Elements of Finite Model Theory , page 6 :

we turn our attention to strings over a finite alphabet, say $Σ = \{ a, b \}$. We want to represent a string as a structure, much like a graph. Given a string $s = s_1 s_2 \ldots s_n$, we create a structure $M_s$ as follows: the universe is $\{ 1,\ldots, n \}$ (corresponding to positions in the string), we have one binary relation $<$ whose meaning of course is the usual order on the natural numbers, and two unary relations $A$ and $B$. Then $A(i)$ is true if $s_i = a$, and $B(i)$ is true if $s_i = b$. For example, $M_{abba}$ has universe $\{ 1, 2, 3, 4 \}$, with $A$ interpreted as $\{ 1, 4 \}$ and B as $\{ 2, 3 \}$.

Let us look at the following second-order sentence in which quantifiers range over sets of positions in a string:

$$\Phi \equiv ∃X \ ∃Y \ \big ( ∀x (X(x) ↔ ¬Y (x))$$

$$∧ \ ∀x \ ∀y \ (X(x) ∧ Y(y) → x < y)$$

$$∧ \ ∀x \ (X(x) → A(x) ∧ Y(x) → B(x)) \big ).$$

When is $M_s$ a model of $\Phi$? This happens iff there exists two sets of positions, $X$ and $Y$, such that $X$ and $Y$ form a partition of the universe (this is what the first conjunct says), that all positions in $X$ precede the positions in $Y$ (that is what the second conjunct says), and that for each position $i$ in $X$, the $i$th symbol of $s$ is $a$, for each position $j$ in $Y$, the $j$th symbol is $b$ (this is stated in the third conjunct). That is, the string starts with some $a$’s, and then switches to all $b$’s.

Using the language of regular expressions, we can say that

$$M_s \vDash \Phi \ \text{iff} \ s \in a^∗b^∗.$$

Comment on comment

From your comments above, we can assume that the alphabet is $Σ = \{ a, b \}$; we can assume that the (monadic) predicate variable $Z$ is the variable to be quantified (as $X$ and $Y$ above).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .