2504/2504.00006.md

Title: 1 Introduction

URL Source: https://arxiv.org/html/2504.00006

Published Time: Wed, 02 Apr 2025 00:00:20 GMT

Markdown Content: Self-graphing equations

Samuel Allen Alexander

Abstract

Can you find an x⁢y 𝑥 𝑦 xy italic_x italic_y-equation that, when graphed, writes itself on the plane? This idea became internet-famous when a Wikipedia article on Tupper’s self-referential formula went viral in 2012. Under scrutiny, the question has two flaws: it is meaningless (it depends on typography) and it is trivial (for reasons we will explain). We fix these flaws by formalizing the problem, and we give a very general solution using techniques from computability theory.

Suppose your friend sends you an x⁢y 𝑥 𝑦 xy italic_x italic_y-equation and you start graphing it. After graphing for a few minutes, you notice that what you’ve graphed so far looks like the letter x 𝑥 x italic_x. You continue graphing, and you notice that you’ve just plotted the letter y 𝑦 y italic_y on your graphing paper. After some more work, you notice that you’ve just added the symbol +++ in between the x 𝑥 x italic_x and the y 𝑦 y italic_y. You continue this way for many hours until the equation is completely graphed. Then you step back and realize that what you’ve written on your graphing paper is the very equation your friend sent you!

A self-graphing equation is an equation such that, when you graph it, you get the equation itself back, written on your graphing paper. This idea received a lot of attention when a Wikipedia article on Tupper’s self-referential formula went viral in 2012 1 1 1 Tupper’s so-called self-referential formula is not actually self-referential at all (nor did he himself call it self-referential [6]). Rather, it’s a formula whose graph contains every possible 106×17 106 17 106\times 17 106 × 17-pixel bitmap. Tupper later posted an actually self-referential formula on his website [7], but it received less attention. Tupper’s original formula has been generalized by Somu and Mishra [4]. Trávník has also published a self-graphing formula [5]..

The problem of finding a self-graphing equation is meaningless because it depends on typography. It’s also trivial, if no limit is placed on what functions one can use in the equation and how they are written. Indeed, fix a particular image I⊆ℝ 2 𝐼 superscript ℝ 2 I\subseteq\mathbb{R}^{2}italic_I ⊆ blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT of the equation “F⁢(x,y)=1 𝐹 𝑥 𝑦 1 F(x,y)=1 italic_F ( italic_x , italic_y ) = 1” on the plane (for example, the letter F 𝐹 F italic_F could be the union of a vertical line segment and two horizontal line segments; the parentheses could be fragments of Bézier curves; and so on), and define F:ℝ→{0,1}:𝐹→ℝ 0 1 F:\mathbb{R}\to{0,1}italic_F : blackboard_R → { 0 , 1 } by

F⁢(x,y)={1 if(x,y)∈I,0 otherwise.𝐹 𝑥 𝑦 cases 1 if(x,y)∈I,0 otherwise.F(x,y)=\begin{cases}1&\mbox{if $(x,y)\in I$,}\ 0&\mbox{otherwise.}\end{cases}italic_F ( italic_x , italic_y ) = { start_ROW start_CELL 1 end_CELL start_CELL if ( italic_x , italic_y ) ∈ italic_I , end_CELL end_ROW start_ROW start_CELL 0 end_CELL start_CELL otherwise. end_CELL end_ROW

By construction the graph of the equation F⁢(x,y)=1 𝐹 𝑥 𝑦 1 F(x,y)=1 italic_F ( italic_x , italic_y ) = 1 is I 𝐼 I italic_I, an image of the equation F⁢(x,y)=1 𝐹 𝑥 𝑦 1 F(x,y)=1 italic_F ( italic_x , italic_y ) = 1 on the plane. So F⁢(x,y)=1 𝐹 𝑥 𝑦 1 F(x,y)=1 italic_F ( italic_x , italic_y ) = 1 is trivially a self-graphing equation. Clearly, in order to make the problem nontrivial, it is necessary to specify which functions are allowed, and how they are written!

We will address the two problems of meaninglessness and triviality by formalizing the problem. Then, rather than focusing on any particular typography or any particular choice of what functions are allowed, we will instead give sufficient conditions thereon. Any typography, and any choice of functions, which satisfies these sufficient conditions, will be guaranteed to yield a self-graphing equation. To do this, we will invoke the so-called recursion theorem from computability theory (appropriately, the same theorem which was classically used to prove the existence of self-printing computer programs, also known as Quines).

2 Formalization

“What was a compelling proof in 1810 may well not be now; what is a fine closed form in 2010 may have been anathema a century ago” [2]

Definition 1.

If A≠∅𝐴 A\not=\emptyset italic_A ≠ ∅ is a finite alphabet, write A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT for the set of finite strings from A 𝐴 A italic_A. By a notion of equations we mean a finite alphabet A 𝐴 A italic_A together with a function Gr:A∗→𝒫⁢(ℝ 2):Gr→superscript 𝐴 𝒫 superscript ℝ 2\mathrm{Gr}:A^{}\to\mathscr{P}(\mathbb{R}^{2})roman_Gr : italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT → script_P ( blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) assigning to every string σ∈A∗𝜎 superscript 𝐴\sigma\in A^{*}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT a subset Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) of ℝ 2 superscript ℝ 2\mathbb{R}^{2}blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT called the graph of σ 𝜎\sigma italic_σ.

For example, if A 𝐴 A italic_A contains symbols x 𝑥 x italic_x, y 𝑦 y italic_y, +++, 2, === and 1 1 1 1, and if σ∈A∗𝜎 superscript 𝐴\sigma\in A^{*}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is the string “x 2+y 2=1 superscript 𝑥 2 superscript 𝑦 2 1 x^{2}+y^{2}=1 italic_x start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT + italic_y start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT = 1”, then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) might be (but we do not require it to be!) the unit circle centered at the origin. Or, if A 𝐴 A italic_A contains symbols r 𝑟 r italic_r, θ 𝜃\theta italic_θ, cos\cos roman_cos, === and 1 1 1 1, and if σ 𝜎\sigma italic_σ is the string “r=1+cos⁡θ 𝑟 1 𝜃 r=1+\cos\theta italic_r = 1 + roman_cos italic_θ”, then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) might be the graph of a cardioid. Or if σ 𝜎\sigma italic_σ is the string “+⁣=+=+ =” (or if σ 𝜎\sigma italic_σ is the blank string), then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) might be an error message, “Error: Invalid equation”, written on the plane (as, say, a union of points, line segments, and Bézier curve fragments).

Definition 2.

