Abstract

Purpose: This paper introduces and rigorously proves the Simplicity-Expressive Power Principle (SEPP). It establishes a single, quantitative information-theoretic principle from which the classical limitative results of Gödel, Turing, and Chaitin can be seen as immediate consequences, thereby offering a deep and unified explanation for the limits of formal reasoning.

Methods: The methodology is twofold. First, a formal development within algorithmic information theory is used to define a system's "Expressive Power" and prove the main theorem, SEPP. Second, this formal result is used as the rigorous foundation for a philosophical argument that reframes the limits of reason as a law of complexity conservation.

Results: The main theorem is $\mathrm{Exp}(F) \le K(F) + c$. The paper demonstrates that this principle is both generative, yielding a new Principle of Diminishing Algorithmic Returns, and unifying, providing a common informational source from which Gödel's, Turing's, and Chaitin's theorems can be rigorously derived.

Conclusion: SEPP is a fundamental law of information for formal systems. This result supports a constructivist model of mathematics, offers a potential re-framing of the puzzle of the "unreasonable effectiveness" of mathematics, and has broad implications for formal epistemology and the philosophy of physics.

Introduction

A single, quantitative principle governs the limits of formal reasoning: the Simplicity-Expressive Power Principle (SEPP). In conceptual terms, SEPP states that a formal system’s capacity to describe complex phenomena is strictly bounded by the complexity of its own axioms. This principle provides a unified framework for understanding why all formal systems are inherently constrained, revealing that the limits of reason are not arbitrary but follow from a fundamental law linking a system's simplicity to its expressive reach.

Contribution and Relation to Prior Work

The foundational concepts of algorithmic information theory (AIT) have long been used to analyze the limits of formal systems (Li and Vit´anyi 2008;Calude 2002;Yanosky 2013). Key historical concepts include Solomonoff's theory of inductive inference (Solomonoff 1964), Levin's search algorithm (Levin 1973), and Chaitin's Omega number (Chaitin 1987). These landmark theories primarily address questions of prediction, problem-solving, and a system's introspective limits—what it can know about its own computational processes.

This paper builds on this foundation but is fundamentally different in its purpose and scope. SEPP is a principle of extrospective description. Its central question is not about prediction or internal problem-solving, but about a system's capacity to describe and ground knowledge of external phenomena.

The critical insight is that while the Complexity-Entropy bound ($H(P) \le K(P)+c$) is a known inequality relating two properties of a single object (a distribution $P$), SEPP elevates this into a law about a formal system $F$. The innovation lies in using this bound as a probe to define a new, fundamental property of the system itself: its maximum Expressive Power, $\mathrm{Exp}(F)$. SEPP is therefore not a statement about any particular distribution, but a statement about the system's total descriptive budget.

The contribution of this work is thus threefold:

1. We introduce Expressive Power, $\mathrm{Exp}(F)$, a new measure designed specifically to quantify a system's maximum descriptive reach.
2. We frame the relationship between this power and the system's simplicity as a fundamental law, SEPP.
3. We demonstrate that this single, extrospective law is a powerful unifying source from which the classical, introspective limitative theorems of Gödel, Turing, and Chaitin can be derived as necessary corollaries, and from which new insights can be generated.

This unifying and generative power demonstrates that SEPP is not merely a repackaging of known bounds, but a new and more general law of informational economics for formal systems.

Formalizing Simplicity and Expressive Power

The simplicity of a system $F$ is naturally defined as the length of its ultimate description, its Kolmogorov complexity, $K(F)$. Defining its expressive power requires a more robust philosophical defense.

On the Definition of Expressive Power

The central definition of this paper is that of Expressive Power, $\mathrm{Exp}(F)$. It is an intentionally idealized measure, designed to answer a specific, fundamental question: What is the absolute, law-like boundary of a formal system's capacity to ground knowledge about probabilistic phenomena? To answer this, each component of the definition is a necessary choice.

First, we model phenomena with probability distributions, and we measure their informational content using Shannon entropy. This is not an arbitrary choice; Shannon entropy is the canonical, rigorously justified measure of information for a probabilistic source in information theory. Any principle aiming to quantify descriptive power must engage with it.

Second, we demand the strongest possible epistemic standard: certification via formal proof. A system only truly "knows" or "describes" that which it can prove. Any weaker standard, such as mere consistency, would fail to capture the system's actual deductive reach. Our goal is not to measure a system's day-to-day "usefulness," but to find its ultimate informational limit. To find this hard limit, we must demand this strongest standard of knowledge.

