All infinite models are representable over the naturals

Stream: Equational

[Jose Brox]

I believe that someone asked somewhere if we could restrict our search of infinite models to the natural numbers, I have time to answer now (apologies if this is not the case!):

By the downward Löwenheim–Skolem Theorem, any first-order theory (equational theory in our case) that has an infinite model, has an infinite model of countable cardinality. Hence we can restrict to magmas M of countably infinite cardinality.

Now, get any bijection f between (M,·) and the naturals N, and use
n*m := f(f^-1(n)·f^-1(m)) as the magma product over N. Then f is an isomorphism of magmas. Hence it suffices to look for magmas over the natural numbers.

[Mario Carneiro]

This is in fact proved as part of the completeness theorem - the "universal counterexample" FreeMagmaWithLaws α Γ is countable if α is, and there are also reductions there showing that it suffices to take α := ℕ