By a glyphed notion of equations we mean a triple (A,Gr,Gl)𝐴 Gr Gl(A,\mathrm{Gr},\mathrm{Gl})( italic_A , roman_Gr , roman_Gl ) where (A,Gr)𝐴 Gr(A,\mathrm{Gr})( italic_A , roman_Gr ) is a notion of equations and Gl:A→𝒫⁢(ℝ 2):Gl→𝐴 𝒫 superscript ℝ 2\mathrm{Gl}:A\to\mathscr{P}(\mathbb{R}^{2})roman_Gl : italic_A → script_P ( blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) is a function assigning to each x∈A 𝑥 𝐴 x\in A italic_x ∈ italic_A a set Gl⁢(x)⊆ℝ 2 Gl 𝑥 superscript ℝ 2\mathrm{Gl}(x)\subseteq\mathbb{R}^{2}roman_Gl ( italic_x ) ⊆ blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT called the glyph of x 𝑥 x italic_x.

If A 𝐴 A italic_A contains the symbol 0 0, then Gl⁢(0)Gl 0\mathrm{Gl}(0)roman_Gl ( 0 ) might be, for example, the circle of radius 1 2 1 2\frac{1}{2}divide start_ARG 1 end_ARG start_ARG 2 end_ARG centered at (1 2,1 2)1 2 1 2(\frac{1}{2},\frac{1}{2})( divide start_ARG 1 end_ARG start_ARG 2 end_ARG , divide start_ARG 1 end_ARG start_ARG 2 end_ARG ) (so as to nicely fit in the 1×1 1 1 1\times 1 1 × 1 unit square [0,1]2 superscript 0 1 2[0,1]^{2}[ 0 , 1 ] start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT, lending itself to a monospace font where each character is 1 1 1 1 unit wide). But it does not have to be. If A 𝐴 A italic_A contains the symbol X 𝑋 X italic_X, then Gl⁢(X)Gl 𝑋\mathrm{Gl}(X)roman_Gl ( italic_X ) might be, for example, the union of the line segment from (0,0)0 0(0,0)( 0 , 0 ) to (1,1)1 1(1,1)( 1 , 1 ) and the line segment from (0,1)0 1(0,1)( 0 , 1 ) to (1,0)1 0(1,0)( 1 , 0 ) (again nicely lending itself to a monospace font where each character is 1 1 1 1 unit wide). But it does not have to be.

Definition 3.

(Extending glyphs to strings)

1. 1.For all S⊆ℝ 2 𝑆 superscript ℝ 2 S\subseteq\mathbb{R}^{2}italic_S ⊆ blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT and all r∈ℝ 𝑟 ℝ r\in\mathbb{R}italic_r ∈ blackboard_R, let S→r={(x+r,y):(x,y)∈S}superscript 𝑆→absent 𝑟 conditional-set 𝑥 𝑟 𝑦 𝑥 𝑦 𝑆 S^{\rightarrow r}={(x+r,y),:,(x,y)\in S}italic_S start_POSTSUPERSCRIPT → italic_r end_POSTSUPERSCRIPT = { ( italic_x + italic_r , italic_y ) : ( italic_x , italic_y ) ∈ italic_S }, the result of translating S 𝑆 S italic_S to the right by r 𝑟 r italic_r units.

Whenever (A,Gr,Gl)𝐴 Gr Gl(A,\mathrm{Gr},\mathrm{Gl})( italic_A , roman_Gr , roman_Gl ) is a glyphed notion of equations, we will extend Gl Gl\mathrm{Gl}roman_Gl to a function on A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT, also written Gl Gl\mathrm{Gl}roman_Gl (this will cause no confusion), as follows. Let σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT.

*   •If σ 𝜎\sigma italic_σ is the empty string, let Gl⁢(σ)=∅Gl 𝜎\mathrm{Gl}(\sigma)=\emptyset roman_Gl ( italic_σ ) = ∅. 
*   •If σ 𝜎\sigma italic_σ is the string of length 1 1 1 1, whose first (and only) character is x∈A 𝑥 𝐴 x\in A italic_x ∈ italic_A, let Gl⁢(σ)=Gl⁢(x)Gl 𝜎 Gl 𝑥\mathrm{Gl}(\sigma)=\mathrm{Gl}(x)roman_Gl ( italic_σ ) = roman_Gl ( italic_x ). 
*   •Otherwise, σ 𝜎\sigma italic_σ is the string x 0⁢…⁢x k subscript 𝑥 0…subscript 𝑥 𝑘 x_{0}\ldots x_{k}italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT … italic_x start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT where each x i∈A subscript 𝑥 𝑖 𝐴 x_{i}\in A italic_x start_POSTSUBSCRIPT italic_i end_POSTSUBSCRIPT ∈ italic_A. Let

Gl⁢(σ)=Gl⁢(x 0)→0∪⋯∪Gl⁢(x k)→k.Gl 𝜎 Gl superscript subscript 𝑥 0→absent 0⋯Gl superscript subscript 𝑥 𝑘→absent 𝑘\mathrm{Gl}(\sigma)=\mathrm{Gl}(x_{0})^{\rightarrow 0}\cup\cdots\cup\mathrm{Gl% }(x_{k})^{\rightarrow k}.roman_Gl ( italic_σ ) = roman_Gl ( italic_x start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT ) start_POSTSUPERSCRIPT → 0 end_POSTSUPERSCRIPT ∪ ⋯ ∪ roman_Gl ( italic_x start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT ) start_POSTSUPERSCRIPT → italic_k end_POSTSUPERSCRIPT .

Thus, Gl⁢(σ)Gl 𝜎\mathrm{Gl}(\sigma)roman_Gl ( italic_σ ) is the result of writing σ 𝜎\sigma italic_σ on the plane, from left to right, translating the glyph of each i 𝑖 i italic_i th character to the right by i 𝑖 i italic_i units. The resulting union is particularly easy to visualize if we assume that for every x∈A 𝑥 𝐴 x\in A italic_x ∈ italic_A, Gl⁢(x)⊆[0,1]2 Gl 𝑥 superscript 0 1 2\mathrm{Gl}(x)\subseteq[0,1]^{2}roman_Gl ( italic_x ) ⊆ [ 0 , 1 ] start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT. In that case, the glyphs of A 𝐴 A italic_A comprise a monospace font where every character has width 1 1 1 1, and the glyph of a string in A∗superscript 𝐴 A^{*}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is the result of writing the glyphs of the individual characters from left to right in the usual way. This assumption will make the results in this paper more intuitive, but, interestingly, the whole paper will work just fine without this assumption.

Definition 4.