A potential objection is that this definition is so strong that the expressive power of powerful real-world theories like ZFC might be quite low. This objection correctly identifies the definition's strength but mistakes its purpose. The principle $\mathrm{Exp}(F) \le K(F) + c$ is a hard boundary, a law of information. The fact that a theory like ZFC—with its relatively simple axioms, so $K(\text{ZFC})$ is small—cannot certify phenomena of arbitrarily high entropy is not a failure of the definition, but a profound result of the principle itself. It reveals that even our most powerful theories are informationally bounded.

Definition 2.1 (Expressive Power). The expressive power of a formal system $F$, $Exp(F)$, is the maximal Shannon entropy of any lower semi-computable probability distribution that the system can certify.

Definition 2.2 (Certification). A consistent R.E. system $F$ certifies a lower semi-computable probability distribution $P$ if, for every string $s$ in the support of $P$ (i.e., where $P(s) > 0$), $F$ can prove a statement of the form $\ulcorner \mathrm{Prob}(\bar{s}, \bar{p}, \bar{q}) \urcorner$, which is interpreted as the formal assertion that $P(s) \ge p/q$ for positive integers $p, q$. In essence, $F$ must be able to prove a positive rational lower bound for the probability of every outcome that can occur.

Remark 2.3 (On the Strength of the Certification Condition). One might consider weaker epistemic standards for a system's descriptive capacity. For example, a system could be said to "model" a distribution if it could merely prove the distribution's entropy value, or if it could certify the probabilities of some but not all outcomes. However, such definitions, while potentially useful for measuring practical applicability, are insufficient for establishing a fundamental, law-like boundary. To find the absolute, hard limit on a system's ability to ground knowledge, we must demand the strongest, most rigorous standard: the provable certification of every possible outcome. The strength of the definition is thus a necessary feature for the principle to have the force of a fundamental law.

