# Logic: cardinality of the set of formulas

How can you proof that $||L||=|L|$ if $L$ is infinite (where $||L||$ stands for the cardinality of the set of all $L$-formulas and $|L|$ the number of all constants, function and relation symbols)?

The case where $L$ is finite is clear for me, because in that case you can just count all the formulas by an induction argument, so $||L||=|\mathbb{N}|$.

-
Hint: Formulae are finite strings. (Not posted as an answer because it's probably too terse for that.) – Lord_Farin Aug 24 '13 at 11:09

If $X$ is an infinite set and $X^*$ is the set of finite lists of elements of $X$, then $\mbox{card}(X) = \mbox{card}(X^*)$. Taking $X$ to be the set of all constant, function, relation and logical symbols, the set of all formulas is a subset of $X^*$ and hence $\|L\| \le \mbox{card}(X) = |L|$ (where the equality holds because $L$ is infinite and there are only finitely many logical symbols). The converse inequality $|L| \le \|L\|$ holds (without the assumption that $L$ is infinite) because given a constant, function or relation symbol you can construct a formula containing that symbol (and no other).