Learning Equivalence Relations on Polish Spaces

We investigate natural variations of behaviourally correct learning and explanatory learning – two learning paradigms studied in algorithmic learning theory – that allow us to ``learn’’ equivalence relations on Polish spaces. We give a characterization of the learnable equivalence relations in terms of their Borel complexity and show that the behaviorally correct and explanatory learnable equivalence relations coincide both in uniform and non-uniform versions of learnability and provide a characterization of the learnable equivalence relations in terms of their Borel complexity. We also show that the set of uniformly learnable equivalence relations is ${\mathrm{\Pi }}_1^1$-complete in the codes and study the learnability of several equivalence relations arising naturally in logic as a case study.