Pure inductive logic

Pure Inductive Logic

Pure inductive logic (PIL) is the area of mathematics concerned with the theoretical and mathematical foundations of inductive logic [1]. It combines classical predicate logic and probability theory. Probability values are assigned to sentences of a first order relational language to represent degrees of belief that should be held by a rational agent. Conditional probability values represent degrees of belief on the basis of some evidence.

PIL studies prior probability functions on the set of sentences and evaluaes rationality of such prior probability functions via proposing principles that such functions should satisfy. Each of the principles guarantees that, in some respect, the function assigns probability values to sentences rationally and that also the derived assignments of conditional probability values given some evidence are rational.

History

Inductive logic started to take a clearer shape in the early 20th century in the work of William Ernest Johnson and John Maynard Keynes , and was further developed by Rudolf Carnap. Carnap introduced the distinction between pure and applied inductive logic,, and the modern Pure Inductive Logic evolves within the pure, uninterpreted approach envisaged by Carnap.

Framework

Pure Inductive Logic uses first order predicate logic without equality, with the usual connectives $\wedge ,\vee ,\neg ,\to$ (and, or, not and implies respectively), quantifiers $\exists ,\forall$, finitely many predicate (relation) symbols and countably many constant symbols $a_{1},a_{2},a_{3},\ldots$

There are no function symbols. The predicate symbols can be unary, binary or of higher arities. The finite set of predicate symbols may vary whist the rest of the language is fixed. It is a convention to refer to the language as $L$ and write

$~~~~~~~~~\{L={R_{1},R_{2},\ldots R_{q}\}}$

where the $R_{i}$ list the predicate symbols. The set of all sentences is denoted $SL$. If a sentence is written with constants appearing in it listed then it is assumed that the list includes all those that appear. ${\cal {T}}L$ is the set of structures for $L$ with universe $\{a_{1},a_{2},\ldots \}$ and with each constant symbol $a_{i}$ interpreted as itself.

A probability function for sentences of $L$ is a function $w$ with domain $SL$ and values in the real interval $[0,1]$ satisfying Kolmogorov's axioms and Gaifman's condition on quantified sentences which postulates that the constant symbols name all individuals. That is:

- any logically valid sentence $\theta$ has probability 1: $w(\theta )=1$

- if sentences $\theta$ and $\phi$ are mutually exclusive then $w(\theta \vee \phi )=w(\theta )+w(\phi )$

- for a formula $\psi (x)$ with one free variable the probability of $\exists x\,\psi (x)$ is the limit of probabilities of $\psi (a_{1})\vee \psi (a_{2})\vee \ldots \vee \psi (a_{n})$ as $n$ tends to $\infty$.

For $w$ and a sentence $\phi$ with $w(\phi )>0$, the conditional probability function is defined by

$~~~~~~~~~~~~~~w(\theta \mid \phi )={\frac {w(\theta \wedge \phi )}{w(\phi )}}$

Unlike belief functions in many valued logics [2], it is not the case that the probability value of a compound sentence is determined by the probability values of its components. Probability respects the classical semantics: logically equivalent sentences must be given the same probability value. Hence logically equivalent sentences are often identified.

A state description for a finite set of constants is a conjunction of predicates (or their negations) instantiated exclusively by these constants, and such that for any such eligible atomic sentence either it or its negation appear in the conjunction.

Any probability function is uniquely determined by its values on state descriptions. To define a probability functions, it suffices to specify nonnegative values of all state descriptions for $a_{1},\ldots ,a_{n}$ (for all $n$) so that the values of all state descriptions for $a_{1},\ldots ,a_{n},a_{n+1}$ extending a given state description for $a_{1},\ldots ,a_{n}$ sum to the value of the state description they all extend, with the convention that the (only) state description for no constants is a tautology and that has value 1.

If $\Theta$ is a state description for a set of constants including $a_{i},a_{j}$ then it is said that $a_{i},a_{j}$ are indiscernible in $\Theta$, $a_{i}\sim _{\Theta }a_{j}$, just when upon adding equality to the language (and axioms of equality to the logic), the sentence $\Theta \wedge a_{i}=a_{j}$ would be consistent.

