{'fraction_non_alphanumeric': 0.055912749440396245, 'fraction_numerical': 0.011096823355717484, 'mean_word_length': 3.6912421805183198, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Finite Relation Algebras

We will show that almost all nonassociative relation algebras are symmetric and integral (in the sense that the fraction of both labelled and unlabelled structures that are symmetric and integral tends to 1), and using a Fra\"iss\'e limit, we will establish that the classes of all atom structures of nonassociative relation algebras and relation algebras both have 0-1 laws. As a consequence, we obtain improved asymptotic formulas for the numbers of these structures and broaden some known probabilistic results on relation algebras.


Introduction
The calculus of relations is a branch of logic that was developed in the nineteenth century, largely due to the work of Augustus De Morgan, Charles Peirce, and Ernst Schröder; see [6], [22], and [24], for example. By the beginning of twentieth century, the calculus of relations was considered to be an important branch of logic. Indeed, in [23], Bertrand 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 [1]. Interest in the field mostly faded until the publication of [25], where Alfred 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 Rudolf Carnap (see [3]), but similar ideas appeared earlier. In [7] and [8], Ronald 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ȋ, Kogan, Liogon'kiȋ, and Talanov in the nineteen seventies; see [12] and [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 Kevin Compton in [4] and [5]. In the context of relation algebras, there has been surprisingly little research published on probabilistic results of this nature. In [19], Roger 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.

Preliminaries
We begin by giving a formal definition of labelled and unlabelled probabilities of properties. We will mostly follow the approach taken in [10]. Note that by N we mean {1, 2, . . . }. Definition 1 (Probabilities). Let 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 ∈ N, let U n be a set with precisely one representative from each isomorphism class of n-element structures from K and let L n be the set of all structures in K with universe {1, . . . , n}. Let P be some property of F -structures that is invariant under isomorphisms (for example, a firstorder property). Let s : N → N be the increasing sequence of values of n with U n = ∅. If the limit exists, we call it the unlabelled probability of P and denote it by Pr U (P, K). If the limit exists, we call it the labelled probability of P and denote it by Pr L (P, K). If Pr U (P, K) = 1, we say that almost all structures in 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 [10] 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 [8].

Proposition 2.
Let 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 Pr L (R, K) = 1. If one of Pr U (P, K) and Pr L (P, K) exists, then both quantities exist and are equal. Now we are in the position to recall the definiton of an almost sure theory. Definition 3 (Almost sure theory). Let 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 σ with Pr L (σ, K) = 1 the almost sure theory of K.
Next, we will give a brief introduction to relation algebras. For a more extensive introduction, we refer the reader to Hirsch and Hodkinson [13], Maddux [20], and Givant [11]. We begin by defining relation algebras. To match the notation used in lattice theory, we will use ∨ and ∧ rather than + and ·. This allows us to use a more group theoretic notation by using · and e rather than ; and 1 ′ . We will assume that unary operations are applied first and use multiplicative notation for ·. Therefore x˘z ∧ y ′ means ((x˘) · z) ∧ (y ′ ), for example. We call d := e ′ the diversity element. We use ≈ for logical equality, as in universal algebra. To avoid reusing symbols, we wil use for logical disjunction, for logical conjunction, and ¬ for logical negation. Where it is possible, we will usually drop superscripts on operations.

Definition 4 (Relation algebras
). An algebra A = A; ∨, ∧, ·, ′ ,˘, 0, 1, e is called a nonassociative relation algebra iff A; ∨, ∧, ′ , 0, 1 is a Boolean algebra, e is an identity element for ·, and the triangle laws hold, i.e., we have for all x, y, z ∈ A. The class of all nonassociative relation algebras will be denoted by NA. An algebra A ∈ NA is called a relation algebra iff · is associative. The class of all relation algebras will be denoted by RA. An algebra A ∈ NA is said to be symmetric iff A | = = x˘≈ 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.
5. If a is an atom, then a˘is an atom.
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 A ∈ 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. It turns out that these structures can be axiomatised.
We call a {f, T, I}-structure U integral iff we have |I| = 1, and symmetric iff The class of all symmetric and integral members of FAS will be denoted by FSIAS. Now, let 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) ≈ x and The above definition abuses language slightly; a non-trivial A ∈ NA is called integral iff xy = 0 implies that x = 0 or y = 0, which is equivalent to e being an atom when A ∈ RA, but not in general. We refer to Maddux [20] and Maddux [21] for further details. Next, we introduce the notion of a cycle (from Maddux [19]) which can be used to define and describe these structures.