(Self-graphing equations) Let 𝒜=(A,Gr,Gl)𝒜 𝐴 Gr Gl\mathcal{A}=(A,\mathrm{Gr},\mathrm{Gl})caligraphic_A = ( italic_A , roman_Gr , roman_Gl ) be a glyphed notion of equations. By a self-graphing equation in 𝒜 𝒜\mathcal{A}caligraphic_A we mean a string σ∈A∗𝜎 superscript 𝐴\sigma\in A^{*}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT such that Gr⁢(σ)=Gl⁢(σ)Gr 𝜎 Gl 𝜎\mathrm{Gr}(\sigma)=\mathrm{Gl}(\sigma)roman_Gr ( italic_σ ) = roman_Gl ( italic_σ ).

3 Computability theory preliminaries

Definition 5.

1. 1.For any sets X 𝑋 X italic_X and Y 𝑌 Y italic_Y, we write f:⊆X→Y f:{\subseteq}X\to Y italic_f : ⊆ italic_X → italic_Y to indicate that f 𝑓 f italic_f is a function whose codomain is Y 𝑌 Y italic_Y and whose domain is some subset of X 𝑋 X italic_X.
2. 2.For all n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, let φ n:⊆ℕ→ℕ\varphi_{n}:{\subseteq}\mathbb{N}\to\mathbb{N}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT : ⊆ blackboard_N → blackboard_N be the n 𝑛 n italic_n th computable function (assuming some fixed enumeration, possibly with repetition, of the computable functions).
3. 3.A function f:⊆ℕ→ℕ f:{\subseteq}\mathbb{N}\to\mathbb{N}italic_f : ⊆ blackboard_N → blackboard_N is total computable if dom⁢(f)dom 𝑓\mathrm{dom}(f)roman_dom ( italic_f ) (the domain of f 𝑓 f italic_f) is all of ℕ ℕ\mathbb{N}blackboard_N.

We state the following celebrated result from computability theory without proof.

Theorem 6.

(The Recursion Theorem) For every total computable f:ℕ→ℕ:𝑓→ℕ ℕ f:\mathbb{N}\to\mathbb{N}italic_f : blackboard_N → blackboard_N, there is some n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N such that φ n=φ f⁢(n)subscript 𝜑 𝑛 subscript 𝜑 𝑓 𝑛\varphi_{n}=\varphi_{f(n)}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT = italic_φ start_POSTSUBSCRIPT italic_f ( italic_n ) end_POSTSUBSCRIPT.

4 Self-constraint: a sufficient condition for the existence of self-graphing equations

In this section we fix a glyphed notion of equations 𝒜=(A,Gr,Gl)𝒜 𝐴 Gr Gl\mathcal{A}=(A,\mathrm{Gr},\mathrm{Gl})caligraphic_A = ( italic_A , roman_Gr , roman_Gl ) (where A 𝐴 A italic_A is a finite nonempty alphabet).

Definition 7.

By a Gödel numbering of A∗superscript 𝐴 A^{*}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT we mean a bijection 2 2 2 One could change this definition to require only that ⌜∙⌝∙⌜⌝\ulcorner\bullet\urcorner⌜ ∙ ⌝ be an injection instead of a bijection, which would be more typical of Gödel numberings. We chose to require the Gödel numbering function to be bijective in order to avoid technical complications.⌜∙⌝:A∗→ℕ:∙⌜⌝→superscript 𝐴 ℕ\ulcorner\bullet\urcorner:A^{}\to\mathbb{N}⌜ ∙ ⌝ : italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT → blackboard_N such that there is some algorithm for computing ⌜⁢σ⁢⌝⌜𝜎⌝\ulcorner\sigma\urcorner⌜ italic_σ ⌝ (for σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT) as a function of σ 𝜎\sigma italic_σ. We refer to ⌜⁢σ⁢⌝⌜𝜎⌝\ulcorner\sigma\urcorner⌜ italic_σ ⌝ as the Gödel number of σ 𝜎\sigma italic_σ (we think of ⌜⁢σ⁢⌝⌜𝜎⌝\ulcorner\sigma\urcorner⌜ italic_σ ⌝ as a numerical encoding of σ 𝜎\sigma italic_σ).

Definition 8.

The glyphed notion of equations 𝒜 𝒜\mathcal{A}caligraphic_A is self-constrained if there exists a Gödel numbering ⌜∙⌝∙⌜⌝\ulcorner\bullet\urcorner⌜ ∙ ⌝ of A∗superscript 𝐴 A^{*}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT and a total computable f:ℕ→ℕ:𝑓→ℕ ℕ f:\mathbb{N}\to\mathbb{N}italic_f : blackboard_N → blackboard_N such that:

• •For all n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, if φ n⁢(0)=⌜⁢τ⁢⌝subscript 𝜑 𝑛 0⌜𝜏⌝\varphi_{n}(0)=\ulcorner\tau\urcorner italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) = ⌜ italic_τ ⌝ for some τ∈A∗𝜏 superscript 𝐴\tau\in A^{}italic_τ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT, then f⁢(n)=⌜⁢σ⁢⌝𝑓 𝑛⌜𝜎⌝f(n)=\ulcorner\sigma\urcorner italic_f ( italic_n ) = ⌜ italic_σ ⌝ for some σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT such that Gr⁢(σ)=Gl⁢(τ)Gr 𝜎 Gl 𝜏\mathrm{Gr}(\sigma)=\mathrm{Gl}(\tau)roman_Gr ( italic_σ ) = roman_Gl ( italic_τ ).

If f 𝑓 f italic_f is as in Definition 8, then f 𝑓 f italic_f should intuitively be thought of as being computed by an algorithm which takes an input n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N and outputs an equation whose graph is the output of φ n⁢(0)subscript 𝜑 𝑛 0\varphi_{n}(0)italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) (if any), written on the plane. The strings in question are encoded by Gödel numbers to standardize the functions in question and allow the usage of standard computability theory, but intuitively one should think of f 𝑓 f italic_f and φ n subscript 𝜑 𝑛\varphi_{n}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT as outputting strings from A∗superscript 𝐴 A^{*}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT. If 0∉dom⁢(φ n)0 dom subscript 𝜑 𝑛 0\not\in\mathrm{dom}(\varphi_{n})0 ∉ roman_dom ( italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ) then it does not matter what f⁢(n)𝑓 𝑛 f(n)italic_f ( italic_n ) is, only that f⁢(n)𝑓 𝑛 f(n)italic_f ( italic_n ) be defined.

