There are multiple connections between model-theoretic notions of complexity and machine learning. NIP formulas correspond to PAC-learning by way of VC-dimension, and stable formulas correspond to online learning by way of Littlestone dimension, also known as Shelah's 2-rank. We explore a similar connection between formulas without the finite cover property and equivalence query learning. In equivalence query learning, a learner attempts to identify a certain set from a set system by making hypotheses and receiving counterexamples. We use the notion of (strong) consistency dimension, an analogue of the the negation of the finite cover property for set systems. We show that finite (strong) consistency dimension and finite LIttlestone dimension characterize equivalence query learning, drawing on ideas from model theory. We also discuss the role of Littlestone dimension and strong consistency dimension in algorithms.