Definition 9 (Cycles). Let U be a {f, T, I}-structure and let
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 ∩ {a, b, c} = ∅, and a diversity triple otherwise. We call [a, b, c] an identity cycle iff it contains an identity triple, and a diversity cycle other- We call a an identity atom iff a ∈ I and a diversity atom otherwise. We extend these ideas to {f, e, T } in the obvious way.
The following result from [19] illustrates the connection between cycles and the axioms for FAS and FSIAS e .
(a) The following are equivalent: The following are equivalent: Based on Proposition 8 and Proposition 10, once given a finite set U , some e ∈ U , and an involution f : U → U with f (e) = e, each U ∈ FAS that is an expansion of U ; f, {e} 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 [19], Maddux obtains asymptotic formulas using this method. The results we will need from [19] are summarised in the following results.  4. There are (n − 1)((n − 1) 2 − 3s + 2)/6 + (s − 1)/2 diversity cycles with 6 triples.
6. There are P (n, s) : 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 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 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 [17]. Therefore one might be interested in the asymptotics of the fraction of representable relation algebras. Maddux took the first steps in this direction in [19].
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 Roland Fraïssé in [9]. We will mostly follow Hodges [15]. Firstly, we recall some definitions.
Definition 15 (Age). Let A be a structure. The age of A is the class of all finitely generated structures that embed into A.
Definition 16 (HP, JEP, and AP). Let K be a class of similar structures. We say that K has the hereditary property (HP) iff K is closed under forming finitely generated structures. We say that K has the joint embedding property (JEP) iff, for all A, B ∈ K, there is some C ∈ K that both A and B embed into. We say that K has the amalgamation property (AP) iff, for all A, B, C ∈ K and embeddings µ : A → B and ν : A → C, there is some D ∈ K and embeddings µ ′ : B → D and ν ′ : Definition 17 (Homogeneity). Let A be a structure. We call A ultrahomogenous iff every isomorphism between finitely generated substructures of A extends to an automorphism of A. We call A weakly homogeneous iff, for all finitely generated structures B and C of A with B C and all embeddings µ : B → A, there is an embedding ν : C → A extending µ.
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. (Fraïssé's Theorem). Let S be a countable signature and let K be a class of at most countable S-structures, that has the HP, JEP, and AP. Then there is an S-structure F (called a Fraïssé limit of K), unique up to isomorphism, such that F is at most countable, K is the age of F, and F is ultrahomogeneous.

Proposition 19
To state the last result of this section, we need to recall some definitions.
Definition 20 (Uniform local finiteness). Let K be a class of similar structures. We say that K is uniformly locally finite iff there is a function f : N → N, such that, for all A ∈ K, each n ∈ N, and every subset S of A with |S| n, the substructure of A generated by S has cardinality at most f (n).

Proposition 21. Let S be a finite signature, let 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 F be a Fraïssé limit of K.
Then the first-order theory of F is ℵ 0 -categorical and has quantifier elimination.
By the Squeeze Principle, the fraction of members of FAS with universe {1, . . . , n} in FSIAS tends to 1. Combining these results, Proposition 2, Proposition 8, and Proposition 13(1), we find that almost all members of FAS belong to FSIAS, which is what we wanted.
Combining this with Proposition 8 and Proposition 13. 2., we obtain the following.

Corollary 23. Almost all finite nonassociative relation algebras are symmetric integral relation algebras.
Using Proposition 10 and Proposition 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 FAS. Based on Proposition 22, it will be enough to establish a 0-1 law for FSIAS. We essentially follow the method outlined in the introduction of Bell and Burris in [2]. 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 FSIAS e rather than FSIAS, then translate the result, as FSIAS does not have the HP. First, we show that a limit exists.

Lemma 25. FSIAS e has a Fraïssé limit.
Proof. By Theorem 19, it is enough to show that FSIAS e has the HP, JEP, and AP.
By definition, FSIAS e is the class of finite members of a universal class. Based on this, FSIAS e is closed under forming substructures, so FSIAS e clearly has the HP.
For the AP, let S, V, W ∈ FSIAS e and let µ : S → V and ν : S → W be embeddings. Without loss of generality, we can assume that V ∩ W = S and µ and ν are inclusion maps. Thus, we can define U := U ; f U , e, T U , where U := V ∪ W , f U is given by and T U := T V ∪ T W . Let a, b, c ∈ U and assume that (a, b, c) ∈ T U . By construction, we have (a, b, c ∈ V and (a, b, c) ∈ T V ) or (a, b, c ∈ W and (a, b, c) ∈ T W ). In the first case, If a ∈ V , then we have (a, e, a) ∈ T U , since T V ⊆ T U and V satisfies (II). Similarly, (a, e, a) ∈ T U when a ∈ W . Since U = V ∪ W , it follows that (a, e, a) ∈ T U in every case. Lastly, let a, b ∈ U such that (a, e, b) ∈ T U . By construction, (a, b ∈ V and (a, e, b) ∈ T V ) or (a, b ∈ W and (a, e, b) ∈ T W ). Since V and W satisfy (II), we have a = b, so (II) holds. Since V and W both satisfy f (x) ≈ x, it follows that f V and f W are both identity maps.
By construction, f U is an identity map, so U | = = f (x) ≈ x. By definition, U = V ∪ W , hence |U | |V | + |W |. Thus, U is finite. Based the above results, we have U ∈ FSIAS e . Clearly, the inclusion maps ı V : V → U and ı W : W → U are embeddings and ı V •µ = ı W •ν. Combining these results, we find that FSIAS e has the AP, which is what we wanted to show.
Clearly, FSIAS e contains a trivial structure. This structure embeds into all A ∈ FSIAS e , so the JEP follows from the AP. Thus, FSIAS e has the HP, JEP and AP, as required.
Definition 26 (L SI , T SI , and S SI ). Let L SI be a Fraïssé limit of FSIAS e , let T SI be the first-order theory of L SI , and let S SI be the almost sure theory of FSIAS e .
The elements of FSIAS e are symmetric, so generated substructures contain at most one extra element, namely e. So, by Proposition 21, we have the following.
Next we introduce what Bell and Burris call extention axioms in [2]. The sentences essentially assert that a substructure can be extended by a single point in all possible ways. Here ¬ 0 and ¬ 1 mean no symbol and ¬, respectively.
Definition 28. Let A SI be the set of first-order sentences of the form Since the age of L is FSIAS e , we must have U ∈ FSIAS e , so it is easy to see that V ∈ FSIAS e . Again, since the age L is FSIAS e , there is a substructure W of L that is isomorphic to V. Let µ : V → W be an isomorphism. Then µ • ı U is an isomorphism from U to the substructure of L generated by µ [U ]. As L is ultrahomogeneous, µ • ı U extends to an automorphism, say ν. Then, by construction, ν −1 (µ(v)) is the witness to the sentence from A SI given by n, c, and each c i , and c ij , when choosing x i = u i , for each 1 i n. Thus, L | = = A SI . Conversely, assume that L | = = A SI . To show that L ∼ = L SI , we need to show that FSIAS e is the age of L and that L is ultrahomogeneous. As L is a symmetric model of (IP) and (II), the age of L is a subset of FSIAS e . Assume, for a contradiction, that this inclusion is proper. Let U be an element of minimal size in FSIAS that is not in the age of L. Clearly, |U | > 1. Now, let u ∈ U \ {e U } and let V denote the substructure of U generated by V := U \ {u}.
for all 1 i m, and let for all 1 i j m. As L | = = A SI , 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 := µ(v i ), for all 1 i m. By construction, the substructure of L generated by µ[V ] ∪ {y} is isomorphic to U. Thus, U embeds into L, so U is in the age of L, contradicting our assumption. Lastly, based on Lemma 18, it will be enough to establish that L is weakly homogeneous. Let U V be finitely generated substructures of L and let µ : U → L be an embedding. Note that since L is symmetric, e is the only new element that can be generated by a subset. If U = V, then we are done. Assume that U = V and fix some v ∈ V \ U . Let m := |U | − 1, let {u 1 , . . . , u m } be an enumeration of U \ {e U }, let for all 1 i m, and let for all 1 i j m. As L | = = A SI , 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 = µ(u i ), for all 1 i m. By construction, the map ν : U ∪ {v} → L given by embeds the substructure of V generated by U ∪ {v} into L. By assumption, V is finite, hence µ can be extended to an embedding ν : V → L by repeating this construction. Thus, L is weakly homogeneous, which is what we wanted to show.
Based on Theorem 19, we have the following.
Proof. Let n ∈ N, let m ∈ ω, let c, c i , c ij ∈ {0, 1}, for all 1 i j m, and let σ be the sentence from A SI defined by these parameters. Clearly, given non-identity elements x 1 , . . . , x m , y ∈ {1, . . . , n} such that y = x i , for all 1 i n, at most cycles are forced to be consistent for σ 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 , . . . , x m , n − m − 1 ways to select y given x 1 , . . . , x m , and the choices of y are independent once x 1 , . . . , x n are selected. Based on these results, the fraction of structures not modelling σ is bounded above by Clearly, (n − 1) m n m = 2 m log 2 (n) and n − m − 1 < n, so this quantity is below 2 m log 2 (n)+n log 2 (1−2 −(m 2 +3m+2)/2 ) .
By the Squeeze Principle, the fraction of structures not modelling σ tends to 0. Thus, A SI ⊆ S SI , as claimed.
So, based on Proposition 19 and Lemma 29, we have the following.
This result can be translated to a result for FSIAS. As there is a one-to-one correspondence between isomorphism classes in FSIAS and FSIAS e , this observation and Corollary 32 tell us that FSIAS has a 0-1 law, as required.
Hence, by Theorem 22, we have the following.

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 [18] and by Hirsch and Hodkinson in [13]. 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, Jackson, and Kowalski in [14].
Determining whether or not Corollary 34 extends to the classes of nonassociative relation algebras and relation algebras would also be an interesting problem.

Acknowledgements
This is a pre-print of a paper contributed to the Journal of Symbolic Logic. The final authenticated version is available at: https://doi.org/10.1017/jsl.2021.81. The author would like to thank Roger Maddux for suggesting the result from Corollary 23.