We can illustrate Remark 9 with the following analogy. Say that k∈ℕ 𝑘 ℕ k\in\mathbb{N}italic_k ∈ blackboard_N is an FLT-counterexample (here FLT stands for “Fermat’s Last Theorem”) if k>2 𝑘 2 k>2 italic_k > 2 and there exist positive integers a,b,c 𝑎 𝑏 𝑐 a,b,c italic_a , italic_b , italic_c such that a k+b k=c k superscript 𝑎 𝑘 superscript 𝑏 𝑘 superscript 𝑐 𝑘 a^{k}+b^{k}=c^{k}italic_a start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT + italic_b start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT = italic_c start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT. For every x∈ℝ 𝑥 ℝ x\in\mathbb{R}italic_x ∈ blackboard_R, let ψ⁢(x)𝜓 𝑥\psi(x)italic_ψ ( italic_x ) be the number of FLT-counterexamples ≤x absent 𝑥\leq x≤ italic_x. A teacher does not need to know Fermat’s Last Theorem in order to assign a student the task of graphing the equation y=ψ⁢(x)𝑦 𝜓 𝑥 y=\psi(x)italic_y = italic_ψ ( italic_x ). Without knowing Fermat’s Last Theorem is true, a teacher can even, with some tedious mechanical effort, rewrite y=ψ⁢(x)𝑦 𝜓 𝑥 y=\psi(x)italic_y = italic_ψ ( italic_x ) in “closed form” (at least if the closed form is allowed to include infinite sums—see [1]). Knowledge of Fermat’s Last Theorem is required in order to graph the equation, not to state it.

We will now show that self-contraint is a sufficient condition for existence of a self-graphing equation. At first glance, self-constraint might seem like such a strong requirement as to leave one in doubt whether any reasonable notions of equations actually satisfy it. We will give an example in Section 5 of a notion of equations which is self-constrained and therefore has a self-graphing equation, and the example should help the reader to better understand how self-constraint can be satisfied. Basically, the key is that infinite products or infinite sums can be used to encode quantifiers ∃\exists∃ and ∀for-all\forall∀.

Theorem 10.

If 𝒜 𝒜\mathcal{A}caligraphic_A is self-constrained then there exists a self-graphing equation in 𝒜 𝒜\mathcal{A}caligraphic_A.

Proof.

Let ⌜∙⌝∙⌜⌝\ulcorner\bullet\urcorner⌜ ∙ ⌝ and f:ℕ→ℕ:𝑓→ℕ ℕ f:\mathbb{N}\to\mathbb{N}italic_f : blackboard_N → blackboard_N be as in Definition 8.

Subclaim: There is a total computable function g:ℕ→ℕ:𝑔→ℕ ℕ g:\mathbb{N}\to\mathbb{N}italic_g : blackboard_N → blackboard_N such that for all n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, φ g⁢(n)⁢(0)=f⁢(n)subscript 𝜑 𝑔 𝑛 0 𝑓 𝑛\varphi_{g(n)}(0)=f(n)italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT ( 0 ) = italic_f ( italic_n ).

This Subclaim is actually a special case of a theorem from computability theory called the “S⁢m⁢n 𝑆 𝑚 𝑛 Smn italic_S italic_m italic_n theorem”, but we will sketch a direct proof here. Let g:ℕ→ℕ:𝑔→ℕ ℕ g:\mathbb{N}\to\mathbb{N}italic_g : blackboard_N → blackboard_N be the function computed by the following algorithm:

1. 1.Take input n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N.
2. 2.Let X=f⁢(n)𝑋 𝑓 𝑛 X=f(n)italic_X = italic_f ( italic_n ).

Let P 𝑃 P italic_P be the following algorithm:

1.   (a)Take input m∈ℕ 𝑚 ℕ m\in\mathbb{N}italic_m ∈ blackboard_N. 
2.   (b)Output X 𝑋 X italic_X (ignoring the value of m 𝑚 m italic_m). 

4. 4.Output an encoding of P 𝑃 P italic_P (a number k 𝑘 k italic_k such that φ k subscript 𝜑 𝑘\varphi_{k}italic_φ start_POSTSUBSCRIPT italic_k end_POSTSUBSCRIPT is the function computed by P 𝑃 P italic_P).

For any n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, by construction φ g⁢(n)subscript 𝜑 𝑔 𝑛\varphi_{g(n)}italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT is the function computed by the above algorithm P 𝑃 P italic_P (for the given n 𝑛 n italic_n). Thus φ g⁢(n)⁢(0)subscript 𝜑 𝑔 𝑛 0\varphi_{g(n)}(0)italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT ( 0 ) is computed by ignoring the input m=0 𝑚 0 m=0 italic_m = 0 and outputting X=f⁢(n)𝑋 𝑓 𝑛 X=f(n)italic_X = italic_f ( italic_n ). Thus φ g⁢(n)⁢(0)=f⁢(n)subscript 𝜑 𝑔 𝑛 0 𝑓 𝑛\varphi_{g(n)}(0)=f(n)italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT ( 0 ) = italic_f ( italic_n ). Since we have provided an algorithm for g 𝑔 g italic_g, g 𝑔 g italic_g is computable. Clearly dom⁢(g)=ℕ dom 𝑔 ℕ\mathrm{dom}(g)=\mathbb{N}roman_dom ( italic_g ) = blackboard_N, so g 𝑔 g italic_g is total computable. This proves the Subclaim.

Let g 𝑔 g italic_g be as in the Subclaim. By the Recursion Theorem (Theorem 6) there is some n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N such that φ n=φ g⁢(n)subscript 𝜑 𝑛 subscript 𝜑 𝑔 𝑛\varphi_{n}=\varphi_{g(n)}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT = italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT. In particular,

φ n⁢(0)=φ g⁢(n)⁢(0)=f⁢(n)⁢is defined. (∗)subscript 𝜑 𝑛 0 subscript 𝜑 𝑔 𝑛 0 𝑓 𝑛 is defined. (∗)\varphi_{n}(0)=\varphi_{g(n)}(0)=f(n)\mbox{ is defined. ($*$)}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) = italic_φ start_POSTSUBSCRIPT italic_g ( italic_n ) end_POSTSUBSCRIPT ( 0 ) = italic_f ( italic_n ) is defined. ( ∗ )

Let σ,τ∈A∗𝜎 𝜏 superscript 𝐴\sigma,\tau\in A^{*}italic_σ , italic_τ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT be such that f⁢(n)=⌜⁢σ⁢⌝𝑓 𝑛⌜𝜎⌝f(n)=\ulcorner\sigma\urcorner italic_f ( italic_n ) = ⌜ italic_σ ⌝ and φ n⁢(0)=⌜⁢τ⁢⌝subscript 𝜑 𝑛 0⌜𝜏⌝\varphi_{n}(0)=\ulcorner\tau\urcorner italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) = ⌜ italic_τ ⌝. We claim σ 𝜎\sigma italic_σ is a self-graphing equation in 𝒜 𝒜\mathcal{A}caligraphic_A. To see this, compute:

