LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
sav08:weak_monadic_logic_of_one_successor [2008/05/15 10:35]
vkuncak
sav08:weak_monadic_logic_of_one_successor [2015/04/21 17:30] (current)
Line 18: Line 18:
  
 Let $\mathbb{N} = \{0,​1,​2,​\ldots\}$ denote non-negative integers. ​ Let $D$ be the set of all //finite subsets// of $\mathbb{N}$. ​ We consider the set of interpretations $(D,​\alpha)$ where for each variable $v$ we have $\alpha(v) \in D$, where $\subseteq$ is the subset relation Let $\mathbb{N} = \{0,​1,​2,​\ldots\}$ denote non-negative integers. ​ Let $D$ be the set of all //finite subsets// of $\mathbb{N}$. ​ We consider the set of interpretations $(D,​\alpha)$ where for each variable $v$ we have $\alpha(v) \in D$, where $\subseteq$ is the subset relation
-\[+\begin{equation*}
    ​\alpha({\subseteq}) = \{ (S_1,S_2) \mid S_1 \subseteq S_2 \}    ​\alpha({\subseteq}) = \{ (S_1,S_2) \mid S_1 \subseteq S_2 \}
-\]+\end{equation*}
 and the relation $succ(v_1,​v_2)$ is the successor relation on integers lifted to singleton sets: and the relation $succ(v_1,​v_2)$ is the successor relation on integers lifted to singleton sets:
-\[+\begin{equation*}
    ​\alpha(succ) = \{ (\{k\},​\{k+1\}) \mid k \in \mathbb{N} \}    ​\alpha(succ) = \{ (\{k\},​\{k+1\}) \mid k \in \mathbb{N} \}
-\]+\end{equation*}
 The meaning of formulas is given by standard [[First-order logic semantics]]. The meaning of formulas is given by standard [[First-order logic semantics]].
  
Line 92: Line 92:
  
 Relations on singleton sets: Relations on singleton sets:
-\[+\begin{equation*}
    r^s_F = \{(p,q) \mid F(\{p\},​\{q\}) \}    r^s_F = \{(p,q) \mid F(\{p\},​\{q\}) \}
-\]+\end{equation*}
  
 Relations on binary representations:​ Relations on binary representations:​
-\[+\begin{equation*}
    r^b_F = \{(p,q) \mid F(N(p),​N(q)) \}    r^b_F = \{(p,q) \mid F(N(p),​N(q)) \}
-\]+\end{equation*}
  
 Addition is not definable as some $r^s_F$, but it is definable as $r^b_F$. Addition is not definable as some $r^s_F$, but it is definable as $r^b_F$.