It seems that Deniz is raising a slightly uncomfortable question of whether some circularity is built into mathematical foundations. A similar common-sense circularity is what might be called the "paradox of the dictionary": since all words are defined in terms of other words, either dictionaries are hopelessly circular, or some words need to be left undefined in order to break out of the impasse.

As it happens, I am preparing an article for eventual exportation to the nLab which at the outset deals with precisely this question. In the present draft, I have this passage:

Logical foundations avoids this paradox ultimately by being concrete. We may put it this way: logic at the primary level consists of instructions for dealing with formal linguistic items, but the concrete actions for executing those instructions (electrons moving through logic gates, a person unconsciously making an inference in response to a situation) are not themselves linguistic items, not of the language. They are nevertheless as precise as one could wish.
$$ $$
We emphasize this point because in our descriptions below, we obviously must use language to describe logic, and some of this language will look just like the formal mathematics that logic is supposed to be prior to. Nevertheless, the apparent circularity should be considered spurious: it is assumed that the programmer who reads an instruction such as "concatenate a list of lists into a master list" does not *need* to have mathematical language to formalize this, but will be able to translate this directly into actions performed in the real world. However, at the same time, the mathematically literate reader may *like* having a mathematical meta-layer in which to understand the instructions. The presence of this meta-level should not be a source of confusion, leading one to think we are pulling a circular "fast one".

In other words, to break out of the circularity, it is enough to observe that computers can be programmed to recognize certain strings as well-formed terms or formulas (of a given axiomatic theory), and how to recognize inferences as valid. It's not as if there needs to be some background theory, or the prior existence of a completed or actual infinity of all expressions which might come up, sitting inside the computer. The computer is programmed to handle finite parts of the theory correctly, and the same applies to human users of a theory (although we say "taught", not "programmed").