Bases for Structures and Theories II

In Part I of this paper (Ketland in Logica Universalis 14:357–381, 2020), I assumed we begin with a (relational) signature P = {Pi} and the corresponding language LP , and introduced the following notions: a definition system dΦ for a set of new predicate symbols Qi, given by a set Φ = {φi} of defining LP -formulas (these definitions have the form: ∀x(Qi(x) ↔ φi)); a corresponding translation function τΦ : LQ → LP ; the corresponding definitional image operator DΦ, applicable to LP - structures and LP -theories; and the notion of definitional equivalence itself: for structures A + dΦ ≡ B + dΘ; for theories, T1 + dΦ ≡ T2 + dΘ. Some results relating these notions were given, ending with two characterizations for definitional equivalence. In this second part, we explain the notion of a representation basis. Suppose a set Φ = {φi} of LP -formulas is given, and Θ = {θi} is a set of LQ-formulas. Then the original set Φ is called a representation basis for an LP -structure A with inverse Θ iff an inverse explicit definition ∀x(Pi(x) ↔ θi) is true in A + dΦ, for each Pi. Similarly, the set Φ is called a representation basis for a LP -theory T with inverse Θ iff each explicit definition ∀x(Pi(x) ↔ θi) is provable in T +dΦ. Some results about representation bases, the mappings they induce and their relationship with the notion of definitional equivalence are given. In particular, we show that T1 (in LP ) is definitionally equivalent to T2 (in LQ), with respect to Φ and Θ, if and only if Φ is a representation basis for T1 with inverse Θ and T2 ≡ DΦT1.