text:
\section{Final Remarks}\label{section:Conclusion}%

We have exposed two linear orders $\ord,\ordb$ and a built-in
permutation $\pi$ such that both,
$\class{FO}(\ord,\ordb)$ and $\class{FO}(\ord,\pi)$ have the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$
(Theorem~\ref{thm:MainThm-linearorders} and
Corollary~\ref{cor:permutation}).

Of course, it can be debated
  whether linear orders are really ``simpler'' than addition and
  multiplication or the $\ensuremath{\FktsFont{BIT}}$ predicate. Actually, this article
  precisely shows that, with respect to expressive power of
  first-order logic, they are not. However, in an intuitive sense,
  linear orders appear to be simpler, as they are just the transitive
  closure of a linear number of edges, and thus the structure of one
  linear order is more homogenous than, say, the structure of $\ensuremath{\FktsFont{BIT}}$.
The characterisation given in Corollary~\ref{cor:permutation}
even shows that $\class{FO}(\ensuremath{\FktsFont{BIT}})$ can be captured by using
$<$ and the linear number of edges provided by the built-in permutation $\pi$.

We note that there is no set $M$ of
\emph{unary} built-in predicates such that $\class{FO}(<,M)$ has at least the
expressive power of $\class{FO}(\ensuremath{\FktsFont{BIT}})$. This is due to the fact that,
according to \cite{BILST-JCSS}, $\class{FO}(<,M)$ has the Crane Beach
property while $\class{FO}(\ensuremath{\FktsFont{BIT}})$ does not have this property.

\section*{Acknowledgement}
We would like to thank Lauri Hella for an inspiring discussion on the
Crane Beach property that led to the proof of Theorem~\ref{thm:CraneBeachProperty}.
Furthermore, we thank the anonymous referees for their valuable comments.

\section{$\class{FO}(<,\ordc)$ Does Not Capture $\class{FO}(\ensuremath{\FktsFont{BIT}})$}\label{section:cranebeach}

In this section we show that the linear orders $\ord$ and $\ordc$ alone are not sufficient
  to capture $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
\begin{thm}\label{thm:CraneBeachProperty}
 $\class{FO}(\ord,\ordc)$ is strictly less expressive than $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
\end{thm}
\proof
Lemma~\ref{lemma:Bit2ordcetc} tells us that $\class{FO}(\ord,\ordc)$
is at most as expressive as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
To show that $\class{FO}(\ord,\ordc)$ does not have the same expressive power as
$\class{FO}(\ensuremath{\FktsFont{BIT}})$,
we make use of the so-called \emph{Crane Beach property}
\cite{BILST-JCSS}, which is defined as follows:

\medskip

\begin{enumerate}[$\bullet$]
\item
Let $\ell$ be a list of built-in predicates. The logic $\class{FO}(\ell)$ is
said to have the \emph{Crane Beach property} if the following is true:
Every string-language $L$ that is definable in $\class{FO}(\ell)$ and that
has a \emph{neutral letter}, is also
definable in $\class{FO}(\ord)$.
Here, a letter $e$ is called \emph{neutral for $L$}, if
  for all strings $w_1$, $w_2$ we have \ $w_1w_2\in L \iff w_1ew_2\in L$.
\end{enumerate}

\medskip

\noindent
Clearly, $\class{FO}(<)$ has the Crane Beach property by definition.
From \cite{BILST-JCSS} we know
that $\class{FO}(\ensuremath{\FktsFont{BIT}})$ does
\emph{not} have the \emph{Crane Beach property}.
In the remainder of this proof, we show that $\class{FO}(\ord,\ordc)$ has
the Crane Beach property. This, in particular, will tell us that
$\class{FO}(\ord,\ordc)$ does not have the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.

