Some other things we can't not believe in ...

Of course there are others that are peculiar, and almost certainly related.

Could we say, for instance, that someone understood basic arithmetic if they also believed that it didn't work?  This is a tricky one.

They would need to give us an explanation with made arithmetic sense.

If they said, for instance, "I can see how adding up works for the examples you have shown me, but I don't think you can extrapolate from these cases to all possible cases"; we would know they were making a mistake of some kind.

On the other hand, Gödel's proofs are, exactly, proofs that arithmetic does not work in the way that many Arithmeticians previously thought.  Certain basic expectations cannot be extended to the set of all possible numbers.

No-one, however, would draw the conclusion from Gödel's argument that there must be something fundamentally wrong with arithmetical computation - or, for instance, with the fundamental theorem (unique factoring into primes).

We're just changing out a bit of structure here, not rebuilding the boat.  Even if the change makes some aspects of the navigation appear more mysterious than they did before...