16112 LABEL:LastPageJan. 02, 2019Feb. 11, 2020 checkmark lipicscheckmark

# Undecidability of a weak version of mso+U

Mikołaj Bojańczyk  University of Warsaw, Poland<EMAIL_ADDRESS>,  Laure
Daviaud  City, University of London, United Kingdom<EMAIL_ADDRESS>,  Bruno Guillon  LIMOS, Université Clermont Auvergne, Aubière, France
<EMAIL_ADDRESS>,  Vincent Penelle  University of Bordeaux, CNRS,
Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France
<EMAIL_ADDRESS>and  A. V. Sreejith  IIT Goa, India
<EMAIL_ADDRESS>
###### Abstract.

We prove the undecidability of mso on $\omega$-words extended with the second-
order predicate $\texttt{U}_{1}$$\left(X\right)$ which says that the distance
between consecutive positions in a set $X\subseteq\mathbb{N}$ is unbounded.
This is achieved by showing that adding $\texttt{U}_{1}$ to mso gives a logic
with the same expressive power as mso+U, a logic on $\omega$-words with
undecidable satisfiability. As a corollary, we prove that mso on
$\omega$-words becomes undecidable if allowing to quantify over sets of
positions that are ultimately periodic, _i.e._ , sets $X$ such that for some
positive integer $p$, ultimately either both or none of positions $x$ and
$x+p$ belong to $X$.

###### Key words and phrases:

MSO logic, undecidability

##  1\. Introduction

This paper is about monadic second-order logic (mso) on $\omega$-words.
Büchi’s famous theorem says that given an mso sentence describing a set of
$\omega$-words over some alphabet, one can decide if the sentence is true in
at least one $\omega$-word [8]. Büchi’s theorem along with its proof using
automata techniques have been the inspiration for a large number of
decidability results for variants of mso, including Rabin’s theorem on the
decidability of mso on infinite trees [12].

By now it is quite well understood that mso is a maximal decidable logic over
finite words. One formalisation of this can be found in [10] (Theorem 9),
which shows that the class of regular languages is the maximal class which:
(a) has decidable satisfiability; and (b) is closed under Boolean operations
and images under rational relations. The general idea behind the result in
[10] is that a non-regular language has a Myhill-Nerode equivalence relation
of infinite index, and this together with closure under Boolean operations and
images under rational relations can be used to generate counters, Turing
machines, and then arbitrary languages in the arithmetic hierarchy. However,
for languages of infinite words, the situation is different as logic over
omega-words can talk about asymptotic properties, and getting a counter from
asymptotic properties can be much harder. One of the themes developed in the
wake of Büchi’s result is the question: what can be added to mso on
$\omega$-words so that the logic remains decidable? One direction, studied
already in the sixties, has been to extend the logic with predicates such as
_“position $x$ is a square number”_ or _“position $x$ is a prime number”_. See
[2, 9] and the references therein for a discussion on this line of research.
Another direction, which is the one taken in this paper, is to study
quantifiers which bind set variables. These new quantifiers may for instance
talk about the number of sets satisfying a formula, hence being midway between
the universal and the existential quantifiers, like the quantifier _“there
exists uncountably many sets”_ [1] (which _a posteriori_ does not extend the
expressivity of mso on finitely branching trees). Another way is to consider
quantifiers that talk about the asymptotic behaviors of infinite sets. This
was already the direction followed in [3], where the authors define
_Asymptotic mso_, a logic which talks about the asymptotic behaviors of
sequences of integers in a topological flavour. Another example is _the
quantifier U_ which was introduced in [5] and that says that some formula
$\varphi\left(X\right)$ holds for arbitrarily large finite set $X$:

$\texttt{U}X\varphi\left(X\right):\text{``for all $k\in\mathbb{N}$,
$\varphi\left(X\right)$ is true for some finite set $X$ of size at least
$k$''}\text{.}$

However, in [7] it was shown that mso+U, namely mso extended with the
quantifier U, has undecidable satisfiability; see [4] for a discussion on this
logic.

In this work, we study a, _a priori_ , weaker version of mso+U, the logic
mso+$\texttt{U}_{1}$, namely mso extended with _the second-order predicate
$\texttt{U}_{1}$_ defined by:

$\text{$\texttt{U}_{1}$$\left(X\right)$}:\text{``for all $k\in\mathbb{N}$,
there exist two consecutive positions of $X$ at distance at least
$k$''}\text{.}$

######  Example .

  * •

The set $X=\\{10n\mid n\in\mathbb{N}\\}$ does not satisfy $\texttt{U}_{1}$, as
for every $n$, $10(n+1)-10n=10$, so there are no two consecutive positions at
distance at least $11$.

  * •

The set $X=\\{2^{n}\mid n\in\mathbb{N}\\}$ does satisfy $\texttt{U}_{1}$, as
for every $k$, $2^{k+1}-2^{k}>k$, and $2^{k+1}$ and $2^{k}$ are consecutive in
$X$.

  * •

The set $X=\\{10m+n\mid\text{n is the }m^{\text{th}}\text{ digit of }\pi\\}$
does not satisfy $\texttt{U}_{1}$, the difference between two consecutive
elements being at most $19$, as there is always an element between $10m$ and
$10m+9$.

######  Example  ([6]).

Consider the language of $\omega$-words of the form
$a^{n_{1}}ba^{n_{2}}b\cdots$ such that $\left\\{n_{1},n_{2},\ldots\right\\}$
is unbounded. This language can be defined in mso+U by a formula saying that
there are factors of consecutive $a$’s of arbitrarily large size. It can also
be defined in mso+$\texttt{U}_{1}$ saying that the set of the positions
labeled by $b$ satisfies the predicate $\texttt{U}_{1}$.

It is easy to see that the predicate $\texttt{U}_{1}$ can be defined in the
logic mso+U: a set $X$ satisfies $\texttt{U}_{1}$$\left(X\right)$ if and only
if there exist intervals (finite connected sets of positions) of arbitrarily
large size which are disjoint with $X$. Therefore, the logic
mso+$\texttt{U}_{1}$ can be seen as a fragment of mso+U. Is this fragment
proper? The main contribution of this paper is showing that actually the two
logics are the same:

######  Theorem .

The logics mso+U and mso+$\texttt{U}_{1}$ define the same languages of
$\omega$-words, and translations both ways are effective.

We believe that mso+$\texttt{U}_{1}$ can be reduced to many extensions of mso,
in a simpler way than reducing mso+U.

As an example, we consider a quantifier which talks about ultimately periodic
sets. A set of positions $X\subseteq\mathbb{N}$ is called _ultimately
periodic_ if there is some period $p\in\mathbb{N}$ such that for sufficiently
large positions $x\in\mathbb{N}$, either both or none of $x$ and $x+p$ belong
to $X$. For example, the set $\\{10n\mid n\in\mathbb{N}\\}$ is periodic (with
period 10), but the set $\\{10m+n\mid\text{n is the }m^{\text{th}}\text{ digit
of }\pi\\}$ is not periodic. We consider the logic mso+P, _i.e._ , mso
augmented with _the quantifier P_ that ranges over ultimately periodic sets:

$\texttt{P}X\varphi\left(X\right):\text{``the formula $\varphi\left(X\right)$
is true for all ultimately periodic sets $X$''}.$

Though quantifier P extends the expressivity of mso, it is _a priori_ not
clear whether it has decidable or undecidable satisfiability. However, using
Theorem 1, we obtain the following result, which answers an open question
raised in [6].

######  Theorem .

Satisfiability over $\omega$-words is undecidable for mso+P.

Another example is the logic mso +probability as defined in [11]. This line of
thought is not developed in the present article, but we can make the following
reasoning. A set X satisfies $\texttt{U}_{1}(X)$ if and only if there exists
an infinite set $Y$ of blocks in $X$ with the following property: there is
nonzero probability of choosing a subset $Z\subseteq\mathbb{N}$ such that in
every block from $Y$, there is at least one element of $Z$. Therefore, mso
+probability is more expressive than
$\textsc{mso}{}{\text{+}\texttt{U}_{1}{}}$.

### Outline of the paper.

The rest of the paper is mainly devoted to the proof of Theorem 1. In Section
2 we introduce an intermediate logic mso+$\texttt{U}_{2}$. We first prove that
mso+U and mso+$\texttt{U}_{2}$ are effectively equivalent (Section 2.1, Lemma
2.1). Then, we prove that mso+$\texttt{U}_{2}$ and mso+$\texttt{U}_{1}$ are
also effectively equivalent (Section 2.2, Lemma 2.2), assuming a certain
property, namely Lemma 2.2. The proof of this latter lemma is the subject of
Section 3. Finally, in Section 4, we discuss the expressive power of mso+P
with respect to mso+U. We prove Theorem 1 and we show that the property
“ultimately periodic” can be expressed in mso+U if allowing a certain
encoding.

##  2\. How MSO+$\texttt{U}_{1}$ talks about vector sequences

In this section, we introduce a new predicate on pairs of sets of positions
$\texttt{U}_{2}$$\left(R,I\right)$ and consider the logic mso extended with
this predicate: mso+$\texttt{U}_{2}$. We first prove in Section 2.1, that
mso+U has the same expressive power as mso+$\texttt{U}_{2}$. Then, we show in
Section 2.2, that mso+$\texttt{U}_{2}$ is itself as expressive as
mso+$\texttt{U}_{1}$, assuming a certain property, namely Lemma 2.2. The proof
of this lemma is given in Section 3.

###  2.1. From quantifier U to predicate $\texttt{U}_{2}$

We say that a sequence of natural numbers is _unbounded_ if arbitrarily large
numbers occur in it. For two disjoint sets of positions
$R,I\subseteq\mathbb{N}$ with $R$ infinite, we define a sequence of numbers as
in Figure 1: the $i$-th element of this sequence is the number of elements
from $I$ between the $i$-th and the $(i+1)$-th elements from $R$. In
particular, elements of $I$ in positions smaller than all the positions from
$R$ are not relevant.

Figure 1. Two sets of positions $R,I\subseteq\mathbb{N}$ and the sequence in
$\mathbb{N}^{\omega}$ that they define. The sequence is only defined when $R$
and $I$ are disjoint, and $R$ is infinite.

We now define the binary predicate $\texttt{U}_{2}$:

$\texttt{U}_{2}\left(R,I\right):\text{ ``the sequence of numbers encoded by
$R,I$ is defined and unbounded''}.$

The difference between the predicate $\texttt{U}_{1}$, which has one free set
variable, and the predicate $\texttt{U}_{2}$, which has two free set
variables, is that the latter is able to ignore some positions. It is
illustrated by the following example, which can be easily defined in
mso+$\texttt{U}_{2}$.

######  Example .

Let $L$ be the union of the languages of $\omega$-words of the form
$(ac^{*})^{n_{1}}b(ac^{*})^{n_{2}}b\cdots$ where
$\left\\{n_{1},n_{2},\ldots\right\\}$ is unbounded. It can be defined in
mso+$\texttt{U}_{2}$ in the following way: an $\omega$-word belongs to $L$ if
and only if it belongs to $\big{(}{(ac^{*})}^{*}b\big{)}^{\omega}$ and the
sequence of numbers encoded by $R=\left\\{\text{set of positions labeled by
$b$}\right\\}$ and $I=\left\\{\text{set of positions labeled by $a$}\right\\}$
is unbounded. The language also admits a simple definition in mso+U: there
exist arbitrarily large finite sets of positions labeled by $a$ such that no
two positions from the set are separated by a $b$. It is however not
straightforward to define it in the logic mso+$\texttt{U}_{1}$, since in every
$\omega$-word, the distance between two successive $b$’s separated by at least
one $a$ can be increased by adding occurrences of $c$’s, without changing the
membership of the word to the language.

