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

Article type: Research Article

Authors: Korec, Ivan

Affiliations: Mathematical Institute, Slovak Academy of Sciences, Štefánikova 49, 81473 Bratislava, Czechoslovakia

Note: [1] This work was supported by Grant 364/1991 of Slovak Academy of Sciences.

Abstract: For almost all binary relations R⊆N2 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.

DOI: 10.3233/FI-1993-182-414

Journal: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 287-296, 1993