We study model theoretic properties of valued fields (equipped with a real-valued multiplicative valuation), viewed as metric structures in continuous first order logic.

For technical reasons we prefer to consider not the valued field (K, |·|) directly, but rather the associated projective spaces KPn, as bounded metric structures.

We show that the class of (projective spaces over) metric valued fields is elementary, with theory MVF, and that the projective spaces Pn and are Pm biinterpretable for every n, m ≥ 1. The theory MVF admits a model completion ACMVF, the theory of algebraically closed metric valued fields (with a nontrivial valuation). This theory is strictly stable (even up to perturbation).

Similarly, we show that the theory of real closed metric valued fields, RCMVF, is the model companion of the theory of formally real metric valued fields, and that it is dependent.

In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initial formula. All $\text {OBDD}$ s in such proofs have the same order of variables. We initiate the study of $\text {OBDD}$ based proof systems that additionally contain a rule that allows changing the order in $\text {OBDD}$ s. At first we consider a proof system $\text {OBDD}(\land , \text{reordering})$ that uses the conjunction (join) rule and the rule that allows changing the order. We exponentially separate this proof system from $\text {OBDD}(\land )$ proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of $\text {OBDD}(\land , \text{reordering})$ refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for $\text {OBDD}(\land )$ proofs and the second one extends the result of Tveretina et al. from $\text {OBDD}(\land )$ to $\text {OBDD}(\land , \text{reordering})$ .

