On learning down-sets in quasi-orders, and ideals in Boolean algebras

The paper studies learnability from positive data for families of down-sets in quasi-orders, and for families of ideals in Boolean algebras. We establish some connections between learnability and algebraic properties of the underlying structures. We prove that for a computably enumerable quasi-order (Q,≤Q), the family of all its down-sets is BC-learnable (i.e., learnable w.r.t. semantical convergence) if and only if the reverse ordering (Q,≥Q) is a well-quasi-order. In addition, if the quasi-order (Q,≤Q) is computable, then BC-learnability for the family of all down-sets is equivalent to Ex-learnability (learnability w.r.t. syntactic convergence). We prove that for a computable upper semilattice U, the family of all its ideals is BC-learnable if and only if this family is Ex-learnable, if and only if each ideal of U is principal. In general, learnability depends on the choice of an isomorphic copy of U. We show that for every infinite, computable atomic Boolean algebra B, there exist computable algebras A and C isomorphic to B such that the family of all computably enumerable ideals in A is BC-learnable, while the family of all computably enumerable ideals in C is not BC-learnable.