The Occurrence Number (& Dependance number)

The Occurrence Number

$\mathcal{L}[\tau ]=\bigcup _{\begin{array}{c}{\tau }_0\subset \tau \\ |{\tau }_0|\le \kappa \end{array}}\mathcal{L}[{\tau }_0]$ Then $\kappa$ is the occurrence number of the logic $\mathcal{L}$

I.e., The class of $\mathcal{L}-$formulas, $\mathcal{L}[\tau ]$ is the union of the formula-classes in some vocabulary ${\tau }_0$ such that $|{\tau }_0|<\kappa$. $⟹\forall \phi \in \mathcal{L}[\tau ],\exists \psi \in \mathcal{L}[{\tau }_0]$ such that $\phi ⟺\psi$ (We can reduce all formulas of $\mathcal{L}[\tau ]$ to that of a smaller sub-vocabulary ${\tau }_0,\mathcal{L}[{\tau }_0]$), given that the $occ(\mathcal{L}<|\tau |),$ via logical equivalence).

E.g., The number of formulas a (set-sized) logic can form is given by: max{$|\tau |,{\aleph }_0$} for FOL, SOL, HOL,…,etc.

For infinitary logic it is given by: max{|$\tau$|, ${\kappa }_L$}${}^{<{\kappa }_L}$ Where ${\kappa }_L$ is the supremum (smaller upper bound) of the length of formulae allowed $\to$ For FOL, the number of possible formulae is ${\aleph }_0$ for $|\tau |\le {\aleph }_0$ (i.e., a countable language), or $|\tau |$ if $|\tau |>{\aleph }_0$ (i.e., an uncountable language $\to$ For an infinitary logic ${\mathcal{L}}_{\kappa ,\kappa }$ we have ${\kappa }^{{\kappa }_L}$ for $\kappa >|\tau |$ and $|\tau {|}^{\kappa }$ = $|\tau |$ for $|\tau |>{\kappa }_L$ $\to$ It is known that the occurrence number of FOL (as well as SOL, HOL) is ${\aleph }_0$ $⟹$ That finite vocabularies are enough to formulate any statement in FOL $⟹$ In the case of an uncountable vocabulary $\tau$ then there are uncountably many ($|\tau |-$ many) logically equivalent formulae for each sentence $\phi \in \mathcal{L}[{\tau }_0]$ for $|{\tau }_0|\le {\aleph }_0$ Thus, the effective number of distinct formulas are given by: max{$|\tau |,occ(\mathcal{L})$} = max{$|\tau |,{\aleph }_0$} $⟹|\tau |-$many sentences for $|\tau |\le {\aleph }_0$ for finitary logic

Alternative Definition of Occurrence Number: An alternative definition to the occurrence number is the supremum of symbols allowed in a formula of the logic $\mathcal{L}$ E.g., Consider the infinitary logic ${\mathcal{L}}_{\kappa ,\kappa }$ for $\kappa$ is a regular cardinal, then $occ({\mathcal{L}}_{\kappa ,\kappa })=\kappa$ is the supremum of the length of formulae allowed since for $|\tau |<\kappa$, you can only have $\kappa$-many sentences… $\to$ if $\kappa$ is singular, then $occ({\mathcal{L}}_{\kappa ,\kappa })={\kappa }^{+}$ (the successor of $\kappa$, assuming the axiom of choice) $\to$ Since SOL,…,HOL only allows finitely-long formulae (note: second-order logic is referring to ${\mathcal{L}}_{\kappa ,\kappa }^2$), the occurrence number is the same as FOL, ${\aleph }_0$.

Effective no. of Sentences

$\to$ Note: It can be seen that the infinitary definition of the number of formulae can be applied to FOL, max{$|\tau |,{\kappa }_L$}${}^{<{\kappa }_L}=$ max{$|\tau |,{\aleph }_0$}${}^{<{\aleph }_0}=$ max{$|\tau |,{\aleph }_0$}${}^n$ for $n\in \mathbb{N}$ $\to |\tau |>{\aleph }_0$ $⟹|\tau {|}^n=|\tau |$ since $|\tau |$ is infinite $\to$ The effective number of distinct formulas (up to logical equivalence) is given by (general case): max{$|\tau |,occ(\mathcal{L})$}${}^{<occ(\mathcal{L})}$ You could also define the number of formulas up to validity (perhaps using the dependance number instead?)

For $occ(\mathcal{L})>|\tau |$ we get the following: i) $occ(\mathcal{L})\le 2^{<occ(\mathcal{L})}$, then $occ(\mathcal{L}{)}^{<occ(\mathcal{L})}=2^{<occ(\mathcal{L})}$ (this result in particular depends on the global continuum hypothesis ii) $occ(\mathcal{L})>2^{<occ(\mathcal{L})}$ $occ(\mathcal{L})$

$\therefore 2^{<occ(\mathcal{L})}$ or $occ(\mathcal{L})$ distinctly many sentences