Gr⁢(σ)Gr 𝜎\displaystyle\mathrm{Gr}(\sigma)roman_Gr ( italic_σ )=Gl⁢(τ)absent Gl 𝜏\displaystyle=\mathrm{Gl}(\tau)= roman_Gl ( italic_τ )(Definition 8) =Gl⁢(σ),absent Gl 𝜎\displaystyle=\mathrm{Gl}(\sigma),= roman_Gl ( italic_σ ) ,(By ∗*∗, σ=τ 𝜎 𝜏\sigma=\tau italic_σ = italic_τ)

as desired. ∎

5 A Concrete Context for a Self-Graphing Equation

To conclude, we will give an example of a particular glyphed notion of equations 𝒜=(A,Gr,Gl)𝒜 𝐴 Gr Gl\mathcal{A}=(A,\mathrm{Gr},\mathrm{Gl})caligraphic_A = ( italic_A , roman_Gr , roman_Gl ) not too unlike how we write and graph equations in practice. We will argue that this particular 𝒜 𝒜\mathcal{A}caligraphic_A is self-constrained. Thus, Theorem 10 guarantees the existence of a self-graphing equation in 𝒜 𝒜\mathcal{A}caligraphic_A.

For an alphabet, let

A=𝐴 absent\displaystyle A={}italic_A ={a,b,c,…,z}𝑎 𝑏 𝑐…𝑧\displaystyle{a,b,c,\ldots,z}{ italic_a , italic_b , italic_c , … , italic_z }(Letters) ∪{0,1,2,…,9}0 1 2…9\displaystyle{}\cup{0,1,2,\ldots,9}∪ { 0 , 1 , 2 , … , 9 }(Digits) ∪{(}∪{)}\displaystyle{}\cup{(}\cup{)}∪ { ( } ∪ { ) }(Left and right parentheses) ∪{+,⋅,−,/,,∧=}\displaystyle{}\cup{+,\cdot,-,/,{}^{\wedge},=}∪ { + , ⋅ , - , / , start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT , = }(Plus, times, minus, division, exponentiation, equality) ∪{Π,_,∞}Π _\displaystyle{}\cup{\Pi,_,\infty}∪ { roman_Π , _ , ∞ }(Infinite product machinery)

(for concreteness, A 𝐴 A italic_A can be taken to be a subset of ℕ ℕ\mathbb{N}blackboard_N of cardinality 26+10+2+6+3=47 26 10 2 6 3 47 26+10+2+6+3=47 26 + 10 + 2 + 6 + 3 = 47). The reader should think of ∧ as an exponentiation operator, as in the equation 2 3∧=8 2{}^{\wedge}3=8 2 start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT 3 = 8 (read: “2 2 2 2 to the power 3 3 3 3 equals 8 8 8 8”). The character Π Π\Pi roman_Π should be thought of as an infinite product symbol, to be used (in combination with ∧, _ __ _, ===, ∞\infty∞, and parentheses) as in the equation: Π⁢_⁢(n=0)⁢∞∧⁢(1∧⁢n)=1 Π _ 𝑛 0 superscript superscript 1 𝑛 1\Pi_(n=0){}^{\wedge}\infty(1^{\wedge}n)=1 roman_Π _ ( italic_n = 0 ) start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT ∞ ( 1 start_POSTSUPERSCRIPT ∧ end_POSTSUPERSCRIPT italic_n ) = 1 (read: “The product, as n 𝑛 n italic_n goes from 0 0 to ∞\infty∞, of 1 n superscript 1 𝑛 1^{n}1 start_POSTSUPERSCRIPT italic_n end_POSTSUPERSCRIPT, equals 1 1 1 1”).

Choose glyphs Gl:A→𝒫⁢(ℝ 2):Gl→𝐴 𝒫 superscript ℝ 2\mathrm{Gl}:A\to\mathcal{P}(\mathbb{R}^{2})roman_Gl : italic_A → caligraphic_P ( blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) for writing A 𝐴 A italic_A such that each such glyph is written inside the square [0,1]×[0,1]0 1 0 1[0,1]\times[0,1][ 0 , 1 ] × [ 0 , 1 ] using pixels of dimension 1 100×1 100 1 100 1 100\frac{1}{100}\times\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG × divide start_ARG 1 end_ARG start_ARG 100 end_ARG, each such pixel being a translation, by an integer multiple of 1 100 1 100\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG horizontally and an integer multiple of 1 100 1 100\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG vertically, of the square [0,1 100]×[0,1 100]0 1 100 0 1 100[0,\frac{1}{100}]\times[0,\frac{1}{100}][ 0 , divide start_ARG 1 end_ARG start_ARG 100 end_ARG ] × [ 0 , divide start_ARG 1 end_ARG start_ARG 100 end_ARG ]. For example, Gl⁢(+)Gl\mathrm{Gl}(+)roman_Gl ( + ), the glyph of the +++ sign, might be ([50 100,51 100]×[0,1])∪([0,1]×[50 100,51 100])50 100 51 100 0 1 0 1 50 100 51 100([\frac{50}{100},\frac{51}{100}]\times[0,1])\cup([0,1]\times[\frac{50}{100},% \frac{51}{100}])( [ divide start_ARG 50 end_ARG start_ARG 100 end_ARG , divide start_ARG 51 end_ARG start_ARG 100 end_ARG ] × [ 0 , 1 ] ) ∪ ( [ 0 , 1 ] × [ divide start_ARG 50 end_ARG start_ARG 100 end_ARG , divide start_ARG 51 end_ARG start_ARG 100 end_ARG ] ) (the first argument to ∪\cup∪ being a rectangle of height 1 1 1 1 and width 1/100 1 100 1/100 1 / 100 and the second argument to ∪\cup∪ being a rectangle of height 1/100 1 100 1/100 1 / 100 and width 1 1 1 1), which can clearly be formed by such pixels.

