3

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!

Pi o r
  • 143
  • For a language to be uncountable, you need an uncountable alphabet. – Hagen von Eitzen Aug 19 '14 at 08:35
  • 1
    Yes, but that doesn't necessarily mean that there are uncountably many variables. There are also the constant symbols, the function symbols, the predicate symbols... – Pi o r Aug 19 '14 at 08:41

1 Answers1

7

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.

Kyle Gannon
  • 6,363