Skip to content

The Proof Theory Blog

!(A & B) = !A ⊗ !B

Menu
  • Home
  • About
  • Contribute
  • Resources
Menu

On representations and their brute-forced connections.

Posted on March 13, 2023March 14, 2023 by Sam Sanders

TL;DR: classical Reverse Mathematics makes heavy use of so-called codes or representations. We observe a major problem with this coding practise, namely the connection between open sets and continuous functions, which is ‘brute-forced’ by the coding of these objects.

The long version: Reverse Mathematics needs no introduction on this blog and neither does L_2, the language of second-order arithmetic. As is well-known, L_2 contains a sort for natural numbers and a sort for sets of natural numbers. Using this frugal setup, one can represent higher-order objects via -often cumbersome- codes or representations.

First of all, as a case in point, here is the definition of ‘code for continuous function’, which looks nothing like the usual ‘epsilon-delta’ definition at first glance.

A (code for a) continuous function on [0, 1] is a set of quintuples \Phi\subset \mathbb{N}\times \mathbb{Q}\times \mathbb{Q}\times \mathbb{Q}\times \mathbb{Q}^{+} which satisfies the following three conditions:
1) If (a, r)\Phi(b, s) and (a,r)\Phi(b', s') then |b-b'|\leq s+s',
2) If (a,r)\Phi(b,s) and |a'-a|+r'\leq r then (a', r')\Phi(b,s),

3) If (a,r)\Phi(b,s) and |b-b'|+s\leq s' then (a,r)\Phi(b',s'),

and the domain condition:

    \[(\forall x\in [0,1])(\forall \epsilon>0)(\exists (m,a,r,b,s)\in \Phi)(|x-a|<r\wedge s<\epsilon ),\]


where (a,r)\Phi(b,s) is an abbreviation for (\exists (m,a,r,b,s) \in \Phi).

(see Simpson’s excellent SOSOA, II.6.1)

Complicated as such codes may look, they are ‘easy to find’: as shown here, one only needs weak Koenig’s lemma (WKL) to show that a third-order [0,1]\rightarrow \mathbb{R}-function that is continuous has an RM-code in the above sense, working in Kohlenbach’s base theory for higher-order Reverse Mathematics. In this way, the use of codes for continuous functions does not (seem to) have a big influence on the Reverse Mathematics of the ‘Big Five’, the weakest system of which is WKL. In short:

codes for continuous functions are easy to find, namely the weakest Big Five system suffices.

Secondly, open sets of reals also are not available directly in L_2 and are represented as unions of open balls. We write ‘x\in U‘ for (\exists n\in \mathbb{N})(a_n<x<b_n) for an open set U=\cup_{n\in \mathbb{N}} (a_n, b_n). It is then a natural question how hard it is to prove the following ‘coding principle’ (Open), where open sets of reals are given by their characteristic functions (well-known from measure and probability theory):

(Open) For any open set O\subset [0,1], there is a sequence of intervals ((a_n, b_n))_{n\in \mathbb{N}} such that O=\cup_n (a_n, b_n).

One can show (see Remark 1.13 here) that open sets without any representation occur `in the wild’, namely in the study of regulated and bounded variation functions. The latter are rather tame and play an important role in e.g. Fourier analysis. In this way, (Open) is not just spielerei.

As shown here, none of the Big Five can prove the coding principle (Open), and the same for much stronger principles. In fact, (Open) is ‘explosive’ in that adding it to \Pi_1^1-CA_0^\omega, the higher-order version of \Pi_1^1-CA_0, one can derive the much stronger \Pi_2^1-CA_0. In a nutshell, we have:

codes for open sets are hard to find, namely none of the Big Five systems suffice.

Thirdly, the above two paragraphs show that open sets and continuous functions are fundamentally different classes of objects. Since Reverse Mathematics is supposed to analyse theorems of ordinary mathematics as they stand (see I.8.9 and IV.2.8 in SOSOA for this very pov), this fundamental difference must be respected. Unfortunately, this fundamental difference is not reflected in second-order Reverse Mathematics in light of the following theorem.

Given a code RM-open set U=\cup_n\in \N (a_n, b_n), we can effectively find a code for a continuous function h_U such that x\in U \leftrightarrow h_U(x)>0 for all real x. Vice versa, for a code for a continuous function f, we can effectively find a code for an open set V=\cup_m(c_m, d_m) such that f(x)>0\leftrightarrow x \in V.

(See Simpson’s excellent SOSOA, II.7.1 for a proof in the base theory RCA_0.)

Now, the connection between codes for open sets and continuous functions is of course well-known from (Turing) computability theory, and enables the representation of third-order objects in L_2. That is all well and good for computability theory, but Reverse Mathematics is supposed to deal with mathematics ‘as it stands’. As it stands, the coding of open sets and continuous functions ‘brute-forces’ the identification of two fundamentally different classes of objects, which is not acceptable if one stands by the grand foundational claims made in Reverse Mathematics.

In my opinion, the above observations are fundamentally more problematic than previous problems associated with coding, like in the case of the Nielsen-Schreier theorem (see here). As we will observe in a future post, coding similarly distorts the relation between well-known function classes, e.g. bounded variation and Baire 1, but that is for another day.

In conclusion, the coding practice of second-order Reverse Mathematics brute-forces the identification of two fundamentally different classes of objects, namely open sets and continuous functions. If one believes that Reverse Mathematics should analyse theorems ‘as they stand’, this kind of identification is not acceptable.



Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Meta

  • Register
  • Log in
  • Entries RSS
  • Privacy Policy

Search

© 2023 The Proof Theory Blog | Powered by Minimalist Blog WordPress Theme
The Proof Theory Blog uses cookies, but you can opt-out if you wish. For further information see our privacy policy. Cookie settingsAccept
Privacy & Cookies Policy

Privacy Overview

This website uses cookies to improve your experience while you navigate through the website. Out of these cookies, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may have an effect on your browsing experience.
Necessary
Always Enabled
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Non-necessary
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
SAVE & ACCEPT