1 Introduction
The calculus of relations is a branch of logic that was developed in the nineteenth century, largely due to the work of De Morgan, Peirce, and Schröder; see [Reference De Morgan6, Reference Peirce22, Reference Schröder24], for example. By the beginning of twentieth century, the calculus of relations was considered to be an important branch of logic. Indeed, in [Reference Russell23], Russell stated that “the subject of symbolic logic is formed by three parts: the calculus of propositions, the calculus of classes, and the calculus of relations.” The calculus of relations even played a role in the birth of model theory. Indeed, Leopold Löwenheim stated and proved the earliest known version of the Löwenheim–Skolem Theorem as a result on the calculus of relations; for more details, see [Reference Badesa1]. Interest in the field mostly faded until the publication of [Reference Tarski25], where Tarski defined an abstract algebraic counterpart to the calculus of relations, namely relation algebras. Tarski and many of his students took an interest in these algebras, which lead to relation algebras becoming a fairly popular area of research that is still active.
The idea of defining the probability of a property holding in a class of finite structures as a limit is due to Carnap (see [Reference Carnap3]), but similar ideas appeared earlier. In [Reference Fagin7, Reference Fagin8], Fagin looked at the probability of certain sentences holding in the classes of all relational structures of a given type as well as asymptotic formulas for the numbers of these structures. The study of
$0$
–
$1$
laws was initiated by Glebskiĭ et al. in the 1970s; see [Reference Glebskiĭ, Kogan, Liogon’kiĭ and Talanov12, Reference Liogon’kiĭ16]. The study of conditions that guarantee the existence of
$0$
–
$1$
laws for first-order and monadic second-order properties were studied extensively by Compton in [Reference Compton4, Reference Compton5]. In the context of relation algebras, there has been surprisingly little research published on probabilistic results of this nature. In [Reference Maddux19], Maddux finds an asymptotic formula for the number of nonassociative relation algebras in which the identity is an atom and the number of integral relation algebras, and shows that almost all of these algebras are rigid and satisfy any finite set of equations that hold in all representable relation algebras. In the present article, we show that almost all finite nonassociative relation algebras are symmetric and have e as an atom, and establish a
$0$
–
$1$
law for the class of all atom structures of finite nonassociative relation algebras. Combining these results with the results of Maddux, we obtain a simple asymptotic formula for both the number of nonassociative relation algebras and the number of relation algebras, and show that almost all finite nonassociative relation algebras are integral relation algebras.
2 Preliminaries
We begin by giving a formal definition of labelled and unlabelled probabilities of properties. We will mostly follow the approach taken in [Reference Freese10]. Note that by
$\mathbb {N}$
we mean
$\{1,2,\dots \}$
.
Definition 1 (Probabilities)
Let
$\mathcal {K}$
be a class of finite structures of a finite signature F that is closed under isomorphism and has no upper bound on the size of its members. For all
$n \in \mathbb {N}$
, let
$\mathcal {U}_n$
be a set with precisely one representative from each isomorphism class of n-element structures from
$\mathcal {K}$
and let
$\mathcal {L}_n$
be the set of all structures in
$\mathcal {K}$
with universe
$\{1,\dots ,n\}$
. Let P be some property of F-structures that is invariant under isomorphisms (for example, a first-order property). Let
$s \colon \mathbb {N} \to \mathbb {N}$
be the increasing sequence of values of n with
$\mathcal {U}_n \neq \varnothing $
. If the limit
$$ \begin{align*} \lim_{n \to \infty} \frac{|\{{\textbf{A}}\ \in \mathcal{U}_{s(n)} \mid {\textbf{A}} \mathrel{{|}\kern-0.47ex{=}\kern-1.725ex{=}} P\}|}{|\mathcal{U}_{s(n)}|}, \end{align*} $$
exists, we call it the unlabelled probability of P and denote it by
$\operatorname {\mathrm {{Pr}_{U}}}(P,\mathcal {K})$
. If the limit
$$ \begin{align*} \lim_{n \to \infty} \frac{|\{{\textbf{A}}\ \in \mathcal{L}_{s(n)} \mid {\textbf{A}} \mathrel{{|}\kern-0.47ex{=}\kern-1.725ex{=}} P\}|}{|\mathcal{L}_{s(n)}|}, \end{align*} $$
exists, we call it the labelled probability of P and denote it by
$\operatorname {\mathrm {{Pr}_{L}}}(P,\mathcal {K})$
. If
$\operatorname {\mathrm {{Pr}_{U}}}(P,\mathcal {K}) = 1$
, we say that almost all structures in
$\mathcal {K}$
satisfy P.
We will mostly work with classes where there are elements of every possible cardinality, so the sequence s will be the identity sequence.
The result we will need from Freese [Reference Freese10] is stated below; this result is stated for algebras, but the proof also works for relational structures. Similar results appear in earlier articles, such as Fagin [Reference Fagin8].
Proposition 2. Let
$\mathcal {K}$
be a class of similar finite structures of a finite signature F that is closed under isomorphism and has no upper bound on the size of its members, let R be the property of being rigid (i.e., having a trivial automorphism group), let P be a property F-structures that is invariant under isomorphism, and assume that we have
$\operatorname {\mathrm {{Pr}_{L}}}(R,\mathcal {K}) = 1$
. If one of
$\operatorname {\mathrm {{Pr}_{U}}}(P,\mathcal {K})$
and
$\operatorname {\mathrm {{Pr}_{L}}}(P,\mathcal {K})$
exists, then both quantities exist and are equal.
Now we are in the position to recall the definition of an almost sure theory.
Definition 3 (Almost sure theory)
Let
$\mathcal {K}$
be a class of finite structures of a finite signature F that is closed under isomorphism and has no upper bound on the size of its members. We call the set of all first-order sentences
$\sigma $
with
$\operatorname {\mathrm {{Pr}_{L}}}(\sigma ,\mathcal {K}) = 1$
the almost sure theory of
$\mathcal {K}$
.
Next, we will give a brief introduction to relation algebras. For a more extensive introduction, we refer the reader to Hirsch and Hodkinson [Reference Hirsch and Hodkinson13], Maddux [Reference Maddux21], and Givant [Reference Givant11]. We begin by defining relation algebras. To match the notation used in lattice theory, we will use
$\vee $
and
$\wedge $
rather than
$+$
and
$\cdot $
. This allows us to use a more group theoretic notation by using
$\cdot $
and e rather than
$;$
and
$1'$
. We will assume that unary operations are applied first and use multiplicative notation for
$\cdot $
. Therefore
$x\breve {\ } z \wedge y'$
means
$((x \breve {\ }) \cdot z) \wedge (y ')$
, for example. We call
$d \mathrel {\mathop :}= e'$
the diversity element. We use
$\approx $
for logical equality, as in universal algebra. To avoid reusing symbols, we will use
$\curlyvee $
for logical disjunction,
$\curlywedge $
for logical conjunction, and
$\neg $
for logical negation. Where it is possible, we will usually drop superscripts on operations.
Definition 4 (Relation algebras)
An algebra
${{\textbf {A}}} = \langle A;\vee ,\wedge ,\cdot ,{'},{\breve {\ }}, 0,1,e\rangle $
is called a nonassociative relation algebra iff
$\langle A;\vee ,\wedge ,{'},0,1\rangle $
is a Boolean algebra, e is an identity element for
$\cdot $
, and the triangle laws hold, i.e., we have
$$ \begin{align*} xy \wedge z = 0 \iff x\breve{\ } z \wedge y = 0 \iff zy\breve{\ } \wedge x = 0, \end{align*} $$
for all
$x,y,z \in A$
. The class of all nonassociative relation algebras will be denoted by
${\textsf {NA}}$
. An algebra
${{\textbf {A}}} \in {\textsf {NA}}$
is called a relation algebra iff
$\cdot $
is associative. The class of all relation algebras will be denoted by
${\textsf {RA}}$
. An algebra
${{\textbf {A}}} \in {\textsf {NA}}$
is said to be symmetric iff
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} x\breve {\ } \approx x$
.
We extend ideas from Boolean algebra to these algebras in the obvious way. For example, an atom of a nonassociative relation algebra is an atom of its Boolean algebra reduct.
Some basic properties of these algebras are summarised in the following result.
Proposition 5. Let
${{\textbf {A}}} \in {\textsf {NA}}$
.
-
1.
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} x(y \vee z) \approx xy \vee xz$
and
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} (x \vee y)z \approx xz \vee yz$
. -
2.
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} (x \vee y)\breve {\ } \approx x\breve {\ } \vee y\breve {\ }$
. -
3.
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} 0\breve {\ } = 0$
,
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} 1\breve {\ } = 1$
,
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} e\breve {\ } = e$
, and
${{\textbf {A}}}\mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} d\breve {\ } = d$
. -
4.
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} x\breve {\ }\breve {\ } \approx x$
. -
5. If a is an atom, then
$a\breve {\ }$
is an atom. -
6. If
${{\textbf {A}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} e \approx 0$
, then
${{\textbf {A}}}$
is trivial.
Based on Proposition 5, the operations of a complete atomic (and, in particular, a finite) nonassociative relation algebra are completely determined by their values on its atoms. Since a finite
${{\textbf {A}}}\in {\textsf {NA}}$
has
$\log _2(|A|)$
atoms, this means these algebras are determined by a small subset of its elements. This motivates the following definitions. When e is an atom, it is sometimes convenient to include it in the signature rather than a unary relation.
Definition 6 (Atom structure)
Let
${{\textbf {A}}}$
be a complete atomic nonassociative relation algebra. We call
$\operatorname {\mathbf{At}}({{\textbf {A}}}) \mathrel {\mathop :}= \langle \operatorname {\mathrm {{At}}}({{\textbf {A}}}); f_{{\textbf {A}}}, I_{{\textbf {{A}}}}, T_{{\textbf {{A}}}}\rangle $
the atom structure of
${{\textbf {A}}}$
, where
$\operatorname {\mathrm {{At}}}({{\textbf {A}}})$
denotes the set of all atoms of
${{\textbf {A}}}$
,
$f_{{\textbf {A}}}$
is defined by
$x \mapsto x\breve {\ }$
,
$I_{{\textbf {{A}}}} \mathrel {\mathop :}= \{ a \in \operatorname {\mathrm {{At}}}({{\textbf {A}}}) \mid a \leqslant e\}$
, and
$T_{{\textbf {A}}} \mathrel {\mathop :}= \{ (a,b,c) \in \operatorname {\mathrm {{At}}}({{\textbf {A}}})^3 \mid ab \geqslant c\}$
. If e is an atom, we put
$\operatorname {\mathbf{At}}_e({{\textbf {A}}}) \mathrel {\mathop :}= \langle \operatorname {\mathrm {{At}}}({{\textbf {A}}}); f_{{\textbf {A}}}, e,T_{{\textbf {A}}}\rangle $
.
It turns out that these structures can be axiomatised.
Definition 7 (
${\textsf {FAS}}$
,
${\textsf {FSIAS}}$
, and
${\textsf {FSIAS}}_e$
)
Let
${\textsf {FAS}}$
denote the class of all finite structures of the signature
$\{f,T,I\}$
(where f is a unary operation symbol, I is a unary relation symbol, and T is a ternary relation symbol) that satisfy
-
(P) for all
$a,b,c \in U$
, we have
$(f(a),c,b) , (c,f(b),a) \in T$
whenever
$(a,b,c) \in T$
, -
(I) for all
$a,b \in U$
, we have
$a = b$
if and only if
$i \in I$
with
$(a,i,b) \in T$
.
We call a
$\{f,T,I\}$
-structure
${{\textbf {U}}}$
integral iff we have
$|I| = 1$
, and symmetric iff
${{\textbf {U}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} f(x) \approx x$
. The class of all symmetric and integral members of
${\textsf {FAS}}$
will be denoted by
${\textsf {FSIAS}}$
. Now, let
${\textsf {FSIAS}}_e$
be the class of all finite structures of the signature
$\{f,e,T\}$
(where f is a unary operation symbol, e is a nullary operation symbol, i.e., a constant, and T is a ternary relation symbol) that satisfy
$f(x) \approx x$
and
-
(IP) for all
$a,b,c \in U$
, we have
$(f(a),c,b) , (c,f(b),a) \in T$
whenever
$(a,b,c) \in T$
, -
(II) for all
$a,b \in U$
, we have
$a = b$
if and only if there is some
$(a,e,b) \in T$
.
The above definition abuses language slightly; a non-trivial
${{\textbf {A}}} \in {\textsf {NA}}$
is called integral iff
$xy = 0$
implies that
$x=0$
or
$y = 0$
, which is equivalent to e being an atom when
${{\textbf {A}}} \in {\textsf {RA}}$
, but not in general. We refer to Maddux [Reference Maddux20, Reference Maddux21] for further details.
Proposition 8.
${\textsf {FAS}}$
is precisely the class of all atom structures of finite members of
${\textsf {NA}}$
,
${\textsf {FSIAS}}$
is precisely the class of all atom structures of finite, integral, and symmetric members of
${\textsf {NA}}$
. There are bijective correspondences between the sets of isomorphism classes from:
-
1. the class of finite members of
${\textsf {NA}}$
and
${\textsf {FAS}}$
; -
2. the class of finite, integral, and symmetric members of
${\textsf {NA}}$
and
${\textsf {FISAS}}$
; -
3.
${\textsf {FSIAS}}$
and
${\textsf {FSIAS}}_e$
.
Next, we introduce the notion of a cycle (from Maddux [Reference Maddux19]) which can be used to define and describe these structures.
Definition 9 (Cycles)
Let
${{\textbf {U}}}$
be a
$\{f,T,I\}$
-structure and let
$a,b,c \in U$
. We call
$(a,b,c)$
,
$(f(a),c,b)$
,
$(b,f(c),f(a))$
,
$(f(b),f(a),f(c))$
,
$(f(c),a,f(b))$
, and
$(c,f(b),a)$
the Peircean transforms of
$(a,b,c)$
. The set of all of these triples is called a cycle, and is denoted by
$[a,b,c]$
. We call
$(a,b,c)$
an identity triple iff
$I \cap \{a,b,c\} \neq \varnothing $
, and a diversity triple otherwise. We call
$[a,b,c]$
an identity cycle iff it contains an identity triple, and a diversity cycle otherwise. We call
$(a,b,c)$
consistent iff
$(a,b,c) \in T$
, and forbidden otherwise. We call
$[a,b,c]$
consistent iff
$[a,b,c] \subseteq T$
, and forbidden iff
$[a,b,c] \cap T = \varnothing $
. We call a an identity atom iff
$a \in I$
and a diversity atom otherwise. We extend these ideas to
$\{f,e,T\}$
in the obvious way.
The following result from [Reference Maddux19] illustrates the connection between cycles and the axioms for
${\textsf {FAS}}$
and
${\textsf {FSIAS}}_e$
.
Proposition 10.
-
1. Let
${{\textbf {U}}}$
be an
$\{f,T,I\}$
-structure.-
(a) The following are equivalent:
-
i.
${{\textbf {U}}}$
satisfies (P); -
ii. for all
$a,b,c \in U$
, the cycle
$[a,b,c]$
is either consistent or forbidden.
-
-
(b) The following are equivalent:
-
i.
${{\textbf {U}}}$
satisfies (I); -
ii. for all
$a, b \in U$
, we have
$a = b$
if and only if
$[a,i,b]$
is consistent, for some
$i \in I$
.
-
-
(c) If
${{\textbf {U}}}$
is integral, then the following are equivalent:-
i.
${{\textbf {U}}}$
satisfies (I); -
ii.
$f(e) = e$
and
$\{[a,e,a] \mid a \in U\}$
is the set of consistent identity cycles, where e is the unique element of I.
-
-
-
2. Let
${{\textbf {U}}}$
be a
$\{f,e,T\}$
-structure.-
(a) The following are equivalent:
-
i.
${{\textbf {U}}}$
satisfies (IP); -
ii. for all
$a,b,c \in U$
, the cycle
$[a,b,c]$
is either consistent or forbidden.
-
-
(b) The following are equivalent:
-
i.
${{\textbf {U}}}$
satisfies (II); -
ii.
$f(e) = e$
and
$\{[a,e,a] \mid a \in U\}$
is the set of consistent identity cycles.
-
-
Based on Propositions 8 and 10, once given a finite set U, some
$e \in U$
, and an involution
$f \colon U \to U$
with
$f(e) = e$
, each
${{\textbf {U}}} \in {\textsf {FAS}}$
that is an expansion of
$\langle U;f,\{e\}\rangle $
is completely determined by which cycles are consistent or forbidden. Using this observation, it is possible count the number of atom-structures of a given (finite) size. Indeed, in [Reference Maddux19], Maddux obtains asymptotic formulas using this method. The results we will need from [Reference Maddux19] are summarised in the following results.
Proposition 11. Let U be an n-element set, for some
$n \in \mathbb {N}$
, let
$e \in U$
, let f be an involution of U with
$f(e) = e$
, and let
$s \mathrel {\mathop :}= |\{a \in U \mid f(a) = a\}|$
.
-
1. There are
$s-1$
diversity cycles with
$1$
triple; ones of the form
$[a,a,a]$
. -
2. There are
$(n-s)/2$
diversity cycles with
$2$
triples; ones of the form
$[a,a,f(a)]$
, where
$f(a) \neq a$
. -
3. There are
$(s-1)(n-2)$
diversity cycles with
$3$
triples; ones of the form
$[a,b,b]$
, where
$f(a)=a$
and
$a \neq b$
. -
4. There are
$(n-1)((n-1)^2-3s+2)/6 + (s-1)/2$
diversity cycles with
$6$
triples. -
5. There are
$Q(n,s) \mathrel {\mathop :}= (n-1)((n-1)^2+3s-1)/6$
diversity cycles in total. -
6. There are
$P(n,s) \mathrel {\mathop :}= (s-1)! ((n-s)/2)! 2^{(n-s)/2}$
automorphisms of
$\langle U;f,\{e\}\rangle $
.
Before we state the next result, we will pause to recall the definition of representability.
Definition 12 (RRA)
Let E be an equivalence relation over a set D. We call the structure
the proper relation algebra on E, where
be the powerset (i.e., set of all subsets) of E,
$\mid $
is relational composition,
${^{c}}$
is set complement relative to E,
${^{-1}}$
is relational inverse, and
$\mathrm {id}_D$
is the identity relation on D. Thus, for each
$R,S \subseteq E$
,
$$ \begin{align*} R \mid S &= \{ (x,z) \in D^2 \mid (x,y) \in R, (y,z) \in S, \mbox{ for some } y \in D\}, \\ R^{-1} &= \{ (y,x) \in D^2 \mid (x,y) \in R\}, \\ \mathrm{id}_D & = \{ (x,y) \in D^2 \mid x = y \}. \end{align*} $$
A relation algebra is said to be representable iff it embeds into a proper relation algebra. The class of representable relation algebras will be denoted by
${\textsf {RRA}}$
.
The problem of determining whether every relation algebra is representable was the main focus of research into relation-type algebras for many years, until it was solved in the negative by Lyndon in [Reference Lyndon17]. Therefore one might be interested in the asymptotics of the fraction of representable relation algebras. Maddux took the first steps in this direction in [Reference Maddux19].
Proposition 13.
-
1. Almost all integral labelled structures in
${\textsf {FAS}}$
are rigid. -
2. If E is the conjunction of a finite set of equations that hold in all members of
${\textsf {RRA}}$
, then E holds in almost all finite elements of
${\textsf {NA}}$
in which e is an atom. In particular, almost all nonassociative relation algebras in which e is an atom are relation algebras.
Proposition 14. For all
$n,s \in \mathbb {N}$
with
$s \leqslant n$
and
$n-s$
even, let
$F(n,s)$
be the number of isomorphism classes of n-atom integral relation algebras with s atoms satisfying
$x \breve {\ } = x$
. Then
$2^{Q(n,s)}/P(n,s)$
is an asymptotic formula for
$F(n,s)$
, in the sense that, for all
$\varepsilon> 0$
, there exists
$N\in \mathbb {N}$
such that if
$n,s \in \mathbb {N}$
with
$n> N$
,
$s \leqslant n$
, and
$n-s$
even, then
$$ \begin{align*} \Bigg| 1 - \frac{F(n,s)P(n,s)}{2^{Q(n,s)}} \Bigg| < \varepsilon. \end{align*} $$
Further, the same statement holds for nonassociative relation algebras in which e is an atom.
We conclude with a reminder of Fraïssé limits, which were defined by Fraïssé in [Reference Fraïssé9]. We will mostly follow Hodges [Reference Hodges15]. Firstly, we recall some definitions.
Definition 15 (Age)
Let
${{\textbf {A}}}$
be a structure. The age of
${{\textbf {A}}}$
is the class of all finitely generated structures that embed into
${{\textbf {A}}}$
.
Definition 16 (HP, JEP, and AP)
Let
$\mathcal {K}$
be a class of similar structures. We say that
$\mathcal {K}$
has the hereditary property (HP) iff
$\mathcal {K}$
is closed under forming finitely generated structures. We say that
$\mathcal {K}$
has the joint embedding property (JEP) iff, for all
${{\textbf {A}}}, {{\textbf {B}}} \in \mathcal {K}$
, there is some
${{\textbf {C}}} \in {K}$
that both
${{\textbf {A}}}$
and
${{\textbf {B}}}$
embed into. We say that
$\mathcal {K}$
has the amalgamation property (AP) iff, for all
${{\textbf {A}}},{{\textbf {B}}},{{\textbf {C}}} \in \mathcal {K}$
and embeddings
$\mu \colon {{\textbf {A}}} \to {{\textbf {B}}}$
and
$\nu \colon {{\textbf {A}}} \to {{\textbf {C}}}$
, there is some
${{\textbf {D}}} \in \mathcal {K}$
and embeddings
$\mu ' \colon {{\textbf {B}}} \to {{\textbf {D}}}$
and
$\nu ' \colon {{\textbf {C}}} \to {{\textbf {D}}}$
such that
$\mu ' \circ \mu = \nu ' \circ \nu $
.
Definition 17 (Homogeneity)
Let
${{\textbf {A}}}$
be a structure. We call
${{\textbf {A}}}$
ultrahomogenous iff every isomorphism between finitely generated substructures of
${{\textbf {A}}}$
extends to an automorphism of
${{\textbf {A}}}$
. We call
${{\textbf {A}}}$
weakly homogeneous iff, for all finitely generated structures
${{\textbf {B}}}$
and
${{\textbf {C}}}$
of
${{\textbf {A}}}$
with
${{\textbf {B}}} \leqslant {{\textbf {C}}}$
and all embeddings
$\mu \colon {{\textbf {B}}} \to {{\textbf {A}}}$
, there is an embedding
$\nu \colon {{\textbf {C}}} \to {{\textbf {A}}}$
extending
$\mu $
.
The following result shows that these definitions coincide
Proposition 18. A finite or countable structure is ultrahomogeneous if and only if it is weakly homogeneous.
The main result on these structures is the following existence and uniqueness result, known as Fraïssé’s Theorem.
Proposition 19 (Fraïssé’s Theorem)
Let S be a countable signature and let
$\mathcal {K}$
be a class of at most countable S-structures, that has the HP, JEP, and AP. Then there is an S-structure
${{\textbf {F}}}$
(called a Fraïssé limit of
$\mathcal {K}$
), unique up to isomorphism, such that
${{\textbf {F}}}$
is at most countable,
$\mathcal {K}$
is the age of
${{\textbf {F}}}$
, and
${{\textbf {F}}}$
is ultrahomogeneous.
To state the last result of this section, we need to recall some definitions.
Definition 20 (Uniform local finiteness)
Let
$\mathcal {K}$
be a class of similar structures. We say that
$\mathcal {K}$
is uniformly locally finite iff there is a function
$f \colon \mathbb {N}\to \mathbb {N}$
, such that, for all
${{\textbf {A}}} \in \mathcal {K}$
, each
$n \in \mathbb {N}$
, and every subset S of A with
$|S| \leqslant n$
, the substructure of
${{\textbf {A}}}$
generated by S has cardinality at most
$f(n)$
.
Proposition 21. Let S be a finite signature, let
$\mathcal {K}$
be a uniformly locally finite class of S-structures with the HP, JEP, and AP, and at most countably many isomorphism types of finitely generated S-structures, and let
${{\textbf {F}}}$
be a Fraïssé limit of
$\mathcal {K}$
. Then the first-order theory of
${{\textbf {F}}}$
is
$\aleph _0$
-categorical and has quantifier elimination.
3 Main results
First, we show that almost all finite nonassociative relation algebras are symmetric and have e as an atom. The proof and the observation that almost all nonassociative relation algebras in which e as an atom are symmetric were discovered independently by the author, but this result was also conjectured by Roger Maddux in a private communication.
Theorem 22. Almost all members of
${\textsf {FAS}}$
are in
${\textsf {FSIAS}}$
.
Proof. Let
$n \geqslant 5$
, let U be an n-element set, and let
$1 \leqslant i < n$
. Clearly, there are
$\binom {n}{i}$
ways to select i identity atoms. Now, let
$0 \leqslant p \leqslant \lfloor (n-i)/2 \rfloor $
. There are at most
$\binom {n-i}{2}^p$
involutions of U with p non-fixed pairs, i.e., with sets of the form
$\{u, f(u)\}$
with
$u \neq f(u)$
, since
${\binom {n-i}{2}}^p$
is the number of p independent selections of
$2$
-element sets of diversity atoms. Based on Proposition 10(1b), there are
$(2^i - 1)^n$
possible ways of selecting identity cycles, since each element of U must appear in at least one of the i cycles of the given form. Lastly, based on Proposition 11(5), there are
$2^{Q(n-i+1,n-i+1-2p)}$
ways to select diversity cycles; the number of choices of diversity cycles in a
$(n-i+1)$
-element structure satisfying
$|I|=1$
and a n-element structures such that
$|I| = i$
and
$|U \setminus I| = n-i$
is clearly the same. Hence, by Proposition 5(5), the fraction of members of
${\textsf {FAS}}$
with universe
$\{1,\dots ,n\}$
that belong to
${\textsf {FSIAS}}$
is bounded below by
$$ \begin{align*} &\hspace{12pt}\frac{n2^{Q(n,n)}}{\sum_{i=1}^{n} \sum_{p = 0}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)}} \\ & = \frac{1}{(\sum_{i=1}^{n} \sum_{p = 0}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)})/n}. \end{align*} $$
We have
$$ \begin{align*} & \quad\,\, \frac{1}{n}\sum_{i=1}^{n} \sum_{p = 0}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)} \\ & = \frac{1}{n} \sum_{p=0}^{\lfloor (n-1)/2 \rfloor} n \binom{n-1}{2}^p 2^{Q(n,n-2p)-Q(n,n)} \\ & \quad\,\, + \frac{1}{n}\sum_{i=2}^{n-1} \sum_{p = 0}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)}. \end{align*} $$
Clearly,
$$ \begin{align*} \binom{n-1}{2}^p \leqslant \bigg(\frac{n^2}{2}\bigg)^p. \end{align*} $$
Now,
$$ \begin{align*} Q(n,n-2p) - Q(n,n) &= \frac{1}{6}(n-1)((n-1)^2 + 3(n-2p) - 1)\\ &\quad - \frac{1}{6}(n-1)((n-1)^2 + 3n -1) \\ &= \frac{1}{6}(n-1)((n-1)^2 +3n-6p-1 -((n-1)^2 +3n-1)) \\ &= \frac{1}{6}(n-1)(3n -6p - 3n) \\ &= (1-n)p, \end{align*} $$
hence
$$ \begin{align*} \bigg( \frac{n^2}{2} \bigg)^p 2^{Q(n,n-2p)- Q(n,n)} &= \bigg( \frac{n^2}{2} \bigg)^p 2^{(1-n)p} \\ &= \bigg(\frac{n^2}{2^n}\bigg)^p. \end{align*} $$
Since
$n \geqslant 5$
, we have
$0 < n^2/2^n < 1$
, so the formula for a geometric sum gives
$$ \begin{align*} \frac{1}{n} \sum_{p=0}^{\lfloor (n-1)/2 \rfloor} n \binom{n-1}{2}^p 2^{Q(n,n-2p)-Q(n,n)}&\leqslant \sum_{p=0}^{\lfloor (n-1)/2 \rfloor} \bigg(\frac{n^2}{2^n}\bigg)^p \\ &= \frac{1 - (n^2/2^n)^{\lfloor (n-1)/2 \rfloor +1}}{1 - n^2/2^n}. \end{align*} $$
Using basic limits,
$n^2/2^n$
and
$(n^2/2^n)^{\lfloor (n-1)/2 \rfloor +1}$
tend to
$0$
, and so
$$ \begin{align*} \lim_{n \to \infty} \bigg(\frac{1 - (n^2/2^n)^{\lfloor (n-1)/2 \rfloor +1}}{1 - n^2/2^n}\bigg) = 1. \end{align*} $$
Define
$S(m) \mathrel {\mathop :}= Q(m,m)$
, for each
$m \in \mathbb {N}$
. We have
$$ \begin{align*} S(m) &= \frac{1}{6}(m-1)((m-1)^2+3m-1) \\ &= \frac{1}{6}(m-1)(m^2-2m+1+3m-1)\\ &= \frac{1}{6}(m-1)(m^2+m) \\ &= \frac{1}{6}(m^3-m), \end{align*} $$
for each
$m \in \mathbb {N}$
. Using the formula for a difference of cubes, we get
$$ \begin{align*} &S(n-i+1) - S(n)\\ &\quad = \frac{1}{6}((n-i+1)^3 - (n-i+1) - n^3+n)\\ &\quad = \frac{1}{6}((n-i+1-n)((n-i+1)^2 + n(n-i+1) + n^2) + i - 1) \\ &\quad = \frac{1}{6}(-(i-1)(n^2 -2(i-1)n + (i-1)^2 + n^2 - (i-1)n + n^2) + i-1)\\ &\quad = \frac{1}{6}(-3(i-1)n^2 + 3(i-1)^2n - (i-1)^3 + i-1). \end{align*} $$
In particular,
$$ \begin{align*} i = 2 & \implies S(n-i+1) - S(n) = - \frac{1}{2}n^2+\frac{1}{2}n, \\ i = 3 & \implies S(n-i+1) - S(n) = -n^2+2n-1, \\ i = 4 & \implies S(n-i+1) - S(n) = - \frac{3}{2}n^2+ \frac{9}{2}n -4. \end{align*} $$
If
$1 \leqslant i < n$
and
$1 \leqslant p \leqslant \lfloor (n-i)/2 \rfloor $
, then
$\lfloor (n-i)/2 \rfloor \leqslant n$
,
$\binom {n}{i} \leqslant n^n$
,
$\binom {n-i}{2}^p \leqslant (n^2)^n = n^{2n}$
,
$(2^i-1)^n \leqslant 2^{in}$
, and
$Q(n-i+1,n-i+1-2p) \leqslant S(n-i+1)$
. Over the interval
$[1,\infty )$
,
$x \mapsto (x^3-x)/6$
is increasing, hence
$S(n-i+1)-S(n)$
is maximised when i is minimised. Since
$n \geqslant 5$
, we have
$n-1 \geqslant 4$
and
$2^n> 1$
. Hence, using the formula for a geometric sum, we get
$$ \begin{align*} & \quad \,\, \frac{1}{n}\sum_{i=2}^{n} \sum_{p = 0}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)} \\ & \leqslant \frac{1}{n} \sum_{i=2}^{n} \sum_{p=0}^{\lfloor (n-i)/2 \rfloor} n^n n^{2n} (2^i-1)^n 2^{S(n-i+1)-S(n)} \\ & \leqslant \frac{1}{n} \sum_{i=2}^{n} n n^{3n} (2^i-1)^n 2^{S(n-i+1)-S(n)} \\ & = \sum_{i=2}^{n} n^{3n} (2^i-1)^n 2^{S(n-i+1)-S(n)} \\ & = n^{3n} 3^{n} 2^{-n^2/2+n/2} + n^{3n}7^{n} 2^{-n^2 + 2n -1} + \sum_{i=4}^{n} n^{3n} (2^i-1)^n 2^{S(n-i+1)-S(n)} \\ & \leqslant n^{3n} 3^{n} 2^{-n^2/2+n/2} + n^{3n}7^{n} 2^{-n^2 + 2n -1} + \sum_{i=4}^{n} n^{3n} 2^{in} 2^{-3n^2/2+9n/2-4} \\ & \leqslant n^{3n} 3^{n} 2^{-n^2/2+n/2} + n^{3n}7^{n} 2^{-n^2 + 2n -1} + n^{3n}2^{-3n^2/2+9n/2-4} \sum_{i=0}^{n} (2^n)^i \\ & = n^{3n} 3^{n} 2^{-n^2/2+n/2} + n^{3n}7^{n} 2^{-n^2 + 2n -1} + n^{3n}2^{-3n^2/2+9n/2-4} \frac{2^{n(n+1)}-1}{2^n-1}. \end{align*} $$
We have
$$ \begin{align*} n^{3n} 3^{n} 2^{-n^2/2+n/2} = 2^{3n\log_2(n) + \log_2(3)n-n^2/2+n/2}, \end{align*} $$
which clearly tends to
$0$
. Similarly,
$$ \begin{align*} n^{3n} 7^n 2^{-n^2+2n+1} = 2^{3n\log_2(n)+\log_2(7)n -n^2+2n-1}, \end{align*} $$
which tends to
$0$
. Lastly,
$$ \begin{align*} n^{3n}2^{-3n^2/2+9n/2-4} \frac{2^{n(n+1)}-1}{2^n-1} &= 2^{3n\log_2(n) - n^2/2+11n/2-4} \frac{2^{-n^2-n}(2^{n^2+n}-1)}{2^n-1} \\ & = 2^{3n\log_2(n)-n^2/2 +11n/2 -4} \frac{1-2^{-n^2-n}}{2^{n}-1}. \end{align*} $$
Now, it is clear that
$2^{3n\log _2(n)-n^2/2+9n/2-4}$
tends to
$0$
and
$(1-2^{-n^2-n})/(2^n-1)$
tends to
$0$
, hence the term above has limit
$0$
. Combining these results with basic limits, we get
$$ \begin{align*} \lim_{n\to \infty} \Bigg( \frac{1}{n}\sum_{i=1}^{n} \sum_{p = 1}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)}\Bigg) \leqslant 1, \end{align*} $$
and so
$$ \begin{align*} \lim_{n \to \infty} \Bigg(\frac{1}{(\sum_{i=1}^{n} \sum_{p = 1}^{\lfloor (n-i)/2 \rfloor} \binom{n}{i} \binom{n-i}{2}^p (2^i - 1)^n 2^{Q(n-i+1,n-i+1-2p)-Q(n,n)})/n}\Bigg) \geqslant 1. \end{align*} $$
By the Squeeze Principle, the fraction of members of
${\textsf {FAS}}$
with universe
$\{1,\dots ,n\}$
in
${\textsf {FSIAS}}$
tends to
$1$
. Combining these results, Propositions 2, 8, and 13(1), we find that almost all members of
${\textsf {FAS}}$
belong to
${\textsf {FSIAS}}$
, which is what we wanted.⊣
Combining this with Propositions 8 and 13(2), we obtain the following.
Corollary 23. Almost all finite nonassociative relation algebras are symmetric integral relation algebras.
Using Propositions 10 and 14, we obtain the following.
Corollary 24.
$2^{Q(n,n)}/(n-1)!$
is an asymptotic formula for the number of n-atom nonassociative relation algebras. The same formula holds if we add the assumption of associativity, symmetry, or e being an atom.
Next, we aim to establish a
$0$
–
$1$
law for
${\textsf {FAS}}$
. Based on Proposition 22, it will be enough to establish a
$0$
–
$1$
law for
${\textsf {FSIAS}}$
. We essentially follow the method outlined in the introduction of Bell and Burris in [Reference Bell and Burris2]. For the completeness proof required for this method, we will make use of a Fraïssé limit. It will be convenient to work with the class
${\textsf {FSIAS}}_e$
rather than
${\textsf {FSIAS}}$
, then translate the result, as
${\textsf {FSIAS}}$
does not have the HP. First, we show that a limit exists.
Lemma 25.
${\textsf {FSIAS}}_e$
has a Fraïssé limit.
Proof. By Theorem 19, it is enough to show that
${\textsf {FSIAS}}_e$
has the HP, JEP, and AP.
By definition,
${\textsf {FSIAS}}_e$
is the class of finite members of a universal class. Based on this,
${\textsf {FSIAS}}_e$
is closed under forming substructures, so
${\textsf {FSIAS}}_e$
clearly has the HP.
For the AP, let
${{\textbf {S}}},{{\textbf {V}}},{{\textbf {W}}} \in {\textsf {FSIAS}}_e$
and let
$\mu \colon {{\textbf {S}}} \to {{\textbf {V}}}$
and
$\nu \colon {{\textbf {S}}} \to {{\textbf {W}}}$
be embeddings. Without loss of generality, we can assume that
$V \cap W = S$
and
$\mu $
and
$\nu $
are inclusion maps. Thus, we can define
${{\textbf {U}}} \mathrel {\mathop :}= \langle U; f^{{\textbf {U}}},e, T^{{\textbf {U}}}\rangle $
, where
$U \mathrel {\mathop :}= V \cup W$
,
$f^{{\textbf {U}}}$
is given by
$$ \begin{align*} f^{{\textbf{U}}}(x) = \begin{cases} f^{{\textbf{V}}}(x), & \mbox{if } x \in V, \\ f^{{\textbf{W}}}(x), & \mbox{if } x \in W, \end{cases} \end{align*} $$
and
$T^{{\textbf {U}}} \mathrel {\mathop :}= T^{{\textbf {V}}} \cup T^{{\textbf {W}}}$
. Let
$a,b,c \in U$
and assume that
$(a,b,c) \in T^{{\textbf {U}}}$
. By construction, we have (
$a,b,c \in V$
and
$(a,b,c) \in T^{{\textbf {V}}}$
) or (
$a,b,c \in W$
and
$(a,b,c) \in T^{{\textbf {W}}}$
). In the first case,
$(f^{{\textbf {U}}}(a),c,b), (c,f^{{\textbf {U}}}(b),a) \in T^{{\textbf {U}}}$
, since
$T^{{\textbf {V}}} \subseteq T^{{\textbf {U}}}$
,
$f^{{\textbf {U}}}{\upharpoonright }_V = f^{{\textbf {V}}}$
, and
${{\textbf {V}}}$
satisfies (IP). Similarly, we have
$(f^{{\textbf {U}}}(a),c,b),(c,f^{{\textbf {U}}}(b),a) \in T^{{\textbf {U}}}$
in the second case, so
${{\textbf {U}}}$
satisfies (IP). Let
$a \in U$
. If
$a \in V$
, then we have
$(a,e,a) \in T^{{\textbf {U}}}$
, since
$T^{{\textbf {V}}} \subseteq T^{{\textbf {U}}}$
and
${{\textbf {V}}}$
satisfies (II). Similarly,
$(a,e,a) \in T^{{\textbf {U}}}$
when
$a \in W$
. Since
$U = V \cup W$
, it follows that
$(a,e,a) \in T^{{\textbf {U}}}$
in every case. Lastly, let
$a,b \in U$
such that
$(a,e,b) \in T^{{\textbf {U}}}$
. By construction, (
$a,b \in V$
and
$(a,e,b) \in T^{{\textbf {V}}}$
) or (
$a,b \in W$
and
$(a,e,b) \in T^{{\textbf {W}}}$
). Since
${{\textbf {V}}}$
and
${{\textbf {W}}}$
satisfy (II), we have
$a = b$
, so (II) holds. Since
${{\textbf {V}}}$
and
${{\textbf {W}}}$
both satisfy
$f(x) \approx x$
, it follows that
$f^{{\textbf {V}}}$
and
$f^{{\textbf {W}}}$
are both identity maps. By construction,
$f^{{\textbf {U}}}$
is an identity map, so
${{\textbf {U}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} f(x) \approx x$
. By definition,
$U = V \cup W$
, hence
$|U| \leqslant |V|+|W|$
. Thus, U is finite. Based the above results, we have
${{\textbf {U}}} \in {\textsf {FSIAS}}_e$
. Clearly, the inclusion maps
$\imath _V \colon V \to U$
and
$\imath _W \colon W \to U$
are embeddings and
$\imath _V \circ \mu = \imath _W \circ \nu $
. Combining these results, we find that
${\textsf {FSIAS}}_e$
has the AP, which is what we wanted to show.
Clearly,
${\textsf {FSIAS}}_e$
contains a trivial structure. This structure embeds into all
${{\textbf {A}}} \in {\textsf {FSIAS}}_e$
, so the JEP follows from the AP. Thus,
${\textsf {FSIAS}}_e$
has the HP, JEP and AP, as required.⊣
Definition 26 (
${{\textbf {L}}}_{{\textsf {SI}}}$
,
$T_{{\textsf {SI}}}$
, and
$S_{{\textsf {SI}}}$
)
Let
${{\textbf {L}}}_{{\textsf {SI}}}$
be a Fraïssé limit of
${\textsf {FSIAS}}_e$
, let
$T_{{\textsf {SI}}}$
be the first-order theory of
${{\textbf {L}}}_{{\textsf {SI}}}$
, and let
$S_{{\textsf {SI}}}$
be the almost sure theory of
${\textsf {FSIAS}}_e$
.
The elements of
${\textsf {FSIAS}}_e$
are symmetric, so generated substructures contain at most one extra element, namely e. So, by Proposition 21, we have the following.
Corollary 27.
$T_{{\textsf {SI}}}$
is
$\aleph _0$
-categorical and has quantifier elimination.
Next we introduce what Bell and Burris call extention axioms in [Reference Bell and Burris2]. The sentences essentially assert that a substructure can be extended by a single point in all possible ways. Here
$\neg ^0$
and
$\neg ^1$
mean no symbol and
$\neg $
, respectively.
Definition 28. Let
$A_{{\textsf {SI}}}$
be the set of first-order sentences of the form
where
$m \in \omega $
and
$c, c_i, c_{ij} \in \{0,1\}$
, for all
$1 \leqslant i \leqslant j \leqslant m$
.
Lemma 29. Let
${{\textbf {L}}}$
be countable model of (II), (IP), and
$f(x) \approx x$
. Then
${{\textbf {L}}} \cong {{\textbf {L}}}_{{\textsf {SI}}}$
if and only if
${{\textbf {L}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} A_{{\textsf {SI}}}$
.
Proof. For the forward direction, assume that
${{\textbf {L}}} \cong {{\textbf {L}}}_{{\textsf {SI}}}$
. Then
${{\textbf {L}}}$
is a Fraïssé limit of
${\textsf {FSIAS}}_e$
, hence the age of
${{\textbf {L}}}$
is
${\textsf {FSIAS}}_e$
and
${{\textbf {L}}}$
is ultrahomogeneous. Let
$n \in \omega $
, let
$c,c_i, c_{ij} \in \{0,1\}$
, for all
$1 \leqslant i \leqslant j \leqslant n$
, and let
$u_1,\dots , u_n \in L\setminus \{e^{{\textbf {L}}}\}$
. Let
${{\textbf {U}}}$
denote the substructure of
${{\textbf {L}}}$
generated by
$U \mathrel {\mathop :}= \{u_1,\dots ,u_n\}$
. Fix some element
$v \notin U$
and define
${{\textbf {V}}} \mathrel {\mathop :}= \langle V; f^{{\textbf {V}}}, e^{{\textbf {V}}}, T^{{\textbf {V}}}\rangle $
, where
$V \mathrel {\mathop :}= U \cup \{e^{{\textbf {F}}},v\}$
,
$f^{{\textbf {V}}} = \mathrm {id}_V$
,
$e^{{\textbf {V}}} = e^{{\textbf {L}}}$
, and
$T^{{\textbf {V}}}$
is given by
$$ \begin{align*} \begin{cases} T^{{\textbf{U}}} \cup [v,e^{{\textbf{L}}},v]\cup [v,v,v]&\\ \quad\cup \Big(\bigcup \{ [u_i,v,v] \mid c_i = 0\} \Big)\cup \Big(\bigcup\{ [u_i, u_j, v] \mid c_{ij} = 0\}\Big) & \mbox{if } c = 0, \\ T^{{\textbf{U}}} \cup [v,e^{{\textbf{L}}},v] \cup \Big(\bigcup \{ [u_i,v,v] \mid c_i = 0\} \Big)& \\ \quad \cup\Big(\bigcup\{ [u_i, u_j, v] \mid c_{ij} = 0\}\Big) & \mbox{if } c = 1. \end{cases} \end{align*} $$
Since the age of
${{\textbf {L}}}$
is
${\textsf {FSIAS}}_e$
, we must have
${{\textbf {U}}} \in {\textsf {FSIAS}}_e$
, so it is easy to see that
${{\textbf {V}}} \in {\textsf {FSIAS}}_e$
. Again, since the age
${{\textbf {L}}}$
is
${\textsf {FSIAS}}_e$
, there is a substructure
${{\textbf {W}}}$
of
${{\textbf {L}}}$
that is isomorphic to
${{\textbf {V}}}$
. Let
$\mu \colon {{\textbf {V}}} \to {{\textbf {W}}}$
be an isomorphism. Then
$\mu \circ \imath _U $
is an isomorphism from
${{\textbf {U}}}$
to the substructure of
${{\textbf {L}}}$
generated by
$\mu [U]$
. As
${{\textbf {L}}}$
is ultrahomogeneous,
$\mu \circ \imath _U $
extends to an automorphism, say
$\nu $
. Then, by construction,
$\nu ^{-1}(\mu (v))$
is the witness to the sentence from
$A_{{\textsf {SI}}}$
given by n, c, and each
$c_i$
, and
$c_{ij}$
, when choosing
$x_i = u_i$
, for each
$1 \leqslant i \leqslant n$
. Thus,
${{\textbf {L}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} A_{{\textsf {SI}}}$
.
Conversely, assume that
${\textbf {L}} \models A_{\sf SI}$
. To show that
${\textbf {L}} \cong {\textbf {L}}_{\sf SI}$
, we need to show that
${\sf FSIAS}_e$
is the age of
${\textbf {L}}$
and that
${\textbf {L}}$
is ultrahomogeneous. As
${\textbf {L}}$
is a symmetric model of (IP) and (II), the age of
${\textbf {L}}$
is a subset of
${\sf FSIAS}_e$
. Assume, for a contradiction, that this inclusion is proper. Let
${\textbf {U}}$
be an element of minimal size in
${\sf FSIAS}$
that is not in the age of
${\textbf {L}}$
. Clearly,
$|U|> 1$
. Now, let
$u \in U \setminus \{e^{\textbf {U}}\}$
and let
${\textbf {V}}$
denote the substructure of
${\textbf {U}}$
generated by
$ V := U \setminus \{u\}$
. By our minimality assumption,
${\textbf {V}}$
embeds into
${\textbf {L}}$
. Let
$\mu \colon {\textbf {V}} \to {\textbf {L}}$
be such an embedding. Let
$m := |V|-1$
, let
$\{v_1,\dots ,v_m\}$
be an enumeration of
$V\setminus \{e^{\textbf {V}}\}$
, let
$$\begin{align*}c := \begin{cases} 0 & {\textrm{if }} [u,u,u] \subseteq T^{\textbf{U}},\\ 1 & {\textrm{if }} [u,u,u] \nsubseteq T^{\textbf{U}}, \end{cases} \end{align*}$$
let
$$\begin{align*}c_i := \begin{cases} 0 & {\textrm{if }} [v_i,u,u] \subseteq T^{\textbf{U}}, \\ 1 & {\textrm{if }} [v_i,u,u] \nsubseteq T^{\textbf{U}}, \end{cases} \end{align*}$$
for all
$1 \le i \le m$
, and let
$$\begin{align*}c_{ij} := \begin{cases} 0 & {\textrm{if }} [v_i,v_j,u] \subseteq T^{\textbf{U}}, \\ 1 & {\textrm{if }} [v_i,v_j,u] \nsubseteq T^{\textbf{U}}, \end{cases} \end{align*}$$
for all
$1 \le i \le j \le m$
. As
${\textbf {L}} \models A_{\sf SI}$
,
${\textbf {L}}$
satisfies the sentence defined by c and each
$c_i$
and
$c_{ij}$
, so there is a witness, say y, for the choice of
$x_i := \mu (v_i)$
, for all
$1 \le i \le m$
. By construction, the substructure of
${\textbf {L}}$
generated by
$\mu [V] \cup \{y\}$
is isomorphic to
${\textbf {U}}$
. Thus,
${\textbf {U}}$
embeds into
${\textbf {L}}$
, so
${\textbf {U}}$
is in the age of
${\textbf {L}}$
, contradicting our assumption.
Lastly, based on Lemma 18, it will be enough to establish that
${\textbf {L}}$
is weakly homogeneous. Let
${\textbf {U}} \le {\textbf {V}}$
be finitely generated substructures of
${\textbf {L}}$
and let
$\mu \colon {\textbf {U}} \to {\textbf {L}}$
be an embedding. Note that since
${\textbf {L}}$
is symmetric, e is the only new element that can be generated by a subset. If
${\textbf {U}} = {\textbf {V}}$
, then we are done. Assume that
${\textbf {U}} \neq {\textbf {V}}$
and fix some
$v \in V \setminus U$
. Let
$m := |U|-1$
, let
$\{u_1,\dots ,u_m\}$
be an enumeration of
$U\setminus \{e^{\textbf {U}}\}$
, let
$$\begin{align*}c := \begin{cases} 0 & {\textrm{if }} [v,v,v] \subseteq T^{\textbf{V}},\\ 1 & {\textrm{if }} [v,v,v] \nsubseteq T^{\textbf{V}}, \end{cases} \end{align*}$$
let
$$\begin{align*}c_i := \begin{cases} 0 & {\textrm{if }} [u_i,v,v] \subseteq T^{\textbf{V}}, \\ 1 & {\textrm{if }} [u_i,v,v] \nsubseteq T^{\textbf{V}}, \end{cases} \end{align*}$$
for all
$1 \le i \le m$
, and let
$$\begin{align*}c_{ij} := \begin{cases} 0 & {\textrm{if }} [u_i,u_j,v] \subseteq T^{\textbf{V}}, \\ 1 & {\textrm{if }} [u_i,u_j,v] \nsubseteq T^{\textbf{V}}, \end{cases} \end{align*}$$
for all
$1 \le i \le j \le m$
. As
${\textbf {L}} \models A_{\sf SI}$
,
${\textbf {L}}$
satisfies the sentence defined by c and each
$c_i$
and
$c_{ij}$
, so there is a witness, say y, for the choice of
$x_i = \mu (u_i)$
, for all
$1 \le i \le m$
. By construction, the map
$\nu \colon U \cup \{v\} \to L$
given by
$$\begin{align*}\nu(x) = \begin{cases} \mu(x) & {\textrm{if }} x \in U, \\ y & {\textrm{if }} x = v \end{cases} \end{align*}$$
embeds the substructure of
${\textbf {V}}$
generated by
$U \cup \{v\}$
into
${\textbf {L}}$
. By assumption,
${\textbf {V}}$
is finite, hence
$\mu $
can be extended to an embedding
$\nu \colon {\textbf {V}} \to {\textbf {L}}$
by repeating this construction. Thus,
${\textbf {L}}$
is weakly homogeneous, which is what we wanted to show.⊣
Based on Theorem 19, we have the following.
Corollary 30. Together, (IP), (II),
$f(x) \approx x$
, and
$A_{{\textsf {SI}}}$
form a
$\aleph _0$
-categorical and therefore complete theory.
Lemma 31.
$A_{{\textsf {SI}}} \subseteq S_{{\textsf {SI}}}$
.
Proof. Let
$n \in \mathbb {N}$
, let
$m \in \omega $
, let
$c, c_i, c_{ij} \in \{0,1\}$
, for all
$1 \leqslant i \leqslant j \leqslant m$
, and let
$\sigma $
be the sentence from
$A_{{\textsf {SI}}}$
defined by these parameters. Clearly, given non-identity elements
$x_1,\dots ,x_m, y \in \{1,\dots ,n\}$
such that
$y \neq x_i$
, for all
$1 \leqslant i \leqslant n$
, at most
$$ \begin{align*} 1+m+\frac{m^2+m}{2} = \frac{m^2+3m+2}{2}, \end{align*} $$
cycles are forced to be consistent for
$\sigma $
to be satisfied for these given choices. Thus, the fraction of structures failing the sentence with these choices is below
$1-2^{-(m^2+3m+2)/2}$
. There are
$(n-1)^m$
ways to select
$x_1,\dots ,x_m$
,
$n-m-1$
ways to select y given
$x_1,\dots ,x_m$
, and the choices of y are independent once
$x_1,\dots ,x_n$
are selected. Based on these results, the fraction of structures not modelling
$\sigma $
is bounded above by
$$ \begin{align*} (n-1)^m (1-2^{-(m^2+3m+2)/2})^{n-m-1}.\\[-15pt] \end{align*} $$
Clearly,
$(n-1)^m \leqslant n^{m} = 2^{m\log _2(n)}$
and
$n-m -1 < n$
, so this quantity is below
$$ \begin{align*} 2^{m \log_2(n) + n\log_2(1-2^{-(m^2+3m+2)/2}) }. \\[-15pt]\end{align*} $$
Since
$1-2^{-(m^2+3m+2)/1} < 1$
, we have
$\log _2(1 -2^{-(m^2+3m+2)/2}) < 0$
, hence
$$ \begin{align*} \lim_{n \to \infty} 2^{m \log_2(n) + n\log_2(1-2^{-(m^2+3m+2)/2}) } = 0. \\[-15pt]\end{align*} $$
By the Squeeze Principle, the fraction of structures not modelling
$\sigma $
tends to 0. Thus,
$A_{{\textsf {SI}}} \subseteq S_{{\textsf {SI}}}$
, as claimed.⊣
So, based on Proposition 19 and Lemma 29, we have the following.
Corollary 32.
$S_{{\textsf {SI}}}$
is
$\aleph _0$
-categorical, and therefore complete. Thus,
${\textsf {FSIAS}}_e$
has a
$0$
–
$1$
law.
This result can be translated to a result for
${\textsf {FSIAS}}$
.
Corollary 33.
${\textsf {FSIAS}}$
has a
$0$
–
$1$
law.
Proof. Let
${{\textbf {U}}} \in {\textsf {FSIAS}}$
, let
$e^{{\textbf {U}}}$
be the unique element of I, let
${{\textbf {U}}}_e \mathrel {\mathop :}= \langle U; f^{{\textbf {U}}}, e^{{\textbf {U}}}, T^{{\textbf {U}}}\rangle $
, let
$\sigma $
be a
$\{f,T,I\}$
-sentence, and let
$\sigma _e$
be the
$\{f,e,T\}$
-sentence obtained from
$\varphi $
by replacing all occurences of
$I(x)$
, for some x, with
$x \approx e$
. By construction,
${{\textbf {U}}} \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} \varphi $
if and only if
${{\textbf {U}}}_e \mathrel {{|}\kern -0.47ex{=}\kern -1.725ex{=}} \varphi _e$
. As there is a one-to-one correspondence between isomorphism classes in
${\textsf {FSIAS}}$
and
${\textsf {FSIAS}}_e$
, this observation and Corollary 32 tell us that
${\textsf {FSIAS}}$
has a
$0$
–
$1$
law, as required.⊣
Hence, by Theorem 22, we have the following.
Corollary 34.
${\textsf {FAS}}$
has a
$0$
–
$1$
law.
4 Further work
Perhaps the most obvious open problem in this area is problem of determining whether almost all nonassociative relation algebras are representable; this problem is mentioned by Maddux in [Reference Maddux21] and by Hirsch and Hodkinson in [Reference Hirsch and Hodkinson13]. A possible first step to solving this problem could be solving the corresponding problems for the classes of feebly and qualitatively representable algebras introduced by Hirsch et al. in [Reference Hirsch, Jackson and Kowalski14].
Problem 1. Determine whether almost all nonassociative relation algebras are feebly, qualitatively, or (strongly) representable.
Determining whether or not Corollary 34 extends to the classes of nonassociative relation algebras and relation algebras would also be an interesting problem.
Problem 2. Determine whether
${\textsf {NA}}$
and
${\textsf {RA}}$
have
$0$
–
$1$
laws.
Acknowledgements
The author would like to thank Roger Maddux for suggesting the result from Corollary 23.
