Mathematical Inconsistency in Solomonoff Induction?

My understanding is that a hypothesis is a program which generates a complete prediction of all observations. So there is no specific hypothesis (X OR Y), for the same reason that there is no sequence of numbers which is (list of all primes OR list of all squares).

Note that by "complete prediction of all observations" I don't mean things like "tomorrow you'll see a blackbird", but rather the sense that you get an observation in a MDP or POMDP. If you imagine watching the world through a screen with a given frame rate, every hypothesis has to predict every single pixel of that screen, for each frame.

I don't know where this is explained properly though. In fact I think a proper explanation, which explains how these idealised "hypotheses" relate to hypotheses in the human sense, would basically need to explain what thinking is and also solve the entire embedded agency agenda. For that reason, I place very little weight on claims linking Solomonoff induction to bounded human or AI reasoning.

I went through the maths in OP and it seems to check out. I think the core inconsistency is that Solomonoff Induction implies $l(X\cup Y)=l\left(X\right)$ which is obviously wrong. I'm going to redo the maths below (breaking it down step-by-step more). curi has $2l\left(X\right)=l\left(X\right)$ which is the same inconsistency given his substitution. I'm not sure we can make that substitution but I also don't think we need to.

Let $X$ and $Y$ be independent hypotheses for Solomonoff induction.

According to the prior, the non-normalized probability of $X$ (and similarly for $Y$) is: (1)

$$P\left(X\right)=\frac{1}{2^{l\left(X\right)}}$$

what is the probability of $X\cup Y$? (2)

$$\begin{array}{cc}P(X\cup Y)& =P\left(X\right)+P\left(Y\right)-P(X\cap Y)\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)}}\cdot \frac{1}{2^{l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)}\cdot 2^{l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\end{array}$$

However, by Equation (1) we have: (3)

$$P(X\cup Y)=\frac{1}{2^{l(X\cup Y)}}$$

thus (4)

$$\frac{1}{2^{l(X\cup Y)}}=\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}$$

This must hold for any and all $X$ and $Y$.

curi considers the case where $X$ and $Y$ are the same length, starting with Equation (4), we get (5):

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\\ & =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(X\right)}}-\frac{1}{2^{l\left(X\right)+l\left(X\right)}}\\ & =\frac{2}{2^{l\left(X\right)}}-\frac{1}{2^{2l\left(X\right)}}\\ & =\frac{1}{2^{l\left(X\right)-1}}-\frac{1}{2^{2l\left(X\right)}}\end{array}$$

but (6)

$$\frac{1}{2^{l\left(X\right)-1}}\gg \frac{1}{2^{2l\left(X\right)}}$$

and (7)

$$0\approx \frac{1}{2^{2l\left(X\right)}}$$

so: (8)

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& \simeq \frac{1}{2^{l\left(X\right)-1}}\\ \therefore l(X\cup Y)& \simeq l\left(X\right)-1\\ & \square \end{array}$$

curi has slightly different logic and argues $l(X\cup Y)\simeq 2l\left(X\right)$ which I think is reasonable. His argument means we get $l\left(X\right)\simeq 2l\left(X\right)$. I don't think those steps are necessary but they are worth mentioning as a difference. I think Equation (8) is enough.

I was curious about what happens when $l\left(X\right)\ne l\left(Y\right)$. Let's assume the following: (9)

$$\begin{array}{cc}l\left(X\right)& <l\left(Y\right)\\ \therefore \frac{1}{2^{l\left(X\right)}}& \gg \frac{1}{2^{l\left(Y\right)}}\end{array}$$

so, from Equation (2): (10)

$$\begin{array}{cc}P(X\cup Y)& =\frac{1}{2^{l\left(X\right)}}+\frac{1}{2^{l\left(Y\right)}}-\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}\\ \underset{l\left(Y\right)\to \infty }{lim}P(X\cup Y)& =\frac{1}{2^{l\left(X\right)}}+{\frac{1}{2^{l\left(Y\right)}}}^0-{\frac{1}{2^{l\left(X\right)+l\left(Y\right)}}}^0\\ \therefore P(X\cup Y)& \simeq \frac{1}{2^{l\left(X\right)}}\end{array}$$

by Equation (3) and Equation (10): (11)

$$\begin{array}{cc}\frac{1}{2^{l(X\cup Y)}}& \simeq \frac{1}{2^{l\left(X\right)}}\\ \therefore l(X\cup Y)& \simeq l\left(X\right)\\ \Rightarrow l\left(Y\right)& \simeq 0\end{array}$$

but Equation (9) says $l\left(X\right)<l\left(Y\right)$ --- this contradicts Equation (11).

So there's an inconsistency regardless of whether $l\left(X\right)=l\left(Y\right)$ or not.

Details can be found in the excellent textbook by Li and Vitanyi.

In this context, "hypothesis" means a computer program that predicts your past experience and then goes on to make a specific prediction about the future.

"X or Y" is not such a computer program - it's a logical abstraction about computer programs.

Now, one might take two programs that have the same output, and then construct another program that is sorta like "X or Y" that runs both X and Y and then reports only one of their outputs by some pseudo-random process. In which case it might be important to you to know about how you can construct Solomonoff induction using only the shortest program that produces each unique prediction.

If you are guessing a binary sequence the job of a hypothesis is top say whether the next bit is going to be 1 or 0. A combination where both are fine or equally predicted fails to be a hypothesis. If you have partial predictions of X1XX0X and XX11XX you can "or" them into X1110X. But if you try to combine 01000 and 00010 the result will not be 01010 but something like 0X0X0.

Mathematically one option to handle partial predictions is to model them as groups of concrete "non-open" predictions which are compatible with them. 0X0X0 is short hand for {01010, 00010,01000,00000}. But 0X0X0 is not a hypothesis but a hypothesis schema or some other way of referring to the full set.

Statement that has room of interpretation what symbol it predicts will come next can't serve as a hypothesis. If we have a rorcharcs ink blot and a procedure to unambigiusly turn them into symbols that might not leave any wiggle room. But if the procedure is unspecified it fails to mean or predict anything for alignment with data checking purposes. You can't be correct or wrong if you don't call anything.

Even if you have "inkplot1" and "inkoplot2" as predictive hypotheses it is uncertain that "inkplo1 or inkplot2" has any procedure to turn into a prediction and even if it could have it might not be deducable for the rules for inkplots without connecting "ors". if "inkplot1" would predict 0 and "inkplot2" would predict 1 a generic combination will yield a "anything might happen" result which fails to be a prediction at all (ie "I have no idea what the next symbol is going to be"). But having a or rule that combined 010000 and 000010 into 0100010 has to be encoding specific.

I think you're seeing the problem of the universal prior. It's a free variable and depending on how you like to talk about it, you set it normatively, arbitrarily, on faith, or to serve a particular purpose.