{'fraction_non_alphanumeric': 0.05641933497536946, 'fraction_numerical': 0.009082512315270935, 'mean_word_length': 3.831907772406099, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computable Axiomatizability of Elementary Classes

The goal of this paper is to generalise Alex Rennet's proof of the non-axiomatizability of the class of pseudo-o-minimal structures. Rennet showed that if L is an expansion of the language of ordered fields and K is the class of pseudo-o-minimal L-structures (L-structures elementarily equivalent to an ultraproduct of o-minimal structures) then K is not computably axiomatizable. We give a general version of this theorem, and apply it to several classes of topological structures.


Introduction
Given a class K of L-structures, we write Th(K) for the first order theory of K; that is, the set of all Lsentences that are true in every structure of K. Recall that a class K is called elementary when M |= Th(K) if and only if M is an element of K, and that this holds if and only if K is closed under ultraproducts and ultraroots [6][Corollary 8.5.13]. We say that an elementary class K is computably axiomatizable if there is a computable axiomatization of Th(K). With this terminology, Rennet proved that the class of pseudo-ominimal fields is not computably axiomatizable.
Rennet's paper was motivated by a number of results, among them Ax's proof [1] that the theory of finite fields is decidable, and hence that the class of pseudo-finite fields is computably axiomatizable. As with finite fields, the class of o-minimal structures in a given language is not elementary: for instance, take an ultraproduct of structures {M n : n ∈ N }, where each M n is a copy of the real numbers with the usual ordering and a language which also contains a unary predicate for the set {0, 1, . . . , n}. It is easy to see that each M n is o-minimal, but that the ultraproduct has a copy of the natural numbers as a definable set; this is clearly not a finite union of points and intervals, and hence the ultraproduct is not o-minimal. Thus, the class of o-minimal structures is not closed under ultraproducts, and so is not elementary.
Multiple proposals were made for possible axiomatizations of the class of pseudo-o-minimal structures (see [3] and [11], for instance). However, Rennet showed that in the case where the language expands that of ordered fields, there is no computable axiomatization for the theory of o-minimality, and hence the class of pseudo-o-minimal structures is not computably axiomatizable.
In [4], Haskell and Macpherson developed the notion of C-minimality, a generalization of o-minimality obtained by replacing the binary ordering by a ternary relation. Haskell and Macpherson looked at another generalization of o-minimality in [5], P -minimality, which is defined so that P -minimal fields are p-adically closed, just as o-minimal fields are real closed. Given the similarities between these settings and o-minimality, they are both contexts in which it is natural to ask whether Rennet's theorem applies.
In this paper, we adapt Rennet's proof to apply to a more general theorem, which answers an open question posed by Rennet as well as allowing the proof to apply to other structures, such as C-minimal and P -minimal structures. Section 2 contains the preliminaries and proof of the generalized theorem, while Section 3 contains some examples, including the those mentioned above.

Preliminaries and the Generalized Theorem
Fix any computable language L 0 , and assume that L 1 is a proper computable expansion of L 0 containing at least one new unary predicate N . Unless stated otherwise, assume all structures and formulas are over the language L 1 .
Recall the notion of a provability relation which plays a fundamental role in the proof of Gödel's Second Incompleteness Theorem (see, for instance, [2]): if Γ is a computable list of sentences then there exists a binary relation prov(s, d) in Peano Arithmetic such that in the standard model, prov(s, d) if and only if d is the code number of a sentence and s is the code number for a proof of that sentence from Γ.
The following definition was developed by Pillay in [8]: Definition 1. Suppose M is a structure with a formula B(x,ȳ) (where x is a single variable andȳ is a tuple) such that the set of M-subsets {B(x,ā) M :ā ⊆ M } is a basis for a topology on M . We say that such an M is a first-order topological structure, or simply a topological structure. Note that for any M ′ ≡ M, (M ′ , B) is also a topological structure.
Theorem 1. Suppose K is a class of topological L 1 -structures such that for each A ∈ K, discrete definable subsets of A are finite. Let Λ be a computable list of L 1 -sentences which is a potential computable axiomatization for the class Th(K), and let T be the theory in the language L 2 = L 1 ∪ {α, µ, <, 0, 1} described below: If T is consistent then there is an L 1 -structure R L1 Λ which satisfies Λ, but is not elementarily equivalent to an ultraproduct of structures in K. Thus, the class {M : M |= Th(K)} is not computably axiomatizable.
Proof. Every model of T interprets a model of Peano Arithmetic, and so by Gödel's Second Incompleteness Theorem, T + ¬ Con(T ) is also consistent. Thus, there exists a model (A, N ) of T + ¬ Con(T ). In particular, if prov(s, d) is the provability relation for T and c is the Gödel number for the statement 0 = 1 then Fix x ∈ N with x ≥ a. Since (A, N ) satisfies the axiom schema (III), (A, N ≤x ) satisfies Λ. By Theorem 2.7 of [7], since N ≤x is an initial segment of a model N of PA with bounded portions of addition and multiplication, it is a ∆ 0 -elementary substructure of N . Thus, since a being a code for a proof of 0 = 1 in T is a ∆ 0 -property of a ∈ N ≤x , we have N ≤x |= ∃s prov(s, c).
We claim that (A, N ≤x ) is the desired structure R L1 Λ . Suppose for contradiction that (A, N ≤x ) is elementarily equivalent to an ultraproduct of structures in K: where U is a non-principal ultrafilter on I, and every (B i , M i ) is a structure in K. By elementary equivalence, (I), and Los's Theorem, U-most of the M i are discrete; since they are trivially definable, by assumption U-most of the M i are finite.
Then, since N ≤x is an initial segment of a model of PA, so is M and U-most of the M i . But U-most of the M i are finite, so U-most of the M i are finite initial segments of a model of PA, and hence are isomorphic to a substructure of N with universe {0, 1, . . . , n} for some n ∈ N. That is, U-most M i are isomorphic, for some n i , to the structure N ni = ({0, 1, . . . , n i }, α ≤ni , µ ≤ni , < ≤ni ).
As before, let c be a code for 0 = 1 and prov(d, s) the provability relation for T . Since N ≤x ≡ M, we have M |= ∃s prov(s, c). Choose an index i such that (B i , M i ) is an element of K and M i is isomorphic to some N ni as above. Then M i |= ∃s prov(s, c); but M i ∼ = N ni is a ∆ 0 -elementary substructure of N, which means there exists b ∈ N such that N |= prov(b, c). Because of the interpretation of prov(b, c) in the standard model N, this b corresponds to an actual proof of 0 = 1 in T . Hence T is inconsistent, contradicting our assumption, and so (A, N ≤x ) cannot be elementarily equivalent to an ultraproduct of structures in K.
Remark 1. Note that the requirement of the predicate N being included in the language is merely a convenience. Any occurrence of N could be replaced by a distinguished formula in one variable and the proof would be unaffected.

Consequences
The examples below are all straightforward consequences of the theorem, which amount to choosing an appropriate class for K and showing that the theory T from the theorem is consistent. The first answers positively a question posed by Rennet: does the result hold for o-minimality over languages which do not expand the field language? Example 1. The class of pseudo-o-minimal structures is not computably axiomatizable.
Proof. Let L 0 be the language {≤}, L 1 an appropriate expansion of L 0 , and K the class of o-minimal L 1structures. Let Λ be a purported axiomatization of the class of pseudo-o-minimal structures, and note that each A ∈ K has a topology with uniformly definable basis B(x, c, d) = {x : c < x < d}.
Suppose S ⊆ A is a discrete definable set in an o-minimal structure. Since S is a finite union of points and intervals and cannot contain any intervals, it must be a finite union of points, and so discrete definable sets in o-minimal structures are finite. Thus, K satisfies the assumptions of Theorem 1.
It remains to show that T is consistent. Consider the L 0 structure Q = (Q, <). We obtain an L 2 structure by interpreting N as the natural numbers, each other function or relation symbol in L 1 as the empty function or relation, and the symbols in L 2 by their usual meanings in the natural numbers. Under this interpretation, N is clearly a discrete embedding of Peano Arithmetic. Since each initial segment of N is finite, each (Q, <, N ≤x ) is a definitional expansion of (Q, <). Then, since (Q, <) is o-minimal, Q |= ∀x ∈ N φ ≤x for each φ ∈ Λ.
Example 2. The class of pseudo-P -minimal structures is not computably axiomatizable.
Proof. Let L 0 be the language used in [5], L 1 an appropriate expansion of L 0 , and K the class of P -minimal L 1 -structures. Let Λ be a purported axiomatization of the class of pseudo-P -minimal structures, and note that each A ∈ K has a topology with uniformly definable basis It follows from Lemma 4.3 of [5] that every discrete definable set in a P -minimal structure is finite.
To show T is consistent, consider the p-adic numbers Q p with N interpreted as the set {p n : n ∈ N} and each other function or relation symbol in L 1 interpreted as the empty set. Clearly, N is discrete; if we choose interpretations for α, µ, <, 0, 1 via the bijection p n ⇐⇒ n between N ⊆ Q p and the natural numbers, we get that N is a model of Peano Arithmetic. Finally, we see that that condition (III) holds via the same definitional expansion argument given in the o-minimal case.
Example 3. The class of pseudo-C-minimal structures is not computably axiomatizable.
Proof. We use the notion of C-minimality from [4]. Let L 0 be the language consisting only of a C-relation C, L 1 an appropriate expansion of L 0 , and K the class of C-minimal L 1 -structures. Then the cones B(x, b, c) = {x : C(b; c, x)} are a uniformly definable basis for a topology on each A ∈ K. As noted in Lemma 2.4 of [4], discrete definable sets in C-minimal structures are finite.
Note that a reduct of any C-minimal structure to the language L 0 will still be C-minimal, as removing elements of the language other than the C-relation does not affect the definable sets. Consider the structure A consisting of the algebraic numbers with the C-relation C(x, y, where v is any p-adic valuation. Taking the same interpretation of N, α, µ, <, 0, 1 as in the P -minimal case, we get a discrete embedding of Peano Arithmetic in A. Since the initial segments of N are again finite, and hence definitional expansions of A, we get condition (III).
In section 3 of [8], Pillay defines a dimension rank D M for first order topological structures, which we will not repeat here. He notes that every first order topological structure is either unstable or has the discrete topology (in which case the theorem is either trivially true or trivially false, depending on whether the structure is infinite). However, he does introduce a different notion of stability for such structures: In the case of an ordered structure, t-minimality is equivalent to o-minimality [8,Proposition 6.2]. Any algebraic Lie group over R or C is t.t.t., and the one-dimensional examples are t-minimal. Let M = (Q, B), where B(x, y 1 , y 2 ) is the relation y 1 < x < y 2 if y 1 < y 2 , x < y 1 if y 1 = y 2 , and x > y 1 if y 1 > y 2 . As in the o-minimal example, we obtain an L 2 structure by interpreting N as the natural numbers, every other L 1 function or relation as the empty set, and α, µ, <, 0, 1 as their usual interpretations in the natural numbers. Clearly, N is a discrete model of Peano Arithmetic, which gives conditions (I) and (II). It remains to show that M ≤x = (Q, B, {0, 1, . . . , x}, . . .) is t.t.t. and hence that T is consistent.
First, note that B gives the usual topology on Q, which is cleary Hausdorff, and thus we have condition (D) of t.t.t. Moreover, the definable sets in M ≤x are precisely the same as those in (Q, <), and hence are finite unions of points and intervals: this gives conditions (A) and (B). Finally, any set X ⊆ M without interior in M must be a finite union of points, in which case D M (X) = 0, and so D M (M ) = 1. This is equivalent to condition (C) by Proposition 3.7 of [8]. Thus, M satisfies condition (III), which means T is consistent and Theorem 1 can be applied.
Example 5. The class of pseudo-t-minimal structures is not computably axiomatizable.
Proof. In the previous example, we have already shown everything necessary except that the structure M ≤x = (Q, B, {0, 1, . . . , x}, . . .) has d(M ) = 1. But this is equivalent to saying that Q (with its usual topology) is connected, which is clearly true.