In unary PIL, all the predicates $R_{1},\ldots ,R_{q}$ are unary. Formulae of the form

$~~~~~~~~~~~~\alpha (x)=\pm R_{1}(x)\wedge \pm R_{2}(x)\wedge \ldots \wedge \pm R_{q}(x)$

where $\pm R$ stands for one of $R$, $\neg R$, are called atoms. It is assumed that they are listed in some fixed order as $\alpha _{1},\alpha _{2},\ldots ,\alpha _{2^{q}}$. A state description specifies an atom for each constant involved in it, and it can be written as a conjunction of these atoms instantiated by the corresponding constants. Two constants are indiscernible in the state description if it specifies the same atom for them.

Central question

Assume a rational agent inhabits a structure for the language $L$ but knows nothing about which one it is. What probability function $w$ should he adopt when $w(\theta )$ is to represent his degree of belief that a sentence $\theta$ is true in this ambient structure?

Rational Principles

The following principles have been proposed as desirable properties of a rational prior probability function $w$ for $L$.

The Constant Exchangeability Principle, Ex. The probability of a sentence $\theta (a_{1},a_{2},\ldots ,a_{m})$ does not change when the $a_{1},a_{2},\ldots ,a_{m}$ in it are replaced by any other $m$-tuple of (distinct) constants.

The Principle of Predicate Exchangeability, Px. If $R,R'$ are predicates of the same arity then for a sentence $\theta$,

