Let $\mathcal{L}$ be a first order language consisting of:
- $P_i$ predicate symbols, $f_j$ function symbols & $c_k$ constant symbols indexed respectively by th sets $I,J$ & $K$. Furthermore the arity function that assigns each predicate and function symbol to a positive integer.
- A countable infinite set of variables, $X$.
- The logical connectives: $\neg,\vee$ and universal quantifier $\forall$.
If $L$ is the set of formulas of $\mathcal{L}$, show that $|L|=\max\{|X|,|I|,|J|,|K|\}$.
I think this is meant to be a straightforward exercise but the only argument I can come up with is very tedious and am not too confident about it, so I think there must be a better argument or can anyone improve the argument I have presented below to make it less laborious. Also please let me know of any errors and how to correct them. Should I maybe use a Gödel style numbering argument and construct an explicit map(but won't this work for only countable languages)? Also I have not bothered about parentheses and commas in the language, is this fine or do I need to count them as well and if so how? Thanks in advance.
Put $T$ to be the set of all terms of $\mathcal{L}$ and $T_0$ to be all the variable and constant symbols, so $|T_0|=\max\{|X|,|K|\}$. Then for each $f_j$ and $n\geq 1$, define $Y_{f_j,n-1}:=\{f_j(x_1,...,x_{ar(f_j)}|x_1,...,x_{ar(f_j)}\in T_{n-1}\}$ and $T_n:=T_{n-1}\cup(\bigcup\limits_{j\in J}Y_{f_j,n-1})$.
Now the surjection, $(T_{n-1})^{ar(f_j)}\rightarrow Y_{f_j,n-1}$ defined by $(x_1,...,x_{ar(f_j)})\mapsto f_j(x_1,...,x_{ar(f_j)})$ implies that $|Y_{f_j,n-1}|\leq|T_{n-1}|$, and by induction we get, $|T_{n}|=|T_{n-1}|+|\bigcup\limits_{j\in J}Y_{f_j,n-1}|=|T_{n-1}|+|J|.|T_{n-1}|=\max\{|X|,|J|,|K|\}$. Thus we have $|T|=|\bigcup\limits_{n<\omega}T_n|\leq\aleph_o.\max\{|X|,|J|,|K|\}=\max\{|X|,|J|,|K|\}$ and as the reverse inequality is obvious we have $|T|=\max\{|X|,|J|,|K|\}$.
Then for each $P_i$ define $Z_{P_i}:=\{P(t_1,...,t_{ar(P_i)})|t_1,...,t_{ar(P_i)}\in T\}$.
So as $Z_{P_i}\subset T^{ar(P_i)}$, we have $|Z_{P_i}|\leq |T|$, therefore the cardinality of the set of atomic formulae, $|L_0|=|\bigcup\limits_{i\in I}Z_{P_i}|\leq |I|.\max\{|X|,|K|,|J|\}=\max\{|X|,|K|,|J|,|I|\}$.
Now for $n\geq1$ define recursively:
- $L_{n,\neg}:=\{\neg\varphi|\varphi\in L_{n-1}\}$,
- $L_{n,\vee}:=\{\varphi\vee\psi|\varphi,\psi\in L_{n-1}\}$,
- $L_{n,\forall}:=\{\forall x\varphi|\varphi\in L_{n-1}\}$ and
- $L_n:=L_{n,\neg}\cup L_{n,\vee}\cup L_{n,\forall}$.
Then as the surjections, $L_{n-1}\rightarrow L_{n,\neg}$ (resp. $L_{n,\forall}$) defined by $\varphi\mapsto \neg\varphi$ (resp. $\forall x\varphi$) and $(L_{n-1})^2\rightarrow L_{n,\vee}$ defined by $(\varphi,\psi)\mapsto\varphi\vee\psi$; implies that $|L_{n-1}|=|L_{n,\neg}|=|L_{n,\vee}|=|L_{n,\forall}|$. By induction we can then conclude that
$|L|=|\bigcup\limits_{n<\omega}L_n|\leq\aleph_0.|L_n|=\aleph_0.\max\{|X|,|I|,|J|,|K|\}=\max\{|X|,|I|,|J|,|K|\}$ and as the reverse inequality is is quite apparent, so the exercise is done.