Define Gr:A∗→𝒫⁢(ℝ 2):Gr→superscript 𝐴 𝒫 superscript ℝ 2\mathrm{Gr}:A^{}\to\mathscr{P}(\mathbb{R}^{2})roman_Gr : italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT → script_P ( blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) so that for every σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT, if σ 𝜎\sigma italic_σ is a valid equation, then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) is the graph of σ 𝜎\sigma italic_σ. If σ 𝜎\sigma italic_σ is not a valid equation, then let Gr Gr\mathrm{Gr}roman_Gr be some arbitrary nonempty subset of ℝ 2 superscript ℝ 2\mathbb{R}^{2}blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT, for example, an error message written on the plane (we only require it to be nonempty so as not to inadvertently make the empty string a trivial self-graphing equation). For example, if σ 𝜎\sigma italic_σ is the string “x 2∧+y 2∧=1 x{}^{\wedge}2+y{}^{\wedge}2=1 italic_x start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT 2 + italic_y start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT 2 = 1”, then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) is the unit circle; if σ 𝜎\sigma italic_σ is the string “x 2∧=−1 x{}^{\wedge}2=-1 italic_x start_FLOATSUPERSCRIPT ∧ end_FLOATSUPERSCRIPT 2 = - 1” then Gr⁢(σ)Gr 𝜎\mathrm{Gr}(\sigma)roman_Gr ( italic_σ ) is the empty set.

In this way, we obtain a glyphed notion of equations 𝒜=(A,Gr,Gl)𝒜 𝐴 Gr Gl\mathcal{A}=(A,\mathrm{Gr},\mathrm{Gl})caligraphic_A = ( italic_A , roman_Gr , roman_Gl ). We will argue that 𝒜 𝒜\mathcal{A}caligraphic_A is self-constrained and thus (by Theorem 10) admits a self-graphing equation. In other words, we will argue (Definition 8) that there is a Gödel numbering ⌜∙⌝∙⌜⌝\ulcorner\bullet\urcorner⌜ ∙ ⌝ of A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT and a total computable f:ℕ→ℕ:𝑓→ℕ ℕ f:\mathbb{N}\to\mathbb{N}italic_f : blackboard_N → blackboard_N such that for all n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, if φ n⁢(0)=⌜⁢τ⁢⌝subscript 𝜑 𝑛 0⌜𝜏⌝\varphi_{n}(0)=\ulcorner\tau\urcorner italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) = ⌜ italic_τ ⌝ then f⁢(n)=⌜⁢σ⁢⌝𝑓 𝑛⌜𝜎⌝f(n)=\ulcorner\sigma\urcorner italic_f ( italic_n ) = ⌜ italic_σ ⌝ for some σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT such that Gr⁢(σ)=Gl⁢(τ)Gr 𝜎 Gl 𝜏\mathrm{Gr}(\sigma)=\mathrm{Gl}(\tau)roman_Gr ( italic_σ ) = roman_Gl ( italic_τ ).

Let ⌜∙⌝:A∗→ℕ:∙⌜⌝→superscript 𝐴 ℕ\ulcorner\bullet\urcorner:A^{}\to\mathbb{N}⌜ ∙ ⌝ : italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT → blackboard_N assign numbers bijectively to strings from A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT in some way that could be written out as an algorithm. There are many ways to do this and it does not matter which way it is done. As one example, we could linearly order A 𝐴 A italic_A and then enumerate A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT by listing all the length-0 0 strings in A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT (in alphabetical order), followed by all the length-1 1 1 1 strings in A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT (in alphabetical order), followed by all the length-2 2 2 2 strings in A∗superscript 𝐴 A^{}italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT (in alphabetical order) and so on, and let each ⌜⁢σ⁢⌝⌜𝜎⌝\ulcorner\sigma\urcorner⌜ italic_σ ⌝ be the position in which σ 𝜎\sigma italic_σ occurs in the resulting list.

We want f⁢(n)𝑓 𝑛 f(n)italic_f ( italic_n ) to output ⌜⁢σ⁢⌝⌜𝜎⌝\ulcorner\sigma\urcorner⌜ italic_σ ⌝ for some σ∈A∗𝜎 superscript 𝐴\sigma\in A^{}italic_σ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT such that the graph of σ 𝜎\sigma italic_σ is Gl⁢(τ)Gl 𝜏\mathrm{Gl}(\tau)roman_Gl ( italic_τ ), where τ∈A∗𝜏 superscript 𝐴\tau\in A^{}italic_τ ∈ italic_A start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is the string whose code is output by φ n⁢(0)subscript 𝜑 𝑛 0\varphi_{n}(0)italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) (if 0∈dom⁢(φ n)0 dom subscript 𝜑 𝑛 0\in\mathrm{dom}(\varphi_{n})0 ∈ roman_dom ( italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT )). For such τ 𝜏\tau italic_τ, what does it mean for a pair (x,y)∈ℝ 2 𝑥 𝑦 superscript ℝ 2(x,y)\in\mathbb{R}^{2}( italic_x , italic_y ) ∈ blackboard_R start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT to be in Gl⁢(τ)Gl 𝜏\mathrm{Gl}(\tau)roman_Gl ( italic_τ )? It means that…

∃a,b,c,d,e∈ℕ⁢s.t.⁢P⁢(n,a,b,c,d,e)𝑎 𝑏 𝑐 𝑑 𝑒 ℕ s.t.𝑃 𝑛 𝑎 𝑏 𝑐 𝑑 𝑒\exists a,b,c,d,e\in\mathbb{N}\mbox{ s.t.\ }P(n,a,b,c,d,e)∃ italic_a , italic_b , italic_c , italic_d , italic_e ∈ blackboard_N s.t. italic_P ( italic_n , italic_a , italic_b , italic_c , italic_d , italic_e )(*)

…where P⁢(n,a,b,c,d,e)𝑃 𝑛 𝑎 𝑏 𝑐 𝑑 𝑒 P(n,a,b,c,d,e)italic_P ( italic_n , italic_a , italic_b , italic_c , italic_d , italic_e ) is the statement:

The n 𝑛 n italic_n th Turing machine (i.e., the Turing machine which computes φ n subscript 𝜑 𝑛\varphi_{n}italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT), when run with input 0 0, halts after exactly a 𝑎 a italic_a steps, with output b 𝑏 b italic_b, and when b 𝑏 b italic_b is interpreted as a string τ 𝜏\tau italic_τ (using ⌜∙⌝∙⌜⌝\ulcorner\bullet\urcorner⌜ ∙ ⌝), τ 𝜏\tau italic_τ has length at least c+1 𝑐 1 c+1 italic_c + 1—let the c 𝑐 c italic_c th symbol of τ 𝜏\tau italic_τ (counting from 0 0) be called τ c subscript 𝜏 𝑐\tau_{c}italic_τ start_POSTSUBSCRIPT italic_c end_POSTSUBSCRIPT—and the 1 100×1 100 1 100 1 100\frac{1}{100}\times\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG × divide start_ARG 1 end_ARG start_ARG 100 end_ARG pixel with bottom-left coordinates (d/100,e/100)𝑑 100 𝑒 100(d/100,e/100)( italic_d / 100 , italic_e / 100 ) is an element of Gl⁢(τ c)Gl subscript 𝜏 𝑐\mathrm{Gl}(\tau_{c})roman_Gl ( italic_τ start_POSTSUBSCRIPT italic_c end_POSTSUBSCRIPT ), and (x−c,y)𝑥 𝑐 𝑦(x-c,y)( italic_x - italic_c , italic_y ) (the result of translating (x,y)𝑥 𝑦(x,y)( italic_x , italic_y ) to the left by c 𝑐 c italic_c units) is in said pixel (so that (x,y)𝑥 𝑦(x,y)( italic_x , italic_y ) is in the translation of said pixel by c 𝑐 c italic_c units to the right, which is said pixel’s representation in Gl⁢(τ)Gl 𝜏\mathrm{Gl}(\tau)roman_Gl ( italic_τ ) by Definition 3).