In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on $\text {OBDD}$ s and symbolic quantifier elimination (we denote algorithms based on this approach as $\text {OBDD}(\land , \exists )$ algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme $\text {OBDD}(\land , \exists , \text{reordering})$ algorithms. We notice that there exists an $\text {OBDD}(\land , \exists )$ algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time (a standard example of a hard system of linear equations over $\mathbb {F}_2$ ), but we show that there are formulas representing systems of linear equations over $\mathbb {F}_2$ that are hard for $\text {OBDD}(\land , \exists , \text{reordering})$ algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over $\mathbb {F}_2$ that correspond to checksum matrices of error correcting codes.

A relation on a linearly ordered structure is called semi-bounded if it is definable in an expansion of the structure by bounded relations. We study ultimate behavior of semi-bounded relations in an ordered module M over an ordered commutative ring R such that M/rM is finite for all nonzero r ϵ R. We consider M as a structure in the language of ordered R-modules augmented by relation symbols for the submodules rM, and prove several quantifier elimination results for semi-bounded relations and functions in M. We show that these quantifier elimination results essentially characterize the ordered modules M with finite indices of the submodules rM. It is proven that (1) any semi-bounded k-ary relation on M is equal, outside a finite union of k-strips, to a k-ary relation quantifier-free definable in M, (2) any semibounded function from Mk to M is equal, outside a finite union of k-strips, to a piecewise linear function, and (3) any semi-bounded in M endomorphism of the additive group of M is of the form x ↦ σx, for some σ from the field of fractions of R.

If ${\cal M},{\cal N}$ are countable, arithmetically saturated models of Peano Arithmetic and ${\rm{Aut}}\left( {\cal M} \right) \cong {\rm{Aut}}\left( {\cal N} \right)$, then the Turing-jumps of ${\rm{Th}}\left( {\cal M} \right)$ and ${\rm{Th}}\left( {\cal N} \right)$ are recursively equivalent.

Supercompact extender based forcings are used to construct models with HOD cardinal structure different from those of V. In particular, a model where all regular uncountable cardinals are measurable in HOD is constructed.

We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

Let {We}e∈ω be a standard enumeration of the recursively enumerable (r.e.) subsets of ω = {0,1,2,…}. The lattice of recursively enumerable sets, , is the structure ({We}e∈ω,∪,∩). ≡ is a congruence relation on if ≡ is an equivalence relation on and if for all U, U′ ∈ and V, V′ ∈ , if U ≡ U′ and V ≡ V′, then U ∪ V ≡ U′ ∪ V′ and U ∩ V ≡ U′ ∩ V′. [U] = {V ∈ | V ≡ U} is the equivalence class of U. If ≡ is a congruence relation on , the elements of the quotient lattice / ≡ are the equivalence classes of ≡. [U] ∪ [V] is defined as [U ∪ V], and [U] ∩ [V] is defined as [U ∩ V]. We say that a congruence relation ≡ on is if {(i, j)| Wi ≡ Wj} is . Define =* by putting Wi, =* Wj if and only if (Wi − Wj)∪ (Wj − Wi) is finite. Then =* is a congruence relation. If D is any set, then we can define a congruence relation by putting Wi Wj if and only if Wi ∩ D =* Wj ∩D. By Hammond [2], a congruence relation ≡ ⊇ =* is if and only if ≡ is equal to for some set D.

The Friedberg splitting theorem [1] asserts that if A is any recursively enumerable set, then there exist disjoint recursively enumerable sets A0 and A1 such that A = A0∪ A1 and such that for any recursively enumerable set B

Call a family of subsets of a set E inductive if and is closed under unions with disjoint singletons, that is, if

A Frege structure is a pair (E, ν) with ν a map to E whose domain dom(ν) is an inductive family of subsets of E such that

In [2] it is shown in a constructive setting that each Frege structure determines a subset which is the domain of a model of Peano's axioms. In this note we establish, within the same constructive setting, three facts. First, we show that the least inductive family of subsets of a set E is precisely the family of decidable Kuratowski finite subsets of E. Secondly, we establish that the procedure presented in [2] can be reversed, that is, any set containing the domain of a model of Peano's axioms determines a map which turns the set into a minimal Frege structure: here by a minimal Frege structure is meant one in which dom(ν) is the least inductive family of subsets of E. And finally, we show that the procedures leading from minimal Frege structures to models of Peano's axioms and vice-versa are mutually inverse. It follows that the postulation of a (minimal) Frege structure is constructively equivalent to the postulation of a model of Peano's axioms.

All arguments will be formulated within constructive (intuitionistic) set theory.

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ïssé 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.

We show that the Lascar group $\operatorname {Gal}_L(T)$ of a first-order theory T is naturally isomorphic to the fundamental group $\pi _1(|\mathrm {Mod}(T)|)$ of the classifying space of the category of models of T and elementary embeddings. We use this identification to compute the Lascar groups of several example theories via homotopy-theoretic methods, and in fact completely characterize the homotopy type of $|\mathrm {Mod}(T)|$ for these theories T. It turns out that in each of these cases, $|\operatorname {Mod}(T)|$ is aspherical, i.e., its higher homotopy groups vanish. This raises the question of which homotopy types are of the form $|\mathrm {Mod}(T)|$ in general. As a preliminary step towards answering this question, we show that every homotopy type is of the form $|\mathcal {C}|$ where $\mathcal {C}$ is an Abstract Elementary Class with amalgamation for $\kappa $ -small objects, where $\kappa $ may be taken arbitrarily large. This result is improved in another paper.

We study model theory of actions of finite groups on substructures of a stable structure. We give an abstract description of existentially closed actions as above in terms of invariants and PAC structures. We show that if the corresponding PAC property is first order, then the theory of such actions has a model companion. Then, we analyze some particular theories of interest (mostly various theories of fields of positive characteristic) and show that in all the cases considered the PAC property is first order.

In most published systems of modal logic only one or two modal operators occur as undefined constants alongside the primitives of non-modal logic. But in a single informal argument many non-interdefinable modal operators may occur. E.g. in philosophy we may have ‘it is logically true that’, ‘it is analytic that’, and ‘it is physically necessary that’; and in jurisprudence or private international law we may have statements about what it is obligatory or not obligatory to do under several different systems of rules. Moreover even if the contexts of such operators are all referentially opaque, in Quine's sense [1] of being exempt from the substitutivity of truth-functional biconditionals, some are, as it were, opaquer than others, in being exempt from the substitutivity of certain non-truth-functional biconditionals as well.

Let be a finite sequence of algebras of sets given on a set with more than pairwise disjoint sets not belonging to It was shown in [4] and [5] that in this case Let us consider, instead a finite sequence of algebras It turns out that if for each natural i ≤ l there exist no less than pairwise disjoint sets not belonging to then But if l ≥ 195 and if for each natural i ≤ l there exist no less than pairwise disjoint sets not belonging to then After consideration of finite sequences of algebras, it is natural to consider countable sequences of algebras. We obtained two essentially important theorems on a countable sequence of almost σ-algebras (the concept of almost σ-algebra was introduced in [4]).