Logic (math.LO)

  • PDF
    Russell is a logical framework for the specification and implementation of deductive systems. It is a high-level language with respect to Metamath language, so inherently it uses a Metamath foundations, i.e. it doesn't rely on any particular formal calculus, but rather is a pure logical framework. The main difference with Metamath is in the proof language and approach to syntax: the proofs have a declarative form, i.e. consist of actual expressions, which are used in proofs, while syntactic grammar rules are separated from the meaningful rules of inference. Russell is implemented in c++14 and is distributed under GPL v3 license. The repository contains translators from Metamath to Russell and back. Original Metamath theorem base (almost 30 000 theorems) can be translated to Russell, verified, translated back to Metamath and verified with the original Metamath verifier. Russell can be downloaded from the repository https://github.com/dmitry-vlasov/russell
  • PDF
    By a pure logical framework we mean a framework which does not rely on any particular formal calculus. For example, Metamath is an instance of a pure logical framework. Another example is the Russell system (https://github.com/dmitry-vlasov/russell). In this paper, we describe the proof search algorithm used in Russell. The algorithm is proved to be correct and complete, i.e. it gives only valid proofs and any valid proof can be found (up to a substitution) by the proposed algorithm.
  • PDF
    We prove that, given $\epsilon>0$ and an integer $k\geq 1$, there is an integer $n$ such that the following holds. Suppose $G$ is a sufficiently large finite group, and $A\subseteq G$ is $k$-stable. Then there is a subgroup $H$ of $G$, of index at most $n$, and $Y\subseteq G$, which is a union of left cosets of $H$, such that $|A\vartriangle Y|\leq\epsilon|H|$. It follows that, for any left coset $C$ of $H$, either $|C\cap A|\leq \epsilon|H|$ or $|C\setminus A|\leq \epsilon|H|$. This generalizes recent work of Terry and Wolf on vector spaces over $\mathbb{F}_p$.
  • PDF
    We prove that the Fraïssé limit of a Fraïssé class $\mathcal C$ is the (unique) countable structure whose isomorphism type is comeager (with respect to a certain logic topology) in the Baire space of all structures whose age is contained in $\mathcal C$ and which are defined on a fixed countable universe. In particular, the set of groups isomorphic to Hall's universal group is comeager in the space of all countable locally finite groups and the set of fields isomorphic to the algebraic closure of $\mathbb F_p$ is comeager in the space of countable fields of characteristic $p$.
  • PDF
    Let $L$ be a countable language. We characterize, in terms of definable closure, those countable theories $\Sigma$ of $\mathcal{L}_{\omega_1, \omega}(L)$ for which there exists an $S_\infty$-invariant probability measure on the collection of models of $\Sigma$ with underlying set $\mathbb{N}$. Restricting to $\mathcal{L}_{\omega, \omega}(L)$, this answers an open question of Gaifman from 1964, via a translation between $S_\infty$-invariant measures and Gaifman's symmetric measure-models with strict equality. It also extends the known characterization in the case where $\Sigma$ implies a Scott sentence. To establish our result, we introduce machinery for building invariant measures from a directed system of countable structures with measures.