For $|\tau |>occ(\mathcal{L})$ we get the following: i) $|\tau |\le 2^{<occ(\mathcal{L})}$, then $|\tau {|}^{<occ(\mathcal{L})}=2^{<occ(\mathcal{L})}$ For $|\tau |\le 2^{<occ(\mathcal{L})}$ ii) $|\tau |>2^{occ(\mathcal{L})}$, then $|\tau |$ $\therefore 2^{<occ(\mathcal{L})}$ or $|\tau |-$many distinct sentences

• Since FOL, SOL,…, HOL are finitary logics (allow finitely-long formulae), then these logic have an occurrence number of ${\aleph }_0$ (sometime notated as $\omega$ instead) $⟹$ That finite vocabularies are ‘enough’ to formulate any statement in these logics (up to logical equivalence) $⟹$ In the case of an uncountable vocabulary $\tau$, then there are uncountably-many logically equivalent formulae to the formulae in $\mathcal{L}[{\tau }_0]$ (such that ${\tau }_0\subseteq \tau$ and $|\tau |<{\aleph }_0$) $\to$ $|\mathcal{L}[\tau ]|>|\mathcal{L}[{\tau }_0]|$ for $|{\tau }_0|\le occ(\mathcal{L})$ i.e., For some $\phi \in \mathcal{L}[\tau ],$ there is some $\psi$ such that $\phi ⟺\psi$

Note:

• A logic $\mathcal{L}$ being set-sized (that is for a vocabulary $\tau ,|\mathcal{L}[\tau ]|\le \lambda$ for $\lambda$ is a cardinal) $⟹\mathcal{L}$ has an occurrence number, $occ(\mathcal{L})$. Not necessarily vice versa, consider the following logic: $\mathcal{L}(Q_{\alpha })$, i.e., we add a cardinality quantifier for every cardinal ${\aleph }_{\alpha }$, this logic has an occurrence number but forms a proper class of formulae (given a vocabulary $\tau$).
• If a vocabulary $\tau ,$ is proper-class sized (i.e., $|\tau |=\infty$, or more formally $|\tau |>\kappa$ for an arbitrarily large cardinal $\kappa$), then the class of $\mathcal{L}$-formulas, $\mathcal{L}[\tau ]$, would also from a proper-class (i.e., $|\mathcal{L}[\tau ]|=\infty$), no matter the logic (even if $\mathcal{L}=$ FOL), although as given above, the number of ‘effective’ formulae would be set-sized if $occ\mathcal{L}<\infty$.

Alternatively, the number of effective sentences may be given by the following construction: Let ${\tau }_{\phi }=$ {$\phi |\phi ⟺\psi$} For $\phi ,\psi \in \mathcal{L}[\sigma ]$ $\mathcal{K}=\bigcup _{\phi \in \mathcal{L}[\sigma ]}{\tau }_{\phi }$ Then $|\mathcal{K}|$ is the effective number of sentences (number of logically distinct sentences) of the logic $\mathcal{L}$ The number of “semantically-distinct” sentences may also be defined Let ${\tau }_{\phi }=$ {$\phi |\mathfrak{A}$ is a $\sigma$-structure and $\mathfrak{A}\models \phi ⟺\mathfrak{A}\models \psi$} For $\phi ,\psi \in \mathcal{L}[\sigma ]$ $\mathcal{K}=\bigcup _{\phi \subseteq \mathcal{L}[\sigma ]}{\tau }_{\phi }$ Then $|\mathcal{K}|$ is the number of semantically distinct sentences of the logic $\mathcal{L}$

Result: For $\mathcal{L}$ is ‘small’ and assume $occ(\mathcal{L})<\infty$, then for all $\kappa$, $h_{\kappa }(\mathcal{L})<\infty$ proof: Set $\mu =\kappa ,$ and let $\tau$ be a ‘universal’ vocabulary of power $\mu$ (i.e., $\tau$ contains $\mu$-many relation and function symbols of each arity). In order to investigate $h_{\kappa }(\mathcal{L})$, we can confine ourselves to $\tau$-sentences of $\mathcal{L}$ Since $\mathcal{L}[\tau ]$ is a set, we have $h_{\kappa }(\mathcal{L})=$ sup{$|\mathfrak{A}|\mathfrak{A}\models \phi ,\phi \subseteq \mathcal{L}[\tau ],|\phi |\le \kappa$ and $\phi$ does not have arbitrarily large models} < $\infty$ i.e., $occ(\mathcal{L})<\infty ⟹h_{\kappa }(\mathcal{L})<\infty$

Note: if $\mathcal{L}[\tau ]$ is set-like and $occ(\mathcal{L}<\infty )$ then we also have: $occ({\mathcal{L}}_{\omega ,\omega })=\omega ⟹l(\mathcal{L})=\omega$

