Suppose that I have a model M that overfits a large dataset S such that the test error is 30%. Does that mean that there will always exist a model that is smaller and less complex than M that will have a test error less than 30% on S (and does not overfit S).
over-fitting does seem to imply an upper bound on model complexity.
As complexity of the model increases, its generality tends to decrease. This is not an indisputable fact, but an identifiable trend, provided that the model is not inundated with redundancy.
For polynomial expressions, a Taylor series of 100 terms can always perfectly represent the position of 100 points in a time series, although no predictive general information can be ascertained from the 100 coefficients of the Taylor series. This is also true for spectral analysis, Lyapunov exponent estimation, spline fitting, or artificial network convergence.
What is generally accepted as the definition of over-fitting does not come from the AI field. It originates from the mathematics of surface approximation using closed forms. The closed forms may be derived from a single differential equation or systems of them, but not usually, since closed forms do not exist for many such systems.
The information science principles behind feature extraction are closely aligned to the correlation between generality and predictive usefulness.
Still, we can't conclude, "There will always exist a model that is smaller and less complex than $M$ that will have a test error less than 30% on $S$." Counter examples can probably be constructed with a little thought and effort.