Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}|$.

share|improve this question
1  
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

1 Answer 1

up vote 4 down vote accepted

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.