One of the basic theorems in universal algebra is Birkhoff's variety theorem: the smallest equationally axiomatizable class containing a class $\mathbf{K}$ of algebras coincides with the class obtained by taking homomorphic images of subalgebras of direct products of elements of $\mathbf{K}$. G. Gratzer asked whether the variety theorem is equivalent to the Axiom of Choice. In 1980, two of the present authors proved that Birkhoff's theorem can already be derived in $ZF$. Surprisingly, the Axiom of Foundation plays a crucial role here: we show that Birkhoff's theorem cannot be derived in $ZF + AC \{\text{Foundation}\}$. even if we add Foundation for Finite Sets. We also prove that the variety theorem is equivalent to a purely set-theoretical statement, the Collection Principle. This principle is independent of $ZF \{\operatorname{Foundation}$. The second part of the paper deals with further connections between axioms of $ZF$-set theory and theorems of universal algebra.