Definability of Arithmetic Operations from the Order and a Random Relation 1

Abstract

For almost all binary relations $\mathit{R}\subseteq {\mathit{N}}^2$ the addition and multiplication on the set N of nonnegative integers (and hence all arithmetical relations) are first order definable in the structure (N; ⩽, R). The defining formulae can be chosen independently on R and the words “for almost all” mean “with probability 1” by a very natural probability measure.