Let’s examine the subclauses of (∗*∗).

• •The subclause “The n 𝑛 n italic_n th Turing machine, when run on input 0 0, halts after exactly a 𝑎 a italic_a steps, with output b 𝑏 b italic_b”, can be expanded out into a complicated statement in the language of arithmetic (“There exists k 𝑘 k italic_k such that k 𝑘 k italic_k encodes a sequence C 0,C 1,…,C a subscript 𝐶 0 subscript 𝐶 1…subscript 𝐶 𝑎 C_{0},C_{1},\ldots,C_{a}italic_C start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT , italic_C start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_C start_POSTSUBSCRIPT italic_a end_POSTSUBSCRIPT of Turing machine snapshots such that…”).
• •The subclause “the 1 100×1 100 1 100 1 100\frac{1}{100}\times\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG × divide start_ARG 1 end_ARG start_ARG 100 end_ARG pixel with bottom-left coordinates (d/100,e/100)𝑑 100 𝑒 100(d/100,e/100)( italic_d / 100 , italic_e / 100 ) is an element of Gl⁢(τ c)Gl subscript 𝜏 𝑐\mathrm{Gl}(\tau_{c})roman_Gl ( italic_τ start_POSTSUBSCRIPT italic_c end_POSTSUBSCRIPT )”, can be written as a finite disjunction of quantifier-free statements about individual pixels, namely, at most 100⋅100⋅|A|⋅100 100 𝐴 100\cdot 100\cdot|A|100 ⋅ 100 ⋅ | italic_A | such disjuncts: one per 1 100×1 100 1 100 1 100\frac{1}{100}\times\frac{1}{100}divide start_ARG 1 end_ARG start_ARG 100 end_ARG × divide start_ARG 1 end_ARG start_ARG 100 end_ARG pixel in [0,1]2 superscript 0 1 2[0,1]^{2}[ 0 , 1 ] start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT per symbol in A 𝐴 A italic_A. For example, if the glyph of symbol “+++” includes pixel [50/100,51/100]×[0,1/100]50 100 51 100 0 1 100[50/100,51/100]\times[0,1/100][ 50 / 100 , 51 / 100 ] × [ 0 , 1 / 100 ], then this pixel-symbol pair contributes the quantifier-free disjunct: (τ c=“x”)∧(d=50)∧(e=0)subscript 𝜏 𝑐“x”𝑑 50 𝑒 0(\tau_{c}=\mbox{``x''})\wedge(d=50)\wedge(e=0)( italic_τ start_POSTSUBSCRIPT italic_c end_POSTSUBSCRIPT = “x” ) ∧ ( italic_d = 50 ) ∧ ( italic_e = 0 ).
• •The subclause “(x−c,y)𝑥 𝑐 𝑦(x-c,y)( italic_x - italic_c , italic_y ) is in said pixel” can be rephrased as “d/100≤x−c≤(d+1)/100 𝑑 100 𝑥 𝑐 𝑑 1 100 d/100\leq x-c\leq(d+1)/100 italic_d / 100 ≤ italic_x - italic_c ≤ ( italic_d + 1 ) / 100 and e/100≤y≤(e+1)/100 𝑒 100 𝑦 𝑒 1 100 e/100\leq y\leq(e+1)/100 italic_e / 100 ≤ italic_y ≤ ( italic_e + 1 ) / 100”.

We claim that all subclauses of (∗*∗) can be written as equations of the form E=0 𝐸 0 E=0 italic_E = 0 using only symbols from A 𝐴 A italic_A; to see this, we reason inductively:

