Classifying the Arithmetical Complexity of Teaching Models

Abstract

This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching, such as the problem of deciding, given an effective coding \(\{{\mathcal L}_0,{\mathcal L}_1,{\mathcal L}_2,\ldots \}\) of all uniformly r.e. families, any e such that \({\mathcal L}_e = \{L^e_0,L^e_1,\ldots ,\}\), any i and d, whether or not the teaching dimension of \(L^e_i\) with respect to \({\mathcal L}_e\) is upper bounded by d.