We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class. In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning. In the second part of the paper we consider learning from texts that for some k contain all positive II_k-formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results can be shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from II_1-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from II_1-texts and can be limit-refuting learned from II_2-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from II_1-texts. For the full language of arithmetic, which contains in addition plus and times, for any k there is an axiomatizable class that can be limit-refuting learned from II_(k+1)-texts but not from II_k-texts. A similar result with k + 3 in place of k + 1 holds with respect to the language of Presburger's arithmetic.
展开▼
