  We consider the problem of answering queries about formulas of first-order
logic based on background knowledge partially represented explicitly as other
formulas, and partially represented as examples independently drawn from a
fixed probability distribution. PAC semantics, introduced by Valiant, is one
rigorous, general proposal for learning to reason in formal languages: although
weaker than classical entailment, it allows for a powerful model theoretic
framework for answering queries while requiring minimal assumptions about the
form of the distribution in question. To date, however, the most significant
limitation of that approach, and more generally most machine learning
approaches with robustness guarantees, is that the logical language is
ultimately essentially propositional, with finitely many atoms. Indeed, the
theoretical findings on the learning of relational theories in such generality
have been resoundingly negative. This is despite the fact that first-order
logic is widely argued to be most appropriate for representing human knowledge.
In this work, we present a new theoretical approach to robustly learning to
reason in first-order logic, and consider universally quantified clauses over a
countably infinite domain. Our results exploit symmetries exhibited by
constants in the language, and generalize the notion of implicit learnability
to show how queries can be computed against (implicitly) learned first-order
background knowledge.
