User:IssaRice/Logical induction notation

This is in user space because it's not really about machine learning.

Term	Notation	Type	Definition	Notes
$\mathcal{F}$-combination	$A$	$\mathcal{S}\cup \{0,1\}\to {\mathcal{F}}_n$		Function application of an $\mathcal{F}$-combination uses square brackets instead of parentheses. Why? As far as I can tell, this is because each coefficient is in $\mathcal{F}$ so is itself a function. This means we have two senses of "application": we can pick out the specific coefficient we want (square brackets), or we can apply each coefficient to return something (parentheses).
Holdings from $T$ against $\overline{\mathbb{P}}$ (a $\mathbb{Q}$-combination)	$T(\overline{\mathbb{P}})$	$\mathcal{S}\cup \{0,1\}\to \mathbb{Q}$
Trading strategy	$T$	$\mathcal{S}\cup \{1\}\to \mathcal{E}\mathcal{F}$
Feature	$\alpha$	$[0,1{]}^{\mathcal{S}\times {\mathbb{N}}^{+}}\to \mathbb{R}$ or equivalently $(\mathcal{S}\times {\mathbb{N}}^{+}\to [0,1])\to \mathbb{R}$ or equivalently $\mathcal{F}$

Example of a 5-strategy given on p. 18 of the paper:

$\underset{{\xi }_1}{\underbrace{[(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}-{\varphi }^{*5}]}}\cdot (\varphi -{\varphi }^{*5})+\underset{{\xi }_2}{\underbrace{[{\varphi }^{*5}-(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}]}}\cdot (\mathrm{\neg }\mathrm{\neg }\varphi -(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5})$

Since the coefficients (${\xi }_1$ and ${\xi }_2$) are in ${\mathcal{E}\mathcal{F}}_5$, this is an ${\mathcal{E}\mathcal{F}}_5$-combination. Let's call this 5-strategy $T_5$. We can pick out the coefficient for the $\varphi$ term like $T_5[\varphi ]=(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}-{\varphi }^{*5}$. But since each coefficient is a feature (which is a function), we can also apply each coefficient to some valuation sequence $\overline{\mathbb{V}}$, like this:

$T_5(\overline{\mathbb{V}})=[(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}(\overline{\mathbb{V}})-{\varphi }^{*5}(\overline{\mathbb{V}})]\cdot (\varphi -{\varphi }^{*5}(\overline{\mathbb{V}}))+[{\varphi }^{*5}(\overline{\mathbb{V}})-(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}(\overline{\mathbb{V}})]\cdot (\mathrm{\neg }\mathrm{\neg }\varphi -(\mathrm{\neg }\mathrm{\neg }\varphi {)}^{*5}(\overline{\mathbb{V}}))$

Now each coefficient is a real number, so $T_5(\overline{\mathbb{V}})$ is an $\mathbb{R}$-combination. Note that since $T_5:\mathcal{S}\cup \{1\}\to {\mathcal{E}\mathcal{F}}_5$ is a function that takes a sentence or the number $1$ and $\overline{\mathbb{V}}$ is a valuation sequence (not a sentence or number), there appears to be a type error in writing $T_5(\overline{\mathbb{V}})$. What is going on is that we aren't evaluating $T_5$ at $\overline{\mathbb{V}}$; rather, we are evaluating each coefficient of $T_5$, to convert the range of $T_5$ from ${\mathcal{E}\mathcal{F}}_5$ to $\mathbb{R}$.

To summarize the types:

• $T_5:\mathcal{S}\cup \{1\}\to {\mathcal{E}\mathcal{F}}_5$
• $T_5[\varphi ]\in {\mathcal{E}\mathcal{F}}_5$ in other words $T_5[\varphi ]:[0,1{]}^{\mathcal{S}\times {\mathbb{N}}^{+}}\to \mathbb{R}$
• $T_5(\overline{\mathbb{V}}):\mathcal{S}\cup \{1\}\to \mathbb{R}$

If $T=c+{\xi }_1{\varphi }_1+\cdots +{\xi }_k{\varphi }_k:\mathcal{S}\cup \{1\}\to {\mathcal{E}\mathcal{F}}_n$, then

$\mathbb{V}(T)=c+{\xi }_1\mathbb{V}({\varphi }_1)+\cdots +{\xi }_k\mathbb{V}({\varphi }_k)\in {\mathcal{E}\mathcal{F}}_n$

and

$T(\overline{\mathbb{V}})=c(\overline{\mathbb{V}})+{\xi }_1(\overline{\mathbb{V}}){\varphi }_1+\cdots +{\xi }_k(\overline{\mathbb{V}}){\varphi }_k:\mathcal{S}\cup \{1\}\to \mathbb{R}$

and

$\mathbb{W}(T(\overline{\mathbb{V}}))=c(\overline{\mathbb{V}})+{\xi }_1(\overline{\mathbb{V}})\mathbb{W}({\varphi }_1)+\cdots +{\xi }_k(\overline{\mathbb{V}})\mathbb{W}({\varphi }_k)\in \mathbb{R}$

I think $\mathbb{W}(T(\overline{\mathbb{V}}))=(\mathbb{W}(T))(\overline{\mathbb{V}})$.

The following is used in the Fixed Point Lemma (5.1.1):

Writing the $n$-strategy as

$T_n=\sum _{j=1}^k{\xi }_j{\varphi }_j-\sum _{j=1}^k{\xi }_j\underset{j}{\overset{*n}{\varphi }}$

we have

$\mathbb{V}(T_n({\mathbb{P}}_{\le n-1},\mathbb{V}))=\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \mathbb{V}({\varphi }_j)-\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \underset{j}{\overset{*n}{\varphi }}({\mathbb{P}}_{\le n-1},\mathbb{V})$

But ${\varphi }^{*n}({\mathbb{P}}_{\le n-1},\mathbb{V})=\mathbb{V}({\varphi }_j)$ so the two sums cancel to obtain $0$.

External links

• https://arbital.com/p/logical_inductor_nota/
• https://arbital.com/p/logical_induction/