The following lemma follows essentially from the same argument as in [6, Lemma
5.5].

######  Lemma .

The logics mso+U and mso+$\texttt{U}_{2}$ define the same languages of
$\omega$-words, and translations both ways are effective.

###### Proof.

The predicate $\texttt{U}_{2}$ is easily seen to be expressible in mso+U: a
sequence of numbers encoded by $R$ and $I$ is unbounded if the subsets of
elements of $I$ between two consecutive elements of $R$ are of arbitrarily
large size, which is expressible in mso+U. For the converse implication, we
use the following observation. A formula $\texttt{U}X\varphi\left(X\right)$ is
true if and only if the following condition holds:

$(\star)$:

There exist two sets $R,I\subseteq\mathbb{N}$ which satisfy
$\texttt{U}_{2}$$\left(R,I\right)$ such that for every two consecutive
positions $r,s\in R$, there exists some finite $X$ satisfying
$\varphi\left(X\right)$ which contains all positions of $I$ between $r$ and
$s$. Here is a picture of property $(\star)$:  ‣ 2.1:

Condition $(\star)$:  ‣ 2.1 is clearly expressible in mso with the predicate
$\texttt{U}_{2}$. Hence the lemma will follow once we prove the equivalence:
$\texttt{U}X\varphi(X)$ if and only if $(\star)$:  ‣ 2.1. The right-to-left
implication is easy to see. For the converse implication, we do the following
construction. We define a sequence of positions $0=x_{0}<x_{1}<\ldots$ as
follows by induction. Define $x_{0}$ to be the first position, _i.e._ , the
number $0$. Suppose that $x_{n}$ has already been defined. By the assumption
$\texttt{U}X\varphi\left(X\right)$, there exists a set $X_{n+1}$ which
satisfies $\varphi$ and which contains at least $n$ positions after $x_{n}$.
Define $x_{n+1}$ to be the last position of $X_{n+1}$. This process is
illustrated in the following picture:

Define $R$ to be all the positions $x_{0},x_{1},\ldots$ in the sequence thus
obtained, and define $I$ to be the set of positions $x$ such that
$x_{n}<x<x_{n+1}$ and $x\in X_{n+1}$ holds for some $n$. By construction, the
sets $I$ and $R$ thus obtained will satisfy $\texttt{U}_{2}$. ∎

###  2.2. From predicate $\texttt{U}_{2}$ to predicate $\texttt{U}_{1}$

Lemma 2.1 above states that mso+U and mso+$\texttt{U}_{2}$ have the same
expressive power, thus giving a first step towards the proof of Theorem 1. The
second step, which is the key point of our result, is the following lemma,
which states that mso+$\texttt{U}_{2}$ is as expressive as
mso+$\texttt{U}_{1}$.

######  Lemma .

The logics mso+$\texttt{U}_{2}$ and mso+$\texttt{U}_{1}$ define the same
languages of $\omega$-words, and translations both ways are effective.

Note that one direction is straightforward, since
$\texttt{U}_{1}$$\left(X\right)$ holds if and only if
$\texttt{U}_{2}$$\left(X,\mathbb{N}\setminus X\right)$ holds. Hence, it
remains to show that the predicate $\texttt{U}_{2}$ can be defined by a
formula of the logic mso+$\texttt{U}_{1}$ with two free set variables.

In our proof, we use terminology and techniques about sequences of vectors of
natural numbers that were used in the undecidability proof for mso+U [7]. A
_vector sequence_ is defined to be an element of
$\left(\mathbb{N}^{*}\right)^{\omega}$, _i.e._ , a sequence of possibly empty
tuples of natural numbers. For a vector sequence
$\mathbf{f}\in\left(\mathbb{N}^{*}\right)^{\omega}$, we define its _dimension_
, denoted by $\texttt{dim}\left(\mathbf{f}\right)\in\mathbb{N}^{\omega}$, as
being the number sequence of the dimensions of the vectors: the $i$-th element
in $\texttt{dim}\left(\mathbf{f}\right)$ is _the dimension of the $i$-th
vector_ in $\mathbf{f}$, _i.e._ , the number of coordinates in the $i$-th
tuple in $\mathbf{f}$. We say that a vector sequence $\mathbf{f}$ _tends
towards infinity_ , denoted by $\mathbf{f}\rightarrow\infty$, if every natural
number appears in finitely many vectors from $\mathbf{f}$.

Recall Figure 1, which showed how to encode a number sequence using two sets
of positions $R,I\subseteq\mathbb{N}$. We now show that the same two sets of
positions can be used to define a vector sequence. As it was the case in
Figure 1, we assume that $R$ is infinite and disjoint from $I$. Under these
assumptions, we write
$\mathbf{f}_{R,I}\in\left(\mathbb{N}^{*}\right)^{\omega}$ for the vector
sequence defined according to the description from Figure 2, _i.e._ , the
sequence of vectors whose coordinates are the lengths of intervals in $I$
between two consecutive elements of $R$. Remark that $0$ is not encoded and
thus that $\mathbf{f}_{R,I}$ contains possibly empty vectors with only
positive coordinates. As for Figure 1, the positions of $I$ smaller than all
the positions of $R$ are not relevant.

Figure 2. Two sets of positions $I,R\subseteq\mathbb{N}$ and the vector
sequence that they encode. This vector sequence is defined only when $I$ and
$R$ are disjoint and $R$ is infinite.

The following lemma states that the unboundedness of the dimensions of a
vector sequence can be expressed in mso+$\texttt{U}_{1}$. Its proof will be
the subject of Section 3.

######  Lemma .

There is a formula $\varphi\left(R,I\right)$ in mso+$\texttt{U}_{1}$ which is
true if and only if the vector sequence $\mathbf{f}_{R,I}$ is defined and
satisfies $\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded.

###### Proof of Lemma 2.2 assuming Lemma 2.2.

As the predicate $\texttt{U}_{1}$ is easily definable in mso+$\texttt{U}_{2}$
($\texttt{U}_{1}$$\left(X\right)$ holds if and only if
$\texttt{U}_{2}$$\left(X,X\setminus\mathbb{N}\right)$ holds), it remains to
prove the converse, _i.e._ , to exhibit a formula $\varphi\left(X,Y\right)$ of
mso+$\texttt{U}_{1}$ which holds if and only if
$\texttt{U}_{2}$$\left(X,Y\right)$ holds.

Since $\texttt{U}_{2}$$\left(X,Y\right)$ holds if and only if
$\texttt{U}_{2}$$\left(X,Y\setminus X\right)$ holds and because
$\texttt{U}_{2}$$\left(X,Y\right)$ implies that $X$ is infinite, it is
sufficient to write a formula $\varphi\left(R,I\right)$ which holds if and
only if $\texttt{U}_{2}$$\left(R,I\right)$ holds, assuming $R$ and $I$ are
disjoint and $R$ is infinite. We fix such $R$ and $I$, which hence define a
vector sequence $\mathbf{f}_{R,I}$ according to the encoding of Figure 2.
Furthermore, $\texttt{U}_{2}$$\left(R,I\right)$ holds if and only if summing
all coordinates of each vector from the sequence yields a number sequence
which is unbounded. We show that we can construct a $J\subseteq I$ such that
$\texttt{U}_{2}$$\left(R,I\right)$ holds if and only if the dimension of
$\mathbf{f}_{R,J}$ is unbounded.

For every non negative integer $x$, if $2x$ belongs to $I$ as well as either
$2x+1$ or $2x-1$, then we remove $2x$ from $I$. Let $J$ denote the thus
obtained set. As at least one position from $I$ over two is kept in $J$, we
have that $\texttt{U}_{2}$$\left(R,I\right)$ holds if and only if
$\texttt{U}_{2}$$\left(R,J\right)$ holds. Furthermore, $J$ has the property
that each of its point is isolated whence the sum of the coordinates of a
vector from $\mathbf{f}_{R,J}$ is equal to its dimension. Therefore,
$\texttt{U}_{2}$$\left(R,J\right)$ holds if and only if the dimension of the
vector sequence $\mathbf{f}_{R,J}$ is unbounded. Moreover, $J$ is definable in
mso in the sense that there is a mso-formula with two free set variables $I$
and $J$ which holds if and only if $J$ is obtained from $I$ by the process
given above.

We conclude the proof of Lemma 2.2 by applying Lemma 2.2. ∎

##  3\. Expressing unboundedness of dimensions

This section is devoted to proving Lemma 2.2. Our proof has two steps. In
Section 3.1, we show that in order to prove Lemma 2.2, it suffices to show the
following lemma.

######  Lemma .

There is a formula $\varphi\left(R,I\right)$ in mso+$\texttt{U}_{1}$ which is
true if and only if the vector sequence $\mathbf{f}_{R,I}$ is defined and
satisfies $\mathbf{f}_{R,I}\rightarrow\infty$ and
$\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded.

Lemma 3 itself will be proved in Section 3.2.

###  3.1. From Lemma 3 to Lemma 2.2

Recall that the vector sequence $\mathbf{f}_{R,I}$ is defined if and only if
$R$ is infinite and disjoint from a set $I$, which is clearly expressible in
mso. So from now on, we will always consider vector sequences
$\mathbf{f}_{R,I}$ which are defined.

Given a vector sequence, a _sub-sequence_ is an infinite vector sequence
obtained by dropping some of the vectors, like this:

An _extraction_ is obtained by removing some of the coordinates in some of the
vectors, but keeping at least one coordinate from each vector, like this:

In particular a vector sequence containing at least one empty vector has no
extraction. An extraction is called _interval-closed_ if the coordinates which
are kept in a given vector are consecutive, like this:

A _$1$ -extraction_ is an extraction with only vectors of dimension $1$. In
particular, it is interval-closed. A _sub-extraction_ is an extraction of a
sub-sequence.

The following lemma gives two conditions equivalent to the unboundedness of
the dimension of a vector sequence.

######  Lemma .

Let $\mathbf{f}$ be a vector sequence. Then
$\texttt{dim}\left(\mathbf{f}\right)$ is unbounded if and only if one of the
following conditions is true:

  1. (1)

There exists a sub-extraction $\mathbf{g}$ of $\mathbf{f}$ such that
$\mathbf{g}\rightarrow\infty$ and $\texttt{dim}\left(\mathbf{g}\right)$ is
unbounded.

  2. (2)

There exists an interval-closed sub-extraction $\mathbf{g}$ of $\mathbf{f}$
such that $\texttt{dim}\left(\mathbf{g}\right)$ is unbounded and $\mathbf{g}$
is bounded, _i.e._ , there exists a bound $n\in\mathbb{N}$ such that all the
coordinates occurring in the sequence are less than $n$.

###### Proof.

The if implication is clear, since admitting a sub-extraction of unbounded
dimension trivially implies the unboundedness of the dimension.

We now focus on the only-if implication. Assume that
$\texttt{dim}\left(\mathbf{f}\right)$ is unbounded and condition (1) is false.
Then, for all sub-extractions $\mathbf{g}$ of $\mathbf{f}$ we have that
$\mathbf{g}\rightarrow\infty$ implies $\texttt{dim}\left(\mathbf{g}\right)$ is
bounded. This implies that there exists a constant $m$ such that for all
vectors $v$ in $\mathbf{f}$, the number of coordinates greater than $m$ is
less than $m$. Indeed, if no such $m$ exists, we can exhibit a sub-extraction
$\mathbf{g}$ of $\mathbf{f}$, which tends towards infinity and has unbounded
dimension. Let us mark the coordinates smaller than $m$ in every vector of
$\mathbf{f}$. For every integer $n$, we can find a vector of $\mathbf{f}$ with
at least $n$ consecutive marked coordinates. Indeed suppose there is at most
$n$ consecutive marked coordinates in every vector. Then, as there are at most
$m$ unmarked coordinates, a vector cannot have dimension greater than
$n(m+1)+m$ (_i.e._ , $m+1$ blocks of $n$ marked positions plus $m$ unmarked
positions separating them). This contradicts that
$\texttt{dim}\left(\mathbf{f}\right)$ is unbounded.