Remark 2.4 (Relation to Chaitin's $\Omega_F$). The reader familiar with AIT may wonder how $\mathrm{Exp}(F)$ relates to Chaitin's halting probability for a theory, $\Omega_F$. While both are measures of a theory's information content linked to its complexity $K(F)$, they capture different aspects of its power. $\Omega_F$ measures the theory's capacity to resolve its own internal questions (the halting of programs it can specify). In contrast, $\mathrm{Exp}(F)$ is defined to measure the theory's capacity to describe external phenomena—arbitrary probability distributions. The goal of SEPP is to establish a limit on a system's descriptive reach into the world, for which the Shannon entropy of certifiable distributions is the more direct and natural tool.

Theorem 2.5 (Simplicity-Expressive Power Principle (SEPP)). For any consistent, recursively enumerable (R.E.) formal system , the following inequality holds:

Remark 2.6 (On the Constant $c$). The constant is not part of the formal system $F$ itself. Rather, it represents the fixed, non-negotiable complexity of the universal framework of computation and logic —pegged to a specific choice of universal Turing machine $U$ —within which $F$ is expressed. It is the size of the "interpreter" program needed to parse axioms, derive theorems, and relate complexity to probability. In conceptual terms, if $K(F)$ is the informational cost of a system's specific axioms, $c$ is the constant informational overhead of the entire apparatus of reason. Its existence ensures that the total informational budget for any formal system is strictly finite, and while its value depends on the choice of $U$, the law itself is invariant up to this additive constant.

Remark 2.7 (An Intuitive Example of SEPP). Consider a trivial formal system, $F_{trivial}$, whose only axiom allows it to prove $\ulcorner \mathrm{Prob}(\text{"0"}, 1, 2) \urcorner$.

• Simplicity: The description of this single axiom is a short string, so its simplicity $K(F_{trivial})$ is a small constant.
• Expressive Power: $F_{trivial}$ certifies the distribution $P$ where $P(\text{"0"}) = 1$ and $P(x)=0$ otherwise. The Shannon entropy of this distribution is $H(P) = 0$. This is the richest distribution it can certify, so $\mathrm{Exp}(F_{trivial}) = 0$.
• The Principle Holds: The inequality $0 \le K(F_{trivial}) + c$ is clearly true. To describe richer phenomena (distributions with entropy $> 0$), a system would require more complex axioms.

Consequences of SEPP: Generation and Unification

This section demonstrates SEPP's dual role. The proofs in this section are presented as concise logical arguments, with technical lemmas detailed in the Appendix.

A Generative Consequence

Corollary 3.1 (Principle of Diminishing Algorithmic Returns). Let $F_{i+1} = F_i \cup \{A_i\}$ be a sequence of consistent systems. The marginal gain in expressive power per unit of added complexity is bounded by approximately 1.

Proof This result follows from applying SEPP to both $F_i$ and $F_{i+1}$ and combining it with the subadditivity of complexity. The formal proof in the Appendix shows that the gain in expressive power, $\mathrm{Exp}(F_{i+1}) - \mathrm{Exp}(F_i)$, is bounded by the complexity of the new axiom, $K(A_i|F_i)$, plus a small constant. $\blacksquare$

A Unifying Consequence

The following derivations are not intended to replace the original, constructive proofs of the limitative theorems. Rather, their purpose is explanatory and unifying. In the same way that conservation laws in physics (e.g., conservation of energy) provide a high-level, unifying explanation for disparate phenomena without replacing the detailed mechanical derivations, SEPP provides a single, high-level informational principle that explains why these disparate logical limitations must exist. The goal is to show that they are all necessary consequences of the same fundamental mismatch between a finite axiomatic complexity and an infinite descriptive demand.

Corollary 3.2 (Gödel's First Incompleteness Theorem (Gödel 1931)). Any consistent R.E. system $F$ containing arithmetic is incomplete.

Proof Assume $F$ is complete. As rigorously demonstrated in the Appendix, such a complete system would be required to certify constructed probability distributions of arbitrarily high entropy. This would mean its expressive power, $\mathrm{Exp}(F)$, must be infinite. However, as an R.E. system, its simplicity, $K(F)$, is finite. This establishes a contradiction, $\infty \le K(F) + c$, which violates SEPP. $\blacksquare$

Corollary 3.3 (Undecidability of the Halting Problem (Turing 1936)). There is no algorithm that decides the halting problem.

Proof Assume a halting decider exists. A formal system $F_{Halt}$ equipped with this decider could, as shown in the Appendix, violate Chaitin's incompleteness theorem for any complexity bound. This, in turn, implies its expressive power would be infinite: $\mathrm{Exp}(F_{Halt}) = \infty$. But such a system has a finite simplicity $K(F_{Halt})$. This yields the contradiction $\infty \le K(F_{Halt}) + c$, violating SEPP. $\blacksquare$

Corollary 3.4 (Chaitin's Incompleteness Theorem). For any consistent R.E. system $F$, there is a constant $L \approx K(F)$ such that $F$ cannot prove any theorem of the form $\ulcorner K(x) > L \urcorner$.

Proof As rigorously proven in the Appendix, if a system could prove that strings have arbitrarily high complexity, its expressive power would necessarily be infinite. This would mean $\mathrm{Exp}(F) = \infty$, which contradicts SEPP's requirement that $\mathrm{Exp}(F)$ be bounded by the finite simplicity $K(F)$. $\blacksquare$

Philosophical Contribution and Conclusion

This paper has introduced, proven, and demonstrated the consequences of the Simplicity-Expressive Power Principle. The dual results establish SEPP as a fundamental law of information for formal systems. The depth of this unification lies in its explanatory power: it reframes the limits of reason, shifting the paradigm from one of logical paradox to one of complexity conservation.

This perspective provides a powerful formal basis for a constructivist model of mathematics. The limits of reason are not arbitrary flaws but are a direct, quantifiable consequence of building knowledge from a finite axiomatic base. SEPP formally explains Gödelian incompleteness—the inability of a theory to prove all truths about its domain. But the history of mathematics reveals a second, related struggle with what might be termed incompleteness of domain: the inability of a domain to furnish the objects needed to solve its own problems. The extension from the natural numbers to the integers to solve simple subtraction is a classic case. In both instances, the path forward is the same: the injection of genuinely novel information, be it a new axiom or a new type of object. While a Platonist position remains coherent, SEPP supports a more parsimonious alternative, suggesting that mathematics is better modeled as a verb than a noun: an ongoing process of construction against these dual limits, forever bounded by the complexity of its own starting points.

Furthermore, this constructivist model offers a potential resolution to the long-standing puzzle of the "unreasonable effectiveness of mathematics" in the physical sciences. The mystery of why our physical world conforms to abstract mathematical laws is most potent from a Platonist perspective. A constructivist viewpoint, however, reframes the question: we invent and select mathematical tools precisely because they are effective at modeling the observed regularities of the universe. The effectiveness is not a miracle, but a result of targeted design. The Simplicity-Expressive Power Principle then explains why this effectiveness is not "unreasonable" but is, in fact, bounded and necessarily incomplete. Our most powerful physical theories, from General Relativity to the Standard Model, are formal systems $F$ with remarkably low Simplicity, $K(F)$. SEPP therefore dictates that their Expressive Power, $\mathrm{Exp}(F)$, must be finite. This formally guarantees that they will be incomplete approximations that break down at the limits of complexity—exactly what we observe at singularities or the quantum gravity scale. The effectiveness of mathematics is thus rendered "reasonable": it is the predictable power of simple models to approximate, but never fully capture, a complex reality.

In conclusion, SEPP is a fundamental law of information for formal systems. Its primary contribution is to provide a unified, quantitative explanation for the limits of reason, shifting the paradigm from one of logical paradox to one of complexity conservation. This perspective provides a powerful formal basis for a constructivist model of mathematics and offers a new, information-theoretic lens on the relationship between formal systems and the world they are built to describe. It establishes that any attempt at a "perfect" description is doomed not by self-reference, but by the simple and inexorable laws of informational economics.

Remark 4.1 (A Speculative Parallel to Physics). The law of bounds on formal description established by SEPP resonates with similar informational limits found in fundamental physics. The trade-off between a system's Simplicity ($K(F)$) and its Expressive Power ($\mathrm{Exp}(F)$) exhibits a striking conceptual parallel to the trade-off between momentum certainty and position certainty in the Heisenberg Uncertainty Principle. This parallel is, of course, conceptual, not a claim of formal equivalence; there is no suggestion here of a direct mathematical mapping between the constant $c$ and Planck's constant. Rather, both SEPP and the HUP can be seen as manifestations of a deeper, universal principle: that the specification of information is subject to fundamental, inescapable trade-offs. Whether this is a mere analogy or a hint of a profound unity between the laws of logic and the laws of physics is a compelling question for future work.

Declarations

Funding Not applicable.
Conflict of interest The author has no conflicts of interest to declare.
Availability of data and material Not applicable.

References

1. Calude CS (2002) Information and Randomness: An Algorithmic Perspective, 2nd edn. Springer-Verlag, Berlin, Heidelberg
2. Chaitin GJ (1987) Algorithmic Information Theory. Cambridge University Press, Cambridge
3. Gödel K (1931) Über formal unentscheidbare sätze der principia mathematica und verwandter systeme i. Monatshefte für Mathematik und Physik 38:173–198
4. Levin LA (1973) Universal sequential search problems. Problemy Peredachi Informatsii 9(3):115–116. In Russian. English translation in Problems of Information Transmission, 9(3):265–266
5. Li M, Vitányi PMB (2008) An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, New York
6. Shoenfield JR (1967) Mathematical Logic. Addison-Wesley, Reading, MA
7. Solomonoff RJ (1964) A formal theory of inductive inference. Part I. Information and Control 7(1):1–22
8. Turing AM (1937) On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London Mathematical Society s2-42(1):230–265
9. Yanofsky NS (2013) The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us. The MIT Press, Cambridge, MA

Technical Appendix: Formal Proofs and Derivations

This appendix provides the fully detailed definitions and proofs referenced in the main body.

AIT Preliminaries

We assume a standard prefix-free universal Turing machine $U$. All complexities are prefix-free complexities, and all logarithms are base 2.

Definition A.1 (Kolmogorov Complexity). The prefix-free Kolmogorov complexity $K(x)$ of a binary string $x$ is the length of the shortest program $p$ for $U$ that outputs $x$ and halts. $K(x|y)$ is the complexity of $x$ given $y$ as an auxiliary input.

Definition A.2 (Shannon Entropy). Let $P$ be a discrete probability distribution over a set of strings $S$. The Shannon entropy of the distribution, $H(P)$, is defined as:

By convention, $0 \log_2 0 = 0$. Entropy measures the average amount of information or "surprise" provided by an outcome drawn from the distribution.

Proposition A.3 (Chain Rule for Complexity (Li and Vit´anyi)). $K(x,y) \le K(x) + K(y|x) + O(1)$. As a consequence, $K(y) \le K(x,y) + O(1) \le K(x) + K(y|x) + O(1)$.

Proposition A.4 (Complexity-Entropy Bound (Li and Vit´anyi)). For any lower semi-computable probability distribution $P$, its Shannon entropy $H(P)$ is bounded by its Kolmogorov complexity: $H(P) \le K(P) + c$.

Full Proof of the Simplicity-Expressive Power Principle

Lemma A.5 If a consistent R.E. system $F$ certifies a lower semi-computable distribution $P$, then $K(P|F) = O(1)$.

Proof A program can be written that, given a description of $F$, lower-semi-computes $P$. This program acts as an interpreter for the logical framework $\mathcal{L}$. It takes the axioms of $F$ as input, enumerates all theorems of $F$, filters for theorems of the form $\ulcorner \mathrm{Prob}(\bar{s}, \bar{p}, \bar{q}) \urcorner$, and outputs the corresponding pairs $(p/q, s)$. Since $F$ certifies $P$, this procedure constitutes a valid lower-semicomputation of $P$. The length of this interpreter program is a fixed constant, independent of $F$. Thus, $K(P|F) = O(1)$. $\blacksquare$

Theorem A.6 (SEPP, Restated). For any consistent R.E. system , $\mathrm{Exp}(F) \le K(F) + c$.

Proof Let $P$ be any distribution certified by $F$. By Lemma A.5 $K(P|F) \le c_1$. By the Chain Rule, $K(P) \le K(F) + K(P|F) + c_2 \le K(F) + c_1 + c_2$. By the Complexity-Entropy Bound, $H(P) \le K(P) + c_3 \le K(F) + c_1 + c_2 + c_3$. Let $c = c_1+c_2+c_3$. This holds for any certified $P$, and thus for the supremum $\mathrm{Exp}(F)$. $\blacksquare$

Proofs of Corollaries

Proof of Corollary 3.1 (Diminishing Returns) Let $F_{i+1} = F_i \cup \{A_i\}$. Let $\Delta E_i = \mathrm{Exp}(F_{i+1}) - \mathrm{Exp}(F_i)$ and $\Delta K_i = K(A_i|F_i)$. By SEPP on $F_{i+1}$, $\mathrm{Exp}(F_{i+1}) \le K(F_{i+1}) + c$. By subadditivity, $K(F_{i+1}) \le K(F_i) + \Delta K_i + c_1$. Thus, $\Delta E_i \le (K(F_i) - \mathrm{Exp}(F_i)) + \Delta K_i + c_1 + c$. By SEPP on $F_i$, $K(F_i) - \mathrm{Exp}(F_i) \ge -c$. Therefore, $\Delta E_i \le \Delta K_i + c_1$. Dividing by $\Delta K_i$ gives the result. $\blacksquare$

Lemma A.7 If a consistent R.E. system $F$ containing arithmetic is complete, then $\mathrm{Exp}(F) = \infty$.

Proof To prove this, we explicitly construct, for any integer $M > 0$, a lower semi-computable probability distribution $P_M$ with $H(P_M) = M$ and show that a complete system $F$ must certify it.

1. Construction of $P_M$: Let $S_M = \{x \in \{0,1\}^* \mid K(x) > M \}$. This set is infinite but not recursively enumerable. Let $x_1, x_2, \dots, x_{2^M}$ be the first $2^M$ strings in $S_M$ in lexicographical order. Define the distribution $P_M$ to be uniform over this set of strings: $P_M(x_i) = 1/2^M$ for $i \in \{1, \dots, 2^M\}$ and $P_M(x) = 0$ otherwise.
2. Properties of $P_M$: The entropy of this distribution is $H(P_M) = \sum_{i=1}^{2^M} -(1/2^M) \log(1/2^M) = 2^M \cdot (M/2^M) = M$. The distribution $P_M$ is lower semi-computable because one can approximate $K(x)$ from above, and thereby enumerate the set of strings whose complexity is known to be greater than $M$.
3. Certification by a Complete System: For each $i \in \{1, \dots, 2^M\}$, the statement "$x_i$ is in the support of $P_M$" is true. This statement is equivalent to the claim that a specific Turing machine (one that searches for and lists the first $2^M$ strings with complexity $> M$) eventually halts and includes $x_i$ in its output. The assertion of a specific Turing machine's halting is a canonical $\Sigma_1$ sentence in the language of arithmetic. By Shoenfield's absoluteness theorem (Shoenfield 1967), $\Sigma_1$ sentences are absolute, meaning if they are true in the standard model of arithmetic, they are provable in any complete axiomatization of arithmetic. Since these statements are true by construction, a complete system $F$ must prove them.
4. Specifically, for each $x_i$ in the support of $P_M$, $F$ must prove the sentence $\ulcorner \mathrm{Prob}(\bar{x_i}, \overline{1}, \overline{2^M}) \urcorner$. This is precisely the condition for certification.
5. Conclusion: Since we can construct such a distribution $P_M$ with entropy $M$ for any arbitrary integer $M$, and a complete system $F$ would certify every one of them, the set of entropies of distributions certified by $F$ is unbounded. Therefore, by definition, $\mathrm{Exp}(F) = \infty$. $\blacksquare$

Lemma A.8 The existence of a halting decider implies the existence of a formal system $F_{Halt}$ with $\mathrm{Exp}(F_{Halt}) = \infty$.

Proof Let $H$ be a hypothetical halting decider algorithm.

1. Constructing the System: Construct the system $F_{Halt}$ by adding to Peano Arithmetic (PA) an axiom schema that formalizes the statement "program $p$ on input $i$ halts if and only if $H(p,i)=1$".
2. Violation of Chaitin's Theorem: A halting decider allows for the computation of the Kolmogorov complexity $K(x)$ for any string $x$. The procedure is as follows: to find $K(x)$, enumerate all programs $p$ in increasing order of length. For each program, run it and use the oracle $H$ to determine if it halts. The first program that halts with output $x$ is the shortest, and its length is $K(x)$.
3. This means that for any integer $n$, the system $F_{Halt}$ can compute a string $x$ such that $K(x) > n$, and can formally prove that its complexity is indeed greater than $n$. For example, it can prove the theorem $\ulcorner K(x) > n \urcorner$.
4. Implication for Expressive Power: By Proposition A.9 (proven next), a system that can prove $\ulcorner K(x) > n \urcorner$ for arbitrarily large $n$ must have infinite expressive power.
5. Conclusion: Since $F_{Halt}$ can prove theorems of this form for any $n$, it follows that $\mathrm{Exp}(F_{Halt}) = \infty$.

Proposition A.9 If a consistent R.E. system $F$ can prove $\ulcorner K(x) > n \urcorner$ for arbitrarily large $n$, then $\mathrm{Exp}(F) = \infty$. $\blacksquare$

Proof Suppose $F$ can prove $\ulcorner K(x) > n \urcorner$ for arbitrarily large $n$. We use this property to show that $F$ must certify distributions of arbitrarily high entropy. For any integer $M > 0$, we can construct a distribution $P_M$ as follows:

1. Construction of $P_M$: Write a program that enumerates all theorems of $F$. Let $S_M = \{x_1, \dots, x_{2^M}\}$ be the set of the first $2^M$ distinct strings for which the program finds a proof of a theorem of the form $\ulcorner K(x_i) > M \urcorner$. Since the premise is that such proofs exist for any $M$, this search will terminate. Define the distribution $P_M$ to be uniform over this set: $P_M(x_i) = 1/2^M$ for $i \in \{1, \dots, 2^M\}$ and $P_M(x)=0$ otherwise.
2. Properties of $P_M$: The entropy of this distribution is $H(P_M) = \sum_{i=1}^{2^M} -(1/2^M) \log(1/2^M) = 2^M \cdot (M/2^M) = M$. The distribution is lower semi-computable because its support set $S_M$ is recursively enumerable by construction.
3. Certification by F: By its very construction, for each $x_i \in S_M$, $F$ can prove that $x_i$ is in the support of $P_M$. $F$ can also prove the size of the set is $2^M$. From this, it can prove the lower bound $\ulcorner \mathrm{Prob}(\bar{x_i}, \overline{1}, \overline{2^M+1}) \urcorner$ for each $x_i$. This is the condition for certification.
4. Conclusion: Since we can perform this construction for any arbitrarily large integer $M$, it follows that for any $M$, there exists a distribution $P_M$ with entropy $M$ that $F$ certifies. The set of entropies of distributions certified by $F$ is therefore unbounded. By definition, $\mathrm{Exp}(F) = \infty$. $\blacksquare$