An infinite branch in a decidable tree

Abstract

We consider a structure $\mathcal{M}=⟨\mathbb{N},\{Tr,<\}⟩$, where the relation $Tr(a,x,y)$ with a parameter $a$ defines a family of trees on $\mathbb{N}$ and $<$ is the usual order on $\mathbb{N}$. We show that if the elementary theory of $\mathcal{M}$ is decidable then (1) the relation $Q(a)\rightleftharpoons$ "there is an infinite branch in the tree $Tr(a,x,y)$" is definable in $\mathcal{M}$, and (2) if there is an infinite branch in the tree $Tr(a,x,y)$, then there is a definable in $\mathcal{M}$ infinite branch.

5 pages,fixed typo in v.2, updated (and simplified) the rank definition