In general, for ‘tame’ languages ($⟹occ(\mathcal{L})<|\tau |$, for a sufficiently large $\tau$), the no. of sentences is at most $2^{|\tau |}$ (ignoring logical distinction and counting logically equivalent sentences as well).

The Dependance Number:

Dependance Number: - The intuition behind the dependance number of a formula $\phi \in \mathcal{L}[\tau ]$ ‘depends’ only on a subset of the vocabulary $\sigma \subset \tau$ - Proposition: Let $\mathcal{L}$ be a logic and $\phi \in \mathcal{L}[\tau ]$ i) $\phi$ depends only on the symbols in $\sigma \subset \tau$ if for all $\tau$-structures $\mathfrak{A},\mathfrak{B}$ such that $\mathfrak{A}\upharpoonright \sigma \cong \mathfrak{B}\upharpoonright \sigma$ we have $\mathfrak{A}\models \phi ⟺\mathfrak{B}\models \phi$. (i.e., The validity of $\phi$ depends only on $\sigma$ and in terms of semantics, the full vocabulary $\tau$ is redundant, that is, the truth value of $\phi$ does not change going from $\sigma$ to $\tau$ ii) A logic is weakly regular if $\mathcal{L}$ satisfies the basic closure properties and relativization property (see Logics, Structures & Models) The cardinal $\kappa >|\sigma |$ for which this occurs is the dependance number and is denoted as $o(\mathcal{L})$

The occurrence number and dependance number are two sides of the same coin. The occurrence number deals with syntax (logical equivalence: $\phi ⟺\psi$), while the dependence number deals with the semantics (semantic equivalence: $\mathfrak{A}\models \phi ⟺\mathfrak{B}\models \phi$).

In one-sorted logic, the occurrence number and dependance number are the same as the substitution property removes ‘redundant’ relation and function symbols (reducing it)

The occurrence number and dependance number differ in the many-sorted case as the substitution property does not enable us to remove redundant sort symbols. E.g., Consider the vocabulary with two sorts $S_1$ and $S_2,$ and allows quantification over each sort separately (i.e., we have relation $R(x,y)$ where $x\in S_1$ and $y\in S_2$). Consider the following sentence $\phi =\forall x\in S_1,\exists y\in S_2,R(x,y)$ This sentence occurs syntactically in the full two-sorted vocabulary $\tau =${$S_1,S_2,R$} $\to$ Both $S_1$ and $S_2$ are required to state this sentence, thus $\phi$ cannot be further reduced to single sorted logic. Semantically, only the sort $S_1$ and relation $R(x,y)$ (only $\sigma =${$S_1,R$} is required). Thus, $\phi$ differs in the semantic case from the syntactic case, as it has been reduced to a single-sorted case, and so the dependance number differs from the occurrence number. From this we can derive that $o(\mathcal{L})\le occ(\mathcal{L})$ always (the occurrence number of a logic is at least that of the dependance number).

• If $o(\mathcal{L})=\omega ,$ then $\mathcal{L}$ has the finite dependance property

Proposition: Let $\mathcal{L}$ be a logic with $o(\mathcal{L})=\mu$ and $l_{\kappa }(\mathcal{L})=\kappa$ and $\tau$ be a vocabulary such that $\mu \le |\tau |\le \kappa$. Then there are up to logical equivalence, $2^{2^{\kappa }}$- many $\tau$-sentences.

Proposition: For every weakly regular logic $\mathcal{L}$ there is a logic ${\mathcal{L}}_1$ such that: i) $\mathcal{L}\equiv {\mathcal{L}}_1$; and ii) if $\phi \in {\mathcal{L}}_1[\tau ],\sigma \subset \tau$ and $\phi$ depends only on $\sigma$, then there is a $\psi \in {\mathcal{L}}_1[\sigma ]$ such that for every $\sigma$-structure there $\mathfrak{A},\mathfrak{A}\models \psi$ iff every expansion of $\mathfrak{A}$ to a $\tau$-structure ${\mathfrak{A}}_1,{\mathfrak{A}}_1\models \phi$ Proof: Add new atomic sentences and consider them of being of the new required vocabulary.

Given a regular logic $\mathcal{L}$ we define a cardinal $OC(\mathcal{L})=\kappa$ to be the smallest number such that for every formula $\phi \in \mathcal{L}[\tau ]$ there is $\sigma \subset \tau$ with $|\sigma |<OC(\mathcal{L})$ and $\phi \in \mathcal{L}[\sigma ]$ $\to$ Proposition: Let $\mathcal{L}$ be a regular logic with dependance number $o(\mathcal{L})$. Then there is a regular logic ${\mathcal{L}}_1$ with $OCC(\mathcal{L})=o(\mathcal{L})$ which is equivalent to $\mathcal{L}$

References

The Hanf Number The Löwenheim Number Infinitary Logics Logics, Structures & Models Model Theoretic Logics.pdf