• •Atomic subclauses like “d=50 𝑑 50 d=50 italic_d = 50” can be written as d−50=0 𝑑 50 0 d-50=0 italic_d - 50 = 0.
• •Atomic subclauses like “e/100≤y 𝑒 100 𝑦 e/100\leq y italic_e / 100 ≤ italic_y” can be rewritten as “y−e/100−|y−e/100|=0 𝑦 𝑒 100 𝑦 𝑒 100 0 y-e/100-|y-e/100|=0 italic_y - italic_e / 100 - | italic_y - italic_e / 100 | = 0”, and the absolute values can be replaced with symbols from A 𝐴 A italic_A by using the fact that |x|=(x 2)1/2 𝑥 superscript superscript 𝑥 2 1 2|x|=(x^{2})^{1/2}| italic_x | = ( italic_x start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT ) start_POSTSUPERSCRIPT 1 / 2 end_POSTSUPERSCRIPT.
• •(Disjunction) If two subclauses can be written in the form E 1=0 subscript 𝐸 1 0 E_{1}=0 italic_E start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 0 and E 2=0 subscript 𝐸 2 0 E_{2}=0 italic_E start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 0 using only symbols from A 𝐴 A italic_A, then so can their disjunction, because “E 1=0 subscript 𝐸 1 0 E_{1}=0 italic_E start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 0 or E 2=0 subscript 𝐸 2 0 E_{2}=0 italic_E start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 0” is equivalent to “(E 1)⋅(E 2)=0⋅subscript 𝐸 1 subscript 𝐸 2 0(E_{1})\cdot(E_{2})=0( italic_E start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT ) ⋅ ( italic_E start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) = 0”.
• •(Negation) If a subclause can be written in the form E=0 𝐸 0 E=0 italic_E = 0 using only symbols from A 𝐴 A italic_A, then so can its negation, because “not⁢(E=0)not 𝐸 0\mbox{not}(E=0)not ( italic_E = 0 )” is equivalent to 0 E 2=0 superscript 0 superscript 𝐸 2 0 0^{E^{2}}=0 0 start_POSTSUPERSCRIPT italic_E start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT = 0 (since 0 0=1 superscript 0 0 1 0^{0}=1 0 start_POSTSUPERSCRIPT 0 end_POSTSUPERSCRIPT = 1[3] but 0 x=0 superscript 0 𝑥 0 0^{x}=0 0 start_POSTSUPERSCRIPT italic_x end_POSTSUPERSCRIPT = 0 for all positive x 𝑥 x italic_x).
• •(Existential Quantifiers) If a subclause E=0 𝐸 0 E=0 italic_E = 0 can be written using only symbols from A 𝐴 A italic_A (where E 𝐸 E italic_E may involve a variable v 𝑣 v italic_v), then so can the clause ∃v⁢(E=0)𝑣 𝐸 0\exists v(E=0)∃ italic_v ( italic_E = 0 ) for any variable v 𝑣 v italic_v, because ∃v⁢(E=0)𝑣 𝐸 0\exists v(E=0)∃ italic_v ( italic_E = 0 ) is equivalent to Π v=0∞⁢(1−0 E 2)=0 superscript subscript Π 𝑣 0 1 superscript 0 superscript 𝐸 2 0\Pi_{v=0}^{\infty}(1-0^{E^{2}})=0 roman_Π start_POSTSUBSCRIPT italic_v = 0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∞ end_POSTSUPERSCRIPT ( 1 - 0 start_POSTSUPERSCRIPT italic_E start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT ) = 0.
• •(Conjunction, Universal Quantifiers) Closure under conjunction and universal quantification follow because “E 1=0 subscript 𝐸 1 0 E_{1}=0 italic_E start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 0 and E 2=0 subscript 𝐸 2 0 E_{2}=0 italic_E start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 0” is equivalent to “not⁢(not⁢(E 1=0)⁢or not⁢(E 2=0))not not subscript 𝐸 1 0 or not subscript 𝐸 2 0\mbox{not}(\mbox{not}(E_{1}=0)\mbox{ or }\mbox{not}(E_{2}=0))not ( not ( italic_E start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT = 0 ) or roman_not ( italic_E start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT = 0 ) )” and “∀v⁢(E=0)for-all 𝑣 𝐸 0\forall v(E=0)∀ italic_v ( italic_E = 0 )” is equivalent to “not⁢(∃v⁢not⁢(E=0))not 𝑣 not 𝐸 0\mbox{not}(\exists v\mbox{ not}(E=0))not ( ∃ italic_v not ( italic_E = 0 ) )”.

Thus, (∗*∗) itself can be written as an equation E=0 𝐸 0 E=0 italic_E = 0 using only symbols from A 𝐴 A italic_A. Fix such an E 𝐸 E italic_E. For every n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, let n¯¯𝑛\overline{n}over¯ start_ARG italic_n end_ARG be the string of n 𝑛 n italic_n’s decimal digits (for example if n=311 𝑛 311 n=311 italic_n = 311 then n¯¯𝑛\overline{n}over¯ start_ARG italic_n end_ARG is the length-3 3 3 3 string “311”). For every n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, let E⁢(n¯)=0 𝐸¯𝑛 0 E(\overline{n})=0 italic_E ( over¯ start_ARG italic_n end_ARG ) = 0 be the equation obtained by replacing all unquantified occurrences of n 𝑛 n italic_n in E=0 𝐸 0 E=0 italic_E = 0 by n¯¯𝑛\overline{n}over¯ start_ARG italic_n end_ARG. Define f:ℕ→ℕ:𝑓→ℕ ℕ f:\mathbb{N}\to\mathbb{N}italic_f : blackboard_N → blackboard_N so that for all n∈ℕ 𝑛 ℕ n\in\mathbb{N}italic_n ∈ blackboard_N, f⁢(n)=⌜⁢E⁢(n¯)=0⁢⌝𝑓 𝑛⌜𝐸¯𝑛 0⌝f(n)=\ulcorner E(\overline{n})=0\urcorner italic_f ( italic_n ) = ⌜ italic_E ( over¯ start_ARG italic_n end_ARG ) = 0 ⌝.

By construction, f⁢(n)𝑓 𝑛 f(n)italic_f ( italic_n ) outputs (the code of) the equation E⁢(n¯)=0 𝐸¯𝑛 0 E(\overline{n})=0 italic_E ( over¯ start_ARG italic_n end_ARG ) = 0 whose graph is the set of all points (x,y)𝑥 𝑦(x,y)( italic_x , italic_y ) satisfying (∗*∗), i.e., the set of all points in Gl⁢(τ)Gl 𝜏\mathrm{Gl}(\tau)roman_Gl ( italic_τ ) where ⌜⁢τ⁢⌝=φ n⁢(0)⌜𝜏⌝subscript 𝜑 𝑛 0\ulcorner\tau\urcorner=\varphi_{n}(0)⌜ italic_τ ⌝ = italic_φ start_POSTSUBSCRIPT italic_n end_POSTSUBSCRIPT ( 0 ) if such a τ 𝜏\tau italic_τ exists.

Thus, f 𝑓 f italic_f witnesses that 𝒜 𝒜\mathcal{A}caligraphic_A is self-constrained. By Theorem 10, there is a self-graphing equation in 𝒜 𝒜\mathcal{A}caligraphic_A.

In some sense, the crucial key in this example is that the infinite product allows for the expression of the unbounded logical quantifier ∃\exists∃. Together with the propositional logical connectives (AND, OR, NOT), unbounded quantification enables expression of anything that can be expressed in first-order logic.

\setbiblabelwidth

10

References

• [1] Samuel Alexander. Formulas for computable and non-computable functions. Rose-Hulman Undergraduate Mathematics Journal, 7, 2006.
• [2] Jonathan M Borwein, Richard E Crandall, et al. Closed forms: what they are and why we care. Notices of the AMS, 60(1):50–65, 2013.
• [3] Donald E Knuth. Two notes on notation. The American Mathematical Monthly, 99(5):403–422, 1992.
• [4] Sai Teja Somu and Vidyanshu Mishra. On a generalization of Tupper’s formula for m 𝑚 m italic_m colors and n 𝑛 n italic_n dimensions. Discrete Mathematics, 346(12), 2023.
• [5] Jakub Trávník. Trávník’s smooth self-referential formula. https://jtra.cz/stuff/essays/math-self-reference-smooth/index.html, 2019. Accessed: 2024-07-31.
• [6] Jeff Tupper. Reliable two-dimensional graphing methods for mathematical formulae with two free variables. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 77–86, 2001.
• [7] Jeff Tupper. Index of /selfplot. http://www.peda.com/selfplot/, 2007. Accessed: 2024-07-31.