On the $n$-back-and-forth types of Boolean algebras
Open Access
- 1 February 2012
- journal article
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 364 (2) , 827-866
Abstract
The objective of this paper is to uncover the structure of the back-and-forth equivalence classes at the finite levels for the class of Boolean algebras. As an application, we obtain bounds on the computational complexity of determining the back-and-forth equivalence classes of a Boolean algebra for finite levels. This result has implications for characterizing the relatively intrinsically <!-- MATH $\Sigma^0_n$ --> relations of Boolean algebras as existential formulas over a finite set of relations.
Keywords
This publication has 15 references indexed in Scilit:
- Boolean Algebras, Tarski Invariants, and Index SetsNotre Dame Journal of Formal Logic, 2006
- The isomorphism problem for computable Abelian p-groups of bounded lengthThe Journal of Symbolic Logic, 2005
- Computable Homogeneous Boolean Algebras and a MetatheoremAlgebra and Logic, 2004
- Back and forth relations for reduced abelian p-groupsAnnals of Pure and Applied Logic, 1995
- Every Low Boolean Algebra is Isomorphic to a Recursive OneProceedings of the American Mathematical Society, 1994
- Pairs of recursive structuresAnnals of Pure and Applied Logic, 1990
- Categoricity in hyperarithmetical degreesAnnals of Pure and Applied Logic, 1987
- Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical DegreesTransactions of the American Mathematical Society, 1986
- Stability of recursive structures in arithmetical degreesAnnals of Pure and Applied Logic, 1986
- Topological Model Theory1980