Thus by keeping for each vector one of the longest block of consecutive marked
positions and removing vectors without any marked position, we can construct
an interval-closed sub-extraction $\mathbf{g}$ of $\mathbf{f}$ which is
bounded by $m$ and has unbounded dimension. ∎

We now proceed to show how Lemma 3 implies Lemma 2.2. Recall that Lemma 2.2
says that there is a formula $\varphi\left(R,I\right)$ in mso+$\texttt{U}_{1}$
which is true if and only if the vector sequence $\mathbf{f}_{R,I}$ is defined
and satisfies $\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded.

###### Proof of Lemma 2.2 assuming Lemma 3.

Consider $R$ and $I$ two sets of positions such that $\mathbf{f}_{R,I}$ is
defined. We will use Lemma 3.1 to express in mso+$\texttt{U}_{1}$ that
$\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded. The first condition
of the lemma is expressible in mso+$\texttt{U}_{1}$ by Lemma 3, as shown in
the next section. However, in order to express the second condition, we need
that the gaps between consecutive intervals of $I$ have bounded length. This
is ensured by extending the intervals as explained in the following. For any
two disjoint sets $R$ and $I$, let us construct $J$ as follows: $J$ contains
$I$, and for every two consecutive positions $x<y$ in $I$ such that there is
no element of $R$ in between, we add to $J$ all the positions strictly between
$x$ and $y$, except $y-1$, as in Figure 3. The set $J$ is expressible in mso,
in the sense that there is a mso-formula with three free set variables $R$,
$I$, $J$ which holds if and only if $J$ is obtained from $I$ by this process.
Moreover, it is clear that $\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is
unbounded if and only if $\texttt{dim}\left(\mathbf{f}_{R,J}\right)$ is
unbounded since the dimension in both sequences are pairwise equal (see Figure
3). It suffices thus to prove Lemma 2.2 for sets $R$ and $I$ which satisfy:

$(\star)$:

between two consecutive elements of $I$, there is either an element of $R$ or
at most one position not in $I$.

Figure 3. Completion of a vector sequence.

Let $R$ and $I$ be two sets satisfying $(\star)$:  ‣ 3.1. We want to express
that $\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded. It suffices to
show that for each condition in Lemma 3.1, there exists a formula of
mso+$\texttt{U}_{1}$ which says that the condition is satisfied by
$\mathbf{f}_{R,I}$. We treat the two cases separately.

  1. (1)

We want to say that there exists a sub-extraction $\mathbf{g}$ of
$\mathbf{f}_{R,I}$ such that $\mathbf{g}\rightarrow\infty$ and
$\texttt{dim}\left(\mathbf{g}\right)$ is unbounded. Sub-extraction can be
simulated in mso according to the picture in Figure 4, and the condition
“$\mathbf{g}\rightarrow\infty$ and $\texttt{dim}\left(\mathbf{g}\right)$ is
unbounded” can be checked using Lemma 3.

Figure 4. Sub-extraction of a vector sequence.

  2. (2)

We want to say that there exists an interval-closed sub-extraction
$\mathbf{g}$ of $\mathbf{f}_{R,I}$ such that $\mathbf{g}$ is bounded and
$\texttt{dim}\left(\mathbf{g}\right)$ is unbounded. We use the same approach
as in the previous item, _i.e._ , we simulate sub-extraction in the logic
using the encoding from Figure 4, thus obtaining $R^{\prime},I^{\prime}$.
Additionally, we ensure that the selected sub-extraction is interval-closed.
Importantly, taking an interval-closed sub-extraction preserves property
$(\star)$:  ‣ 3.1. It remains therefore to write a formula in
mso+$\texttt{U}_{1}$ which says that sets $R^{\prime},I^{\prime}$ satisfy
$\mathbf{f}_{R^{\prime},I^{\prime}}$ is bounded and
$\texttt{dim}\left(\mathbf{f}_{R^{\prime},I^{\prime}}\right)$ is unbounded.

     * •

The boundedness of $\mathbf{f}_{R^{\prime},I^{\prime}}$ is expressed in
mso+$\texttt{U}_{1}$ by the fact that the complement of $I^{\prime}$ has to
satisfy the negation of $\texttt{U}_{1}$. Indeed, this exactly says that the
intervals of $I^{\prime}$ are bounded.

     * •

Now, since $\mathbf{f}_{R^{\prime},I^{\prime}}$ is bounded then
$\texttt{dim}\left(\mathbf{f}_{R^{\prime},I^{\prime}}\right)$ is unbounded if
and only if the sequence of the number of occurrences of elements of
$I^{\prime}$ between two consecutive elements of $R^{\prime}$ is unbounded.
Consider the set $X$ of all the positions which are either in $R^{\prime}$ or
not adjacent to an element in $I^{\prime}$ (which is expressible in mso).
Then, since $R^{\prime}$ and $I^{\prime}$ satisfy $(\star)$,
$\texttt{dim}\left(\mathbf{f}_{R^{\prime},I^{\prime}}\right)$ is unbounded if
and only if $\texttt{U}_{1}$$\left(X\right)$ holds.

This completes the reduction of Lemma 2.2 to Lemma 3. ∎

###  3.2. Unboundedness of dimensions for sequences tending to infinity

We now prove Lemma 3 whence concluding the proof of Theorem 1. The lemma says
that there is a formula $\varphi\left(R,I\right)$ in mso+$\texttt{U}_{1}$
which is true if and only if the vector sequence $\mathbf{f}_{R,I}$ is defined
and satisfies $\mathbf{f}_{R,I}\rightarrow\infty$ and
$\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is unbounded.

The main idea of the proof is to relate the unboundedness of the dimension
with a property definable in mso+$\texttt{U}_{1}$, namely the _asymptotic mix_
property, which was already used in [7] to prove undecidability of mso+U. This
is done in Lemma 3.2 below, for which we need a couple of notions on vector
sequences.

Given an infinite set $S\subseteq\mathbb{N}$ of positions and a number
sequence $f\in\mathbb{N}^{\omega}$, the _restriction of $f$ to $S$_ is the
number sequence obtained by discarding elements of index not in $S$ and is
denoted ${f}_{\mid S}$. Two number sequences $f$ and $g$ are called
_asymptotically equivalent_ , denoted by $f\sim g$, if they are bounded on the
same sets of positions, _i.e._ , if for every set $S$, ${f}_{\mid S}$ is
bounded if and only if ${g}_{\mid S}$ is bounded. For example, the number
sequences $f=1,1,3,1,5,1,7,1,9,\ldots$ and $g=2,1,4,1,6,1,8,1,10,\dots$ are
asymptotically equivalent, but $f$ and $h=1,3,1,5,1,7,1,9,1,\ldots$ are not.

We say that a vector sequence $\mathbf{f}$ is an _asymptotic mix_ of a vector
sequence $\mathbf{g}$ if for every $1$-extraction $f$ of $\mathbf{f}$, there
exists a $1$-extraction $g$ of $\mathbf{g}$ such that $f\sim g$. In
particular, the empty vector cannot occur in $\mathbf{f}$ or $\mathbf{g}$.
Note that this is not a symmetric relation.

Given two vector sequences $\mathbf{f}$ and $\mathbf{g}$, we say that
$\mathbf{g}$ _dominates_ $\mathbf{f}$, denoted $\mathbf{f}\leq\mathbf{g}$, if
for all $i$, the $i$-th vectors in both sequences have the same dimension, and
the $i$-th vector of $\mathbf{f}$ is coordinatewise smaller than or equal to
the $i$-th vector of $\mathbf{g}$. Furthermore, we suppose that all the
coordinates in $\mathbf{f}$ and $\mathbf{g}$ are positive.

An extraction $\mathbf{g}$ of $\mathbf{f}$ is said to be _strict_ , if at
least one coordinate of each vector of $\mathbf{f}$ has been popped in
$\mathbf{g}$, _i.e._ , the dimensions of the vectors of $\mathbf{g}$ are
pointwise smaller than those of $\mathbf{f}$. In particular, a vector sequence
with some vectors of dimension less than $2$ admits no strict extraction,
nevertheless, it may admit strict sub-extractions.

The following lemma relates the notion of asymptotic mix with the
unboundedness of the dimension of a vector sequence, providing the vector
sequence tends towards infinity.

######  Lemma .

Let $\mathbf{f}$ be a vector sequence such that $\mathbf{f}\rightarrow\infty$.
Then, $\texttt{dim}\left(\mathbf{f}\right)$ is unbounded if and only if there
exists a sub-sequence $\mathbf{h}$ and a strict extraction $\mathbf{g}$ of
$\mathbf{h}$ satisfying:

($P_{\mathbf{g},\mathbf{h}}$):

for every $\mathbf{h}^{\prime}\leq\mathbf{h}$, there exists
$\mathbf{g}^{\prime}\leq\mathbf{g}$ such that $\mathbf{h}^{\prime}$ is an
asymptotic mix of $\mathbf{g}^{\prime}$.

###### Proof.

The if direction follows from [7, Lemma 2.2], while the converse is new to
this work. More precisely, it is proved in [7, Lemma 2.2] that given two
vector sequences $\mathbf{h}$ and $\mathbf{g}$ tending towards infinity, if
$\mathbf{h}$ and $\mathbf{g}$ have bounded dimension, then the two following
properties are equivalent:

(1):

for infinitely many $i$’s, the $i$-th vector of $\mathbf{h}$ has higher
dimension than the $i$-th vector of $\mathbf{g}$;

(2):

the negation of ($P_{\mathbf{g},\mathbf{h}}$): : there exists
$\mathbf{h}^{\prime}\leq\mathbf{h}$ which is not an asymptotic mix of any
$\mathbf{g}^{\prime}\leq\mathbf{g}$.

Let $\mathbf{f}$ be a vector sequence which tends towards infinity and suppose
that it has bounded dimension. Let $\mathbf{h}$ be a sub-sequence of
$\mathbf{f}$ and $\mathbf{g}$ be a strict extraction of $\mathbf{h}$. By
definition, $\mathbf{h}$ and $\mathbf{g}$ satisfy (1): , have bounded
dimension and tend towards infinity. Therefore, by [7, Lemma 2.2], they
satisfy (2): , _i.e._ , the negation of ($P_{\mathbf{g},\mathbf{h}}$): .

We now prove the only if direction. We suppose that $\mathbf{f}$ tends towards
infinity and that $\texttt{dim}\left(\mathbf{f}\right)$ is unbounded. There
exists a sub-sequence $\mathbf{h}$ of $\mathbf{f}$ such that every vector
occurring in $\mathbf{h}$ has dimension at least $2$ and
$\texttt{dim}\left(\mathbf{h}\right)$ tends towards infinity.

Define $\mathbf{g}$ as being the extraction obtained from $\mathbf{h}$ by
dropping the last coordinate in each vector and observe that it is a strict
extraction of $\mathbf{h}$. We prove now a result stronger than required, by
exhibiting a universal $\mathbf{g}^{\prime}\leq\mathbf{g}$ which makes
($P_{\mathbf{g},\mathbf{h}}$):  true whatever the choice of
$\mathbf{h}^{\prime}\leq\mathbf{h}$, hence inverting the order of the
universal and the existential quantifiers. Let $\mathbf{g}^{\prime}$ be the
vector sequence defined as follows: for each position $i$, denoting the $i$-th
vector of $\mathbf{h}$ by $\left(v_{1},v_{2},\ldots,v_{k}\right)$, the $i$-th
vector of $\mathbf{g}^{\prime}$ is set to
$\left(\min\left(v_{1},1\right),\min\left(v_{2},2\right),\ldots,\min\left(v_{k-1},k-1\right)\right)$.
For instance:

