What can be confusing is that the statement "for every x in {}, it doesn’t hold that <anything>" is always true as well.

I mean, yes. But "it doesn't hold that <anything>" is equivalent to "it holds that <not anything>" and since not anything is also anything... Ah, I see.