how many variables in first-order language?

436 Views Asked by At

The book I use deals mostly with countable first-order languages. In these there are countably many variables. Do you demand uncountably many variables in uncountable languages or do countably many variables suffice, since formulas are always finite?

Thx!

1

There are 1 best solutions below

0
On BEST ANSWER

Every sentence is of finite length. Notice also that variable confusion only occurs when we have nested quantification. More concretely, we have need two variable if we want to write $(\forall x) (\exists y) (P(x,y))$ but only one if we want to write $(\forall x)(P(x)) \vee (\exists x)(Q(x))$.

Hence, every sentence needs only finitely many variables and any collection of sentences only needs as many variables as the sentence which needs the most variables (since we can just reuse these variables in the other sentences without confusion).

Since we can have arbitrarily large (but finitely long) sentences, we need countably many variables. But from the second paragraph, it follows that any collection (countable or uncountable) needs at most countably many variables.