The basic idea of the proof that $\class{FO}(\ord,\ordc)$ has the Crane Beach
property is that the order $\ordc$ is useless on structures in which
all columns but the rightmost column contain only neutral letters.
For the proof we follow
the methodology of \cite{BILST-JCSS} and use
\emph{Ehrenfeucht-Fra\"\i{}ss\'{e} games} (EF-game, for short), cf.,
e.g., \cite{Libkin-FMT}.
Let $L$ be a language that is definable in $\class{FO}(\ord,\ordc)$ and
that has a neutral letter.
Let $\Sigma$ be the alphabet of $L$ (i.e., $L\subseteq \Sigma^*$), let
$e\in \Sigma$
denote the neutral letter of $L$, and let $k$ be the quantifier
rank  of the $\class{FO}(\ord,\ordc)$-formula that defines $L$.
Our aim is to show that $L$ is also definable in $\class{FO}(\ord)$.

Towards a contradiction, let us assume that $L$ is \emph{not} definable in
$\class{FO}(\ord)$. Then, in particular, there are (non-empty) strings $u$ and $v$ such that
$u\in L$, $v\not\in L$, and the duplicator has a winning strategy in
the $2k$-round EF-game
on the structures
\[
  \ensuremath{\mathcal{A}} \ := \ \bigstruc{\dom{n^u},n^u,\ord[n^u],(Q_\sigma^u)_{\sigma\in\Sigma}}
  \qquad \text{and} \qquad
  \ensuremath{\mathcal{B}} \ := \ \bigstruc{\dom{n^v},n^v,\ord[n^v],(Q_\sigma^v)_{\sigma\in\Sigma}}
\]
where, for any string $w$, we let $n^w:=|w|-1$.
For each letter
$\sigma$ of $\Sigma$ we let
$Q_\sigma^w := \setc{i\in\dom{n^w}}{w_i=\sigma}$,
where $w=w_0w_1\cdots w_{n^w}$ with $w_i\in\Sigma$ for all $i\in\dom{n^w}$.
Henceforth, the $2k$-round EF-game on
$\ensuremath{\mathcal{A}}$ and $\ensuremath{\mathcal{B}}$ will be called
the \emph{small game}.

Since $L$ has neutral letter $e$, we can assume
without loss of generality that $u$ and $v$ have the same length.
(If not, we can proceed as in \cite{BILST-JCSS}: Append $u$ with $2^{2k}+|v|$
neutral letters $e$, append $v$
with $2^{2k}+|u|$ neutral letters $e$, and note that
the duplicator has a winning strategy in the $2k$-round EF-game on the
padded versions of $\ensuremath{\mathcal{A}}$ and $\ensuremath{\mathcal{B}}$.)

We use $n$ to denote $n^u=n^v$, and we let $u=u_0u_1\cdots u_n$ and
$v=v_0v_1\cdots v_n$ with $u_i,v_i\in\Sigma$.
Now let $N:=q_n +n$, and let $U$ and $V$ be strings of length $N{+}1$ of the form $e^*\,u$
and $e^*\,v$, respectively.
In particular, we know that $U\in L$ and $V\not\in L$.
Note that $U=U_0U_1\cdots U_N$ is the string which, for all $i$ with $0\leq
i\leq n$ carries letter $u_i$
on position $q_n+i$, and which carries the neutral letter on all other
positions; and analogously
$V$ is obtained from $v$.
An illustration of how $U$ and $V$ are embedded in
$\struc{\dom{N},<^N,\ordc[N]}$ is given in Figure~\ref{fig:cranebeachUV}.

\begin{figure}[ht]
\begin{minipage}{6cm}
  \centering
\psset{unit=0.5cm}
  \begin{pspicture}(-1.5,-1.5)(9.5,8.5)

\setlength{\fboxsep}{1pt}

\rput(0,0){$e$}%
\rput(1,0){$e$}%
\rput(1,1){$e$}%
\rput(2,0){$e$}%
\rput(2,1){$e$}%
\rput(2,2){$e$}%
\rput(3,0){$e$}%
\rput(3,1){$e$}%
\rput(3,2){$e$}%
\rput(3,3){$e$}%
\rput(4,0){}%
\rput(4,1){$\vdots$}%
\rput(4,2){}%
\rput(4,3){$\vdots$}%
\rput(4,4){}%
\rput(5,0){}%
\rput(5,1){$\vdots$}%
\rput(5,2){}%
\rput(5,3){$\vdots$}%
\rput(5,4){}%
\rput(5,5){$\vdots$}%
\rput(6,0){$e$}%
\rput(6,1){$e$}%
\rput(6,2){$e$}%
\rput(6,3){$e$}%
\rput(6,4){}%
\rput(6,5){$\vdots$}%
\rput(6,6){$e$}%
\rput(7.1,0){$u_0$}
\rput(7.1,1){$u_1$}
\rput(7.1,2){$u_2$}
\rput(7.1,3){$u_3$}
\rput(7.1,4){}%
\rput(7.1,5){$\vdots$}%
\rput(7.1,6){}%
\rput(7.1,6.9){$u_{n}$}%

\psline(-1.5,-0.5)(7.6,-0.5)%
\psline(-1.5,-1)(7.6,8.1)%
\psline(7.6,-0.5)(7.6,8.1)%
\rput(-1,0){\fbox{0}}%
 \rput(0,1){\fbox{1}}%
 \rput(1,2){\fbox{2}}%
 \rput(2,3){\fbox{3}}%
 \rput(3,4){\fbox{4}}%
\rput(4.5,5.8){$\adots$}%
\rput(5.8,7.1){\fbox{\large $n$}}%
\rput(7,8){}%
\rput(0,-1){\fbox{0}}%
\rput(1,-1){\fbox{1}}%
\rput(2,-1){\fbox{2}}%
\rput(3,-1){\fbox{3}}%
\rput(4,-1){\fbox{4}}%
\rput(5.5,-1){$\cdots$}%
\rput(7.1,-1){\fbox{\large $n$}}%
  \end{pspicture}
\end{minipage}
\hspace{15mm}
\begin{minipage}{6cm}
  \centering
\psset{unit=0.5cm}
  \begin{pspicture}(-1.5,-1.5)(9.5,8.5)
\setlength{\fboxsep}{1pt}

\rput(0,0){$e$}%
\rput(1,0){$e$}%
\rput(1,1){$e$}%
\rput(2,0){$e$}%
\rput(2,1){$e$}%
\rput(2,2){$e$}%
\rput(3,0){$e$}%
\rput(3,1){$e$}%
\rput(3,2){$e$}%
\rput(3,3){$e$}%
\rput(4,0){}%
\rput(4,1){$\vdots$}%
\rput(4,2){}%
\rput(4,3){$\vdots$}%
\rput(4,4){}%
\rput(5,0){}%
\rput(5,1){$\vdots$}%
\rput(5,2){}%
\rput(5,3){$\vdots$}%
\rput(5,4){}%
\rput(5,5){$\vdots$}%
\rput(6,0){$e$}%
\rput(6,1){$e$}%
\rput(6,2){$e$}%
\rput(6,3){$e$}%
\rput(6,4){}%
\rput(6,5){$\vdots$}%
\rput(6,6){$e$}%
\rput(7.1,0){$v_0$}
\rput(7.1,1){$v_1$}
\rput(7.1,2){$v_2$}
\rput(7.1,3){$v_3$}
\rput(7.1,4){}%
\rput(7.1,5){$\vdots$}%
\rput(7.1,6){}%
\rput(7.1,6.9){$v_{n}$}%

\psline(-1.5,-0.5)(7.6,-0.5)%
\psline(-1.5,-1)(7.6,8.1)%
\psline(7.6,-0.5)(7.6,8.1)%
\rput(-1,0){\fbox{0}}%
 \rput(0,1){\fbox{1}}%
 \rput(1,2){\fbox{2}}%
 \rput(2,3){\fbox{3}}%
 \rput(3,4){\fbox{4}}%
\rput(4.5,5.8){$\adots$}%
\rput(5.8,7.1){\fbox{\large $n$}}%
\rput(7,8){}%
\rput(0,-1){\fbox{0}}%
\rput(1,-1){\fbox{1}}%
\rput(2,-1){\fbox{2}}%
\rput(3,-1){\fbox{3}}%
\rput(4,-1){\fbox{4}}%
\rput(5.5,-1){$\cdots$}%
\rput(7.1,-1){\fbox{\large $n$}}%
  \end{pspicture}
\end{minipage}
\caption{Illustration of the strings $U$ (left) and $V$ (right), embedded in
    \mbox{$\struc{\dom{N},<^N,\ordc[N]}$}.\newline
    Row and column numbers are framed.}
 \label{fig:cranebeachUV}
\end{figure}

We will now translate the duplicator's winning strategy in the small game into a winning strategy for the $k$-round
EF-game on the structures
\[
  \ensuremath{\mathfrak{A}} \ := \ \bigstruc{\dom{N},\ord[N],\ordc[N],(Q_\sigma^U)_{\sigma\in\Sigma}}
  \qquad \text{and} \qquad
  \ensuremath{\mathfrak{B}} \ := \ \bigstruc{\dom{N},\ord[N],\ordc[N],(Q_\sigma^V)_{\sigma\in\Sigma}}.
\]
Henceforth, the EF-game on $\ensuremath{\mathfrak{A}}$ and $\ensuremath{\mathfrak{B}}$ will be called the
\emph{big game}. Note that $N$, $U$, and $V$ were chosen in
such a way that with respect to the triangular matrix illustrated in
Figure~\ref{fig:triangle} and restricted to the numbers in $\dom{N}$,
the strings $u$ and $v$ are in the
rightmost column of $\ensuremath{\mathfrak{A}}$ and $\ensuremath{\mathfrak{B}}$.

To find a winning strategy for the big game, the duplicator in
parallel plays (according to her given winning strategy) the small
game and translates moves for the small game into moves for the big game.
To be precise,
for every round $i\in\set{1,\ldots,k}$ of the big game, the
duplicator plays two rounds (namely, rounds $2i{-}1$ and $2i$) in the
small game and proceeds as follows:
If the spoiler chooses an element $\ensuremath{\mathfrak{a}}_i\in\dom{N}$ in
$\ensuremath{\mathfrak{A}}$, the duplicator lets a virtual spoiler choose
$a_{2i-1}:= c(\ensuremath{\mathfrak{a}}_i)$ and $a_{2i}:= r(\ensuremath{\mathfrak{a}}_i)$ in the small game
(thus, $\ensuremath{\mathfrak{a}}_i = q_{a_{2i-1}}+a_{2i}$), considers the
duplicator's answer $b_{2i-1}$ and $b_{2i}$ following her winning
strategy, and chooses
$\ensuremath{\mathfrak{b}}_i:= q_{b_{2i-1}}+ b_{2i}$ as her answer in the big
game (thus, $b_{2i-1}=c(\ensuremath{\mathfrak{b}}_i)$ and $b_{2i}=r(\ensuremath{\mathfrak{b}}_i)$).
If the spoiler chooses an element $\ensuremath{\mathfrak{b}}_i$ in $\ensuremath{\mathfrak{B}}$, the
duplicator's choice of $\ensuremath{\mathfrak{a}}_i$ in $\ensuremath{\mathfrak{A}}$ is determined in the
analogous way.

After the $k$-th round of the big game, we know that the duplicator
has won the small game, since she played according to her winning
strategy. Thus, we have
\begin{enumerate}[(1)]
 \item
   \ $u_{a_i} = v_{b_i}$, \quad for all $i$ with $1\leq i\leq 2k$,
 \item
   \ $a_i < a_j \iff b_i<b_j$, \quad for all $i,j$ with $1\leq i,j\leq 2k$.
\end{enumerate}
Our aim is to show that the duplicator has won the big game, i.e.,
that
\begin{enumerate}[(1')]
 \item
   \ $U_{\ensuremath{\mathfrak{a}}_i} = V_{\ensuremath{\mathfrak{b}}_i}$, \quad for all $i$ with $1\leq i\leq k$,
 \item
   \ $\ensuremath{\mathfrak{a}}_i < \, \ensuremath{\mathfrak{a}}_j\ \iff \ensuremath{\mathfrak{b}}_i<\,\ensuremath{\mathfrak{b}}_j$, \,\quad for all $i,j$ with $1\leq i,j\leq k$,
 \item
   \ $\ensuremath{\mathfrak{a}}_i \ordc \ensuremath{\mathfrak{a}}_j \iff \ensuremath{\mathfrak{b}}_i \ordc \ensuremath{\mathfrak{b}}_j$, \quad for all $i,j$ with $1\leq i,j\leq k$.
\end{enumerate}
Concerning (1'), note that if $a_{2i-1}=n$ then $b_{2i-1}=n$ and
$\ensuremath{\mathfrak{a}}_i =q_n+ a_{2i}$, \
$\ensuremath{\mathfrak{b}}_i=q_n+b_{2i}$, \
$U_{\ensuremath{\mathfrak{a}}_i}=u_{a_{2i}}$, \ and
$V_{\ensuremath{\mathfrak{b}}_i}=v_{b_{2i}}$. Thus, due to (1) we have
$U_{\ensuremath{\mathfrak{a}}_i}=V_{\ensuremath{\mathfrak{b}}_i}$.
Furthermore, if $a_{2i-1}< n$ then $b_{2i-1}<n$ and
$\ensuremath{\mathfrak{a}}_i=q_{a_{2i-1}}+a_{2i} < q_n$ and
$\ensuremath{\mathfrak{b}}_i=q_{b_{2i-1}}+b_{2i}<q_n$.
Thus, $U_{\ensuremath{\mathfrak{a}}_i}=V_{\ensuremath{\mathfrak{b}}_i}$ is the neutral letter.

To obtain (3'), note that we have
 \[
 \begin{array}{rcll}
   \ensuremath{\mathfrak{a}}_i\ordc\ensuremath{\mathfrak{a}}_j
 & \iff
 & r(\ensuremath{\mathfrak{a}}_i)<r(\ensuremath{\mathfrak{a}}_j)\text{ or } \ (r(\ensuremath{\mathfrak{a}}_i)=r(\ensuremath{\mathfrak{a}}_j)\text{
      and } c(\ensuremath{\mathfrak{a}}_i)<c(\ensuremath{\mathfrak{a}}_j))
 & \text{(by equation~\eqref{eq:defOrdc})}
 \\
 & \iff
 & a_{2i}<a_{2j} \text{ or } \ (a_{2i}=a_{2j}\text{
      and } a_{2i-1}<a_{2j-1})
 & \text{(by def.\ of $a_{2i-1},a_{2i}$)}
 \\
 & \iff
 & b_{2i}<b_{2j} \ \text{ or } \ (b_{2i}=b_{2j}\text{ \
      and } b_{2i-1}<b_{2j-1})
 & \text{(by (2))}
 \\
 & \iff
 & r(\ensuremath{\mathfrak{b}}_i)<r(\ensuremath{\mathfrak{b}}_j)\text{ or } \ (r(\ensuremath{\mathfrak{b}}_i)=r(\ensuremath{\mathfrak{b}}_j)\text{
      and } c(\ensuremath{\mathfrak{b}}_i)<c(\ensuremath{\mathfrak{b}}_j))
 & \text{(by def.\ of $\ensuremath{\mathfrak{b}}_i$)}
 \\
 & \iff
 & \ensuremath{\mathfrak{b}}_i\ordc\ensuremath{\mathfrak{b}}_j
 & \text{(by equation~\eqref{eq:defOrdc})}.
 \end{array}
 \]

Note that (2') can be obtained in the same way, using
equation~\eqref{eq:defOrd}.
\\
In summary, the duplicator has won the big game.
We hence obtain that the structures $\ensuremath{\mathfrak{A}}$ and $\ensuremath{\mathfrak{B}}$ satisfy the
same first-order sentences of quantifier rank $k$.
However, since $U\in L$ and $V\not\in L$, this
contradicts our assumption that $L$ is definable by an
$\class{FO}(\ord,\ordc)$-sentence of quantifier rank $k$.
Thus, the proof of Theorem~\ref{thm:CraneBeachProperty} is complete.
\qed

\section{Introduction}\label{section:Introduction}

There are various ways in which arithmetic (i.e., addition and multiplication) on
finite structures can be encoded by other
numerical
predicates. The
following theorem summarises the results from \cite{BIS90,DDLW98,Lynch82-squares,TroyLee03,Bennett-Phd};
see \cite{Schweikardt_ACMToCL} for a survey. Precise definitions are
given in Section \ref{section:preliminaries}.
\begin{thm}\label{thm:FOBit}
 The following logics have the same expressive power (on the class of all finite structures):
 \begin{quote}
   $\class{FO}(\ensuremath{\FktsFont{BIT}})$, \quad
   $\class{FO}(<,\ensuremath{\FktsFont{BIT}})$, \quad
   $\class{FO}(+,\times)$, \quad
   $\class{FO}(+,\praedikat{Squares})$, \quad
   $\class{FO}(<,\times)$, \\
   $\class{FO}(<,+,\times,\praedikat{Exp},\ensuremath{\FktsFont{BIT}},\praedikat{Squares})$
 \end{quote}
 and each of them can describe exactly those string-languages
 that belong to
 $\class{DLOGTIME}$-uniform $\ACzero$.
\end{thm}
From Theorem \ref{thm:FOBit} one might get the impression that
relations with an involved arithmetical structure are necessary to encode arithmetic in a first-order
fashion. Contradicting this intuition, we show in this article that
arithmetic can also be encoded by two particular linear orders.
More precisely, our main result exposes two
linear orders $\ord,\ordb$ such that $\class{FO}(\ord,\ordb)$ has
the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$. A weaker version of this
result (with three further built-in orders)  had been
announced in \cite{BILST-JCSS,Schweikardt_Diss} (cf., Corollary 5.5(d)
in \cite{BILST-JCSS} and Theorem 4.5(d)
in \cite{Schweikardt_Diss}), both referring to an ``unpublished
manuscript on $\class{\itshape MonadicNP}$ with built-in grid structures'' by Schweikardt
and Schwentick.
This paper finally presents this
result along with a detailed proof.
As an easy corollary we also obtain a particular built-in permutation
$\pi$ such that $\class{FO}(\ord,\pi)$ has the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
\bigskip

\textbf{Organisation.}
The remainder of this paper is structured as follows:
In Section~\ref{section:preliminaries} our terminology is fixed.
In Section~\ref{section:FO-colgrids} we introduce two linear
orders $\ord,\ordc$ and two unary predicates $C,Q$ and
show that $\class{FO}(\ord,\ordc,C,Q)$ is as expressive as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
In Section~\ref{section:cranebeach} we show that
$\class{FO}(<,\ordc)$ is strictly less expressive than $\class{FO}(\ensuremath{\FktsFont{BIT}})$; the
proof utilises the so-called Crane Beach property that might
be interesting in its own right.
In Section~\ref{section:linearorders} we show how $\ordc$ and the unary predicates $C$,
$Q$ can be replaced by a single linear order \ordb, and we show how to
represent $\ordb$ by a permutation $\pi$.
Section~\ref{section:Conclusion} concludes the paper.

\section{Capturing $\class{FO}(\ensuremath{\FktsFont{BIT}})$ with Two Linear Orders and Two Unary Predicates}\label{section:FO-colgrids}

This section's aim is to present numerical predicates $\ordc$, $C$,
$Q$ such that $\class{FO}(<,\ordc,C,Q)$ captures $\class{FO}(\ensuremath{\FktsFont{BIT}})$. Here, $C$ and
$Q$ will be unary, and $\ordc$ will be a linear order on $\NN$.

The underlying idea is illustrated in Figure~\ref{fig:triangle}. We
consider the elements of $\NN$ to be distributed into a lower right
triangular matrix with infinitely many columns and rows, where for
every $i\in\NN$, the $i$-th column consists of $i{+}1$ consecutive
numbers, and the $i$-th row contains infinitely many numbers: The
$0$-th column consists of the number 0, the 1-st column consists of
the numbers 1 and 2, the 2-nd column consists of the numbers 3, 4, and
5, and the $i$-th column consists all numbers $z$ with $q_i\leq z \leq
q_i+i$, where $q_i$ denotes the smallest element in this column. I.e.,
$q_0=0$ and $q_{i} = q_{i-1}+i$, for all $i>0$. Thus, $q_i =
\frac{i(i+1)}{2}$, for all $i\in \NN$.

\begin{figure}[ht]
  \centering
\psset{unit=0.5cm}
  \begin{pspicture}(-1.5,-1)(9.5,10)

\setlength{\fboxsep}{1pt}

\rput(0,0){0}%
\rput(1,0){1}%
\rput(1,1){2}%
\rput(2,0){3}%
\rput(2,1){4}%
\rput(2,2){5}%
\rput(3,0){6}%
\rput(3,1){7}%
\rput(3,2){8}%
\rput(3,3){9}%
\rput(4,0){10}%
\rput(4,1){11}%
\rput(4,2){12}%
\rput(4,3){13}%
\rput(4,4){14}%
\rput(5,0){15}%
\rput(5,1){16}%
\rput(5,2){17}%
\rput(5,3){18}%
\rput(5,4){19}%
\rput(5,5){20}%
\rput(6,0){21}%
\rput(6,1){22}%
\rput(6,2){23}%
\rput(6,3){24}%
\rput(6,4){25}%
\rput(6,5){26}%
\rput(6,6){27}%
\rput(7,0){28}
\rput(7,1){29}
\psline(-1.5,-0.5)(8.5,-0.5)%
\rput(9.5,-0.5){$\cdots$}%
\psline(-1.5,-1)(7.5,8)%
\rput(8,8.7){$\adots$}%
\rput(-1,0){\fbox{0}}%
 \rput(0,1){\fbox{1}}%
 \rput(1,2){\fbox{2}}%
 \rput(2,3){\fbox{3}}%
 \rput(3,4){\fbox{4}}%
\rput(4,5){\fbox{5}}%
\rput(5,6){\fbox{6}}%
\rput(6,7){\fbox{7}}%
\rput(7,8){\fbox{8}}%
\rput(0,-1){\fbox{0}}%
\rput(1,-1){\fbox{1}}%
\rput(2,-1){\fbox{2}}%
\rput(3,-1){\fbox{3}}%
\rput(4,-1){\fbox{4}}%
\rput(5,-1){\fbox{5}}%
\rput(6,-1){\fbox{6}}%
\rput(7,-1){\fbox{7}}%
\rput(8,-1){\fbox{8}}%
\rput(8.5,0){$\cdots$}%
\rput(8.5,1){$\cdots$}%
\rput(7.5,2){$\cdots$}%
\rput(7.5,3){$\cdots$}%
\rput(7.5,4){$\cdots$}%
\rput(7.5,5){$\cdots$}%
\rput(7.5,6){$\cdots$}%
\rput(7.5,7){$\cdots$}%
  \end{pspicture}
  \caption{Illustration of columns and rows for the definition of
    $\ordc$. Row numbers and column numbers are framed.}
  \label{fig:triangle}
\end{figure}

We number the rows from bottom up and the
columns from left to right, starting with 0.
For each $x\in\NN$, we write $c(x)$ and $r(x)$ to denote the
\emph{column number} and the \emph{row number} of $x$ in
Figure~\ref{fig:triangle}, and we let $q(x)$ denote the bottom-most
element in the same column as $x$. Thus,
\begin{equation}\label{def:functionscrq}
 c(x) =  \max\setc{i\in\NN}{q_i\leq x}, \qquad
q(x) =  q_{c(x)}, \qquad
 r(x) =  x-q(x).
\end{equation}
As an example, $c(13)=4$, $q(13)=10$, and $r(13)=3$.
Note that, by definition, we have
\begin{equation}\label{eq:nisqnplusrn}
  x=q(x)+r(x) \qquad\text{and}\qquad 0\leq r(x)\leq c(x),
\end{equation}
for every $x\in\NN$.
Clearly, all numbers $x$ of the same column agree on $q(x)$. We
thus sometimes call $q(x)$ the \textit{$q$-value} of the column of a
number $x$.

Of course, the standard order $<$ on $\NN$ is just the bottom-to-top,
left-to-right, column major order of this matrix. That is, for all
$x,y\in\NN$ we have
\begin{eqnarray}\label{eq:defOrd}
  x<y & \iff &
  c(x)<c(y) \quad \text{or}\quad
  \big(\
    c(x) = c(y) \ \ \text{and} \ \ r(x) < r(y)
  \ \big).
\end{eqnarray}
\noindent
We define $\ordc$ as the left-to-right, bottom-to-top, row major
order. I.e., for all $x,y\in\NN$ we let
\begin{eqnarray}\label{eq:defOrdc}
  x\ordc y & \iff &
  r(x)<r(y) \quad \text{or}\quad
  \big(\
    r(x) = r(y) \ \ \text{and} \ \ c(x) < c(y)
  \ \big).
\end{eqnarray}
Thus, we have
\[
0\ordc1\ordc3\ordc6\ordc10\ordc\cdots\ordc2\ordc4\ordc7\ordc\cdots\ordc5\ordc8\ordc\cdots\ordc9\ordc\cdots.
\]
\noindent
We
use the relations $C$ and $Q$ to induce binary
  strings on the columns of the matrix. The
  number encoded by the string induced by $C$ on the $i$-th column (with the
bottom-most element of this column representing the least significant
bit) shall\footnote{Why we represent $i+1$, respectively $q_{i+1}$,
  instead of $i$ and $q_i$ will be explained in Footnote~\ref{fn:plusone}.} be $i+1$, and the
  number induced by $Q$ on the $i$-th column shall be $q_{i+1}$.
That is,
\[ C :=  \setc{x\in\NN}{\text
  bit $r(x)$ of the binary
     representation of $c(x){+}1$ is 1, i.e., }2\nmid\textstyle{\abgerundet{\frac{c(x)+1}{2^{r(x)}}}}},\]
\[ Q := \setc{x\in\NN}{\text
 bit $r(x)$ of the binary
     representation of $q_{c(x)+1}$ \ is 1, i.e., }2\nmid\textstyle{\abgerundet{\frac{q_{c(x)+1}}{2^{r(x)}}}}}.\]\medskip

\begin{figure}[h!tbp]
 \begin{center}
  \includegraphics[width=6.25cm]{figures/figure-C.eps}
  \hspace{10mm}
  \includegraphics[width=6.25cm]{figures/figure-Q.eps}
 \caption{Illustration of the unary predicates $C$ (left) and $Q$
   (right) assigning to each column $i$ the binary representations $\text{Bin}(i{+}1)$ and
   $\text{Bin}(q_{i+1})$ of the numbers $i{+}1$ and $q_{i{+}1}$, respectively. The
   least significant bit of binary representations is in the
   bottom-most row.}
 \label{fig:CQ}
 \end{center}
\end{figure}%
See Figure~\ref{fig:CQ} for an illustration of $C$ and $Q$.
As an example, the restriction of $C$ to column 3 is the set
$\{8\}$ (representing the bit string $100$), and  the restriction of
$Q$ to column 3 is the set $\{7,9\}$ (representing the bit
string $1010$).

Note that, for every $i$, the $i$-th column contains sufficiently many
elements to encode $q_{i+1}=\frac{(i+1)(i+2)}{2}$, since
the $i$-th column has length $i{+}1$ and can thus encode binary representations of
numbers of size up to $2^{i+1}{-}1 \geq q_{i+1}$.

The remainder of this section is devoted to the proof of the following
theorem.
\begin{thm}\label{thm:mainwithunarypredicates}
$\class{FO}(<,\ordc,C,Q)$ has the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
\end{thm}
\proof
That $\class{FO}(\ensuremath{\FktsFont{BIT}})$ is at least as expressive as $\class{FO}(<,\ordc,C,Q)$
is an immediate consequence of the following
lemma.
\begin{lem}\label{lemma:Bit2ordcetc}
 There are $\class{FO}(\ensuremath{\FktsFont{BIT}})$-formulas $\varphi_<(x,y)$,
 $\varphi_{\ordc}(x,y)$, $\varphi_C(x)$, $\varphi_Q(x)$ such that, when
 evaluated in $\struc{\dom{n},\ensuremath{\FktsFont{BIT}}^n}$ for some $n\in\NN$, \
 $\varphi_<(x,y)$ expresses that $x<y$, \
 $\varphi_{\ordc}(x,y)$ expresses that $x\ordc y$, \
 $\varphi_C(x)$ expresses that $x\in C$, \ and \
 $\varphi_Q(x)$ expresses that $x\in Q$.
\end{lem}
\proof
The existence of the formula $\varphi_{\ord}(x,y)$
follows from Theorem~\ref{thm:FOBit}.
Using Theorem~\ref{thm:FOBit}, it is straightforward to find $\class{FO}(\ensuremath{\FktsFont{BIT}})$-formulas
$\varphi_{c}(x,y)$, $\varphi_{r}(x,y)$, and $\varphi_q(x,y)$ which, when interpreted in
$\struc{\dom{n},\ensuremath{\FktsFont{BIT}}^n}$, express that \ $c(x)=y$, \ $r(x)=y$, and
\ $q(x)=y$, \ respectively.
Using these formulas (and Theorem~\ref{thm:FOBit}), it is an easy
exercise to find formulas
$\varphi_{\ordc}(x,y)$, $\varphi_C(x)$, $\varphi_Q(x)$,
expressing the statement of
equation~\eqref{eq:defOrdc} and the definitions of the predicates $C$
and $Q$.
\qed

To prove the opposite direction, we will construct an
$\class{FO}(<,\ordc,C,Q)$-formula that expresses the $\ensuremath{\FktsFont{BIT}}$-predicate.
The construction of this formula will be established by
a
sequence of auxiliary formulas and lemmas.

For every $P\in\set{<,\ordc}$ there are $\class{FO}(P)$-formulas
$\varphi_{\praedikat{max},P}(x)$ and $\varphi_{\praedikat{succ},P}(x,y)$ expressing that $x$
is the maximum element w.r.t.\ the linear order $P$, resp.,
that $y$ is the successor of $x$ w.r.t.\ $P$:
\[
  \varphi_{\praedikat{max},P}(x) \ := \ \ensuremath{\neg}\exists z\ xPz
  \qquad\text{and}\qquad
  \varphi_{\praedikat{succ},P}(x,y) \ := \ \big( xPy \ensuremath{\wedge} \ensuremath{\neg} \exists z ( xPz \ensuremath{\wedge}
  zPy) \big).
\]
For every $c\in\NN$ there is an $\class{FO}(<)$-formula $\varphi_{=c}(x)$
expressing that $x$ is interpreted with the natural number $c$:
\[
  \varphi_{=0}(x) \ := \ \ensuremath{\neg}\exists z\ z<x
  \qquad\text{and}\qquad
  \varphi_{= c+1}(x) \ := \ \exists z\ \big(\varphi_{=c}(z)\ensuremath{\wedge} \phisucc(z,x)\big).
\]
To improve readability of formulas, we will henceforth often write
\begin{center}
$x = c$, \quad $x = \praedikat{max}_P$, \quad $y = \praedikat{succ}_P(x)$, \quad $y = \praedikat{pred}_P(x)$
\end{center}
instead of $\varphi_{=c}(x)$, \
$\varphi_{\praedikat{max},P}(x)$, \ $\varphi_{\praedikat{succ},P}(x,y)$, \ $\varphi_{\praedikat{succ},P}(y,x)$.
Furthermore, we will write
\begin{center}
 $x\leq y$ \quad and \quad $x\ordeqc y$
\end{center}
as shorthands
for \ $(x<y\,\ensuremath{\vee}\, x=y)$ \ and \ $(x \ordc y \, \ensuremath{\vee} \, x=y)$.

\begin{lem}\label{lemma:aux-grid-formulas}
There are formulas
$\phisamecol(x,y)$,
$\phisamerow(x,y)$,
$\phiq(x,y)$, and
$\phirc(x,y)$ in $\class{FO}(<,\ordc)$
such that, when evaluated in $\struc{\dom{n},<^n,\ordc[n]}$ for some $n\in\NN$,
\begin{enumerate}[$-$]
\item
 $\phisamecol(x,y)$ expresses that $c(x)=c(y)$, i.e., $x$ is
 in the same column as $y$,
\item
 $\phisamerow(x,y)$ expresses that $r(x)=r(y)$, i.e., $x$ is
 in the same row as $y$,
\item
 $\phiq(x,y)$ expresses that $q(x)=y$, i.e.,
 $y$ is the bottom-most element in the
 same column as $x$,
\item
 $\phirc(x,y)$ expresses that $r(x)=c(y)$, i.e.,
 $x$'s row-number is the same as $y$'s column-number.
\end{enumerate}
\end{lem}
\proof
Note that the bottom-most row consists of exactly those elements that
are smaller than 2 w.r.t.\ $\ordc$. Thus we can
choose
\[
  \phibot(x) \ := \ \forall z\ ( z=2 \ensuremath{\rightarrow} x\ordc z)
\]
to express that $x$ is an element in the bottom row.

Two elements $x$ and $y$ are in different columns iff there exists an
element in the bottom row that lies between $x$ and $y$ w.r.t.\
$<$. Thus, we can choose
\[
  \phisamecol(x,y) \ := \ \ensuremath{\neg}\exists z\ \big( \phibot(z)\ensuremath{\wedge}
    (x<z\leq y \ \ensuremath{\vee} \ y<z\leq x)
  \big).
\]
Obviously,
$q(x)=y$
iff $y$ lies in the bottom row and in the same
column as $x$. Thus, we can choose
\[
  \phiq(x,y) \ := \ (\; \phibot(y)\ensuremath{\wedge} \phisamecol(x,y)\; ).
\]
For $n\in\NN$ we say that the \emph{last column of $\dom{n}$ is full}
iff there is an $i\in\NN$ such that $n=q_i+i$. Note that
the last column of $\dom{n}$ is full iff
$n{=}0$ or the $<$-predecessor of $n$ is also the $\ordc$-predecessor of $n$ and is different from 0.
This can be expressed by the sentence
\[
\varphi_{\text{last-col-full}} \ := \ \exists z\ \big(
    z=\praedikat{max}_{<} \ \ensuremath{\wedge} \ \big(
         z=0 \ \ensuremath{\vee} \ \exists y\
           (\, y= \praedikat{pred}_{<}(z)\ \ensuremath{\wedge}\  y= \praedikat{pred}_{\ordc}(z) \ \ensuremath{\wedge}\ \ensuremath{\neg}\, y{=}0 \,)
      \big)
    \big).
\]
An element $x$ lies on the diagonal (i.e., $r(x)=c(x)$) iff either its $<$-successor lies in the
bottom row, or $x$ is the maximum element w.r.t. $<$ and the last
column is full. Thus, we can choose
\[
  \phidiag(x)\ := \ \big(
    \exists y\ (\,y=\praedikat{succ}_<(x)\ensuremath{\wedge} \phibot(y)\,) \ \ensuremath{\vee} \
    (\, x=\praedikat{max}_< \, \ensuremath{\wedge} \, \varphi_{\text{last-col-full}}\,)
  \big)
\]
to express that $x$ lies on the diagonal.

Two elements $x$ and $y$ lie in different rows iff there exists an
element on the diagonal that lies between $x$ and $y$ w.r.t.\
$\ordc$.
Thus, we can choose
\[
  \phisamerow(x,y) \ := \ \ensuremath{\neg}\exists z\ \big( \phidiag(z)\ensuremath{\wedge}
    (x\ordc z\ordeqc y \ \ensuremath{\vee} \ y\ordc z\ordeqc x)
  \big).
\]
Finally, for two elements $x$ and $y$ we have $r(x)=c(y)$ iff the
diagonal element $z$ that is in the same row as $x$, is in the same
column as $y$. Thus we can choose
\[
  \phirc(x,y) \ := \ \exists z\ (\,
   \phidiag(z)\ensuremath{\wedge} \phisamerow(x,z)\ensuremath{\wedge}\phisamecol(z,y)
   \,).
\]
This completes the proof of Lemma~\ref{lemma:aux-grid-formulas}.
\qed

\begin{lem}\label{lemma:phiQphiR}
There are $\class{FO}(<,\ordc,C,Q)$-formulas $\phiQ(x,u)$ and $\phiR(x,u)$
which, when evaluated in $\struc{\dom{n},<^n,\ordc[n]}$ for some
$n\in\NN$, express that the $r(u)$-th bit of the binary representation
of $q(x)$, respectively, of $r(x)$, is 1.
\end{lem}
\proof
Note that
if $x{=}0$, then $q(x){=}0$, and thus the $r(u)$-th bit of
the binary representation of
$q(x)$ is 0. If $x>0$, then the binary representation of the number $q(x)$ is given by
relation $Q$ on the elements of the column left to $x$'s column.\footnote{\label{fn:plusone}Here, it is helpful that the $q(x)$ is
  represented in column $c(x)-1$, as this column is guaranteed to be full.} Thus, the $r(u)$-th bit
of $q(x)$ is 1 iff an element $z$ with $r(z)=r(u)$ and $c(z)=c(x)-1$
exists and
belongs to $Q$. Therefore, we can choose
\ $\phiQ(x,u) := $
\[
    \exists y \,\exists z\, \big(
          \phisamecol(x,y) \land z {=} \praedikat{pred}_{\ordc}(y) \land
          \phisamerow(z,y) \land \phisamerow(z,u) \land
           Q(z)
    \big).
\]
The definition of $\phiQ(x,u)$ is illustrated in Figure~\ref{fig:bit}(a).
\newcommand{\punkt}[3][-45]{\psdot(#2)\uput[#1](#2){#3}}
 \begin{figure}[hbtp]
\psset{unit=0.5cm}
    \centering
    \begin{pspicture}(0,-1)(7,7)
     \rput(4,-1){(a)}
      \psline[linestyle=dashed](0,0)(7,0)
      \psline[linestyle=dashed](0,0)(7,7)
      \psline(7,5)(7,1)
      \psline(2,1)(7,1)
      \punkt{7,5}{$x$}
      \punkt{7,1}{$y$}
      \punkt{6,1}{$z$}
      \punkt[-135]{2,1}{$u$}
    \end{pspicture}
\hspace{2cm}
    \begin{pspicture}(0,-1)(7,7)
     \rput(4,-1){(b)}
      \psline[linestyle=dashed](0,0)(7,0)
      \psline[linestyle=dashed](0,0)(7,7)
      \psline(7,5)(5,5)
      \psline(5,5)(5,1)
      \psline(2,1)(5,1)
      \punkt{7,5}{$x$}
      \punkt{5,1}{$y$}
      \punkt{4,1}{$z$}
      \punkt[-135]{2,1}{$u$}
    \end{pspicture}
    \caption{Illustration of the meaning of the variables used in (a) $\phiQ(x,u)$
      and (b) $\phiR(x,u)$.%
}%
    \label{fig:bit}
  \end{figure}

Similarly, if $x{=}0$, then $r(x){=}0$, and thus the $r(u)$-th bit of
the binary representation of
$r(x)$ is 0. If $x>0$, then the binary representation of the number $r(x)$ is given by
relation $C$ on the elements of the \emph{column} of number $r(x)-1$.
Thus, the $r(u)$-th bit of $r(x)$ is 1 iff an element $z$ with $r(z)=r(u)$ and $c(z)=r(x)-1$
exists and belongs to $C$. Therefore, we can choose
\ $  \phiR(x,u) :=$
\[
   \exists y \,\exists z\; \big(\, \phirc(x,y)\ \land\
           z {=} \praedikat{pred}_{\ordc}(y)  \ \land\, \phisamerow(z,y)\land \phisamerow(z,u) \land
           C(z)\,\big).
\]
The definition of $\phiR(x,u)$ is illustrated in Figure~\ref{fig:bit}(b).
\qed

\begin{lem}\label{lemma:phiBitR}
There is an $\class{FO}(<,\ordc,C,Q)$-formula
$\phiBitR(x,z)$ which, when evaluated in
$\struc{\dom{n},<^n,\allowbreak \ordc[n]}$ for some
$n\in\NN$, expresses that the $r(z)$-th bit of the binary
representation of $x$ is 1.
\end{lem}
\proof
Recall from equation~\eqref{eq:nisqnplusrn} that $x=q(x)+r(x)$. We
construct the formula $\phiBitR(x,z)$ in such a way that it
expresses that the $r(z)$-th bit in the binary representation of
$q(x)+r(x)$ is 1.

For this, we
use an auxiliary formula
$\phiQRcarry(x,z)$ which
expresses that the addition of the binary representations of the numbers
$q(x)$ and $r(x)$ produces a carry-bit to be added at the
$r(z)$-th position.
Note that when adding two binary numbers $a_\ell\cdots a_1 a_0$ and
$b_\ell\cdots b_1 b_0$ (where the least significant bit is at the
rightmost position), a carry-bit has to be added at position $j$ iff
there is a position $i<j$ such that $a_i=b_i=1$ and for all positions
$k$ with $i<k<j$ at least one of the values $a_k,b_k$ is 1.
Thus, we can choose
\begin{multline*}
\phiQRcarry(x,z)\ := \
\exists u\; \big(\phisamecol(u,z) \ \land \ u< z \ \land \ \phiQ(x,u) \
\land \
\phiR(x,u)\\
\land \ \forall v\; (u<v<z \rightarrow (\phiQ(x,v) \lor \phiR(x,v)))\big).
\end{multline*}

Note
that the $r(z)$-th bit of the binary representation of $q(x)+r(x)$ is 1
if, and only if,
either no carry-bit has
to be added at position $r(z)$ and the $r(z)$-th bits of $q(x)$ and
$r(x)$ are different, or a carry-bit has to be added at position
$r(z)$ and the $r(z)$-th bits of $q(x)$ and $r(x)$ are the same. Thus,
we can choose
\[
\begin{array}{ll}
\phiBitR(x,z)\ := &
 \big(\ \big( \ensuremath{\neg}\phiQRcarry(x,z) \ \ensuremath{\wedge} \
 (\, \phiQ(x,z)\ensuremath{\leftrightarrow}\ensuremath{\neg}\phiR(x,z)\,) \big)\
 \ensuremath{\vee}
 \\
 & \ \ \ \big(\ \ \, \phiQRcarry(x,z) \ \ensuremath{\wedge} \ (\,\phiQ(x,z)\ensuremath{\leftrightarrow}
 \ \ \,\phiR(x,z)\,) \big) \ \ \ \ \ \big).
\end{array}
\]
\qed

\begin{lem}\label{lemma:phir}
There is an $\class{FO}(<,\ordc,C,Q)$-formula $\phir(x,y)$ which, when
evaluated in $\struc{\dom{n},<^n,\allowbreak \ordc[n],C^n,Q^n}$ for
some $n\in\NN$, expresses that $r(x)=y$.
\end{lem}
\proof
Note that $r(x)=y$ iff the following is true:
for every $u$, the $r(u)$-th bit of $r(x)$ is 1 iff the $r(u)$-th bit of $y$ is 1.
We can thus use the formulas $\phiR(x,z)$ and $\phiBitR(y,z)$ from the
Lemmas~\ref{lemma:phiQphiR} and \ref{lemma:phiBitR} to define
\[
 \phir(x,y)\ := \
 \forall u\ (\,
   \phiR(x,u) \ensuremath{\leftrightarrow} \phiBitR(y,u)
 \,).
\]
\qed

Now, the $\ensuremath{\FktsFont{BIT}}$-predicate can be expressed by the
$\class{FO}(<,\ordc,C,Q)$-formula stating that there is a number $u$ such that
$r(u)=y$ and the $r(u)$-th bit of $x$ is 1. I.e., we can choose
\[
 \phiBit(x,y)\ := \ \exists u\ (\,
   \phir(u,y) \ensuremath{\wedge} \phiBitR(x,u)
 \,).
\]
This finally completes the proof of Theorem~\ref{thm:mainwithunarypredicates}.
\qed

\section{Capturing $\class{FO}(\ensuremath{\FktsFont{BIT}})$ with Two Linear Orders}\label{section:linearorders}

In this section, we show that in
Theorem~\ref{thm:mainwithunarypredicates} the numerical predicates $\ordc, C, Q$ can be
replaced by one particular linear order.
The proof will immediately
follow by combining Theorem~\ref{thm:mainwithunarypredicates} with the
following Lemma~\ref{lem:nomonadic}.

If $R,R_1,\ldots,R_k$ are numerical predicates, we say that $R$ is definable in
  $\class{FO}(R_1,\ldots,R_k)$ \emph{in every finite prefix}  if there is an $\class{FO}$-formula that defines $R^n$ on
$(\dom{n},R_1^n,\ldots,R_k^n)$, for every $n\in\NN$.

\begin{lem}\label{lem:nomonadic}
  For all $k\geq 1$ and
  all unary relations $U_1,\ldots,U_k$ on $\NN$, there is a linear order
  $\ordb$ on $\NN$, such
  that  $\class{FO}(\ord,\ordb)$ is at least as expressive as
  $\class{FO}(\ord,\ordc,\allowbreak U_1,\ldots,U_k)$ on the class of finite structures. Furthermore, if
  $U_1,\ldots,U_k$ are $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definable in every finite prefix then $\ordb$
  can be chosen $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definable in every finite prefix as well.
\end{lem}
\proof
Within this proof, we will use the row numbers, column numbers, and
$q$-numbers defined in equation~\eqref{def:functionscrq}.
Our goal is to encode $\ordc$ and the unary predicates
into a single linear order $\ordb$.
To this end, the crucial observations are the following:
\begin{enumerate}[(1)]
\item For every number $\ell$, the order $\ordc$ can be recovered in a first-order
  fashion from $<$ and a sub-relation of $\ordc$ that orders only
  every $\ell$-th row (i.e., the rows  $0,\ell,2\ell,\ldots{}$).

\item If $\ell$ is chosen large enough with respect to some  number $m$, the remaining rows allow to
  encode $m$ bits of information per element.
\end{enumerate}

\noindent
For the given number $k$, we will choose a sufficiently large number $\ell$.
All rows whose number is a multiple of $\ell$ will be called \textit{backbone rows},
and the elements in these rows will be called \textit{backbone elements}.
In $\ordb$, the backbone elements are ordered just
as in $\ordc$, and every backbone element is smaller w.r.t.\ $\ordb$
than every non-backbone element. The number $2$ is
the smallest non-backbone element w.r.t.\ $\ordb$.
Thus, backbone elements can be identified by the $\class{FO}(<,\ordb)$-formula
\[
  \varphi_{\text{backbone}}(x)\ := \ \forall y\ (y=2 \ensuremath{\rightarrow} x\ordb y).
\]
Figure~\ref{fig:nomonadic} gives an illustration of the overall shape of $\ordb$.
\begin{figure}[ht]
  \centering
\psset{unit=0.4cm}
  \begin{pspicture}(-1,-1)(13,12)
    \psline(-1.5,-0.5)(11.5,-0.5)%
\rput(12.5,-0.5){$\cdots$}%
\psline(-1.5,-1)(10.5,11)%
\rput(11,11.7){$\adots$}%
\multido{\n=0.0+1.0}{12}{\psdot(\n,0)}
\multido{\n=0.5+1.0}{12}{\rput(\n,0){$\ordb$}}
\rput(12.5,0){$\cdots$}
\multido{\n=5.0+1.0}{7}{\psdot(\n,5)}
\multido{\n=5.5+1.0}{7}{\rput(\n,5){$\ordb$}}
\rput(12.5,5){$\cdots$}
\multido{\n=10.0+1.0}{2}{\psdot(\n,10)}
\multido{\n=10.5+1.0}{2}{\rput(\n,10){$\ordb$}}
\rput(12.5,10){$\cdots$}

\cnode*(6,1){2pt}{A}
\cnode*(6,2){2pt}{B}
\cnode*(6,3){2pt}{C}
\cnode*(6,4){2pt}{D}
\rput(6,1.5){\rotateleft{$\ordb$}}
\nccurve[arrows=->,angleA=160,angleB=200]{B}{D}\ncput*[nrot=:U,framesep=0pt]{$\ordb$}
\rput(6,3.5){\rotateright{$\ordb$}}

\cnode*(9,1){2pt}{I}
\cnode*(9,2){2pt}{J}
\cnode*(9,3){2pt}{K}
\cnode*(9,4){2pt}{L}
\rput(9,1.5){\rotateright{$\ordb$}}
\rput(9,2.5){\rotateright{$\ordb$}}
\nccurve[angleA=160,angleB=200,arrows=->]{I}{L}\ncput*[nrot=:U,framesep=0pt]{$\ordb$}

\cnode*(11,6){2pt}{E}
\cnode*(11,7){2pt}{F}
\cnode*(11,8){2pt}{G}
\cnode*(11,9){2pt}{H}
\rput(11,8.5){\rotateleft{$\ordb$}}
\rput(11,7.5){\rotateleft{$\ordb$}}
\nccurve[arrows=->,angleA=-20,angleB=20]{H}{E}\ncput*[nrot=:U,framesep=0pt]{$\ordb$}

\psset{linewidth=0.3mm,linestyle=dotted}
\psline(9,6)(9,9)
\psline(10,6)(10,9)
\psline(4,1)(4,4)
\psline(5,1)(5,4)
\psline(7,1)(7,4)
\psline(10,1)(10,4)
\psline(11,1)(11,4)

  \end{pspicture}
  \caption{Illustration of the definition of $\ordb$ with
    $\ell=5$. For the lower left interval, the corresponding
    permutation $\pi$ is given by $\pi(1)=1$, $\pi(2)=2$, $\pi(3)=4$, $\pi(4)=3$, resulting
    in $u+1\ordb u+2\ordb u+4 \ordb u+3$.}
  \label{fig:nomonadic}
\end{figure}

We call a set
$\{u{+}1,\ldots,u{+}\ell{-}1\}\subseteq\NN$
a \emph{complete interval} if $u$
and $u{+}\ell$ but none of the elements $u{+}1,\ldots,u{+}\ell{-}1$ are backbone elements. In
this case, we call $u$ \emph{complete}.
We say that $u$ is \emph{complete within $\dom{n}$} if $u$ is complete and $u{+}\ell\in\dom{n}$.
Note that
there is an $\class{FO}(<,\ordb)$-formula which, when evaluated in
$\struc{\dom{n},<^n,\ordb[n]}$ for some $n\in\NN$, expresses that
$u$ is complete within $\dom{n}$. This formula simply states that
$u$ is a backbone element, $u{+}\ell$ exists, and none of the elements $u{+}1,\ldots,
u{+}\ell{-}1$ is a backbone element.

The elements of complete intervals will be ordered in such a way
that the order $\ordb$ on every complete interval
$\{u{+}1,\ldots,u{+}\ell{-}1\}$
encodes the unary predicates on the elements
$u$, $u{+}1$, \ldots, $u{+}3\ell{-}1$.
Note that the encoding is sufficiently redundant to make sure that,
even though there are elements in intervals that are not complete
within $\dom{n}$ (i.e., elements close to the diagonal or close to
$n$), the information
whether $x$ is an element of a set $U_i$ is encoded in \emph{some}
complete interval, for every $x>q_{\ell+1}$.

To describe the order $\ordb$ on each complete interval, we use the following notation.
For every number $x\in\NN$, let $B(x)$ be the bit-string of length
$k$, where the $i$-th bit is 1 if and only if $x\in U_i$.
For every complete element $u$ we let $\vec{B}(u)$ be the
bit-string of length $3k\ell$ with
\[
   \vec{B}(u) \ := \ \  B(u)\; B(u+1) \cdots B(u+3\ell-1).
\]

We view each bit-string of length $3k\ell$ as the binary
representation of a number from the set
$\{0,1,\ldots,2^{3k\ell}{-}1\}$, and we write $b(u)$
to denote the according number associated with $u$ by the bit-string
$\vec{B}(u)$.
We choose $\ell$ large enough such that
$(\ell{-}1)!\ge 2^{3k\ell}$. Such an $\ell$
exists, since $n!=2^{\Theta(n\log n)}$ (cf., Stirling's formula) and thus
$(\ell{-}1)!=2^{\Theta(\ell \log \ell)}$, and hence $(\ell{-}1)!\ge
2^{3k\ell}$ for all sufficiently large $\ell$.
Note that by our choice of $\ell$ we
have $0\leq b(u) \leq (\ell{-}1)!-1$, for every complete element $u$.

Let $\pi_0,\ldots,\pi_{(\ell-1)!-1}$ be an enumeration of all permutations
of the set $\{1,\ldots,\ell{-}1\}$.
Now, the elements of every complete interval $\{u{+}1,\ldots,u{+}\ell{-}1\}$
are ordered in $\ordb$ according to $\pi_{b(u)}$ via
\[
  u+\pi_{b(u)}(1)  \ \ \ordb \ \
  u+\pi_{b(u)}(2)  \ \ \ordb \ \
  \cdots \ \ \ordb \ \
  u+\pi_{b(u)}(\ell{-}1).
\]
Note that it is straightforward to construct, for every permutation
$\pi$ of $\set{1,\ldots,\ell-1}$, an $\class{FO}(<,\ordb)$-formula
$\varphi_\pi(u)$ which,
when evaluated in $\struc{\dom{n},<^n,\ordb[n]}$ for some $n\in\NN$,
expresses that $u$ is complete within $\dom{n}$ and the interval
$\{u{+}1,\ldots,u{+}\ell{-}1\}$ is ordered
w.r.t.\ $\ordb$ according to $\pi$.

How
elements that do not belong to complete intervals, and
how
elements of different intervals, relate in $\ordb$ does not matter for
our proof. For concreteness, to fully fix $\ordb$, we choose to
let
\[
  x\ordb y \ \iff \  x<y
\]
for all natural numbers $x,y$ for which the relationship has not yet been
defined (neither directly nor transitively).

It remains to verify that
\begin{enumerate}[(a)]
\item the predicates $\ordc$, $U_1,\ldots,U_k$ are
  $\class{FO}(<,\ordb)$-definable in every finite prefix, and
\item $\ordb$ is $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definable in every finite prefix, provided that the unary
  relations $U_1,\ldots,U_k$ are $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definable in every finite
  prefix.
\end{enumerate}

Towards (a), we can use the formulas $\varphi_\pi(u)$ to construct, for every
$U_i\in\set{U_1,\ldots,U_k}$, an
$\class{FO}(<,\ordb)$-formula $\varphi_{U_i}(x)$ that, when evaluated in
$(\dom{n},<^n,\ordb[n])$ for some $n\in\NN$, expresses that $U_i(x)$
holds.
Note that either $x< q_{\ell+1}$ or $x=u+j$ where $u$ is an element
complete within $\dom{n}$ and $0\leq j<3\ell$.
In the former case,  the information whether
$U_i(x)$ holds can be ``hard-coded'' into
an $\class{FO}(<,\ordb)$-formula, as $q_{\ell+1}$ is a constant. In the latter
case, the information whether
$U_i(x)$ holds, can be inferred from the particular
permutation $\pi$ for which $\varphi_\pi(u)$ holds.

To express the predicate $\ordc$ by an $\class{FO}(<,\ordb)$-formula, we use that,
for all $x,y\in\NN$, we have
$x\ordc y$  if, and only if,
$x=u+i$ and $y=v+j$ where
$u,v$ are backbone elements and $0\leq i,j <\ell$, such that
the following is true:
\begin{enumerate}[(i)]
 \item
   $r(u)<r(v)$, \ or
 \item
   $r(u)=r(v)$ \ and \ either $i<j$ or ($i=j$ and $u\ordb v$).
\end{enumerate}
We note that, for backbone elements $u$ and $v$, we have $r(u)<r(v)$
iff
there is a backbone element $w$ that is the
rightmost element in its row, and $u\ordeqb w \ordb v$. Furthermore, a backbone
element $w$ is rightmost in its row if either it is the maximal backbone element w.r.t.\ to
$\ordb$ or its $\ordb$-successor $w'$ is a backbone element on the
diagonal. The latter can be recognized by the fact that $w'$ and
$w'+1$ are backbone elements.
We can use this to
obtain a formula $\varphi_{\ordc}(x,y)$ expressing that $x\ordc y$.
This concludes (a).

For proving (b) it suffices (due to Theorems~\ref{thm:FOBit} and
\ref{thm:mainwithunarypredicates}) to show that $\ordb$ is
$\class{FO}(\ensuremath{\FktsFont{BIT}},\ordc,U_1,\allowbreak \ldots,U_k)$-definable in every finite prefix.
 First of all, it is easy to
identify the backbone rows. Furthermore, it is straightforward (though
tedious) to infer $b(u)$ for a complete element $u$ provided that
$u+3\ell-1\leq n$.
To infer $b(u)$
for (the at most two) complete elements $u$ with $u+3\ell-1> n$, we use the
fact that, for every $\class{FO}(\ensuremath{\FktsFont{BIT}})$-formula $\psi(x)$ and every $i\in\NN$
one can construct an $\class{FO}(\ensuremath{\FktsFont{BIT}})$-sentence $\psi_i$ such that
$(\dom{n},\ensuremath{\FktsFont{BIT}}^n)\models\psi_i$ if and only if
$(\dom{n+i},\ensuremath{\FktsFont{BIT}}^{n+i})\models\psi(n+i)$.
\qed

From Theorem~\ref{thm:mainwithunarypredicates},
Lemma~\ref{lem:nomonadic} and the fact that the predicates $C$ and $Q$
are $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definable in every finite prefix, we immediately obtain the
main result of this article.
\begin{thm}\label{thm:MainThm-linearorders}
 There is a linear order $\ordb$ on $\NN$ such
  that  $\class{FO}(\ord,\ordb)$ has the same expressive power as
  $\class{FO}(\ensuremath{\FktsFont{BIT}})$ on the class of all finite structures.
\end{thm}

Using Theorem~\ref{thm:MainThm-linearorders}, one also obtains
the analogous result, where the
linear order $\ordb$ is replaced by a built-in permutation
$\pi=(\pi^n)_{n\in\NN}$, that associates, with every $n\in\NN$, a
permutation $\pi^n$ on the set $\dom{n}$.

\begin{cor}\label{cor:permutation}
There is a built-in permutation $\pi$ such that
$\class{FO}(<,\pi)$ is as expressive as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.
\end{cor}
\proof
 Let $\ordb$ be the linear order from
 Theorem~\ref{thm:MainThm-linearorders}.
 For every $n\in\NN$ we define $\pi^n$ as follows: For every
 $i\in\dom{n}$ let $\pi^n(i)$
 be the \emph{index} of $i$ w.r.t.\ $\ordb$, i.e.,
 $\pi^n(i) :=  |\setc{j\in\dom{n}}{j\ordb i}|$.
 Then, for all $i,j\in\dom{n}$ the following is true:
 \[
    i\ordb[n] j
    \ \iff \
    \pi^n(i)\ \ord[n]\ \pi^n(j).
 \]
 Hence, $\ordb$ is definable by the $\class{FO}(<,\pi)$-formula
 $\varphi_{\ordb}(x,y) := \pi(x)\,{<}\,\pi(y)$.
 Therefore, due to Theorem~\ref{thm:MainThm-linearorders},
 $\class{FO}(<,\pi)$ is at least as expressive as $\class{FO}(\ensuremath{\FktsFont{BIT}})$.

 For the opposite direction, we need to find an $\class{FO}(\ensuremath{\FktsFont{BIT}})$-formula
 $\varphi_{\textup{index}}(x,y)$ which expresses that $y$ is the index
 of $x$ w.r.t.\ $\ordb$, i.e., $y=\pi^n(x)$. Using our particular
 choice of the linear order $\ordb$ fixed in the proof of Lemma~\ref{lem:nomonadic}, is not difficult
  to construct $\class{FO}(\ensuremath{\FktsFont{BIT}})$-formulas which
 express that
 \begin{iteMize}{$\bullet$}
 \item $z$ is the total number of backbone elements,
 \item $y$ is the number of backbone elements that are smaller w.r.t.\ $\ordb$
 than  some backbone element $x$, and
\item $y'$ is the number of non-backbone elements that are smaller
  w.r.t.\ $<$ than  some backbone element $x'$.
 \end{iteMize}
With the help of these formulas the formula
$\varphi_{\textup{index}}(x,y)$ can be constructed. To work out the
 details on the precise definition of this formula is a tedious, but
 easy exercise on $\class{FO}(\ensuremath{\FktsFont{BIT}})$-definability.
\qed

Let us note that \cite{Schwentick_CSL97} already
exposed a built-in unary function $f$ such that $\class{FO}(<,f)$
has the same expressive power as $\class{FO}(\ensuremath{\FktsFont{BIT}})$ (see the proof of
Theorem~3 in \cite{Schwentick_CSL97} --- the additional predicate for
multiples of 8 can easily be encoded into $f$). The function $f$
obtained there, however, is not a permutation.

\section{Preliminaries}\label{section:preliminaries}%

We write $\NN$ to denote the set $\set{0,1,2,\ldots}$ of all natural
numbers. For each $n\in\NN$ we
write $\dom{n}$ for the set $\set{0,.\,.\,,n}$ of all natural numbers
of size up to $n$.
We assume that the reader is familiar with \emph{first-order logic}
($\class{FO}$, for short), cf., e.g., the textbook \cite{Libkin-FMT}.

A \emph{$k$-ary numerical predicate} is a relation $P\subseteq\NN^k$.
Particular numerical predicates that were mentioned in the
introduction are
\begin{align*}
  < &:=  \setc{\, (a,b)\in\NN^2\, }{\, a<b\, },\\
  + &:=  \setc{\, (a,b,c)\in\NN^3\, }{\, a+b=c\, },\\
  \times &:=  \setc{\, (a,b,c)\in\NN^3\, }{\, a\cdot b=c\, },\\
  \praedikat{Squares} &:= \setc{\, a\in\NN\, }{\, \text{there exists a }
    b\in\NN \text{ such that } a=b^2\, },\\
  \praedikat{Exp} &:= \setc{\, (a,b,c)\in\NN^3\, }{\, a^b=c\, },\\
  \ensuremath{\FktsFont{BIT}} &:= \setc{\, (a,i)\in\NN^2\, }{\, \text{the $i$-th Bit in the
      binary representation of $a$ is 1, i.e. }
         2 \nmid{\textstyle\abgerundet{\frac{a}{2^i}}}\, }.
\end{align*}
A \emph{$k$-ary built-in predicate} is a sequence
  $(R^n)_{n\in\NN}$ of
  relations, where, for each $n\in\NN$,  $R^n\subseteq \dom{n}^k$.
Clearly, every $k$-ary numerical predicate $P$ naturally induces a $k$-ary built-in predicate
via $P^n := P \cap \dom{n}^k$.
Note that if $P$ is a strict linear order on $\NN$ (i.e., $P\subseteq\NN^2$ is
transitive, and for all $a,b\in\NN$ we have either $a{=}b$ or $(a,b)\in P$
or $(b,a)\in P$), then $P^n$ is a strict linear order on $\dom{n}$,
for every $n\in\NN$.

redpajama_set_name: RedPajamaArXiv


text:
Contact the Hounds
Bob Hart
Geoff Hook
Geoff Poulter
Lawrence Money
Peter Coster
Scot Palmer
Steve Cooper
Terry Brown
Brian Meldrum
Cheryl Critchley
Chris de Kretser
Colin Duck
Dan Eddy
Geoffrey Harris
Ian Callen
John Trevorrow
Mark Harding
Peter Krien
Phil Burfurd
Rhett Kirkwood
Rod Nicholson
Simon Schneider
Steve Perkin
Wayne Ludbey
No forgetting the missing medals
Published 1 week ago - Ron Reed - 1w ago 4
Old Bombers John Birt and Barry Davis relive the glory days.
HE ACHIEVED everything there was to achieve in football with one exception – and even then old Bomber Barry Davis might have been dudded, says Chief Writer RON REED:
THE list of footballers who "coulda, shoulda, woulda" won a Brownlow medal is a long and illustrious one, and there's even a shorter list of players who probably should have won it more often than they did. At Essendon, they have a couple of such stories from the fairly distant past, which they haven't forgotten and probably aren't likely to.
If their recollections are accurate, then the Bombers were indeed robbed on a couple of occasions. Essendon has eight Brownlows but only five winners because Dick Reynolds won their first three, Bill Hutchison the next two, followed by Graham Moss, Gavan Wanganeen and James Hird.
They continue to claim that Hutchison should have three, and that Barry Davis should have one.
Davis was philosophical about this when, accompanied by his old team-mate and coach John Birt, he spoke at the fortnightly Friday lunch hosted by former Carlton star Percy Jones at the North Fitzroy Arms pub.
He didn't bring it up himself, but Birt recalled that in 1969 Davis played a blinder against Fitzroy, his best game of the season and, according to the coach then, Jack Clarke, one of his best ever – but got only two votes from the umpire. The three votes went to the old Lion, Kevin Murray, who Birt and Davis agree, played OK but was far less influential.
When the votes were tallied at the end of the season, Murray prevailed with 19, one more than Davis and Footscray's George Bissett. If Davis had got the three and Murray the two, the result would have been reversed.
Hutchison's misfortune is a more incredible story. In 1955 he was runner-up by one vote to South Melbourne full-back Fred Goldsmith, 21 to 20. But when Essendon played the Swans at Windy Hill on June 4, their versatile champion Hugh Mitchell played on Goldsmith and kicked 9 goals 6 behinds out of a team score of 13.14, and yet Goldsmith somehow got the three votes without which he would not have beaten Hutchison to the medal.
When I put it to Birt that this simply didn't ring true – that perhaps Mitchell was performing his usual role as a ruck-rover and not the spearhead, where he would have been Goldsmith's direct responsibility, he shrugged and insisted that was how it happened.
If so, for bad luck – or weird umpiring – it rivals the sorry tale of Carlton's Greg Williams, who lost his third medal by a vote to Wanganeen in 1993 despite not getting a vote in a match in which he had more than 40 possessions and kicked three goals. So perhaps that was one the Gods gave back to Essendon.
The medal is about the only accolade missing from Davis's spectacular cv. Now 75 but looking 20 years younger, he played 218 games for Essendon, 71 for North Melbourne and 11 for Victoria, won three best and fairests for his first club and two at his second, played in two premierships for Essendon and captained North to its first one, coached Essendon for three years, was named in both clubs' team of the century and is in the AFL Hall of Fame.
He was also a handy club cricketer, who played in the most famous District match ever, the 1965-66 final when Essendon declared at 9-514 only for Bill Lawry to bat for three days for 282 not out to win the game for Northcote. Davis made 61 batting at No 8 and claims he had Lawry caught off his off-spinners but given not out
Birt claims Davis was indirectly responsible for him getting the sack as coach after just one season because, having been told he needed to win the last two games against South Melbourne, which was duly done, and Footscray, he controversially took his captain out of the backline and put him on to the ball, where he kicked one goal nine as the Bombers lost by five points.
However, that turned out to be academic because Birt later learned that the club had been negotiating since halfway through the season for Collingwood's Des Tuddenham to take over as captain-coach.
When Tuddenham arrived, Davis took him for a coffee and gave him a sheet of paper critiquing every player's strengths and weakness and best positions. "He looked at it and said, 'Great,' and then screwed it up and threw it in the nearest bin," Davis said.
The relationship did not improve when Tuddenham told Davis he would no longer be playing on the ball, where he had been starring for years, but would return to the backline where he had played his early footy. "That wasn't good," Davis said.
It got infinitely worse when the new boss famously ordered the players to crawl two laps of the oval on their hands and knees at Sunday morning training, saying, "If you play like babies, you'll train like babies."
"It was a terrible thing to do," said Davis, who along with other senior players complained to the committee, saying they wouldn't put up with "this rubbish".
Before long, both men were gone – Tuddenham back to Collingwood, Davis to North, where he had a more enjoyable and productive relationship with the coaching doyen Ron Barassi, even persuading the great man to give up smoking.
As for Tuddy, "I actually came to like him later in life," he said. Which is probably true of most people who have ever had much to do with the old Magpie firebrand.
Author: Ron Reed
RON REED has spent more than 50 years as a sportswriter or sports editor, mainly at The Herald and Herald Sun. He has covered just about every sport at local, national and international level, including multiple assignments at the Olympic and Commonwealth games, cricket tours, the Tour de France, America's Cup yachting, tennis and golf majors and world title fights.
RON REED has spent more than 50 years as a sportswriter or sports editor, mainly at The Herald and Herald Sun. He has covered just about every sport a... More »
ShareTweetShare on Google+Pin on PinterestSend with WhatsApp
ShareTweetSharePin it
#AFL
Bookmark?Remove?
Bettser than all the rest
Published 1m ago - 11 bookmarks
Lions crippled by a Kouta clone
No good reason to hijack history
Published 1m ago - 8 bookmarks
Another Blues boss bites the dust
Wow's the word for the wild young tyros of Formula One July 16th, 2019
Kiwis the unluckiest losers ever July 15th, 2019
A Test of faith for cricket fans July 12th, 2019
Big wheels hot to trot July 9th, 2019
No forgetting the missing medals July 8th, 2019
So Grand to get real racing again July 2nd, 2019
Kiwis the unluckiest losers ever
Published 2d ago - 0 bookmarks
A Test of faith for cricket fans
Wow's the word for the wild young tyros of Formula One
Unsmiling Russia, a great place for a soccer game
Published 1y ago - John Craven
THE World Cup drew fans from all around the world, including a father and son from Geelong. JOHN CRAVEN tells what it was really like to be there in Russia. More »
How a Swan swam off to the Tigers
Published 2y ago - Greg Thom
HE LIVED through the pain of supporting the wrong side when the Tigers were tearaways at the top, now he finds himself in the right camp at last. GREG THOM tells of his conversion to the Tiger faith: I'VE BEEN a Richmond supporter for 22 years. Which may seem ... More »
Sportshounds
© 2019. Sportshounds. All rights reserved. Powered by The Image Vision Group
We use cookies!
By using this site you agree to the use of cookies, more info.

redpajama_set_name: RedPajamaCommonCrawl


text:
Are you a supplier looking for North American distribution?
Nutraceuticals &
CTCFineChem Solutions
Our Entities
Nutraceuticals & Food Additives
CTCMining Solutions
Raising the Standards of Performance and Sustainability through Chemical Innovation.
CTC Vision and Commitment
Better chemistry for our customers and the environment.
Our facility remains attentive to new manufacturing innovation. TC China fully automates three phases of xanthate production and dithiophosphate production. We continue to explore innovative manufacturing technologies to promote production efficiency and product stewardship.
We strive to grow our business while reducing our environmental footprint and having a positive impact on climate protection. Our team is dedicated to optimise daily operations and remains committed on continously exploring new ways to deliver more sustainable solution.
Dedicated to the safety of people and the environment.
As a company, we share the heritage that brought on the birth of the chemical industry in the 18th century. Since then, the world has come to realize the industrial impact on our planet. Today, CTC is dedicated to the safety of people and the environment, both at our manufacturing site and for the customers we serve.
Our mission is to invest in people and assets for sustainable growth and to uphold the principles of responsible chemical management. We are committed to constantly improving our chemistry and physical process towards lower emissions. On the distribution level, we offer renewable and sustainable options to our customers whenever possible. To serve the increasing market demand for "green" products, we promote reducing the carbon impact of new ingredients as well as making a positive impact on biodiversity both up and downstream of the value chain.
As a founding member of the Responsible Distribution® Canada (RDC), CTC is dedicated to regulatory excellence, environmental accountability, and adherence to the responsible distribution code of practice. We follow rigorous regulatory practices and QA to protect the suppliers and customers.
Diverse and inclusive community of highly skilled chemical professionals.
Since 1932, our privately owned company focuses on what is at the heart of its business: people.
We, at CTC, are well aware that much of our value lies in the long-lasting partnerships we have developped. With trusted suppliers and customers accross the globe, but also internally, with our employees.
Following the Canadian value of inclusion and respect for diversity at home and abroad, CTC is proud to be a diverse and inclusive workforce. We strongly believe in equal opportunities for all, encourage inclusivity and oppose discrimination in all aspects of our business. We support STEM education for all and promote equal opportunity to pursue - and thrive in - STEM careers.
As a company, CTC is committed to creating an environment where business is conducted as a genuine partnership and where integrity and growth are paramount in our thinking.
In engagement with our values, we adhere to and implement ethical labour practices as well as internationally recognized human rights standards in our organization.
Distribute with Us
We find solutions for companies of every size, from startups to global brands. If you're looking for a tailored solution or a reliable distribution partner in North America, get in touch.
Our representative will get back to you within 2 to 3 working days.
Tennant&
About UsOur HistoryOur VisionContact Us
MiningPersonal CarePharmaceuticalsIndustrialNutraceuticals &
Food AdditivesProduct FinderSolutions by MarketSign Up / Log In
CTCMiningCTCFineChem
We never give your information to 3rd party. View our privacy policy and terms of use.
All rights reserved. © 2022 CTC


Important news for collectors or wargamers using figures from these two manufacturers.
Wodensfield 20mm Seven Years War French figures will be available as a 36 piece set from the same source at the end of February.
There will be a small number of additional figures released for the Les Higgins English Civil War and Marlburian ranges shortly, and the Douglas Miniatures Crimean Range are currently being mastered.
Along with the efforts of Rob at Garrison and Angel at NapoleoN, this promises to be something of a Golden Age for the availability of new casts of old ranges.
That's great news - the Crimean range is particularly tempting.


Federal and state statutory and regulatory requirements affecting California transportation systems, including transportation planning and funding law; and government contracting, environmental, and civil rights requirements.
Crosslist: This course is offered by the CE department but may qualify for major credit in PPD. To register, enroll in CE 579.


text:
Victoria J Brill: "tell me, again" solo exhibition
Pencil on Paper Gallery
07JAN 2023 - 18FEB 2023
2023-01-07 09:00:00 2023-02-18 17:00:00 America/Chicago Victoria J Brill: "tell me, again" solo exhibition //artandseek.org/calendar/event/115580/victoria-j-brill-tell-me-again-solo-exhibition Pencil on Paper Gallery, 4755 Algiers Street, Suite 100, Dallas, TX, 75207
tell me, again.
A request for clarity, reassurance, or renewed familiarity for fear of forgetfulness. In her first solo exhibition since 2018, victoria j brill explores the power of personal and generational storytelling and the transience of memory.
All history becomes subjective. What truths are chosen to be held tightly, and what is lost to time, can have a profound effect on one's identity. As each moment is interpreted through our own lens of experience and understanding, we connect new strands of information to the web of our personal story. With reflections of herself as companions, brill grapples with the mutability of memory and her identity under construction.
This deeply personal body of work transforms the artist's likeness into multitudes, creating a series of imagined moments. They surround and mirror each other, all engaging in quiet conversation with their own reflection. These luminous, larger-than-life, and often in-flux echoes hold, lean on, and look after one another as the artist pulls apart her understanding of herself and her place in the real and possible. With eyes closed, lids fluttering, glancing downward or off into the distance, brill's figures evoke moments of quiet felt while recalling the past and considering the next move forward.
These reflective works remind us all to consider and honor who we are, what we've survived and where we've come from.
Official Site Facebook Instagram
Find This Event 4755 Algiers Street · Suite 100 · Dallas, TX 75207


text:
How to use the Navigator
Add/change Profile
Research Facilities Navigator
Universities/Colleges/Hospitals
(-) Bishop's University (1)
Brandon University (6)
British Columbia Institute of Technology (1)
Brock University (1)
Canadian Museum of Nature (1)
Cape Breton University (3)
Carleton University (11)
Cégep de Chicoutimi (1)
Cégep de l'Abitibi-Témiscamingue (1)
Cégep de la Gaspésie et des Îles (1)
Cégep de Lévis-Lauzon (1)
Cégep de Shawinigan (1)
Cégep de Thetford (1)
Cégep de Trois-Rivières (1)
(-) Cégep de Victoriaville (2)
Centennial College (1)
Collège d'Alma (1)
(-) Dalhousie University (4)
École Polytechnique de Montréal (2)
George Brown College (2)
Grande Prairie Regional College (1)
HEC Montréal (1)
Holland College (1)
La Cité collégiale (1)
Lakehead University (2)
Lambton College (1)
McGill University (5)
McMaster University (3)
Memorial University of Newfoundland (6)
Mount Allison University (2)
Niagara College (2)
Nova Scotia Community College (1)
Olds College (5)
Ontario College of Art and Design University (OCAD University) (1)
Queen's University (7)
Red River College of Applied Arts Science and Technology (2)
Royal Military College of Canada (1)
Ryerson University (1)
Saint Mary's University (4)
Simon Fraser University (7)
Sir Sandford Fleming College (1)
Southern Alberta Institute of Technology (1)
The Hospital for Sick Children (3)
The Northern Alberta Institute of Technology (NAIT) (3)
The Ottawa Hospital (2)
The University of British Columbia (19)
The University of Western Ontario (4)
Thompson Rivers University (2)
Trent University (2)
Université de Moncton (1)
Université de Montréal (5)
Université de Sherbrooke (2)
Université du Québec - Institut national de la recherche scientifique (INRS) (6)
Université du Québec à Montréal (4)
Université du Québec à Trois-Rivières (1)
Université du Québec en Abitibi-Témiscamingue (2)
Université Laval (10)
University Health Network (5)
University of Alberta (11)
University of Calgary (3)
University of Guelph (7)
University of Lethbridge (1)
University of New Brunswick (2)
University of Northern British Columbia (1)
University of Ottawa (16)
(-) University of Prince Edward Island (1)
University of Regina (1)
University of Toronto (30)
University of Victoria (3)
University of Waterloo (5)
University of Windsor (3)
Wilfrid Laurier University (1)
Sector of Application
Aerospace and satellites (4)
Arts and cultural industries (2)
Chemical industries (2)
Clean technology (6)
Construction (including building, civil engineering, specialty trades) (1)
Defence and security industries (1)
Energy (renewable and fossil) (4)
Forestry and forest-based industries (3)
Healthcare and social services (7)
Information and communication technologies and media (3)
Life sciences, pharmaceuticals and medical equipment (6)
Management and business related services (1)
Manufacturing and processing (5)
Mining, minerals and metals (1)
Ocean industries (8)
Policy and governance (3)
(-) Agriculture, animal science and food (6)
(-) Environmental technologies and related services (5)
Search "ALL"
Ocean Tracking Network (OTN)
Global marine and freshwater animal tracking and oceanographic monitoring, technology development, data and networking platform
Laboratory of Applied Multiphase Thermal Engineering (LAMTE)
Research in Thermal Fluids, with an emphasis on thermal storage (phase change materials) renewable energy and applied heat transfer (electronics cooling, temperature management and control, etc.)
Climate and Environmental Change Research Laboratory
Research on climate and environmental change, using geological proxy evidence.
Centre of Expertise and Transfer in Organic and Local Agriculture (CETAB)
The team of advisors and researchers at CETAB+ is engaged in organic farming development for companies in this quickly sprouting industry.
Mass spectrometry-based analytical laboratory providing proteomic, metabolomic and lipidomic services in medical and biological sciences
Health and Environments Research Centre [HERC] Laboratory
Research on aerosol science, toxicological impacts of airborne particles on human health, risk assessment of air quality on human health, research and technology development on the implications of climate change for human health and society.
Low environmental impact industrial finishing laboratory
Industrial finishing process research (application, drying, characterization and efficiency)
Biomedical Optics Research Lab
University of Prince Edward Island
Research on novel methods for disease detection and cancer management
The Research Facilities Navigator is an initiative of
Contact the NavigatorPrivacy notice


text:
Macarons vs. macaroons
They sound alike but they're not the same
French macarons are undeniably one of the most beautiful and delicious baked goods. These meringue and almond pastries are a must-have for weddings, everyday occasions, or just to indulge. Macarons are uniquely attractive desserts because of their large variety of colors and flavors. However, despite their rising popularity, there's still some confusion about the difference between macarons and macaroons. Yes, they sound alike, but they're not the same!
Let's clear up some of the differences between those two iconic baked goods.
Most people tend to pronounce them wrong or confuse them, so we're gonna clarify it once and for all.
Pronounced: Ma-kr-aans
Pronounced: Ma-kr-oons
Their ingredients are also different.
A macaron is a sweet meringue-based sandwich-like pastry and a macaroon is a lightly-baked coconut cookie. They both share one key component: whipped egg whites. Beyond that, they are totally different. To better understand what they are made of and why, let's go back in time.
Both words originate from the Italian word maccherone, meaning fine dough.
It all started with an almond paste in Italy around the year 1500. At that time, it was a simple treat, without colors or varied flavors. From Italy, they went to France through the influence of Catherine de Medici, Italian by birth who married Duke Henri de Orleans. In 1660, both desserts were prepared for fairs and special events. Thanks to these events, macaroons became popular and different versions of the cookie were developed in different parts of France, conquering the palates of the aristocracy.
Macaroons were made plain and as a single-side crunchy cookie until 1830, when it began to be the macaron—with one 'o—we all know and love, with two cookies as a kind of sandwich. The inside was filled with jam, spiced butter, or ganache. Since then, they have been a resounding success worldwide. Not only for its sweet taste but also for their unmatched aesthetics.
Made in different varieties of colors and flavors (like Blueberry Cheesecake, Espresso Macchiato, or Birthday Cake), they're one of the most photogenic pastries and have turned into Instagram "stars". Whether it's a single macaron to enjoy with a cup of tea or a pyramid for a party, they definitely are an eye-pleaser, and they make everything around them shine. Whichever pastry you prefer, both macarons and macaroons help us enjoy the sweeter side of life in every bite.
Macarons vs. Macaroons: What's the Difference?
Historia de los macarons: las galletas francesas de colores
Where Do Macaroons Come From? You'll Never Guess!
Macarrón (galleta)


Mystic, CT, March 21, 2019 --(PR.com)-- Michael Whitehouse, author of the book on business networking, "The Guy Who Knows a Guy," has just launched "The Guy Who Knows A Guy Podcast" to help non-profits and entrepreneurs build their networks. His first four podcasts feature digital marketing, business writing, health and accounting experts who will be teaching workshops at the Southeast Connecticut Business Conference on April 25 in Mystic, Connecticut.
"They say it's not what you know, it's who you know, and it's true that a network is one of your most important assets. A network is not something you're born with. It's something you build," says Whitehouse. Every week, Whitehouse will interview entrepreneurs from southeast Connecticut to share their expertise. He'll also answer listener questions on networking, sales, marketing and entrepreneurship. Episode 2 is now available for download on several platforms. Guest Lisa Saunders, editor and writing coach, discusses the credibility and free publicity gained when an entrepreneur authors a book. In Episode 1, Karen Etchells of Innovast Digital Marketing, explains what to consider when launching an effective digital marketing strategy.
Whitehouse, the publisher of the monthly print magazine, Groton-Mystic Neighbors, also writes articles to help non-profits and businesses expand their audiences. People can sign up for his free e-newsletter, which includes an expansive list of upcoming networking events in southeastern Connecticut, his latest "The Guy Who Knows A Guy Podcast" and links to his articles such as "6 Keys to Writing A Non Profit Spotlight," by writing to him at: michael@guywhoknowsaguy.com.
Thurs., April 25, 8 a.m.–4 p.m.
Location: Enders Island, Mystic, Conn.
Whitehouse is available for talks and workshops on networking for beginners and advanced alike. Visit: www.guywhoknowsaguy.com or contact him at: michael@guywhoknowsaguy.com, 203-707-1245. Whitehouse of Groton, Connecticut, is the publisher of the monthly print magazine, Groton-Mystic Neighbors, founder of The Crisis Control Group and Vice President of the Groton Rotary Club. In his book, "The Guy Who Knows a Guy," Whitehouse shares simple techniques to build a network in a new community that anyone can learn.


The continued massive growth in tourism worldwide is placing unprecedented pressure on destinations. Alarming reports of overtourism have highlighted the serious negative impacts that tourism can have on people's lifestyles, natural habitats and wildlife, historic sites and essential resources such as water and energy.
Tourism, however big or small, brings both positive and negative impacts to destinations. What 'overtourism' highlights is that without careful planning, negative impacts can quickly prevail as tourism grows. This can eventually degrade the destination and lead to the destruction of its assets. But with good destination management, tourism can continue to bring economic rewards for the long term, supporting jobs and employment for local people, as well as funds for conservation.
Our new report, 'The Invisible Burden of tourism' has highlighted that destination managers need new skills and resources to meet this challenge.
Understand the impacts of tourism specific to their destination and its assets.
Identify the type of tourism and market sector(s) that bring the greatest benefits.
Assess the socio-economic and environmental risks of tourism and their management priorities.
Build capacity so that destination managers are equipped to support sustainable tourism aims.
Find out more with our new report, the 'Invisible Burden of tourism' and other resources below.
This video explains the 'invisible burden' of tourism on destinations.
A major study conducted with PwC into the impacts of tourism in Cyprus.
In Croatia, local business owners were involved in tourism development, leading to a much more inclusive and beneficial sector.
Our research report into how to optimise tourist spend in the local economy, based on findings from Cyprus and Tenerife.


Medigap is a Medicare Supplement company that helps match customers that are eligible for Medicare with the correct insurance plan to meet their needs. With a countless number of insurance policies available to Medicare members alone, it can be difficult to find the right one for you. Medigap makes sure you are matched with the right insurance policy and that you have a policy that matches your personal budget. This is important because everyone is unique and what works for one client may not necessarily work for another. They also educate the individual on the different options that they can choose from so they can make a good, sound decision on the plan that is right for them.
These services are also handled by specialists that are dedicated to making it easier to find what you are looking for at a rate that fits into your budget. There is no obligation to choose this company if you feel they are not right for you. However, there are not many plans or companies that take out the time to make sure the customers are satisfied and have what they need in the process.
Our job does not stop there, we are also committed to making sure caregivers, as well as family members are properly educated as well. It is imperative that they know and understand this valuable information just in case an emergency should arise. We have found that educating the people around the individual has great rewards and benefits. it allows them to understand their client or family member better and may allow them to assist in providing us with needful information that may slip the individual's mind.
You must qualify for Medicare and have Medicare Part A and B. This is not a stand alone policy. Medigap gives additional coverage to your Medicare policy. The percentage we pay depends on the policy you choose. Most of the time Medicare will cover at least 80% and you will be responsible for the remaining 20%. This percentage can be high depending on the cost of your medical services. Therefore, a Medicare Supplement plan, such as Medigap, can help with this cost.
There are several ways to be eligible for Medicare. For most people, once they turn 65 years old, they are eligible for Medicare. However, you only have one chance to apply, which is a total of seven months. The time you can apply is three months before you start your Medicare policy up to three months after you start. This is the time that you should shop around for a Medicare Supplement policy.
You can also apply for Medicare if you have been legally disabled for at least 24 months. However, this is not offered in every state. If you fall into this category, you will need to check to see if your state offers it. They will also get another chance to enroll when they turn 65 years old.
There are several things that you should be aware of when choosing Medigap. They are listed below.
Since this is a supplement policy, you will be paying a premium to Medicare in addition to a premium for your supplement policy.
These are individual plans and only covers one individual. However, your spouse can get a separate policy if he or she wishes to do so.
These policies are renewable regardless of any health issues that you may have at the time. We are unable to cancel your policy due to these circumstances as long as you are making your regular payments or premiums as agreed upon in your contract with the company.
Medigap does not include prescriptions and there are not currently any plans that cover them. If you would like to have prescription coverage, you will need to apply for Medicare Part D in order to have prescription drug coverage.
There are several ways for you to apply for a Medicare Supplement policy, such as Medigap. You can contact us on the phone or fill out the information requested in order to get a quote from us. We are here to make sure you understand all of your options so that you can make the best decision for your personal needs. You can also contact one of our licensed specialists if you need additional information or have questions about Medigap and the different plans offered.
It would be our pleasure to assist you in finding the right policy for you as we pride ourselves in making sure our customer's needs are met and that they have a plan that fits their individual requirements. We know that choosing the right plan can be a challenging task, but we are here to help.
Feel free to contact us using or contact form here.


ACE: Kandanga Tennis Club's Matthew Thompson, Rose Flower, Eli Gurnett and Mark Flower ready to put into action what they learnt from the JDS.
Tennis: Four players from the Kandanga Tennis Club took the first step in their careers competing for the first time in the Junior Development Series.
Matthew Thompson, Rose Flower, Eli Gurnett and Mark Flower travelled to Mooloolaba last Sunday competing against about 40players from across the Sunshine Coast region.
Club treasurer Steve Banney said the standard was high but these kids would take a lot from this.
"Kandanga is a small club and these players have gotten a lot of experience competing in this competition," he said.
"Unfortunately there were no winners from our club but they still had a lot of fun playing on the synthetic grass courts."
The JDS is held across the regions of Queensland and players from beginner to intermediate are given the chance to hone their skills.
This series is designed to give players their first experience in playing a series of tournaments throughout the year.
Players receive points for each competition they play in and they can then be picked for a major tournament held at Rockhampton.
"It was an eye-opener for our players to see how far they can progress with their tennis," he said.
"They received exposure to an outside competition and play against a range of different players.
"Hopefully there is a JDS program held at Gympie where we can enter more players."
Banney said the kids at the club were being trained by Rob Schmitt every Wednesday afternoon.
"He (Schmitt) is doing a great job" Banney said.
"The four that have competed and any others will continue to be coached and can nominate to compete in the JDS."


Kenny Chesney has always had a soft spot in his heart for the holidays. Whether spent in the Smokey Mountains or somewhere in the islands, the spirit of family, friends and good times are what it's all about. And after a decade, the songwriter from East Tennessee dips his toe back into the holiday waters with the slightly Calypso, wholly acoustic "Christmas In Blue Chair Bay," (clip) hitting radio today, Monday, November 17.
"It seems like there are few times of the year when you can really unplug, really just be in the moment with your family and your friends – and celebrate how great life is," Chesney says. "Over the last ten years, I've really come to appreciate that time off, and what those connections mean, and I wanted to share that feeling with my friends through music.
Kicked back, "Christmas in Blue Chair Bay" celebrates the chilled-out side of Chesney's appeal. Taking it easy, loving life and painting a picture of a simple place where the emphasis is on what's shared between people, it is a different kind of holiday song, but one that paints the fidelity among people with a genuine sense of warmth.
Produced with Buddy Cannon, this is Chesney's first Christmas music since 2003's nearly-Platinum All I Want For Christmas Is A Real Good Tan. Mixing originals with Willie Nelson's "Pretty Paper," Alabama's "Christmas In Dixie" and Keith Whitley's "Just a Kid" and classics "Silent Night" and "I'll Be Home for Christmas," its release caused lines so long at Minneapolis' Mall of America three days before release it prompted the installation of heating units and porta-potties for the people waiting.
With "American Kids" already spending multiple weeks at No. 1, "Til It's Gone" hitting the charts at No. 18 on add date and rising, The Big Revival is speaking to the fans in a way that celebrates the way they live. As his Big Revival Tour has already sold out 110,000 tickets for two shows in Boston in just twelve minutes, the 4-time Country Music Association and 4-consecutive Academy of Country Music Entertainer of the Year knows about settling in for the holidays to recharge what's to come – and "Christmas In Blue Chair Bay" is the sound of good cheer and getting ready for the year ahead with 55 dates and a whole lot more music that just won't stop.
Kenny Chesney's Flora Bama video special coming soon!
So Sam Hunt, is it ex to see or ecstasy?!


Interested in increasing the reproducibility of your research and making collaborartive research easier to manage? This workshop introduces the Open Science Framework (OSF) as a tool to address common issues in research reproducibility and data management. NB: Despite its name, OSF is for more than science.


text:
How can we make technology that frees us, rather than enslaves us?
April 3, 2017 August 26, 2017 torforge15 Comments
Written by Cory Doctorow
In the Foundation series, Isaac Asimov posited three rules to protect humans from robots. As our own technology advances exponentially every day, how can will we make technology that frees us, rather than enslaving us?
Let us begin by cleaving this problem into two pieces, only one of which I am qualified to address:
1. How can we make technology that works well?
2. How can we make technology that fails well?
I only know about #2.
The Second Law of Thermodynamics is a thing. Security—like all forms of experimentally derived knowledge—is a process, not a product. Computers with no known flaws are not flawless: their flaws just have not yet been discovered and reported.
Computers have metastasized. Software is eating the world. Your toaster, pacemaker, car, tractor, insulin pump and thermostat are (or soon will be) computers in fancy cases that have the power to inflict enormous pain and harm upon your person and life. It is correct to view software as a nexus of control for solving your problems. When books become digital objects, publishers attempt to solve their problems by controlling the both the code embedded in the ebooks themselves and the devices that can play them back.
But those problems aren't your problems. The fact that some publishers don't like the used book market and perceive an opportunity to kill it by using software to keep people from giving away, selling, or lending digital books doesn't mean you benefit when they attempt it. Their security from used books is your insecurity of not getting to read used books.
What the entertainment companies started, the rest of the world has cottoned onto. Today, a startling variety of technologies use digital countermeasures to control their owners: insulin pumps stop you from reading your coronary telemetry except by manufacturer-authorized doctors with paid-up software licenses. GM stops you from visiting independent mechanics who diagnose your engine with unauthorized tools and repair it with third-party replacement parts. Voting machine vendors stop independent researchers from validating their products.
This only works if you can't replace the software the manufacturer specifies with software from someone else—say, a competitor of the manufacturer—that gives you back the freedom the software has taken away. That's because the computer the software is running on is a general purpose computer: that's the only kind of computer we know how to build, and it can run any program that can be expressed in symbolic language.
A computer that won't obey you—a DVD player that won't play an out-of-region disc; a phone that won't accept apps that come from third-party app stores—isn't a computer that's incapable of obeying you. That computer can readily do all the things on the forbidden list. It just refuses to do them.
This is what controlling people with their computers means: designing disobedient computers that view their owners as adversaries, that obfuscate their operations from those owners, that prefer the orders they get from distant third parties to the policies set by the person holding the computer, having paid for it.
It's hard to keep people from changing the software on computers they own—even software that's designed to hide from its owner and refuse to shut down can eventually be located and neutralized. If you let skilled adversaries play with a computer whose software is skulking in the operating system's shadows, the skilled adversary will eventually find its spider hole and flush it out and kill it with extreme prejudice. Then that expert will tell everyone else how to do it with their computers.
So it was that in 1998, the US Congress enacted the Digital Millennium Copyright Act (DMCA), whose Section 1201 makes it a serious crime to figure out how the computers you own work and tell other people what you've learned. Under DMCA 1201, it's a potential felony (punishable by a 5 year sentence and a $500,000 fine for a first offense) to weaken or bypass a system that restricts access to a copyrighted work.
Every device with software in it has a copyrighted work in it—software is a copyrighted work. Manufacturers who want to force their customers to use their property in ways beneficial to the manufacturer (and not the device's owner) can configure those devices so that using them in any other way involves tampering with a copyright lock, which makes using your computer in the way you want into a potential felony.
That's why John Deere tractors are designed so that getting them fixed by non-authorized repair people requires breaking a copyright lock; thus Deere can force farmers to pay $230, plus $130/hour for simple service calls. The farmers are just the start: add a vision-system to a toaster and it can prevent you from using third-party bread, and make disabling the bread-enforcement system into a felony.
As software metastasizes into every category of goods, an entertainment industry law from the late XXth Cen is turning into an existential threat to human liberty: we are being Huxleyed into the Full Orwell.
That's for starters. But security is a process, not a product. You can only make a device secure by continuously prodding at it, looking for its defects, and repairing them before they are exploited by your adversary.
DMCA 1201 is now the leading reason that security researchers fail to disclose the vulnerabilities they discover. Once a device has a copyright-protecting lock on it, reporting that device's defects makes you potentially liable to bowel-watering criminal and civil penalties. In 2015, security researchers told the US Copyright Office that they are sitting on potentially lethal bugs in insulin pumps and cars, on bugs in thermostats and voting machines, in entertainment consoles whose unblinking eyes and ever-listening ears witness our most intimate moments.
By providing an incentive to companies to add copyright locks to their systems, we've also given them a veto over who can reveal that they have sold us defective and dangerous products. Companies don't view this as a bug in their digital monopolization strategy: it is a feature.
Isaac Asimov started from the presumption that we'd make positronic brains with a set of fixed characteristic and that this design would be inviolable for millennia, and then wrote several books' worth of stories about which unchanging rules these positronic brains should follow. He was wrong.
Designing computers to treat their owners as untrustworthy adversaries, unfit to reconfigure them or know their defects, is a far more dangerous proposition than merely having computers with bad software. Asimov was interested in how computers work. He should have been paying attention to how they fail.
The failure mode of prohibiting the owners of computers from changing which programs they run, and of knowing whether those computers are secure, is that those computers are now designed to control their owners, rather than being controlled by them.
This is the key difference between computers that liberate and computers that enslave.
Asimov had three laws. I propose two:
1. Computers should obey their owners
2. It should always be legal to tell the truth about computers and their security
Neither of these laws is without potential for mischief. I could write a hundred stories about how they could go wrong. But the harms of following these rules are far worse than the harms of deliberately setting computers to control the people they are meant to serve.
I charge you to be hard-liners for these rules. If they aren't calling you unreasonable, a puritan, a fanatic for these rules, you're not trying hard enough.
The future is riding on it.
Follow Cory Doctorow on Twitter, on his website, and on the blog Boing Boing.
Cory Doctorow, science fiction, Tor Guest Post, Tor Newsletter, tor sidebar, Walkaway
Download a Free Digital Preview of The…
Read the Second Chapter of The Future…
I've Been Lit on Fire Four Times.…
Would You Swipe Right for These SFF…
Excerpt: Knight of the Silver Circle by…
15 thoughts on "How can we make technology that frees us, rather than enslaves us?"
MrPeach says:
As someone who has made it a hobby of destroying TPMs since buying my first computer (an Atari 800) in 1982, I could not agree more with your article.
I shall continue to ply my trade until my last breath, stupid laws be damned.
David Waltner-Toews says:
Don't you mean "But the harms of following these rules are far [LESS] than the harms of deliberately setting computers to control the people they are meant to serve"?
Julanna says:
Thats' what I thought too. I had to read that sentence several times …
Charles Lindsay says:
I agree – Cory's current sentence seems opposite to his intention. Cory? Maybe your proof-reader goofed.
Scott Pearson says:
Although a great deal of Asimov's fiction is linked together in the same universe, the Three Laws were introduced in the Robot series, not the Foundation series.
Rich Zahradnik says:
Was about to post the same thing. The three laws appear in the series of short stories that were turned into the novel "I, Robot" (really interlinked stories) that started with "Robbie." There's not a lot of robot stuff in Foundation.
Cory Doctorow says:
It's true that Foundation stories aren't about positronic brains and their problems, but positronic brains appear in Foundation; they also appear in far-future Robots stories that indicate that the three laws are still being built into robots millennia after their invention.
Pat Moore says:
Thanks for a timely piece. Now I know it is okay to be called paranoid, hater, etc. I always say better that than to be sheep!
Cynthia White says:
What do you suggest as a practical political solution? How would you pressure lawmakers to change the laws and be more open about security? As a non technology geek, I don't have the capacity to mess with my computer's code, and I don't have the ability to be absolutely secure. I can go offline entirely, or I can work with others to change the laws.
I think many people are aware there is a problem. We need practical solutions.
I agree. I suggest supporting pressure groups that sue the USG to invalidate bad laws and pressure them to adopt better ones (and also to stop adopting worse ones):
* EFF (eff.org)
* ACLU (aclu.org)
* Demandprogress (demandprogress.org)
* Fight for the Future (https://www.fightforthefuture.org/
* Software Freedom Law Center (https://www.softwarefreedom.org/)
* Free Software Foundation (fsf.org)
* Software Conservancy (https://sfconservancy.org/)
Many many others!
Pingback: RE: onze algoritmes zijn seksistisch en racistisch – Vileine.com
Pingback: Singpolyma » How can we make technology that frees us, rather than enslaves us? http://www.torforgeblog.com/2017/04/03/how-can-we-make-technology-that-frees-us-rather-than-enslaves-us/
Pingback: Dark Future Ahead 21 – News from the 'Net of a Cyberpunk bent | Sea of Stars RPG Design Journal
Pingback: http://www.torforgeblog.com/2017/04/03/how-can-we-make-technology-that-frees-us-rather-than-enslaves-us/ "Designing computers to treat their owners as untrustworthy adversaries, unfit to reconfigure them or know their defects, is a far more dangerous
bithalver says:
I feel your pain: everybody looks at me like I am a weirdo when I say it is my first thing to root my android phone and tablet to use their full potentional.
Please vorfige me for rgammar miskates; ingiliz not is ym tanive ganluage.
Books: I Like Them, Who Could Have Guessed?
What Makes This Book So Great author Jo Walton talks – what else? – books. Read more →
Building Ilmatar
A Darkling Sea author James L. Cambias talks about creating his world of Ilmatar. Read more →
Love space? Check out @chicagotribune's list of astronaut-themed sci-fi, featuring books by @MaryRobinette, @Nnedi,… https://t.co/arVRi5BUVQ (49 mins ago)
RT @Annaleen: Can't make it to #SDCC to visit the @torbooks booth and get a copy of my forthcoming novel, THE FUTURE OF ANOTHER TIMELINE? N… (4 hours ago)
Who is at #SDCC19 and loves SF thrillers? 🙋♀ Come by booth #2701 at 4:30 pm PST to meet @sl_huang and get a free… https://t.co/mwQGqixW1G (17 hours ago)


You will learn how to be compliant with state regulations, health concerns and enviroment of semi-permanent make-up.
There are certain laws and practices you must follow.
The areas of this topic include: sterilization, sanitation, Bloodborne Pathogen, and Procedure Room Set-up.
One of the most important component of education for semi-permanent make-up is the skin anatomy.
You will be working on the human body, and it is very important that you know much about it.
The areas of this topic are: skin structure, skin conditions & disorders, and skin tone & undertone.
The technique becomes your tool to success in semi-permanent make-up.
The sophisticated skills of the following will be covered: manual & machine technique, brows shape drawing, maping methods, stretching skin method microblading pattern and manual ombre powder fill techniques and more.
In this topic, you will be taught about the range of medical condition clients may have, contraindications, complications, how to prevent and follow protocols.
We will cover methods of topical anesthetics as well as what to use for different areas and procedures, how they work on the skin and how effectively combine/use them.
Learning about colors are critical because you will be working with different colorant.
The real life setting is very important. It is your time to put your knowledge and training on the stage.
All lights on you and its your time to shine! We take it as a real deal and want to ensure you have what it takes to apply it in the real setting smoothly.
That's why we provide all the forms you need: informed consent form, medical history, consultation and more.
We train on how and what to do, how to instruct your client from the beginning to the aftercare.
DISCLAIMER: The following schedule is a basic outline. The schedule is subjected to change anytime without notice.
Models are not guaranteed but You may also bring your own live model, if you want to practice under supervision.
What is Semi-permanent Make up? Health/Safety/State law regulations, Blood-borne pathogen training/ Brows mapping method/Shaping eyebrows and microblading pattern(1) method.
Theory : Skin Anatomy: Skin structure/ Conditions/ Pigment deposition/ Skin under-tone. Latex practice : Microblading pattern(2) with hand tool.
* You will be given a certificate of completion by RachelJ.Academy.
You will be also directed and guided to take the appropriate steps to administer for BBP and body art certification.