| Résume | Given a set \(A\) of natural numbers that are \(k\)-automatic (i.e., their base-\(k\) representations are recognized by some finite automaton) but not definable in \((\mathbb{N},+)\), call A minimal if for any k-automatic set of natural numbers \(B\), the structure \((\mathbb{N},+,B)\) includes \(A\) as a definable set. Conversely, say that \(A\) is maximal if for any such \(B\), the structure \((\mathbb{N},+,B)\) includes \(B\) in its definable sets. In this talk, we will establish that every \(k\)-automatic subset of the naturals is either minimal or maximal, and will further characterize both classes of \(k\)-automatic sets. We will discuss the analogous theorem in higher arities, and the consequences of this definability dichotomy. |