$w(\theta )=w(\theta ')$

where $\theta '$ is the result of simultaneously replacing $R$ by $R'$ and $R'$ by $R$ throughout $\theta$.

The Strong Negation Principle, SN. For a predicate $R$ and sentence $\theta$,

$w(\theta )=w(\theta ')$

where $\theta '$ is the result of simultaneously replacing $R$ by $\neg R$ and $\neg R$ by $R$ throughout $\theta$.

The Principle of Regularity, Reg. If a quantifier-free sentence $\theta$ is satisfiable then $w(\theta )>0$.

The Principle of Super Regularity (Universal Certainty), SReg. If a senctence $\theta$ is satisfiable then $w(\theta )>0$.

The Constant Irrelevance Principle, IP. If sentences $\theta ,\phi$ have no constants in common then $w(\theta \wedge \phi )=w(\theta )\cdot w(\phi )$.

The Weak Irrelevance Principle, WIP. If sentences $\theta ,\phi$ have no constant nor predicates in common then $w(\theta \wedge \phi )=w(\theta )\cdot w(\phi )$.

Language Invariance Principle, Li. There is a family of probability functions $w^{J}$, one on each language $J$, all satisfying Px and Ex, and such that $w^{L}=w$ and if all predicates of $J$ belong also to $K$ then $w^{J}$ and $w^{K}$ agree on sentences of $J$.

The (Strong) Counterpart Principle, CP. If $\theta ,\theta '$ are sentences such that $\theta '$ is the result of replacing some constant/relation symbols in $\theta$ by new constant/relation symbols of the same arity not occurring in $\theta$ then

$w(\theta \mid \theta ')\geq w(\theta ).$

(SCP) If moreover $\theta ''$ is the result of replacing the same and possibly also other constant/relation symbols in $\theta$ by new constant/relation symbols of the same arity not occurring in $\theta$ then

$w(\theta \mid \theta ')\geq w(\theta \mid \theta '')\geq w(\theta ).$

The Invariance Principle, INV. If $F$ is an isomorphism of the Lindenbaum-Tarski algebra of $L$ supported by some permutation $\mu$ of ${\cal {T}}L$ in the sense that for sentences $\theta ,\phi$,

$F([\theta ])=[\phi ]~$ just when $~M\models \theta \Longleftrightarrow \mu (M)\models \phi$

then $w(\theta )=w(\phi )$.

The Permutation Invariance Principle, PIP. As INV except that $F$ is additionally required to map (equivalence classes of) state descriptions to the same.

The Spectrum Exchangeability Principle, Sx. The probability $w(\Theta )$ of a state description $\Theta$ depends only on the spectrum of $\Theta$, that is, on the multiset of sizes of equivalence classes with respect to the equivalence $\sim _{\Theta }$.

Li with Sx. As the Language Invariance Principle but all the probability functions in the family also satisfy Spectrum Exchangeability.

The Principle of Induction, PI. Let $\Theta$ be a state description and $a_{k}$ a constant not appearing in $\Theta$. Let $\Phi$, $\Psi$ be state descriptions extending $\Theta$ to include $a_{k}$. If $a_{k}$ is $\sim _{\Phi }$-equivalent to some and at least as many constants as it is $\sim _{\Psi }$-equivalent to then $w(\Phi \mid \Theta )\geq w(\Psi \mid \Theta )$.

Further Rational Principles for Unary PIL

The Principle of Instantial Relevance, PIR. For a sentence $\theta$, atom $\alpha$ and constants $a_{i},a_{j}$ not appearing in $\theta$,

$w(\alpha (a_{i})\mid \alpha (a_{j})\wedge \theta )\geq w(\alpha (a_{j})\mid \theta )$.

The Generalized Principle of Instantial Relevance, GPIR. For quantifier-free sentences $\psi (a_{i}),\phi (a_{j}),\theta$ with constants $a_{i},a_{j}$ not appearing in $\theta$, if $\psi (x)\models \phi (x)$ then

$w(\psi (a_{i})\mid \phi (a_{j})\wedge \theta )\geq w(\psi (a_{i})\mid \theta ).$

Johnson Sufficientness Principle, JSP. For atoms $\alpha ,\alpha _{h_{1}},\alpha _{h_{2}},\ldots ,\alpha _{h_{n}}$, the probability :$w(\alpha (a_{n+1})\mid \alpha _{h_{1}}(a_{1})\wedge \alpha _{h_{2}}(a_{2})\wedge \ldots \wedge \alpha _{h_{n}}(a_{n}))$ depends only on $n$ and on the number of times $\alpha$ appears amongst the $\alpha _{h_{1}},\alpha _{h_{2}},\ldots ,\alpha _{h_{n}}$.

The Principle of Atom Exchangeability, Ax. If $\tau$ is a permutation of $\{1,2,\ldots ,2^{q}\}$ and $\Theta$ is a state description expressed as a conjunction of instantiated atoms then $w(\Theta )=w(\Theta ')$ where $\Theta '$ obtains from $\Theta$ upon replacing each $\alpha _{i}$ by $\alpha _{\tau (i)}$.

Reichenbach's Axiom, RA. Let $\alpha _{h_{i}}$ for $i=1,2,3,...$ be an infinite sequence of atoms and $\alpha$ an atom. Then as $n$ tends to $\infty$, the difference between the conditional probability

$w(\alpha (a_{n+1})\mid \alpha _{h_{1}}(a_{1})\wedge \alpha _{h_{2}}(a_{2})\wedge \ldots \wedge \alpha _{h_{n}}(a_{n}))$

and the proportion of occurrences of $\alpha$ amongst the $\alpha _{h_{1}},\alpha _{h_{2}},\ldots ,\alpha _{h_{n}}$ tends to 0.

Unary Language Invariance Principle, ULi. As Li, but with languages restricted to the unary ones.

ULi with Ax. As ULi but all the probability functions in the family also satisfy Atom Exchangeability.

Recovery Whenever $\Psi (a_{1},a_{2},\ldots ,a_{n})$ is a state description then there is another state description $\Phi (a_{n+1},a_{n+2},\ldots ,a_{h})$ such that $w(\Phi \wedge \Psi )\neq 0$ and for any quantifier free sentence $\theta (a_{h+1},a_{h+2},\ldots ,a_{h+g})$,

$w(\theta (a_{h+1},a_{h+2},\ldots ,a_{h+g})\,|\,\Phi \wedge \Psi )=w(\theta (a_{h+1},a_{h+2},\ldots ,a_{h+g})).$

Relationships between Principles

LI implies Ex and Px (by definition).

LI implies CP and SCP.

Li with Sx implies PI.

INV implies PIP and Ex.

PIP+Ex implies Sx.

In the unary case, Ex implies PIR

In the unary case, Ax is equivalent to PIP.

In the unary case, Ax+Ex is equivalent to Sx.

Important Probability Functions

Functions $V_{M}$. For a given structure $M$ for $L$ and $\theta \in SL$,

$V_{M}(\theta )=\left\{{\begin{array}{ll}1&{\rm {if}}~M\models \theta ,\\0&{\rm {otherwise}}.\end{array}}\right.$

Functions $\omega ^{\Psi }$. For a given state description $\Psi (a_{1},a_{2},\ldots ,a_{M})$, $\omega ^{\Psi }$ is defined via specifying its values for state descriptions as follows. $\omega ^{\Psi }(\Theta (a_{1},a_{2},\ldots ,a_{n}))$ is the probability that when $a_{h_{1}},a_{h_{2}},\ldots ,a_{h_{n}}$ are randomly picked from $\{a_{1},\ldots ,a_{M}\}$, with replacement and according to the uniform distribution, then $\Psi (a_{1},\ldots ,a_{M})\models \Theta (a_{h_{1}},a_{h_{2}},\ldots ,a_{h_{n}}).$

Functions $^{\circ }\!(\omega ^{\Psi })$. As above but employing a non-standard universe (starting with possibly non-standard state descriptions $\Psi$ and infinitely large $M$) to obtain the standard $^{\circ }\!(\omega ^{\Psi })$.

$\bullet$ The $^{\circ }\!(\omega ^{\Psi })$ are the only probability functions that satisfy Ex and IP.

Functions $u^{\overline {p}}$. For a given infinite sequence ${\overline {p}}=\langle p_{0},p_{1},p_{2},p_{3},\ldots \rangle$ of non-negative reals such that

$p_{1}\geq p_{2}\geq p_{3}\geq \ldots ~$ and $~\sum _{i=0}^{\infty }p_{i}=1$,

$u^{\bar {p}}$ is defined via specifying its values for state descriptions as follows.

For a sequence ${\vec {c}}=\langle c_{1},c_{2},\ldots ,c_{n}\rangle$ of natural numbers (possibly 0) and a state description $\Theta (a_{1},a_{2},\ldots ,a_{n})$, $\Theta$ is consistent with ${\vec {c}}$ if whenever $c_{s}=c_{t}\neq 0$ then $a_{s}\sim _{\Theta }a_{t}$. $C({\vec {c}})$ is the number of state descriptions for $a_{1},a_{2},\ldots ,a_{n}$ consistent with ${\vec {c}}$. $u^{\overline {p}}(\Theta )$ is the sum over those ${\vec {c}}$ with which $\Theta$ is compatible, of

$C({\vec {c}})^{-1}\prod _{s=1}^{n}p_{c_{s}}.$

$\bullet$ The $u^{\overline {p}}$ are the only probability functions that satisfy Li with Sx and WIP. (The language invariant family witnessing Li with Sx consists of the functions $u^{{\overline {p}},J}$ with fixed ${\overline {p}}$, where $u^{{\overline {p}},J}$ is as $u^{\overline {p}}$ but defined with language $J$.)

Further, Unary Probability Functions

Functions $w$_{${\vec {c}}$}. For a vector ${\vec {c}}=\langle c_{1},c_{2},\ldots ,c_{2^{q}}\rangle$ of non-negative real numbers summing to one, $w$_{${\vec {c}}$} is defined via specifying its values for state descriptions as follows:

$w$_{${\vec {c}}$}$(\alpha _{h_{1}}(a_{1})\wedge \alpha _{h_{2}}(a_{2})\wedge \ldots \wedge \alpha _{h_{n}}(a_{n}))=\prod _{i=1}^{n}c_{h_{i}}.$

$\bullet$ The $w$_{${\vec {c}}$} are the only probability functions that satisfy Ex and IP (they are also expressible as $^{\circ }\!(w^{\Psi })$ ).

Carnap Continuum functions $c_{\lambda }$. For $\lambda >0$, the probability function $c_{\lambda }$ is uniquely determined by the values

$c_{\lambda }\left(\alpha _{j}(a_{n+1})\mid \bigwedge _{i=1}^{n}\alpha _{h_{i}}(a_{i})\right)={\frac {m_{j}+\lambda 2^{-q}}{n+\lambda }}$

where $m_{j}$ the is number of times $\alpha _{j}$ occurs amongst the $\alpha _{h_{i}}$. Furthermore, $c_{\infty }$ is the probability function that assigns $2^{-nq}$ to every state description for $n$ constants and $c_{0}$ is the probability function that assigns $2^{-q}$ to any state description in which all constants are indiscernible, 0 to any other state description.

$\bullet$ The $c_{\lambda }$ are the only probability functions that satisfy Ex and JSP.

Functions $w^{\delta }$. For $-(2^{q}-1)^{-1}\leq \delta \leq 1$, $w^{\delta }$ is the average of the $2^{q}$ functions $w$_{${\vec {c}}$} where ${\vec {c}}$ has all but one coordinate equal to each other with the odd coordinate differing from them by $\delta$, so

$w^{\delta }=2^{-q}\sum _{i=1}^{2^{q}}$$w$_{${\vec {e_{i}}}$}

where ${\vec {e_{i}}}=\langle \gamma ,\gamma ,\ldots ,\gamma ,\gamma +\delta ,\gamma ,\ldots ,\gamma \rangle ~$, ($\gamma +\delta$ in </math>i</math>th place) and $\gamma =2^{-q}(1-\delta )$.

For $0\leq \delta \leq 1$, the $w^{\delta }$ are equal to $u^{\bar {p}}$ for

${\bar {p}}=\langle 1-\delta ,\delta ,0,0,0,\ldots \rangle .$

$\bullet$ The $w^{\delta }$ are the only functions that satisfy GPIR, Ex, Ax and Reg.

$\bullet$ The $w^{\delta }$ with $0\leq \delta <1$ are the only functions that satisfy Recovery, Reg and Uli with Ax.

Representation Theorems

A representation theorem for a class of probability functions provides means of expressing every probability function in the class in terms of generic, relatively simple probability functions from the same class.

Represetation theorem for all probability functions. Every probability function $w$ for $L$ can be represented as

$w=\int _{{\cal {T}}L}V_{M}\,d\mu (M)$

where $\mu$ is a $\sigma$-additive measure on the $\sigma$-algebra of subsets of ${\cal {T}}L$ generated by the sets

$[\theta ]=\{\,M\in {\cal {T}}L\mid M\vDash \theta \,\}~~~~(\theta \in SL).$

Representation theorem for Ex (employing non-standard analysis and Loeb Integration Theory). Every probability function $w$ for $L$ satisfying Ex can be represented as

$w=\int _{A}\,^{\circ }\omega ^{\Psi }\,d\mu (\Psi )$

where $A$ is an internal set of state descriptions and $\mu$ is a $\sigma$-additive measure on a $\sigma$-algebra of subsets of $A$ .

Representation theorem for Sx. Every probability function $w$ for $L$ satisfying Sx can be represented as

$w=\int _{\mathbb {B}}\,u^{\overline {p}}\,d\mu ({\overline {p}})$

where ${\mathbb {B} }$ is the set of sequences

${\overline {p}}=\langle p_{0},p_{1},p_{2},p_{3},\ldots \rangle$

of non-negative reals summing to 1 and such that $p_{1}\geq p_{2}\geq p_{3}\geq \ldots$, and $\mu$ is a $\sigma$-additive measure on the Borel subsets of ${\mathbb {B} }$ in the product topology..

de Finetti Representation Theorem (unary). In the unary case (where $L$ is a language containing $q$ unary predicates), the representation theorem for Ex is equivalent to:

$w=\int _{\mathbb {D}}\,w_{\vec {x}}\,d\mu ({\vec {x}}).$

Every probability function $w$ for $L$ satisfying Ex can be represented as

$w=\int _{\mathbb {D}}w_{\vec {x}}\,d\mu ({\vec {x}}).$

where ${\mathbb {D}}$ is the set of vectors ${\vec {x}}=\langle x_{1},x_{2},\ldots ,x_{2^{q}}\rangle$ of non-negative real numbers summing to one and $\mu$ is a $\sigma$-additive measure on ${\mathbb {D}}$.