$\begin{array}[]{rlllllll}\mathbf{h}=&(2,1),&(3,2,1),&(4,3,2,1),&(5,4,3,2,1),&(6,5,4,3,2,1),&\ldots\\\
\mathbf{g}=&(2),&(3,2),&(4,3,2),&(5,4,3,2),&(6,5,4,3,2),&\ldots\\\
\mathbf{g}^{\prime}=&(1),&(1,2),&(1,2,2),&(1,2,3,2),&(1,2,3,3,2),&\ldots\end{array}$

We now prove that every $\mathbf{h}^{\prime}\leq\mathbf{h}$ is an asymptotic
mix of $\mathbf{g}^{\prime}$, that is, for every $1$-extraction $h$ of
$\mathbf{h}^{\prime}$, there exists a $1$-extraction $g$ of
$\mathbf{g}^{\prime}$ such that $h\sim g$. We fix an arbitrary vector sequence
$\mathbf{h}^{\prime}\leq\mathbf{h}$ and a $1$-extraction $h$ of
$\mathbf{h}^{\prime}$. We define $g$ as the number sequence whose $i$-th
number, for each position $i$, is the maximal coordinate in the $i$-th vector
of $\mathbf{g}^{\prime}$ which is less than or equal to the $i$-th number in
$h$. This coordinate always exists since the first coordinate of every vector
in the sequence $\mathbf{g}$’ exists and is equal to $1$. For instance,
according to the previous example and given $\mathbf{h}^{\prime}$ and $h$, the
number sequence $g$ is defined as follows:

$\begin{array}[]{rcccccc}\mathbf{h}^{\prime}=&(1,1),&(2,1,1),&(3,2,1,1),&(4,3,2,1,1),&(5,4,3,2,1,1),&\ldots\\\
h=&1,&2,&1,&4,&1,&\ldots\\\
\mathbf{g}^{\prime}=&(1),&(1,2),&(1,2,2),&(1,2,3,2),&(1,2,3,3,2),&\ldots\\\
\hline\cr g=&1,&2,&1,&3,&1,&\ldots\end{array}$

Observe that, by definition, for every position $i$, the $i$-th number of $g$
is less than or equal to the $i$-th number of $h$. Hence, for every set $S$ of
positions, if ${h}_{\mid S}$ is bounded then so is ${g}_{\mid S}$. Suppose now
that for some set $S$ of positions, ${h}_{\mid S}$ is unbounded and fix an
integer $n$. We want to prove that some number in ${g}_{\mid S}$ is greater
than $n$. Since both $\mathbf{h}$ and $\texttt{dim}\left(\mathbf{h}\right)$
tend towards infinity, we can find a threshold $m\in\mathbb{N}$ such that for
every position $i\geq m$, the $i$-th vector of $\mathbf{h}$ has dimension
greater than $n$ and furthermore all its coordinates are greater than $n$.
Thus, for all positions $i\geq m$, the $n$-th coordinate of the $i$-th vector
of $\mathbf{g}^{\prime}$ is defined and it is equal to $n$. Therefore, for all
$i\in S$ with $i\geq m$ and such that the $i$-th number in $h$ is at least
$n$, the $i$-th number in $g$ is at least $n$ as well. Hence, ${g}_{\mid S}$
is unbounded. ∎

To conclude the proof of Lemma 3, it remains to express in
mso+$\texttt{U}_{1}$ the property stated in Lemma 3.2: given two sets $R$ and
$I$ encoding a vector sequence $\mathbf{f}_{R,I}$ which tends towards
infinity, there exists a sub-sequence $\mathbf{h}$ of $\mathbf{f}_{R,I}$ and a
strict extraction $\mathbf{g}$ of $\mathbf{h}$ satisfying
($P_{\mathbf{g},\mathbf{h}}$): . Note that we can check in
mso+$\texttt{U}_{1}$ that a sequence $\mathbf{f}_{R,I}$ (defined by two set
variables $R$ and $I$) tends towards infinity. Indeed, this holds if and only
if, for any bounded set $Y$ (_i.e._ , such that $\neg\texttt{U}_{1}(Y)$),
ultimately, the intervals of $I$ contain at least two elements of $Y$.

Given a vector sequence $\mathbf{f}$ and a set $S$, we say that an encoding of
$\mathbf{f}$ is _$S$ -synchronised_ if it is of the form $S,J$ for some set
$J$. Sub-sequences and strict extractions can be simulated in mso by defining
subsets of the original encoding, according to the picture in Figure 4. In
particular, given $R$ and $I$, one can construct in mso any sub-sequence
$\mathbf{h}$ of $\mathbf{f}_{R,I}$ and any strict extraction $\mathbf{g}$ of
$\mathbf{h}$, such that the encodings of $\mathbf{h}$ and $\mathbf{g}$ are
$S$-synchronised for some $S\subseteq R$.

Now, we express ($P_{\mathbf{g},\mathbf{h}}$):  on $\mathbf{h}$ and
$\mathbf{g}$ encoded by $S,J$ and $S,J^{\prime}$ respectively. Every dominated
sequence $\mathbf{h}^{\prime}$ (_resp._ $\mathbf{g}^{\prime}$) of $\mathbf{h}$
(_resp._ $\mathbf{g}$) can be obtained by deleting some rightmost consecutive
positions of intervals of $J$ (_resp._ $J^{\prime}$), keeping at least one
position for each interval. This can be done in mso, preserving the
$S$-synchronisation, as depicted below:

Finally, we prove that the property saying that $\mathbf{h}^{\prime}$ is an
asymptotic mix of $\mathbf{g}^{\prime}$ can be expressed in
mso+$\texttt{U}_{1}$ (using the $S$-synchronisation of the encodings of the
two sequences). Indeed, $1$-extractions can be simulated in mso according to
the picture in Figure 4, still preserving the $S$-synchronisation. Consider
then $K,K^{\prime}$ such that $S,K$ encodes a $1$-extraction of
$\mathbf{h}^{\prime}$ and $S,K^{\prime}$ encodes a $1$-extraction of
$\mathbf{g}^{\prime}$, _i.e._ , such that between every two consecutive
positions of $S$, the elements of $K$ (_resp._ $K^{\prime}$) form an interval.
It remains to prove that we can express in mso+$\texttt{U}_{1}$ that
$\mathbf{f}_{S,K}$ and $\mathbf{f}_{S,K^{\prime}}$, viewed as number
sequences, are asymptotically equivalent. We select a subset of indices of the
two number sequences $\mathbf{f}_{S,K}$ and $\mathbf{f}_{S,K^{\prime}}$ by
selecting elements of $S$ and keeping the maximal intervals in $K$ and
$K^{\prime}$ that directly follow the selected elements. Then, we check thanks
to $\texttt{U}_{1}$ that the corresponding sequences of numbers are both
bounded or both unbounded. This process is depicted here:

##  4\. How MSO+U may talk about ultimate periodicity

We consider now the quantifier P defined in the introduction. Recall that a
set of positions $X\subseteq\mathbb{N}$ is called _ultimately periodic_ if
there is some period $p\in\mathbb{N}$ such that for sufficiently large
positions $x\in\mathbb{N}$, either both or none of $x$ and $x+p$ belong to
$X$. We consider the logic mso+P, _i.e._ , mso augmented with _the quantifier
P_ that ranges over ultimately periodic sets:

$\texttt{P}X\varphi\left(X\right):\text{``the formula $\varphi\left(X\right)$
is true for all ultimately periodic sets $X$''}.$

######  Example .

The language of $\omega$-words over $\left\\{a,b\right\\}$ such that the
positions labeled by $a$ form an ultimately periodic set is definable in mso+P
by the following formula:

