On Learning Existentially Definable Subsets in a Computable Structure

The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure S. While provided larger and larger pieces of a subset V of the domain of S, a learner tries to guess the Gödel number of an ∃-formula which defines V in S. In this setting, we consider several classical learning criteria. For a computable structure S, we work with the class Σ₁⁰(S) containing all ∃-definable (without parameters) subsets of S. We focus on some familiar classes of structures S, including equivalence structures and Boolean algebras. We establish the following results. If the ∀∃-theory of a structure S is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families F⊆Σ₁⁰(S) coincide. If S is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families F coincide. We build a computable equivalence structure E such that Σ₁⁰(E) is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy C such that Σ₁⁰(C) is confidently learnable. We construct a computable Heyting algebra H such that for any computable copy C of H, the family Σ₁⁰(C) is not behaviorally correctly learnable.