$\exists X\quad\underbrace{\vphantom{\Big{(}}\forall x\quad\big{(}x\in X\iff
a(x)\big{)}}_{\text{$X$ is the set of positions labeled by
$a$}}\quad\wedge\qquad\underbrace{\neg\Big{(}\texttt{P}Y\quad\big{(}X\neq
Y\big{)}\Big{)}}_{\text{$X$ is ultimately periodic}}\text{.}$

From Example 4, one can see that our quantifier P extends strictly the
expressivity of mso, but it is _a priori_ not clear whether it has decidable
or undecidable satisfiability. However, using Theorem 1, we can prove Theorem
1 which states that satisfiability over $\omega$-words is undecidable for
mso+P.

###### Proof of Theorem 1.

Since mso+U has undecidable satisfiability [7], the same follows for
mso+$\texttt{U}_{1}$ by Theorem 1. Moreover, the predicate $\texttt{U}_{1}$
can be defined in terms of ultimate periodicity: a set $X$ of positions
satisfies $\texttt{U}_{1}$$\left(X\right)$ if and only if for all infinite
ultimately periodic sets $Y$, there are at least two positions in $Y$ that are
not separated by a position from $X$. It follows that every sentence of
mso+$\texttt{U}_{1}$ can be effectively rewritten into a sentence of mso+P
which is true on the same $\omega$-words. Hence, Theorem 1 follows. ∎

The predicate $\texttt{U}_{1}$ can thus be expressed in mso augmented with the
quantifier P. It is not clear that the converse is true, and we leave this as
an open problem. However, in Theorem 4 below, we show that, up to a certain
encoding, all languages expressible in mso+P can be expressed in mso+U.

Let $\Sigma$ be a finite alphabet, $\\#$ be a symbol not belonging to
$\Sigma$, and $\Sigma_{\\#}$ denote $\Sigma\cup\left\\{\\#\right\\}$. We
define $\pi_{\Sigma}:{\Sigma_{\\#}}^{\omega}\to\Sigma^{\omega}$ to be the
function which erases all appearances of $\\#$. This is a partial function,
because it is only defined on $\omega$-words over $\Sigma_{\\#}$ that contain
infinitely many letters from $\Sigma$. We extend $\pi_{\Sigma}$ to languages
of $\omega$-words in a natural way.

######  Theorem .

Every language definable in mso+P over $\Sigma$ is equal to $\pi_{\Sigma}(L)$
for some language $L\subseteq{\Sigma_{\\#}}^{\omega}$ definable in mso+U.

The main difficulty in expressing “ultimate periodicity” is to check the
existence of a constant, namely the period, which is ultimately repeated. Such
a property was already the crucial point in the proof of the undecidability of
mso+U [7]. Indeed the authors managed to express that an encoded vector
sequence (as in Figure 2) tending towards infinity has _“ultimately constant
dimension”_ , _i.e._ , all but finitely many vectors of the sequence have the
same dimension (this dimension will represent the period). This is the content
of the following lemma which is a direct consequence of [7, Lemma 3.1].

######  Lemma .

There exists a formula $\varphi\left(R,I\right)$ in mso+U with two free set
variables which holds if and only if $\mathbf{f}_{R,I}$ is defined, tends
towards infinity, and $\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is
ultimately constant.

In order to use Lemma 4, we will encode a word $w$ over $\Sigma$ by adding
factors of consecutive $\\#$ between every two letters from $\Sigma$, such
that the lengths of those factors tend towards infinity. Let
$w=w_{1}w_{2}\cdots$ be an $\omega$-word over $\Sigma$ where the $w_{i}$’s are
letters, and let $f=n_{1},n_{2},\ldots$ be a number sequence. We define the
$\omega$-word $w_{f}$ over $\Sigma_{\\#}$ as
$w_{1}\\#^{n_{1}}w_{2}\\#^{n_{2}}\cdots$. In particular
$\pi_{\Sigma}(w_{f})=w$. Now, given a sentence $\varphi$ of mso+P over
$\Sigma$, we consider the language $L$ over $\Sigma_{\\#}$ of all the
$\omega$-words of the form $w_{f}$ for $w$ satisfying $\varphi$ and $f$ a
number sequence tending towards infinity. As we can easily check in mso+U that
the sequence of lengths of the factors of $\\#$ tends towards infinity,
Theorem 4 follows immediately from the following lemma.

######  Lemma .

For every sentence $\varphi$ in mso+P, one can effectively construct a formula
$\varphi_{\\#}$ in mso+U such that for every $\omega$-word
$w\in\Sigma^{\omega}$, the following conditions are equivalent:

  1. (1)

$\varphi$ is true in $w$;

  2. (2)

$\varphi_{\\#}$ is true in $w_{f}$ for every $f$ which tends towards infinity.

###### Proof.

Let $\varphi$ be a sentence in mso+P, and $f$ some number sequence tending
towards infinity. Given a word $w$, we construct $w_{f}$ as explained above.

We construct $\varphi_{\\#}$ by induction on the structure of $\varphi$, and
show that at every step of the induction, $\varphi$ is true in $w$ if and only
of $\varphi_{\\#}$ is true in $w_{f}$. To do so, we use the natural mapping
from positions of $w$ into positions of $w_{f}$ to handle free variables. In
particular, every free set variable used in the induction hypothesis is
supposed to contain only positions not labeled by $\\#$. Every formula not
containing the quantifier P is translated straightforwardly, only ignoring all
$\\#$ positions when counting (a bounded number, of course). For example, the
successor relation will be translated by ”the first position to the right not
labelled with $\\#$”. It is routine to check that the satisfiability is the
same in both $w$ and $w_{f}$, thanks to the natural mapping described above.
The key point of the induction is the case of a formula
$\texttt{P}X\varphi\left(X\right)$. We translate it to a formula of the form:
$\forall Y,\mathrm{UP}_{\\#}(Y)\Rightarrow\varphi_{\\#}(Y)$, where
$\mathrm{UP}_{\\#}(Y)$ holds for all sets $Y$ which contain only positions not
labeled by $\\#$ and which are “ultimately periodic when ignoring $\\#$’s”.

Checking if $Y$ does not contain any position labeled by $\\#$ is done by the
formula $\forall y,y\in Y\Rightarrow\neg\\#(y)$. It remains to express the
property “$Y$ is ultimately periodic when ignoring $\\#$’s” as a formula of
mso+U with one free set variable $Y$ which contains only positions not labeled
by $\\#$. It can be done in the following way: “$Y$ is ultimately periodic
when ignoring $\\#$’s” if and only if there exist two sets $R$ and $I$ such
that:

  * •

$I$ is exactly the set of all the $\\#$, $R$ is infinite and disjoint from $I$
(hence $\mathbf{f}_{R,I}$ is defined);

  * •

$\texttt{dim}\left(\mathbf{f}_{R,I}\right)$ is ultimately constant (this
constant dimension will represent the period of $Y$);

  * •

for every infinite set $R^{\prime}$ disjoint from $I$, alternating with $R$
(_i.e._ , such that there is exactly one element of $R^{\prime}$ between two
consecutive elements of $R$) and such that
$\texttt{dim}\left(\mathbf{f}_{R^{\prime},I}\right)$ is ultimately constant,
we have that all elements of $R^{\prime}$ are either ultimately in $Y$ or
ultimately not in $Y$.

These properties can be expressed in mso+U thanks to Lemma 4, since, as $f$
tends towards infinity, the vector sequence $\mathbf{f}_{R,I}$, tends towards
infinity. It is easy to check that the conjunction of these three properties
is equivalent to “$Y$ is ultimately periodic when ignoring $\\#$’s”. ∎

##  5\. Conclusion

We have considered the extensions of mso with the following features (two
quantifiers and two second-order predicates):

$\texttt{U}X\varphi\left(X\right)$:

the formula $\varphi\left(X\right)$ is true for sets $X$ of arbitrarily large
finite size.

$\texttt{U}_{1}$$\left(X\right)$:

for all $k\in\mathbb{N}$, there exist two consecutive positions of $X$ at
distance at least $k$.

$\texttt{U}_{2}$$\left(R,I\right)$:

the sequence of numbers encoded by $R,I$ (Figure 1) is defined and unbounded.

$\texttt{P}X\varphi\left(X\right)$:

the formula $\varphi\left(X\right)$ is true for all ultimately periodic sets
$X$.

We have proved that mso+U, mso+$\texttt{U}_{1}$ and mso+$\texttt{U}_{2}$ have
the same expressive power, and the translations between these logics are
effective (Theorem 1, Lemmas 2.1 and 2.2). Furthermore, all three have
undecidable satisfiability on $\omega$-words by [7]. Moreover we have seen
that $\texttt{U}_{1}$ is expressible in mso+P, while the converse is also true
up to some encoding (Theorem 4). As a consequence, mso extended with the
quantifier P has undecidable satisfiability (Theorem 1).

We believe that mso+$\texttt{U}_{1}$ can be reduced to many extensions of mso,
in a simpler way than reducing mso+U. It is for instance the case for mso
augmented with the quantifier that ranges over periodic sets (and not
necessarily ultimately periodic sets).

## References

  * [1] Vince Bárány, Lukasz Kaiser, and Alexander Rabinovich.  Expressing cardinality quantifiers in monadic second-order logic over chains.  Journal of Symbolic Logic, 76(2):603–619, 2011.
  * [2] Alexis Bès.  A Survey of Arithmetical Definability.  Société Mathématique de Belgique, 2002.
  * [3] Achim Blumensath, Olivier Carton, and Thomas Colcombet.  Asymptotic monadic second-order logic.  In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, pages 87–98, 2014.
  * [4] Mikołaj Bojańczyk.  U.  ACM SIGLOG News, 2(4):2–15, 2015.
  * [5] Mikołaj Bojańczyk.  A bounding quantifier.  In Computer Science Logic, 18th International Workshop, CSL 2004, 13th Annual Conference of the EACSL, Karpacz, Poland, September 20-24, 2004, Proceedings, pages 41–55, 2004.
  * [6] Mikołaj Bojańczyk and Thomas Colcombet.  Bounds in $\omega$-regularity.  In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 285–296, 2006\.
  * [7] Mikołaj Bojańczyk, Pawel Parys, and Szymon Toruńczyk.  The MSO+U Theory of ($\mathbb{N}$,$\leq$) Is Undecidable.  33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 21:1–21:8, 2016\.
  * [8] J. R. Büchi.  On a decision method in restricted second order arithmetic.  In Proceedings of the International Congress on Logic, Method, and Philosophy of Science, pages 1–12, Stanford, CA, USA, 1962. Stanford University Press.
  * [9] Dietrich Kuske, Jiamou Liu, and Anastasia Moskvina.  Infinite and Bi-infinite Words with Decidable Monadic Theories.  In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), volume 41 of Leibniz International Proceedings in Informatics (LIPIcs), pages 472–486, Dagstuhl, Germany, 2015\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [10] Markus Lohrey and Georg Zetzsche.  On Boolean closed full trios and rational Kripke frames.  In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 530–541, Dagstuhl, Germany, 2014. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [11] Henryk Michalewski and Matteo Mio.  Measure quantifier in monadic second order logic.  In International Symposium on Logical Foundations of Computer Science, pages 267–282. Springer, 2016.
  * [12] Michael Rabin.  Decidability of second-order theories and automata on infinite trees.  Transactions of the American Mathematical Society, 141:1–35, 1969\.


case, adiabaticity depends on the relationship between the radial velocity and
the vertical change of the surface flux. If the surface flux is zero, the flow
is adiabatic at any negligibly small radial velocity. But if the surface flux
is not zero (and it is not zero in the real atmosphere, as the reviewer
certainly agrees), then the faster the air expands radially for any given
$\partial J_{S}/\partial z$, the closer to adiabaticity it will be.
Conversely, when the air does not move at all along the radial pressure
gradient ($u=0$, as it is at the point of maximum wind), then there is no
expansion and no reason for a horizontal change of temperature – irrespective
of the magnitude of the radial pressure gradient. These are our grounds to
expect a change in the sign of $\partial T/\partial r$ in the vicinity of
maximum wind, which, judging from the reviewer’s feedback, appear to be novel.

The authors’ response to my comment within the revised manuscript leads into a
digression towards a separate dispute they have with the study of Rousseau-
Rizzi and Emanuel (2019) and their associated comment and reply articles.
While this is tangentially relevant to the current study in that it concerns
potential intensity, this newly added discussion seems to me to be a
distraction from the main arguments of this manuscript, and so I recommend
that it be removed.

The E-PI limitations exposed by the alternative formulation are not confined
to the free troposphere, but likewise affect the transition from volume to
surface fluxes as formulated by Eq. 4. These are very general limitations:
their nature is that, while developing one’s theory, one cannot arbitrarily
specify (by direct assumption or by prediction) the ratios between changes of
pressure, temperature and water vapor mixing ratio, as these are already
related by fundamental constraints that must be respected. An analogue of Eq.
(4) was not specified by Rousseau-Rizzi and Emanuel (2019) for their
derivation of surface E-PI, which, as the reviewer points out elsewhere,
differs only insignificantly from the boundary layer PI. The transition from
volume to surface fluxes was then demonstrably incorrectly specified by
Emanuel and Rousseau-Rizzi (2020) (see Footnote 4). This provides another
illustration (the first one being the hypercanes) to the pervasiveness of the
limitations exposed by the alternative formulation. That is why we believe
that it is relevant to the present discussion.

Further, their characterization of the comment and reply articles appears to
me to be misleading. The authors refer to Montgomery and Smith (2020) as
having pointed out a supposed omission in the derivation of RE19 related to
converting from volume to surface energy fluxes, but as far as I can tell,
MS20 make no such assertion; instead, MS20 dispute an unrelated aspect of the
derivation of RE19 (related to outflow temperature).

Montgomery and Smith (2020, p. 1890) wrote: “…the derivations on p. 1701 would
have been easier to follow had the authors written down the variable of
integration. In particular, it is hard to see how Eq. (15) is obtained from
Eq. (14), since it would appear that the integrals on each side of the
equation have been effectively canceled and replaced by a point evaluation of
the integrands.” This step from Eq. 14 to Eq. 15 is precisely the transition
from the volume to the surface fluxes. In their response, Rousseau-Rizzi and
Emanuel (2020) neither wrote down the variable of integration nor explicitly
derived Eq. 15 from Eq. 14.

The authors then refer to their own comment article as having also pointed out
this omission, which is true, but in my reading of that comment, the authors
don’t actually dispute the validity of RE19 related to that aspect of their
derivation. Instead, in their comment article, the authors conclude that RE19
made an implicit assumption in their derivation, and state “We consider it
reasonable”.

But Emanuel and Rousseau-Rizzi (2020) disagreed with our characterization of
their work and referred to it as being a contradiction.

The authors in their comment then transition to an argument about dissipative
heating, which doesn’t seem relevant to the present study.

Dissipative heating involves one more constraint, which is incompatible with
the other E-PI constraints, see Footnore 4. It is an illustration of the
conflicting assumptions/predictions in E-PI that all have a single cause.

Now, in the revised text, the dissipative heating is more relevant than in the
previous versions, because we show that dissipative heating is responsible for
the unexplained singularity in the superintensity account of Bryan and Rotunno
(2009a), see Appendix C.

So the authors appear to be mischaracterizing RE20 as having not responded to
a critique of MS20 that they do not appear to actually make, and not
responding to a critique of M20 that doesn’t actually challenge the derivation
of RE19 in the manner portrayed here. So if the authors choose to keep this
section (which I recommend removing), they must ensure that their
characterization of the relevant literature is accurate.

We have revised and clarified our arguments on this topic. They are now
confined to three paragraphs in the end of the concluding section plus
Footnote 4. We believe that this discussion is useful and could urge more
clarity in important issues that continue to be obfuscated. We conclude that
“While a detailed analysis of this subject is beyond the scope of the present
paper, we emphasize that the discussion of the numerical validity of E-PI
could be more meaningful if a comprehensive theoretical justification of Eq.
(4) (and its modifications, including the transition between Rousseau-Rizzi
and Emanuel (2019)’s Eqs. 14 and 15 and Emanuel and Rousseau-Rizzi (2020)’s
Eqs. 1 and 2) were provided.”

Minor Comments (and specific examples relating to Major Comments):

1\. P2 l21, p9 l150

Change “grows” to “increases”.

The first sentence was removed from the revised version. The second sentence
was corrected as suggested.

2\. P4 l51

But since the E-PI prediction of maximum wind speed does not actually require
assuming that the air is horizontally isothermal (as the authors now concede),
I think it is misleading to suggest that E-PI underestimates the maximum
achievable TC intensity in a given environment. I think the authors’ argument
here is essentially a “strawman”, because in practice, E-PI is not calculated
using this imposed constraint.

We respectfully disagree that our argument is a “strawman”, because, as we
have already noted, the real atmosphere can be isothermal at the point of
maximum wind irrespective of what E-PI assumes about it. In particular, it is
nearly isothermal in Hurricane Isabel on September 12 and in the control
simulation of Bryan and Rotunno (2009a), which we discuss in detail in,
respectively, section 2 and Appendix C. Horizontal isothermy of surface air
together with $\partial\mathcal{H}/\partial r=0$ at $z=0$ at the radius of
maximum wind, as assumed by Emanuel (1986) and Emanuel (1995), also
corresponds to horizontal isothermy at the point of maximum wind, see Appendix
A, Eq. (A17). In the concluding section we argue why this should generally be
a valid approximation in intense cyclones.

3\. P4 l65-66

Reading over ER11, those authors make the approximation that Tb is constant
when solving for the full radius-height structure of the theoretical wind
field. I’m not certain if they actually make this approximation or not in
order to solve for their approximate analytical asymptotic formulation (their
Eq. 41) of the maximum wind speed (which agrees very closely with their
numerical solution of the theory; their Fig. 9). As discussed in ER11, those
authors make several other approximations that are possibly more severe than
assuming constant Tb, such as neglecting the pressure dependence of saturation
entropy at the SST. Also note that ER11 compare their numerical solutions of
their theory to simulations using the RE87 model (their Fig. 10), and find
very good agreement in the prediction of the maximum wind speed, for different
values of Ck/Cd. Though these were “tuned” (through adjusting the outer
radius) to match the RMW, as far as I can tell, they were not tuned to match
the peak wind speed. And though the RE87 model also neglected the pressure
dependence of s0* to be consistent with the approximation in the theory, I
don’t think it is possible for the effective Tb in the RE87 model to be tuned,
and so presumably any deviations from constant Tb in that model would affect
the simulated TC, were it actually very sensitive to this, as argued by the
authors in the current manuscript. Note that as ER11 intentionally use large
values of both horizontal and vertical mixing lengths in their simulations, it
is unlikely that supergradient winds are a significant factor in that study.

Based on my reading of ER11 discussed above, I think the authors need to
address the apparent contradiction between their own arguments in this
manuscript that assuming Tb is constant results in large underestimation of TC
potential intensity, and the results of ER11, which indicate that an excellent
agreement between theory and numerical simulations is found for the maximum
wind speed, under an assumption of constant Tb in the theoretical analysis.

We appreciate this comprehensive defense of Emanuel and Rotunno (2011)’s
findings, especially in view of their critique by Montgomery et al. (2019) who
demonstrated their inconsistency using a numerical model. But we respectfully
disagree that we should delve into this topic. A numerical model can be tuned
to produce the desired outcome in a variety of ways, such that to pinpoint
from outside what has been done wrong can be in principle impossible. For
example, if Bryan and Rotunno (2009a) had been just slightly less transparent
in reporting their results, to expose the inconsistency in their
superintensity analyses – not supported by their model but presented as if
they were – would have been nearly impossible. Emanuel and Rotunno (2011)’s
assumption of $\partial T_{b}/\partial r=0$ was unambiguously, from the first
principles that are superior to any model, shown to be incompatible with the
other E-PI assumptions – we emphasize that the reviewer does not question this
fact. The burden of proof is now on Emanuel and Rotunno – to persuade the
readers, likewise from the first principles, that this incompatibility is
inconsequential for their conclusions. Our present results will remain
unaffected whatever the outcome.

4\. P4 l72

The authors point out that Rousseau-Rizzi and Emanuel (2019) assume constant
T, in their derivation of a form of PI that applies to the surface wind speed.
However, that study showed that the formulation of surface PI differed from
that of the original “gradient wind PI” of E86 only by Ts replacing Tb in the
numerator of the thermodynamic efficiency term. Since E86 did not need to
assume constant temperature to arrive at the equation for gradient wind PI,
this implies that the assumption of constant T necessary to arrive at the
equation for surface PI is quantitatively unimportant, since surface and
gradient wind PI do not differ that much. As Rousseau-Rizzi and Emanuel (2019)
show that surface PI acts well as a bound on the surface wind speed of
numerically simulated TCs, I think that the authors of the current manuscript
must deal with this contradiction to their arguments. If the authors’ argument
is correct, then why does surface PI (which uses the assumption of constant
temperature) agree well with numerically simulated TCs and with gradient wind
PI (which crucially does not use the assumption of constant temperature)?

The surface E-PI appears to “agree well with numerically simulated TCs” and
“act well as a bound on the surface wind speed of numerically simulated TCs”
only in the study of Rousseau-Rizzi and Emanuel (2019), who proposed it.
Already the next at least partially independent study that examined the
surface E-PI found that it does not. We are puzzled by the fact that the
reviewer is aware of the study of Li et al. (2020) but nevertheless makes the
above statements.

At the same time, the reviewer asks a pertinent question, which can be
reframed as follows: Why does the conventional E-PI formulation, which does
not assume horizontal isothermy, end up with a Carnot efficiency that is only
valid for reversible cycles? Our guess is that Rousseau-Rizzi and Emanuel
(2019) invoked horizontal isothermy to justify the use of Carnot efficiency in
their formulation of surface PI. In reality, E-PI is based on a consideration
of an infinitely narrow thermodynamic cycle with efficiency insensitive to
infinitely small irreversibilities. Therefore, as we discuss in section 3.b,
the assumption of isothermy is not needed for the surface PI either, and,
moreover, it conflicts with the other E-PI assumptions, an obstacle which the
authors do not appear to be taking into consideration. It is another
illustration of the novelty of our formulation and its implications.

5\. P4 l73

Insert “to be” after “appears”.

6\. P6 l98

Spell out “constant”.

7\. P6 l104

Change “low index” to “the subscript”.

8\. P7 l114

Insert “and” before “$\alpha_{d}$”.

9\. P8 l131

Change “that” to “than”.

Comments 5, 7, 8, and 9: Revised as suggested. Comment 6: according to the new
AMS rules, "constant" should be abbreviated as "const", see
https://www.ametsoc.org/index.cfm/ams/publications/author-
information/formatting-and-manuscript-components/.

10\. P8 l135

The authors agree that Tb=constant is not actually assumed in the derivation
of the E86 potential intensity (wind speed). Although this clarity in the
resubmitted manuscript is welcome, I remain concerned that this poses a major
issue for the presumed relevance of this study. Since calculations of the
environmentally-determined PI (which are generally based on some formulation
related to that of E86) do not as far as I’m aware actually use this
assumption, then it isn’t really true that the theoretical maximum intensity
for a given environment is actually a large underestimate of the actual
intensity of real TCs or simulated TCs as a result.

“Environmentally-determined PI” corresponds to $\hat{v}_{E}$ in the revised
text (see Table 1). First, regarding simulated TCs, this closed form of E-PI
is based on the assumption of an isothermal surface air and relative humidity
being constant at the surface everywhere beyond the radius of maximum wind
(Emanuel, 1995, p. 3971). We show in Appendix A that these assumptions
correspond to $\partial T_{b}/\partial r\simeq 0$. So, yes, the
environmentally-determined PI does indeed implicitly assume horizontal
isothermy at the point of maximum wind. And indeed, the control simulation in
the study of Bryan and Rotunno (2009a) is close to horizontal isothermy (see
Appendix C).

Second, for a real and well-studied TC, Hurricane Isabel 2003, it was shown
precisely that the theoretical maximum intensity for a given environment is
actually a large underestimate of the actual intensity. This underestimate
cannot be due to supergradient winds, since they are minimal on the day when
the underestimate is most significant (September 12, see Table 2). It is a
result of the horizontal isothermy at $z=z_{m}$.

11\. P8 l137

Although E86 assumed constant Tb in deriving an equation for the central
surface pressure, I’m pretty sure that in the revised Emanuel (1995)
formulation, the central surface pressure is no longer solved independently of
the maximum wind speed, and so this assumption isn’t really used anymore in
that framework (i.e., the pressure equations of E86 are no longer considered
valid in the present day applications of the theory, as discussed in E95).

The assumption of constant relative humidity at the surface at the radius of
maximum and the assumption of horizontally isothermal surface air, both of
which are used by Emanuel (1995), are equivalent to implicitly assuming an
approximately constant $T_{b}$, see Eq. (A17). Generally, the alternative
formulation makes it clear that there is no freedom to specify surface
relative humidity in E-PI, provided horizontal isothermy at the surface is
assumed.

12\. P8 l141

Insert “therefore” before “C=1”.

Revised.

13\. P9 l152

I think the authors need to clarify what they mean by “superintensity” here,
as I don’t think this is how it is commonly used in the literature. In its
conventional usage, superintensity refers to the exceedance of observed or
simulated wind speeds beyond that of some theoretical bound. But here, the
authors are instead using superintensity to refer to a comparison between two
different theoretical bounds, without respect to real or simulated TCs. This
distinction matters, because the implication of the authors’ statement is that
they have shown that there is some temperature beyond which the theoretical
potential intensity can’t be exceeded by observed or simulated TCs, but I
don’t think the analysis here actually demonstrates this. Note the fact that
the authors refer to the simulations of Li et al. (2020) isn’t relevant to
this concern, because here, the authors are implicitly defining superintensity
as the ratio of two theoretical quantities, not the ratio of a
simulated/observed intensity to the theoretical bound.

Here, in our view, as also below in Comment 17, an important point has
apparently escaped the reviewer’s attention: $v_{A}$ can be used to test the
validity of $v_{E}$, and not vice versa, because $v_{A}$ is more robust
(requires less assumptions) than $v_{E}$. This is explained after Eq. (12). In
this sense $v_{A}$ evaluated at the point of maximum wind is not a theoretical
estimate, since it solely derives from the definition of moist entropy. By
analogy, molar density of air diagnosed from pressure and temperature is not a
theoretical estimate; this “estimate” solely derives from the ideal gas law,
which as we know cannot be very wrong.

Further, Li et al. (2020) use the surface PI of Rousseau-Rizzi and Emanuel
(2019) for evaluation of the wind speed in their simulations, and so what they
show is that the surface wind speed no longer exceeds the surface-PI in
simulations with high SST. But the present manuscript concerns the theoretical
bound on the maximum wind speed at the top of the boundary layer, and so the
authors’ comparison to Li et al. (2020) here isn’t really appropriate in my
view. I don’t think Li et al. (2020) examined the maximum wind speed at any
height, but it is likely that in their simulations, that maximum still exceeds
the respective theoretical maximum, in association with supergradient winds.

We have shown that the explanation of superintensity by supergradient winds as
proposed by Bryan and Rotunno (2009a) is not valid, see Appendix C.

In other words, for a given simulation, it is likely that the maximum surface
wind speed will be closer to surface PI than the maximum wind speed at the top
of the boundary layer is to the traditional gradient wind PI, and so a lack of
surface PI superintensity at high SST does not necessarily imply a lack of
“traditional” superintensity at high SST. As the authors’ analysis here in
this manuscript largely concerns the traditional superintensity whereas Li et
al. are evaluating surface PI superintensity, I don’t the results of Li et al.
can be used to support the authors’ argument. In any case, I don’t think the
authors of this manuscript have actually shown that real or simulated TCs
cannot exceed E86 PI at high SSTs.

We respectfully disagree with the statement that the results of Li et al.
(2020) do not support our argument, for three reasons. First, while it is true
that our analysis largely concerns the traditional superintensity, our robust
alternative formulation is more general and equally applies to all E-PI’s
modifications where $\partial V/\partial r=0$ holds (including surface winds).
Second, at the surface the gradient-wind imbalance can be small (as it is in
the control simulation of Bryan and Rotunno (2009a)), so supergradient winds
cannot explain superintensity. Finally, given that the explanation of
superintensity by supergradient winds alone does not hold, see above, even if
the conventional E-PI demonstrates superintensity at high SST, our formulation
will nevertheless have to be involved to explain it.

14\. P10 l178-187

As I mentioned in my original review, although air flowing inwards towards
lower pressure will expand and thereby tend to cool adiabatically, this is not
the only process going on here. Depending on the location, surface (and
turbulent) heat fluxes will act to warm the air, as will condensational
heating in convection (e.g., within the eyewall), while evaporation of
precipitation falling into the air parcel will yield a cooling tendency.
Although it’s possible that the radial expansion is dominant, the authors need
to acknowledge and discuss these other contributions to the temperature budget
of an air parcel, and not simply assume that adiabatic expansion is the only
important term.

We have presented a quantitative analysis comparing the relative contributions
of adiabatic cooling and surface heat flux, Eq. (17), and discussed in
considerable detail the nature and magnitude of the horizontal temperature
gradient at different locations, see the new section 3.a.

15\. P11 l196

Although it’s true that air within the eye is warmer than elsewhere in
association with subsidence, this subsidence generally only occurs above the
boundary layer. The boundary layer eye of a well-developed hurricane is
typically warm and moist, and its relative warmth is largely the result of
surface sensible heat fluxes.

Revised as follows: “In the eye, the surface heat fluxes and the descending
air motion work to elevate the air temperature above that at the eyewall and
in the outer core.”

16\. P11 l207

The authors state that when the radial temperature gradient approaches the
moist adiabatic lapse rate, E-PI would “infinitely underestimate” the true
potential intensity. This doesn’t seem physically meaningful to me, and I
think underscores that the framework developed here doesn’t really show that
E-PI is underestimating intensity for the reasons given by the authors. And
once again, E-PI does not actually require specifying the radial temperature
gradient, and so I don’t think this is a valid manner of interpreting its
predictions.

The moist adiabatic lapse rate in the radial direction is a theoretical limit
in the considered problem, which corresponds to a disappearing link between
$ds^{*}$ and $dp$, since $ds^{*}$ tends to zero. We believe that discussing it
is informative. Again, it is not relevant whether E-PI assumes anything about
it or not. The question is whether such a gradient can be realized in nature.

17\. P12 l220-225

The authors state that “the large value of C=2.9 nearly compensated the
underestimate that would have otherwise resulted from $B<1$”. But as far as I
can tell, they are inferring C by substituting the observed maximum wind speed
into Eq. 15, not directly estimating C from observations. Therefore, I think
this argument is kind of circular, and we don’t really know that C=2.9, and
therefore we don’t know that a large C compensated for supergradient winds and
brought the observed wind speed into better agreement with E-PI.

The laws of nature are useful as they obviate the need to measure each and
every variable. For example, for an ideal gas you don’t need to measure
simultaneously $T$, $p$ and molar density $N$. From the ideal gas law $p=NRT$
and a known combination of any two variables, you unambiguously know the third
one. Similarly, $\mathcal{C}$ is unambiguously derived from our Eq. (15),
provided all the other variables are known. It cannot be wrong unless the
first law of thermodynamics fails. This is a manifestation of our alternative
formulation being more robust than E-PI (which contains additional
assumptions), an essential point that appears to have escaped the reviewer’s
attention. Therefore, if we trust the observations for Hurricane Isabel 2003,
we do know that a large $\mathcal{C}$ compensated for supergradient winds.

18\. P12 l227

Again, expansion as air flows inwards towards lower pressure is not the only
factor determining the radial temperature gradient near the RMW. Contrary to
the authors’ assertion otherwise, sensible heat fluxes will always contribute
to the temperature budget (unless the air temperature equals SST).

The input of the sensible heat fluxes can be arbitrarily small for any finite
temperature difference, as Eq. (17) demonstrates. It all depends on how fast
the flux of sensible heat declines with altitude relative to how fast the air
moves along the pressure gradient.

19\. P13 l233

The authors refer to a positive temperature gradient at the location of
maximum wind speed being associated with descending motion in the eye. But at
the RMW itself, which is typically located within the eyewall, there is
ascent, not descent, and so other processes are responsible for the local
positive radial temperature gradient.

We agree. This paragraph was removed. Instead, we mention that “Generally,
$\mathcal{C}>1$ at the point of maximum wind can result from the surface air
warming, and/or from the surface relative humidity increasing, towards the
center (see Eqs. (A14) and (A17) in Appendix A).”

20\. P13 l240

“the E-PI’s” should be “the E-PI”.

This line was removed from the text.

21\. P13 l241-243

The authors need to make clearer here that what they are referring to is a
diagnostic PI, and not the traditional concept of PI from E86 of an a priori
environmental thermodynamic limit on achievable intensity. A weak TC (over
SSTs that would support a much stronger TC) is well below its potential
intensity as traditionally defined. It has become common (e.g., Persing and
Montgomery 2003, Bryan and Rotunno 2009) in some studies to instead
diagnostically evaluate whether the conditions of a given PI theory are
satisfied in a numerical simulation, and to compare the simulated intensity at
a given time to the diagnostically calculated PI using data within the TC.
This is ok, but when doing so, the distinction between this diagnostic and
predictions of the maximum intensity for a given environment needs to be made
clear.

We have introduced a special variable $\hat{v}_{E}$ for the “environmental”
version of E-PI as compared to the diagnostic $v_{E}$ (5). In section 3.c we
discuss why these two estimates behave differently when compared with the
observed maximum wind speeds.

22\. P13 l244

This sentence as written is confusing, and I’m not sure what the authors are
trying to say. I think perhaps the authors are intending to state that while
E-PI provides an upper limit on the maximum achievable intensity of TCs, in
its diagnostic form, it underestimates the intensity of a given TC when it is
weak (at least in the view of the authors).

We have clarified as follows: “If horizontal isothermy is a common condition
under which $v_{E}$ (5) underestimates $v_{m}$, one has to explain why in most
cases the maximum wind speeds observed in real cyclones are well below the
environmental version of E-PI, $\hat{v}_{E}$ (Table 1). Since the
underestimate $v_{E}<v_{m}$ results from E-PI assumptions pertaining to the
free troposphere (block E-I in Table 1), the overestimate $\hat{v}_{E}>v_{m}$
indicates that a certain overcompensation should occur in the assumptions
pertaining to the remaining two E-PI blocks, the boundary layer interior and
the air-sea interface (Table 1, blocks E-II and E-III).”

23\. P14 l262 Change “In the result” to “As a result”.

24\. P16 l303 Change “monotonous” to “monotonic”.

25\. P16 l308 Change “adiabat” to “adiabatic“.

Comments 23, 24, and 25: Revised as suggested.

26\. P16 l312-318

Once again, E-PI does not assume anything about the radial temperature
gradient at the top of the boundary layer to obtain the relationship that the
authors are investigating in this study, as the authors now acknowledge. Given
that fact, it is not surprising that this gradient has “not received much
attention in the assessment of E-PI’s validity“, because it has no bearing on
E-PI’s validity (again, I am referring to the formulation in E86, which is the
same form that the authors are examining).

We believe that if there had been a general understanding that, without
assuming anything about the radial temperature gradient, E-PI actually
predicts it, the radial temperature gradient, as a straightforward check on
E-PI ’s validity, would have received much more attention than it did while
the relevant knowledge was missing. Indeed, the radial temperature gradient
has a direct bearing on E-PI’s validity.

27\. P322-323

The discussion in this paragraph is very misleading. The authors are
concluding that E-PI can’t provide an upper limit on TC intensity, as a result
of as assumption that E-PI does not make. It isn’t appropriate to substitute
assumptions made elsewhere (even if by the same authors) to invalidate a
framework that does not make that assumption.

28\. P16 l323-327

Remove the parentheses surrounding these sentences.

29\. P17 l348

“bottomline” should be “bottom line“.

Comments 27, 28, and 29: As the concluding section was considerably re-
written, the corresponding lines were removed.

30\. P18 l352

The authors state that “There were no data utilized in this study.” I don’t
think this is really true, as Table 2 uses data from Hurricane Isabel, as does
Fig. 2, and Fig. 1 uses data from the simulations of Li et al. (2020).

Revised as “There were no raw data utilized in this study”.

31\. Fig. 2

“See section b” should say “See section 3b“.

Corrected.

## References

  * Aberson et al. (2006) Aberson, S. D., Montgomery, M. T., Bell, M., and Black, M.: Hurricane Isabel (2003): New insights into the physics of intense storms. Part II: Extreme localized wind, Bull. Amer. Meteor. Soc., 87, 1349–1354, 10.1175/BAMS-87-10-1349, 2006.
  * Bejan (2019) Bejan, A.: Thermodynamics of heating, Proc. Roy. Soc. A, 475, 20180 820, 10.1098/rspa.2018.0820, 2019.
  * Bell and Montgomery (2008) Bell, M. M. and Montgomery, M. T.: Observed structure, evolution, and potential intensity of category 5 Hurricane Isabel (2003) from 12 to 14 September, Mon. Wea. Rev., 136, 2023–2046, 10.1175/2007MWR1858.1, 2008.
  * Bister et al. (2011) Bister, M., Renno, N., Pauluis, O., and Emanuel, K.: Comment on Makarieva et al. ‘A critique of some modern applications of the Carnot heat engine concept: The dissipative heat engine cannot exist’, Proc. Roy. Soc. A, 467, 1–6, 10.1098/rspa.2010.0087, 2011.
  * Bryan and Rotunno (2009a) Bryan, G. H. and Rotunno, R.: Evaluation of an analytical model for the maximum intensity of tropical cyclones, J. Atmos. Sci., 66, 3042–3060, 10.1175/2009JAS3038.1, 2009a.
  * Bryan and Rotunno (2009b) Bryan, G. H. and Rotunno, R.: The influence of near-surface, high-entropy air in hurricane eyes on maximum hurricane intensity, J. Atmos. Sci., 66, 148–158, 10.1175/2008JAS2707.1, 2009b.
  * Camp and Montgomery (2001) Camp, J. P. and Montgomery, M. T.: Hurricane maximum intensity: Past and present, Mon. Wea. Rev., 129, 1704–1717, 10.1175/1520-0493(2001)129<1704:HMIPAP>2.0.CO;2, 2001.
  * DeMaria and Kaplan (1994) DeMaria, M. and Kaplan, J.: Sea surface temperature and the maximum intensity of Atlantic tropical cyclones, J. Climate, 7, 1324–1334, 10.1175/1520-0442(1994)007<1324:SSTATM>2.0.CO;2, 1994.
  * Emanuel (2004) Emanuel, K.: Tropical cyclone energetics and structure, pp. 165–192, Cambridge University Press, 10.1017/CBO9780511735035.010, 2004.
  * Emanuel (2006) Emanuel, K.: Hurricanes: Tempests in a greenhouse, Physics Today, 59, 74–75, 10.1063/1.2349743, 2006.
  * Emanuel (2020) Emanuel, K.: The relevance of theory for contemporary research in atmospheres, oceans, and climate, AGU Advances, 1, 10.1029/2019AV000129, 2020.
  * Emanuel and Rotunno (2011) Emanuel, K. and Rotunno, R.: Self-stratification of tropical cyclone outflow. Part I: Implications for storm structure, J. Atmos. Sci., 68, 2236–2249, 10.1175/JAS-D-10-05024.1, 2011.
  * Emanuel and Rousseau-Rizzi (2020) Emanuel, K. and Rousseau-Rizzi, R.: Reply to “Comments on ‘An evaluation of hurricane superintensity in axisymmetric numerical models’”, J. Atmos. Sci., 77, 3977–3980, 10.1175/JAS-D-20-0199.1, 2020.
  * Emanuel (1986) Emanuel, K. A.: An air-sea interaction theory for tropical cyclones. Part I: Steady-state maintenance, J. Atmos. Sci., 43, 585–604, 10.1175/1520-0469(1986)043<0585:AASITF>2.0.CO;2, 1986.
  * Emanuel (1988) Emanuel, K. A.: The maximum intensity of hurricanes, J. Atmos. Sci., 45, 1143–1155, 10.1175/1520-0469(1988)045<1143:TMIOH>2.0.CO;2, 1988.
  * Emanuel (1989) Emanuel, K. A.: The finite-amplitude nature of tropical cyclogenesis, J. Atmos. Sci., 46, 3431–3456, 10.1175/1520-0469(1989)046<3431:TFANOT>2.0.CO;2, 1989\.
  * Emanuel (1991) Emanuel, K. A.: The theory of hurricanes, Annu. Rev. Fluid Mech., 23, 179–196, 10.1146/annurev.fl.23.010191.001143, 1991.
  * Emanuel (1995) Emanuel, K. A.: Sensitivity of tropical cyclones to surface exchange coefficients and a revised steady-state model incorporating eye dynamics, J. Atmos. Sci., 52, 3969–3976, 10.1175/1520-0469(1995)052<3969:SOTCTS>2.0.CO;2, 1995.
  * Frank (1977) Frank, W. M.: The structure and energetics of the tropical cyclone I. Storm structure, Mon. Wea. Rev., 105, 1119–1135, 10.1175/1520-0493(1977)105<1119:TSAEOT>2.0.CO;2, 1977.
  * Garner (2015) Garner, S.: The relationship between hurricane potential intensity and CAPE, J. Atmos. Sci., 72, 141–163, 10.1175/JAS-D-14-0008.1, 2015.
  * Kieu (2015) Kieu, C.: Revisiting dissipative heating in tropical cyclone maximum potential intensity, Quart. J. Roy. Meteor. Soc., 141, 2497–2504, 10.1002/qj.2534, 2015.
  * Kieu and Moon (2016) Kieu, C. Q. and Moon, Z.: Hurricane intensity predictability, Bull. Amer. Meteor. Soc., 97, 1847–1857, 10.1175/BAMS-D-15-00168.1, 2016.
  * Kowaleski and Evans (2016) Kowaleski, A. M. and Evans, J. L.: A reformulation of tropical cyclone potential intensity theory incorporating energy production along a radial trajectory, Mon. Wea. Rev., 144, 3569–3578, 10.1175/MWR-D-15-0383.1, 2016\.
  * Lackmann and Yablonsky (2004) Lackmann, G. M. and Yablonsky, R. M.: The importance of the precipitation mass sink in tropical cyclones and other heavily precipitating systems, J. Atmos. Sci., 61, 1674–1692, 2004.
  * Li et al. (2020) Li, Y., Wang, Y., Lin, Y., and Fei, R.: Dependence of superintensity of tropical cyclones on SST in axisymmetric numerical simulations, Mon. Wea. Rev., 148, 4767–4781, 10.1175/MWR-D-20-0141.1, 2020.
  * Makarieva et al. (2010) Makarieva, A. M., Gorshkov, V. G., Li, B.-L., and Nobre, A. D.: A critique of some modern applications of the Carnot heat engine concept: The dissipative heat engine cannot exist, Proc. Roy. Soc. A, 466, 1893–1902, 10.1098/rspa.2009.0581, 2010.
  * Makarieva et al. (2015) Makarieva, A. M., Gorshkov, V. G., and Nefiodov, A. V.: Empirical evidence for the condensational theory of hurricanes, Phys. Lett. A, 379, 2396–2398, 10.1016/j.physleta.2015.07.042, 2015.
  * Makarieva et al. (2017) Makarieva, A. M., Gorshkov, V. G., Nefiodov, A. V., Chikunov, A. V., Sheil, D., Nobre, A. D., and Li, B.-L.: Fuel for cyclones: The water vapor budget of a hurricane as dependent on its movement, Atmos. Res., 193, 216–230, 10.1016/j.atmosres.2017.04.006, 2017.
  * Makarieva et al. (2019) Makarieva, A. M., Gorshkov, V. G., Nefiodov, A. V., Chikunov, A. V., Sheil, D., Nobre, A. D., Nobre, P., and Li, B.-L.: Hurricane’s maximum potential intensity and surface heat fluxes, URL https://arxiv.org/abs/1810.12451, eprint arXiv: 1810.12451v2 [physics.ao-ph], 2019.
  * Makarieva et al. (2020) Makarieva, A. M., Nefiodov, A. V., Sheil, D., Nobre, A. D., Chikunov, A. V., Plunien, G., and Li, B.-L.: Comments on “An evaluation of hurricane superintensity in axisymmetric numerical models”, J. Atmos. Sci., 77, 3971–3975, 10.1175/JAS-D-20-0156.1, 2020.
  * Makarieva et al. (2021) Makarieva, A. M., Gorshkov, V. G., Nefiodov, A. V., Chikunov, A. V., Sheil, D., Nobre, A. D., Nobre, P., Plunien, G., and Molina, R. D.: Water lifting and outflow gain of kinetic energy in tropical cyclones, URL https://arxiv.org/abs/2106.12544v1, eprint arXiv: 2106.12544v1 [physics.ao-ph], 2021.
  * Montgomery and Smith (2020) Montgomery, M. T. and Smith, R. K.: Comments on “An evaluation of hurricane superintensity in axisymmetric numerical models”, J. Atmos. Sci., 77, 1887–1892, 10.1175/JAS-D-19-0175.1, 2020.
  * Montgomery et al. (2006) Montgomery, M. T., Bell, M. M., Aberson, S. D., and Black, M. L.: Hurricane Isabel (2003): New insights into the physics of intense storms. Part I: Mean vortex structure and maximum intensity estimates, Bull. Amer. Meteor. Soc., 87, 1335–1347, 10.1175/BAMS-87-10-1335, 2006.
  * Montgomery et al. (2019) Montgomery, M. T., Persing, J., and Smith, R. K.: On the hypothesized outflow control of tropical cyclone intensification, Quart. J. Roy. Meteor. Soc., 145, 1309–1322, 10.1002/qj.3479, 2019.
  * Pauluis (2011) Pauluis, O.: Water vapor and mechanical work: A comparison of Carnot and steam cycles, J. Atmos. Sci., 68, 91–102, 10.1175/2010JAS3530.1, 2011.
  * Persing and Montgomery (2003) Persing, J. and Montgomery, M. T.: Hurricane superintensity, J. Atmos. Sci., 60, 2349–2371, 10.1175/1520-0469(2003)060<2349:HS>2.0.CO;2, 2003.
  * Rotunno and Emanuel (1987) Rotunno, R. and Emanuel, K. A.: An air-sea interaction theory for tropical cyclones. Part II: Evolutionary study using a nonhydrostatic axisymmetric numerical model, J. Atmos. Sci., 44, 542–561, 1987.
  * Rousseau-Rizzi and Emanuel (2019) Rousseau-Rizzi, R. and Emanuel, K.: An evaluation of hurricane superintensity in axisymmetric numerical models, J. Atmos. Sci., 76, 1697–1708, 10.1175/JAS-D-18-0238.1, 2019.
  * Rousseau-Rizzi and Emanuel (2020) Rousseau-Rizzi, R. and Emanuel, K.: Reply to “Comments on ‘An evaluation of hurricane superintensity in axisymmetric numerical models’”, J. Atmos. Sci., 77, 1893–1896, 10.1175/JAS-D-19-0248.1, 2020.
  * Smith and Montgomery (2013) Smith, R. K. and Montgomery, M. T.: How important is the isothermal expansion effect in elevating equivalent potential temperature in the hurricane inner core?, Quart. J. Roy. Meteor. Soc., 139, 70–74, 10.1002/qj.1969, 2013.
  * Tao et al. (2020a) Tao, D., Bell, M., Rotunno, R., and van Leeuwen, P. J.: Why do the maximum intensities in modeled tropical cyclones vary under the same environmental conditions?, Geophys. Res. Lett., 47, 10.1029/2019GL085980, 2020a.
  * Tao et al. (2020b) Tao, D., Rotunno, R., and Bell, M.: Lilly’s model for steady-state tropical cyclone intensity and structure, J. Atmos. Sci., 77, 3701–3720, 10.1175/JAS-D-20-0057.1, 2020b.
  * Venkat Ratnam et al. (2016) Venkat Ratnam, M., Ravindra Babu, S., Das, S. S., Basha, G., Krishnamurthy, B. V., and Venkateswararao, B.: Effect of tropical cyclones on the stratosphere–troposphere exchange observed using satellite observations over the north Indian Ocean, Atmos. Chem. Phys., 16, 8581–8591, 10.5194/acp-16-8581-2016, 2016.
  * Wang and Lin (2020) Wang, D. and Lin, Y.: Size and structure of dry and moist reversible tropical cyclones, J. Atmos. Sci., 77, 2091–2114, 10.1175/JAS-D-19-0229.1, 2020\.
  * Wang and Lin (2021) Wang, D. and Lin, Y.: Potential role of irreversible moist processes in modulating tropical cyclone surface wind structure, J. Atmos. Sci., 78, 709 – 725, 10.1175/JAS-D-20-0192.1, 2021.
  * Wang et al. (2014) Wang, S., Camargo, S. J., Sobel, A. H., and Polvani, L. M.: Impact of the tropopause temperature on the intensity of tropical cyclones: An idealized study using a mesoscale model, J. Atmos. Sci., 71, 4333–4348, 10.1175/JAS-D-14-0029.1, 2014.
  * Zhou et al. (2017) Zhou, W., Held, I. M., and Garner, S. T.: Tropical cyclones in rotating radiative-convective equilibrium with coupled SST, J. Atmos. Sci., 74, 879–892, 10.1175/JAS-D-16-0195.1, 2017.