-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.tex
3623 lines (2188 loc) · 474 KB
/
main.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[12pt]{article}
\usepackage{personal}
\usepackage{realoracles}
\newtheorem{theorem}{Theorem}[subsection]
\newtheorem{lemma}{Lemma}[subsection]
\newtheorem{corollary}{Corollary}[subsection]
\newtheorem{proposition}{Proposition}[subsection]
\title{Defining Real Numbers With Rational Intervals}
\jtauthor
\date{\today}
%\sloppy%\openup-.1\jot
\begin{document}\maketitle
\begin{abstract}
To know a real number is to know, for any given pair of rational numbers, whether it is between them. This leads to using rational intervals to describe real numbers and even to define them as such. This paper will explore several different definitions of real numbers using rational intervals, exploring their relations and contrasting their differences. Some of the definitions have not been used before. A full exploration of the real numbers as a complete ordered field will be provided as well as some discussion of generalizations and inspirations from this approach.
\end{abstract}
%thinking of real numbers as rational betweenness relations. This paper will define real numbers in that way, codifying relevant properties that make a relation on rationals into a real number. Many uses of real numbers, however, do not immediately produce a rational betweenness relation. Instead, one might have an oracle. An oracle is a rule that, when provided with a rational interval and a rational width, either answer Yes or No depending on if the real number ought to be considered to be in the given interval, or returns an interval containing the real number that includes an endpoint and is no larger than the provided width. After the definitions and basic properties are established, various examples and algorithms are explored in addition to establishing that this form the field of real numbers. The concept of a Family of Overlapping, Notionally Shrinking Intervals is defined and found to be an essential tool in working with real numbers. Mediant approximations, which are related to continued fraction representations, naturally arise from working with intervals. One of the final sections compares and contrast with other common definitions of real numbers, such as Cauchy sequences and Dedekind cuts, in which the conclusion is that the oracle perspective is a master map to the other definitions.
\tableofcontents
\section{Introduction}
The real numbers have a long history of being difficult to understand and use with precision. They also have a long history of being approximated easily to make practical computations happen quite readily.
The essential difficult of irrational real numbers is that infinity is embedded, in an essential way, into each of them. Indeed, pick a random real number and it almost surely is a Library of Babel all by itself. That is just one number. Contrasting that with a rational number and one can see quite a bit of difference between the two concepts.
Traditionally, students first are told that irrational numbers are those whose decimal expansions do not fall into a repeating cycle of digits. For a formal definition of real numbers, the decimal expansions have some difficulties with arithmetic. In the late 1800's, several new definitions arose, most prominently Cauchy sequences and Dedekind cuts. The Cauchy sequence definition results in taking equivalence classes of sequences as a real number. Dedekind cuts are sets of rational numbers. While Cauchy sequences suggest pursuing a computation in order to define a real number, Dedekind cuts invite a lack of computing anything in particular.
All three definitions, and many others, have the idea of rational intervals floating in the background. A decimal approximation is often thought of as an implicit interval. Cauchy sequences have the idea of eventually the tail of the sequence being trapped in an interval of length $\varepsilon$. Dedekind cuts have a lower set being paired with an upper set; this suggests that an element of the lower set and an element of the upper set form a rational interval that spans the cut.
Our goal is to explore definitions of real numbers that use rational intervals. There are already two definitions that explicitly discuss
This definition strikes a balance between having a solid definition of a real number and being useful in computing. Most definitions of real numbers, such as decimal expansions and Cauchy sequences, seem to require explicit computations to even define the number. This is problematic given the infinite nature of real numbers. Other definitions, such as Dedekind cuts, do not require computations to state the number, but they seem to offer, in their usual formulations, little in the way of useful guidance in computing the number.
What we want to provide is an object that can be defined without computation, but provides the underlying mechanism for computing the real number to any precision one wants. In some sense, we are producing the framework for producing approximations to real numbers given the particulars of a given real number. This is analogous to, in functional programming, having a generic sorting algorithm that can be used in a variety of situations by supplying a comparison function to make a pairwise sorting decision while the framework handles the actual details of the global sorting.
Since this is a mechanism that provides answers to our questions, it seems reasonable to call it an oracle. We assert that the best way to understand a real number is that it is an oracle that reveals itself by answering, under repeated questioning, whether it is in various rational intervals.
Informally, the Oracle of $r$ is a rule which, given two rational numbers, will return Yes if $r$ ought to be in the inclusive rational interval defined by the two rational numbers and returns No otherwise. If the answer was a Yes, then we say the interval is an $r$-Yes interval; if the answer is a No, then we say the interval is an $r$-No interval. If we are just speaking of one oracle, we may simply say a Yes-interval or No-interval.
Much like oracles of old, there is also the potential for intervals which we cannot answer definitively Yes or No. This framework allows for that ambiguity, but nevertheless provides a mechanism for making progress towards less uncertainty.
\subsection{Naming Convention}
Throughout this paper $a$, $b$, $c$, and $d$ will be rational numbers, typically used as endpoints of intervals. The letters $e$ and $f$ are often used in the same way though sometimes they are used for the mathematical constant $e$ and common function name of $f$. Additionally, $m, n, p, q, r, s, t, u, v$ will generally be rationals and should be assumed so unless otherwise stated. The letters $x, y, z$ are used for representing real numbers; the Greek letters $\alpha, \beta, \gamma$ may also be used for real numbers.
\subsection{Interval Notation}
We will define a \textbf{rational interval} $a:b$ as a binary rule that, for a given rational $q$, yields Yes if $q$ is between $a$ and $b$, inclusive, and yields No if not. We say that $q$ is in $a:b$ if the interval rule yielded an affirmative answer. We identify $b:a$ as the same rule. The interval $a:b$ contains the interval $c:d$ if being in the interval $c:d$ implies being in the interval $a:b$. We will write $a\lt b$ if we want to indicate the ordering relation between the rationals and that they are strictly not equal. We may also require knowing the ordering, but still allow equality. In that case, we use the notation $a \lte b$ to indicate $a \leq b$. We will also write $a:b < c:d$ to indicate the situation in which $a$ and $b$ are less than $c$ and $d$ which implies that all rationals $q$ in $a:b$ are less than all rationals $r$ in $c:d$.
Please take note that the intervals not only have rational endpoints but they consist entirely of rational points as we do not have real numbers. Throughout, unless we say otherwise, intervals always include their endpoints. If we had the real numbers, these would be closed intervals with rational endpoints. The symbol $:$ was chosen to represent the two endpoints with something in between. Being dotted is to be a reminder that it is just the discrete rational interval under discussion.
We also adopt an extension of this notation as $a_0:a_1:\cdots:a_{n-1}:a_n$ which suggests an interval perspective, but whose content is largely conveying the same information as $a_0 \leq a_1 \leq \cdots \leq a_{n-1} \leq a_n$ though the order could be reversed with the vertical dots. We can also put in the symbols $\lt$ and $\lte$ in that sequence as appropriate which would cement the ordering. We might also write something like $a:\{b,c\}:d$ which would indicate that both $b$ and $c$ are between $a$ and $d$, but the relative ordering of $b$ and $c$ is unknown.
We define the term \textbf{singleton} to be intervals of the form $a:a$, namely the only number in the interval is the rational $a$. We also define the term \textbf{neighborly interval} to be intervals which are not singletons, that is, $a \lt b$ is its form. When we write $a:b$, we do allow for $a=b$.
The\textbf{ $\delta$-halo at $c$}, denoted $c_{\delta}$ is the interval $c-\delta:c+\delta$, where $\delta>0$ is a rational number. We will refer to $\delta$ as a width and if we say a \textbf{width} $\delta$ then we are implying that $\delta$ is a positive rational; it will typically in this paper intended to be used as part of a halo. A \textbf{$c_{\delta}$-compatible interval} is an interval that is contained in $c_{\delta}$ and strictly contains $c$, i.e., if $e \lt f$ is $c_{\delta}$ compatible then $c-\delta:e\lt c \lt f:c+\delta$. We also extend this to more general intervals. Given the interval $a\lte b$ and width $\delta$, then the $\delta$-halo of $a:b$ is the interval $a-\delta:b+\delta$ which may also be denoted $(a:b)_\delta$.
A rational $q$ is \textbf{strictly contained} in $a\lt b$ if $a < q < b$. An interval $c:d$ is \textbf{strictly contained} in $a\lt b$ if both $c$ and $d$ are strictly contained in $a \lt b$. We say that $c \lte d$ is \textbf{nested in} $a\lte b$ if $a \leq c \leq d \leq b$; $a \lte b$ then is also said to \textbf{contain} $c \lte d$.
The length of an interval $|a \lte b |$ is $b-a$.
Assume for this paragraph that we have $a \lt b$, $c \lt d$, and $a \leq c$. We say that $a\lt b$ and $c \lt d$ are \textbf{strictly overlapping} if $c \leq b$, $b \leq d$ and either $a < c$ or $b < d$. Two intervals are \textbf{overlapping} if they are either strictly overlapping or one is nested inside the other. An interval is nested inside itself. The two intervals are \textbf{disjoint} if $b < c$. If the two intervals are disjoint, then we define the \textbf{separation} $S$ to be $c-b$; if they are not disjoint, then the separation is 0. The \textbf{distance} $D$ between the two intervals is the maximum of the difference between the endpoints. The length of an interval is the same as the distance of the interval to itself. Note that the non-negative difference between two points, one from each interval, will never be less than the separation and never greater than the distance. That is, if $q$ is in $a\lt b$ and $p$ is in $c \lt d$, then $S \leq |p-q| \leq D$. We have that $S = 0$ exactly when the two intervals are overlapping. They are strictly overlapping when, in addition to $S=0$, the distance between the two intervals is larger than both the lengths. If the distance is smaller than the longer length, then the shorter one is strictly contained in the other. If the distance is the same as the lengths, then they are the same interval. These statements are easy to establish by cases as is the fact that the distance of the intervals is the same as the separation plus the lengths for disjoint intervals.
Note that we do have transitivity of interval inequality, that is, if $a:b < c:d$ and $c:d < e:f$, then $a:b < e:f$. This follows immediately from the transitivity of inequalities on rationals.
\section{Rational Betweenness Relations as Real Numbers}
Rational betweenness relations is the general idea that a real number is defined as providing a relation on rational numbers. Specifically, two rational numbers are in the relation if the real number ought to be between them. A more common way of saying this is that given a rational interval, the real number should be in that interval.
Since the real number is being defined, we have to come up with some way of describing when a rational relation satisfies describing a betweenness relation based on a real number. This will be used as the definition of the real number.
There are at least five distinct ways of doing this each with their own advantages and disadvantages. The first two approaches are pre-existing approaches. The other three are, as far as this author can determine, new.
For all of the definitions, the basic definition of the arithmetic operations and comparison operators is to do them on the intervals in the definitions. The proofs that these work appropriately may vary, but the basic idea is all the same.
\subsection{Nested Intervals}
This was a definition dating back to Bachmann in 1892, see, for example, \cite{ittay-2015}. It is a generalization of the idea of decimal approximations as ever finer approximations with an implied uncertainty in the last digit.
This is the idea that one has a sequence of intervals $a_n:b_n$ such that $a_n:a_m:b_m:b_n$ for all $=m \geq n$. Additionally, $|a_n - b_n| \to 0$. This latter means that for any positive rational $\varepsilon$, there should exist an $N$ such that if $n \geq N$, then $a_n:\pm \varepsilon$ contains $b_n$. We will call such sequences \textbf{Bachmann sequences}.
This construction is very similar to Cauchy sequences. It has a similar problem that any given real number can be represented by uncountably many such sequences. Thus, there needs to be an equivalence relation imposed on it.
This is done by considering the notion of a refinement of an interval sequence. Namely, if $I_n$ and $J_n$ are two Bachmann sequences with the additional fact that $J_n \subset I_n$ for all $n$, then $J_n$ is a \textbf{refinement} of $I_n$. Two Bachmann sequences are equivalent if there exists a common refinement; that is, $I_n \sim J_n$ exactly when there exists a Bachmann sequence $K_n$ such that $K_n \subset I_n$ and $K_n \subset J_n$ for all $n$. All three sequences are representing the same abstract real number.
Note that this implies that all of the intervals in these three sequences are intersecting one another. The largest refinement of two sequences would be the sequence of intersections of the two given sequences.
A quick sanity check is to assume that $I_n$ represents the rational number $c$ and thus all of the the intervals $I_n$ should contain $c$. Then is $c$ contained in the intervals of all equivalent sequences? The basic trick is to assume that there exists a $J_m$ such that $c \notin J_m$. Then look at the distance from $c$ to the closest endpoint of $J_m$. Find an $n > m$ such that the length of $I_n$ is less than that distance. Then $I_n$ cannot contain $c$ while also intersecting $J_n$ which is contained in $J_m$. Thus, these are not equivalent sequences and so, if they are, $c$ must be in all of the intervals $J_n$.
\subsection{Families of Overlapping Notionally Shrinking Intervals}
A common way of defining a real number is through some specification of intervals whose length is shrinking to 0. This is often in the guise of some core estimate along with some error bounds. We will establish that this is an oracle.
We define the term \textbf{fonsi} to refer to a Family of Overlapping, Notionally Shrinking Intervals. This means a fonsi is a set of rational intervals which are all pairwise intersecting and such that given a positive rational length $\varepsilon$, there exists at least one interval in the family whose length is less than $\varepsilon$.\footnote{We use the term ``notionally shrinking'' to indicate that we want to think of it as shrinking intervals, but there need not be any sequential aspect to this that would qualify as shrinking.} Singletons are allowed in the family and they have length 0.\footnote{There can be at most one singleton as the singletons need to intersect, but we need not presuppose the uniqueness.} A set consisting of a single singleton does qualify for being a fonsi.
One method of defining real numbers among constructivists is to equate a fonsi, or a fine family of intervals, with a real number. See \cite{bridger} and \cite{bridges} for details. The fonsi framework is appealing to the constructivist framework as it aligns strongly with their methods of proof and construction. It also aligns with measurements as we briefly discuss in Section \ref{main:measure}.
One example category is that of the Bachmann sequences. A slight extension of this would be to a sequence of numbers with error bounds such that successive numbers are contained within the previously indicated error bounded intervals. That is, $a_n$ is the sequence of numbers, $\varepsilon_n$ are such that $\varepsilon_n \to 0$, and $a_n-\varepsilon_N:a_m:a_n+\varepsilon_n$ for all $m > n$. It is very common to have error bounds in applications and this is how we can formalize that notion.
One failed example is the set of intervals $\frac{1}{n}:1$. It is an overlapping set which creeps up to zero, but it fails to be shrinking. Another failed example is something like $\frac{1}{n}:\frac{1}{m}$, which does have intervals shrinking to zero, but it fails the overlapping property. A fonsi forces an overlap across the real number that it is representing. We could, for instance, look at $\frac{-1}{m}:\frac{1}{n}$ for all positive integers $m$ and $n$. These overlap and we can find as small an interval as we like. The fonsi $-\frac{p}{q} : \frac{r}{s}$ for all positive integers $p, q, r, s$ represents $0$ though it excludes any interval with an endpoint of $0$. If we allow for $p$ and $r$ to possibly be 0, then this is a maximal fonsi representation of $0$.
Two fonsis are equivalent if they can be combined into a single fonsi. This is equivalent to the requirement that all of the elements of both families intersect one another. Given a rational $c$ that is present in one family, it must be in any equivalent family roughly by the same logic as before. That is, if in a second family, there is an interval that does not contain $c$, then there is a separation between that interval and $c$. Choose an interval of the first family whose length is less than half of the separation. Then it cannot intersect both the interval and $c$. Thus, they are not fonsis that are equivalent.
There is more to say about fonsis as detailed in Section \ref{sec:ni}.
\subsection{Rational Cut Relations}
Rational cut relations are a pure, idealized form encapsulating the algorithm of the Intermediate Value Theorem. This concept is explored in \cite{taylor24dedekind} where it is proved that it is equivalent to the Dedekind cut definition for real numbers.
The idea is that a real number $x$ is a relation on rational numbers such that two rational numbers, possibly identical, are $x$-related if $x$ ought to be between them. It is a symmetrical relation.
To be a rational cut relation, the relation must satisfy the properties listed below.
\begin{enumerate}
\item Existence. $a \xrel b$ holds for some rational interval $a:b$.
\item Cutting. If $a \xrel b$, then for a given $c \neq a, b$ in $a:b$, one of the following holds:
\begin{enumerate}
\item $a \xrel c$ with \sout{$c \xrel b$},
\item $b \xrel c$ with \sout{$c \xrel a$}, or
\item $c \xrel c$.
\end{enumerate}
\item Consistency. Assume $c:d$ contains $a:b$. If $a \xrel b$, then $ c \xrel d$.
\item Rooted. If $c \xrel c$ and $d \xrel d$, then $c=d$.
\item Closed. If $c \in a:b$ for all $a:b$ such that $a \xrel b$, then $c \xrel c$.
\end{enumerate}
The main difficulty with this definition is that there are real numbers that we can define for which $c \xrel c$ cannot be established. Thus, the cutting property cannot be verified. This is our idealized betweenness relation. We assume for this definition that every pair of rationals, including singletons, are either definitively $x$-related or they are not.
Most of the work done in this paper will directly apply to this definition, at least with the assumption that the relation can be determined for any given rational interval. We will point any issues with using this definition in our statements and proofs throughout this paper.
The discussion of these rules will follow similarly to the oracles presented below so we will defer that discussion until then.
\subsection{Rational Exclusion Relations}
This version of a rational betweenness relation replaces the cut property with being able to exclude at least one of a given pair of rational numbers in an interval. We continue to use closed intervals.\footnote{An example of the need is to consider the relation representing 0. If the intervals were open, then the intervals in the relation could be those of the form $-a:b$ where $a, b$ are positive rationals. This would satisfy our properties except for the closed property which would be excluded from the properties for an open interval. But then the question of intervals of the form $0:b$ comes up. They do not need to be a part of the relation and should not be as they exclude 0, but they can be added without conflict. }
To be an exclusion relation, the symmetric relation must satisfy the properties listed below.
\begin{enumerate}
\item Existence. $a \xnan b$ holds for some rational interval $a:b$.
\item Exclusion. If $a \xnan b$ with $a < b$, then given $c, d$ in $a:b$, there exists $e, f$ such that $a:e:f:b$ such that $e \xnan f$ and at least one of $c, d$ is excluded from $e:f$. Furthermore, $a:e$ and $f:b$, if they are neighborly, are not in relation to $x$.
\item Consistency. Assume $c:d$ contains $a:b$. If $a \xnan b$, then $ c \xnan d$. If \sout{$c\xnan d$}, then \sout{$a\xnan b$}.
\item Closed. If $c \in a:b$ for all $a:b$ such that $a \xnan b$, then $c \xnan c$.
\end{enumerate}
\subsection{Oracles}
The idea of an oracle is that it takes in a rational interval and says Yes or No depending on whether the real number is in the interval. Unfortunately, real numbers can be a little more complicated than that. It can be the case that intervals whose endpoint is a particular rational number cannot be answered one way or the other. But what can be ascertained is whether the real number is in a $\delta$-halo of that rational number. We will formalize this.
The Oracle of $x$ is a rule $R_x$ which, when given a rational interval $a:b$, with possibly $a=b$, and a rational width $\delta$, returns either $a:b$ signifying the real number $x$ ought to be in that interval, $a_\delta$ signifying $x$ is in $a_\delta$, $b_\delta$ signifying $x$ is in $b_\delta$, or $\emptyset$ signifying that $x$ ought not to be in $a:b$.
We will say $a:b$ is a Yes interval if $R_x (a:b, \delta) \neq \emptyset$ for all $\delta >0$. It is assumed for all oracles that if $R_x$ returns an interval $c:d$, then $c:d$ is a Yes interval. Thus, if $R_x( a:b, \delta) = a:b$ for some $\delta$, then $a:b$ is a Yes interval.
Note that it is possible that $R_x(a:b, \delta) = a_\delta$ for all $\delta > 0$. The interval $a:b$ is a Yes interval in this case, but it is not the case that $a:b$ has been returned by $R_x$. Additionally, $R_x(a:a, \delta) = a_\delta$ may hold for all $\delta$. This also implies that $a:a$ is a Yes interval though it is never returned by $R_x$.
If $a:b$ is a Yes interval, then we use the notation $a \xora b$. For a No interval, the notation is \sout{$a \xora b$}. If $a_\delta$ is returned from evaluating $R$, then $a_\delta$ is a Yes interval which may be written as $a \xora \pm \delta$ and is a slightly more compact way of writing $a-\delta \xora a + \delta$. If $b_\delta$ is returned, then $b \xora \pm \delta$ is used.
We may also drop the $x$ for the function $R$ when there is only one oracle under discussion. If no real number symbol is given, then $x$ will be used as the default.
To be an oracle, the rule must satisfy the properties listed below.
\begin{enumerate}
\item Existence. $a \xora b$ holds for some rational interval $a:b$.
\item Separating. If $a \xora b$, then for a given $c \neq a, b$ in $a:b$ and given a width $\delta$, there exists a $c_{\delta}$ compatible interval $e:f$ such that exactly one of the following holds true:
\begin{enumerate}
\item $a \xora e$, \sout{$e \xora f$}, \sout{$f \xora b$};
\item \sout{$a \xora e$}, $e \xora f$, \sout{$f \xora b$};
\item \sout{$a \xora e$}, \sout{$e \xora f$}, $f \xora b$;
\end{enumerate}
\item Consistency. Assume $c:d$ contains $a:b$. If $a \xora b$, then $ c \xora d$. If \sout{$c\xora d$}, then \sout{$a\xora b$}.
\end{enumerate}
The Existence and Separating properties are both essential ingredients in algorithmically refining the knowledge about the real number. The Consistency property is more about filling in the blanks when already given some knowledge. In other words, specifying a starting Yes interval and the rule how to do the separating property allows us to develop the real number.
For further elaboration on what each of these properties means:
\begin{enumerate}
\item The Existence property says that there is definitely an interval which the Oracle confirms being in. It is required to avoid the trivial $R(a:b) = \emptyset$ for all $a:b$ which would satisfy all the other conditions, including the Separating property due to that property only applying to Yes-intervals.
The existing interval also gives us a place to start in our approximation schemes that we discuss later.
It is usually easy to verify in any practical example as any Yes-interval will do and we can usually find a very bad approximate interval that is easy to establish.
The existing interval is also part of specifying a limited domain for finding a solution. For example, if using $\sin(x) = 0$ to define $\pi$ using the Intermediate Value Theorem, one needs to specify an interval with exactly one solution, such as the interval $3:4$.
\item Separation is needed to ensure that the Yes will continue to propagate downwards so that we can make progress on narrowing in on $x$. This is crucial to the use of the Oracle in approximating what we take to be a single number $x$. Ideally, we could ask the rule whether $c:c$ is a Yes interval or not. If it was No, then we would be in the case of exactly one of $a:c$ and $c:b$ being a Yes interval while the other one is a No interval. If it was Yes, then we have our real number as the rational number $c$. Unfortunately, it can be hard to ascertain whether a real number is a given rational number or not. This is why we specify a $\delta$ as a tolerance level for knowing about $c$.
We do require that given that fuzziness, the rule should be able to give us an answer, at least in principle with a large, but finite, amount of work. In practice, we may still not be able to answer the question due to computational limitations. This particular difficulty with rationals mirrors the difficulty in other approaches to real numbers.
Separation ensures that there is just one single number under discussion. Without imposing the No conditions, we could have the rule, for example, $R(a:b) = 1$ for all $a:b$ that contain a subinterval of a fixed given interval $m \lt n$. This is compatible with all the properties except for the requirement of having No intervals when separating the interval. In particular, let $m:n$ be our Yes interval and take $c = \frac{m+n}{2}$. Let $\delta = \frac{n-m}{3}$. Then $m:c, c:n, c:\pm \delta, m:c-\delta, c+\delta:n$ are all Yes intervals. So the Yes parts are all satisfied, but the No is not. It is the requirement of having an answer of No which makes this have a single real number that it is representing.
One particular example of needing to impose this is in finding the roots of a function using the intermediate value theorem. Let's say we are looking at $f(x) = (x-1)(x-2)$. The roots are 1 and 2, of course, but let's say we define the oracle rule as saying Yes to any interval $a:b$ for which the signs of $f(a)$ and $f(b)$ are not equal or one of the values is 0. This would represent both the roots 1 and 2. To satisfy the Separation property and get a single solution, we can restrict ourselves to the interval $0.5:1.5$ and require that any interval disjoint from that is a No interval. We can then operate within that interval according to the sign rule.
Because of Consistency, the interval $e:f$ being Yes implies $c_{\delta}$ is a Yes interval. In addition, its complementary intervals in $a:b$ are sub-intervals of the complements of $e:f$ so Consistency implies that the No property gets transmitted to the sub-intervals. Thus, we may simplify the use of the Separation property for oracles as saying either $c_{\delta}$ is a Yes interval or exactly one of $a:c, c:b$ is a Yes interval.
We exclude the endpoints as the No interval part would not be possible. This is different from the exclusion relation in which using the endpoints and excluding one of them is both sensible and yields a new interval.
\item Consistency says that Yes propagates upwards to larger intervals while No propagates downwards to smaller intervals. The Oracle never contradicts itself.
In our examples, this is usually imposed by definition of the rule, corresponding to this not revealing anything of practical use. In some sense, this property is here to ensure that there is a single oracle for a given real number.
Without Consistency, we could have a rule which has multiple refinement targets. Consider, as an example, the rule which is Yes for all intervals containing $0$ but excluding $1$ as well as all intervals containing $3$ but excluding $2$. This satisfies Existence, Separating, and Closed. The closed is satisfied as there is no rational number in all the intervals though we also have two singletons included. Existence is clear. Separating is pretty easy to establish, noting that there are no Yes intervals covering the two integers. It is only consistency which forces the joining of disjoint Yes intervals into a combined interval that Separation can then force a contradiction out of.
The second part of the Consistency property may not feel necessary. Indeed, if $a\lt b$ is strictly contained in the No interval $c:d$, then choose a $\delta$ such that $a- \delta : b+\delta$ is contained in $c:d$, which is possible by the strictly contained property. Then and $a:b$ is a No interval, then if $c:d$ was Yes, we would have a contradiction. Consistency says that we therefore must have $c:d$ as a No interval. We have included this in the property to be explicit about the requirement as we could not otherwise force it to be defined.
\end{enumerate}
This definition does not avoid all of the common downsides of the other definitions of real numbers, but it does reduce them to a context that reflects how real numbers get used in practice. It illustrates those downsides as fundamental to the nature of real numbers while avoiding inessential downsides that other approaches have. See Section \ref{sec:others} for a discussion of other approaches.
A \textbf{singleton oracle }is an oracle whose Yes intervals includes a singleton. We may also refer to them as \textbf{rooted} oracles with the root being the singleton which we can also refer to as the unique rational that is an element of that singleton. These will eventually be identified with the rationals. A \textbf{neighborly oracle} is an oracle whose Yes intervals do not include a singleton. These are the irrationals.\footnote{For a picturesque language, we could call a \textbf{$\delta$-spark}, for a rational $\delta > 0$, of an oracle to be a rational number $q$ such that the $\delta$-halo of $q$ is a Yes interval. A \textbf{star} of an oracle is a rational number $q$ such that $q \xora q$ and this would be a stellar oracle. Stars, if they exist, are unique for a given oracle. A \textbf{galactic} oracle is one which has no star of an oracle. The idea is that we are looking at a number from afar and it looks like a point of light in the sky. That point could be a star in our own galaxy (a rational) or it could be a whole new galaxy, and those stars are generally related to one another by rational arithmetic (algebraic extension).}
We also define the term \textbf{resolvable oracle} to mean an oracle in which all rational intervals have a defined answer to the oracle question. For such an oracle, we can ask about $c:c$ for any singleton and get an answer. This will allow any rational in a Yes interval to divide the interval into two pieces, with exactly one of being a Yes interval, assuming the singleton is a No interval. That is, a resolvable oracle is just another way of expressing a rational cut relation. With Existence and Consistency, what makes a resolvable oracle is the ability to answer the question for every singleton.
\subsubsection{Equality of Oracles}
An attentive reader will notice that the Closed property of the previous two definitions is absent for oracles. This is because it is both not true and can be somewhat deduced from it.
A possible Closed property statement could be of the form: If the $\delta$-halo of $c$ is a Yes interval for all rational $\delta>0$, then $c \xora c$. Additionally, if \sout{$a \xora a$}, then there exists a $\delta$-halo of $a$ such that \sout{$a \xora \pm \delta$}.
The statement that $c \xora c$ is the statement that $R(c:c, \delta)= c:c$ for some $\delta$; the oracle would be compatible at that point with that statement for all $\delta$. Unfortunately, if $R(c:c, \delta) = c_\delta$ for all $\delta > 0$, we cannot conclude that there exists a $\delta > 0$ such that $R(c:c, \delta) = c:c$. It is clear, however, that $c$ is the real number being discussed. The actual claim is that an oracle of this kind is equal to an oracle such that $R(a:b, \delta) = a:b$ if and only if $c \in delta$.
To establish this, we need to first discuss equality of oracles. For the other relations, equality is literal as we assumed a definite answer for them. For oracles, the oracle can return up to three distinct answers if it is not a No interval. This offers some possible differences. Oracles $R$ and $S$ are \textbf{equal} if and only if $R(a:b, \delta) \neq \emptyset$ occurs exactly when $S(a:b, \delta) \neq \emptyset$. That is to say, both oracles return a non-empty interval for the same inputs. They may return different intervals, but they agree on whether an interval is Yesish or not.
An important benefit of the Closed property is that the arithmetic of rationals is unchanged. As we shall see, oracle arithmetic involves interval arithmetic. With the presence of the singletons, we can do arithmetic with them as we do with fractions.
It also helps ensure the uniqueness of an oracle. For example, we could define a $0^+$ oracle by being Yes on all the intervals of the form $a \lt b$ with $a < 0, b \geq 0$, and another oracle $0^-$ as intervals of the form $a \lt b$ with $a \leq 0, b >0$. These two proto-oracles satisfy the other properties. Both could be said to represent $0$, but they are distinct. They obviously fail to satisfy the Closed property. If we add in $0:0$ to them to satisfy the Closed Property, then they fail Consistency since we now need to include all intervals that include $0:0$. This is how we achieve uniqueness.\footnote{If we were using exclusive intervals, we could have at least three representatives. All of them have Yes to $a:b$ with $a<0, b> 0$. One representative is just that, another adds in $a:0$ and the other has $b:0$, depending on how we modify the properties.}
Most representations of real numbers have this issue with rationals. Decimals have the issue of repeating 9s. Dedekind cuts have the question of whether to include the rational or not in its own cut. Continued fraction representations are unique on irrational numbers, but they have two representatives for rationals. Other approaches, such as Cauchy sequences and fonsis, have an abundance of non-unique representations.
In our constructions, we often need to add this in explicitly. Establishing that a rational real is rational can be difficult, possibly impossible. This seems to be one of the essential difficulties with real numbers, to varying degrees. We handle this by using the $\delta$ smearing in the Separating property.
In the Closed property, we have also included the fact that $a:a$ being No implies the existence of a $\delta > 0$ such that $a_\delta$ is No interval. One can argue, non-constructively, that the first statement in the Closed property implies this. Indeed, if there was no such $\delta$, then every $a_\delta$ is a Yes interval and this implies by the Closed property, that $a:a$ is a Yes interval. I have decided to include this in the property as an explicit declaration that we expect this to be constructively doable in the rule. In particular, this applies when one says No to a singleton. To be able to say No suggests some knowledge and that there ought to be a moat around it.
\section{Basic Properties}
Here we collect various useful facts about these relations. The primary focus is on oracles as they are the most practical and difficult, but there will be indications for the other versions.
\subsection{Rooted}
While cut relations have the rooted property as assumed, in the other versions, it can be deduced.
\begin{proposition}[Rooted]\label{pr:rooted}
For an oracle $R$, there is at most one rational number $c$ such that $R(c:c)= c:c$.
\end{proposition}
\begin{proof}
Let $c$ be a rational number such that $c:c$ is a Yes interval. Let $d$ be any other rational number. Then by Consistency, $d:c$ is a Yes interval since it contains the Yes interval $c:c$. Let $m = \frac{d+c}{2}$ be the midpoint and $L=|d-c|$ be the length of the interval which is not 0 as $d \neq c$. Then apply Separation to $m$ as the partition point and $\delta=L/4$. Separation gives us an $m_{\delta}$-compatible interval $e:f$ such that $d:e:m:f:c$ with exactly one of $d:e$, $e:f$, and $f:c$ being a Yes interval. Since $c:c$ is a Yes interval, we know $f:c$ is a Yes interval. Thus $d:e$ is a No interval. Since $d:d$ is contained in the No interval $d:e$, Consistency tells us $d:d$ is a No interval.
\end{proof}
Thus, if an oracle is rooted, its root is unique.
For fonsis, including Bachmann sequences, this is accomplished by picking an $\varepsilon$ smaller than $L$ which necessarily implies an interval in the fonsi that excludes $d$.
For the exclusion relation, take $c$ and $d$ as the points to apply the exclusion to. Since $c \xnan c$, Consistency insists that the exclusionary interval $e:f$ must include $c$.
\subsection{Bisection Approximation}
The practical importance of the Separating property is established by the following bisection algorithm.
\begin{proposition}[Bisection Approximation]\label{pr:short}
Let $R$ be a rule that satisfies the Existence and Separation properties and $\varepsilon > 0$ be a given rational number. Then there exists a Yes interval whose length is less than $\varepsilon$.
\end{proposition}
In particular, this holds for oracles.
We first establish a bisection lemma.
\begin{lemma}
For any rule $R$ that satisfies the Separation property and given the $R$-Yes interval $a\lt b$, there is a Yes-subinterval whose length is at most $\frac{b-a}{2}$.
\end{lemma}
\begin{proof}
Let $L = b-a$ be the interval's length. Then we take the average of the endpoints: $c = \frac{a+b}{2}$ and use $\delta = \frac{L}{4}$. Since $R$ is Separating, there exists a $c_{\delta}$-compatible interval $e \lt f$ such that one of the following holds true:
\begin{enumerate}
\item $R(a:e)=1$, $R(e:f) = R(f:b) = 0$. The interval $a:e$ is the desired subinterval with length at most $\frac{L}{2}$.
\item $R(f:b)=1$, $R(a:e) = R(e:f) = 0$. The interval $f:b$ is the desired subinterval with length at most $\frac{L}{2}$.
\item $R(e:f)=1$, $R(a:e) = R(f:b) = 0$. The interval $e:f$ is the desired subinterval with length at most $\frac{L}{2}$.
\end{enumerate}
Since each of the possibilities leads to a length at most half the length of the given interval, we have established the result.
\end{proof}
If one prefers to have a definite outcome, then item 1 implies $a:c$ is Yes, item 2 implies $c:b$ is Yes, and item 3 implies $c_{L/4}$ is Yes. Each of those intervals is exactly half the length of $b:a$.
We can now prove the bisection approximation.
\begin{proof}
The existence property of $R$ gives us a starting Yes interval. If the interval is of the form $a:a$, then the length is $0 < \varepsilon$.
Otherwise, we can take $a \lt b$ with $L = b-a$. Choose $n > \max(\log_2 (\frac{L}{\varepsilon}), 1)$ which implies $2^n > \frac{L}{\varepsilon}$ as well as $2^{-n} < \frac{\varepsilon}{L}$.\footnote{We are using a logarithm here for convenience and explicitness. Since we are developing the real numbers, this is a bit out of order. But there should be no doubt that one can keep halving a positive number until it is less than any specified positive number.} Apply the bisection lemma $n$ times, starting with $a \lt b$ and, at each step, use the lemma's produced Yes subinterval for the next iteration. This leads to at least halving the length each time. Thus, the length of the final interval is at most $2^{-n} * L < \frac{\varepsilon}{L} L = \varepsilon$.
\end{proof}
This is helpful in establishing the arithmetic properties. In Section \ref{sec:mediant}, we will discuss the mediant approximation which is generally a pretty pleasant computational method to employ that can also generate the continued fraction representation of the real number.
Note that the bisection method will not usually produce the singleton if $r$ is a singleton. The mediant approximation generally does if one can test singletons.
We can now establish alternative conditions for applying the Closed property.
We say that $c$ is \textbf{$\varepsilon$-compatible} with the oracle $R$ if there exists an $R$-Yes interval of length not more than $\varepsilon$ which contains $c$.
\begin{proposition}\label{pr:closed-epsilon}
Let $R$ be an oracle. If $c$ is $\varepsilon$-compatible with $R$ for all $\varepsilon >0$, then $R$ is the Oracle of $c$.
\end{proposition}
\begin{proof}
Let $\delta > 0$ be given. Let $\varepsilon = \frac{\delta}{3}$. By the assumption, there is a Yes interval $a\lt b$ that is no larger than $\varepsilon$ with $a:c:b$. Since $b-a \leq \varepsilon$ and both $c-a$ and $b-c$ are less than $b-a$, we have that the Yes interval $a:b$ is in the interval $c_{\varepsilon}$ which is contained in $c_{\delta}$. Thus $c_{\delta}$ is a Yes interval by Consistency. As $\delta$ was arbitrary, we have that the Closed property applies yielding $c:c$ being a Yes interval.
\end{proof}
\begin{corollary}\label{cor:closed-all}
Given an oracle $R$, if all $R$-Yes intervals contain a number $c$, then $R$ is the Oracle of $c$.
\end{corollary}
\begin{proof}
By the Bisection Approximation, we have the existence of arbitrarily small Yes intervals. By assumption all Yes intervals contain $c$ so these do as well. Thus, the proposition applies.
\end{proof}
\begin{proposition}
Given an oracle $R$, if $R(c:c)=0$, then there exists an $R$-Yes interval that does not contain $c$.
\end{proposition}
\begin{proof}
By the Closed property, there exists a $\delta > 0$ such that $R(c_\delta)=0$. By the Bisection Approximation, we have the existence of an $R$-Yes interval $a:b$ whose length is less than $\delta$. Since $c_\delta$ is a No interval, it cannot contain $a:b$ by Consistency. Let's say that $a$ is outside of $c_\delta$. Then $|a-c| > \delta$ so that while $a_\delta$ contains $a:b$, it does not contain $c$. Thus, $c$ is not contained in the Yes interval $a:b$.
\end{proof}
We establish some basic facts of oracles which we will find useful throughout.
We start with the extremely helpful properties involving intersections and unions. We then discuss the uniqueness of oracles, with the related notions of determining ordering and compatibility. In particular, we define what we mean by $r = s$, $r<s$, $r>s$, and $r ? s$ for oracles $r$ and $s$.
The relation $r ? s$ means that they have not been established to be equal, but they are compatible with that hypothesis. We may want to specify an interval of compatibility, say $a:b$, which is the smallest known interval tested that they both reported Yes on. To denote that, we can use $a:r?s:b$. Another option is to say that they are within a rational tolerance of $\varepsilon > 0$ which can be denoted by $(r?s)_{\varepsilon}$.
\subsection{Intersections and Unions}
Let $a \leq b \leq c \leq d$ with all of them being rationals. The intersection of $a\lte c$ and $b\lte d$ is $b\lte c$ while the union is $a\lte d$. The two intervals $a\lte b$ and $c\lte d$ are disjoint if $b < c$ and they have no intersection nor union, as defined here. We also define the \textbf{intervalized union} of those two disjoint intervals as $a \lte d$. The usual set definition of union in this situation would produce a non-interval while we wish to stay in the interval situation. Mostly, this is used as a convent term for having an interval that contains both of the intervals.
One can either take those as statements from the usual set definitions or take these as the definitions of those terms. It is immediate from the Consistency property that Yes-intervals are closed under unions and that No-intervals are closed under intersection. We will prove that Yes (No) intervals are closed under pairwise intersections (unions).
We start with establishing two $R$-Yes intervals intersect in an $R$-Yes interval.
\begin{proposition}\label{pr:inter}
Let $R$ be an oracle with $I$ and $J$ two $R$-Yes intervals. Then $I$ and $J$ intersect with that intersection being itself a Yes interval.
\end{proposition}
\begin{proof}
Let $I = a \lte b$, $J = c \lte d$ and assume, without loss of generality due to relabeling, that $ a\leq c$. Then we need to show that $b \geq c$ and $c \lte b$ is a Yes interval.
Since $c \lte d$ is contained in $a \lte d$, Consistency implies $a \lte d$ is a Yes interval.
If $b < c$, then we pick $m = \frac{b + c}{2}$ and $\delta = \frac{c-b}{4}$ for the Separating property. Let $e:f$ be the $m_\delta$ compatible interval in that property. Then one of the following holds true but each leads to a contradiction:
\begin{enumerate}
\item $a:e$ is the Yes interval. This implies $f:d$ is a No interval by Separating. Then $c:d$, contained in $f:d$ must be a No interval by Consistency. Thus, we cannot be in this case.
\item $f:d$ is the Yes interval. This implies $a:e$ is a No interval by Separating. Then $a:b$, contained in $a:e$ must be a No interval by Consistency. Thus, we cannot be in this case.
\item $e:f$ is the Yes interval. Then both $a:b$ and $c:d$ are contained in No intervals which also contradicts.
\end{enumerate}
Therefore, $b \geq c$ and we have established that Yes intervals intersect.
We now want to establish that $c\lte b$ is a Yes interval. If $a=c$, then $c:b$ is $a:b$ and is already Yes. If $b=d$, then $c:b$ is $c:d$ and is a Yes interval. If $b > d$, then $c \lte b$ contains $c \lte d$ and, by Consistency, is a Yes interval.
The case that remains, which is the interesting one, is $a < c$ and $ b < d$.
We need to separate into two cases. The first case is if $b=c$. Then for any $\delta > 0$ such that $b_\delta$ is strictly contained in $a:d$, the Separating property applies to give us $a:e:b:f:d$. Since we just established that Yes intervals intersect and $a:e$ does not intersect the Yes interval $b:d$, it must be a No interval. Similarly, $f:d$ is a No interval being disjoint from $a:b$. Thus, $e:f$ is a Yes interval. Since this holds for arbitrarily small $\delta$, we have that $b:b$ is a Yes interval by being Closed and thus this is a rooted oracle at $b$.
Our final case is now $a:c\lt b :d$. Choose $\delta > 0$ such that $b_\delta$ and $c_\delta$ are strictly contained in $a:d$ and disjoint.\footnote{Let $\delta = \min(b-a, d-b, c-a, d-c, c-b)/3$. This should keep the $\delta$-halos away from the endpoints and $\frac{c-b}{3}$ prevents them from overlapping. This is a footnote as we just need to know that this can be done.} Then Separation tells that there exists intervals $c_\delta$-compatible $e:f$ and $b_\delta$-compatible $g:h$ such that $a:e:f:b$ and $c:g:h:d$ partitions the interval into exactly one Yes interval for each. The following may be helpful to keep in mind which is true by the case we are in and our choices: $a < e < c < f< g < b < h < d$.
Since $a:e$ and $h:d$ are disjoint from the Yes intervals $c:d$ and $a:b$, respectively, they cannot be Yes intervals as we just proved that they need to intersect.
Note that by construction, $e:f$ and $g:h$ are disjoint. So at most one of them can be a Yes interval.
If $e:f$ is a Yes interval, then this implies $g:h$ is a No interval and therefore $c:g$ is a Yes interval. Since $c:g$ is contained in $c:b$, we have $c:b$ is Yes by Consistency.
Similarly, if $g:h$ is Yes, then $e:f$ is No implying $f:b$ is Yes. This is contained in $c:b$ so $c:b$ is Yes.
If both $e:f$ and $g:h$ are No, then $f:b$ is Yes and $c:g$ are Yes. This implies $c:b$ is Yes\footnote{Having proved this result, we can say in this case that the interval $f:g$ would also be a Yes interval as it is the intersection of two Yes intervals.}
That concludes the analysis of the cases. In all cases, $c:b$ is a Yes interval.
Thus, we have the intersection of two Yes intervals is a Yes interval.
\end{proof}
We have further shown that if we have two Yes intervals, one of whose lower endpoint is the same as the upper endpoint of the other, then the common endpoint as a singleton is a Yes interval and this is a rooted oracle.
\begin{corollary}\label{cor:kissing}
If $R$ is an oracle and $R(a\lte b)=R(b \lte c) = 1$, then $R(b:b)=1$.
\end{corollary}
This follows from the proof above as well as the the proposition statement that the intersection of two Yes intervals is a Yes interval, noting the intersection here is $b:b$.
\begin{corollary}\label{cor:finite-inter}
For a given oracle, a finite collection of its Yes intervals will have a non-empty intersection which is itself a Yes interval.
\end{corollary}
\begin{proof}
We have already established it for pairs. Let $\{A_i\}_{i=1}^n$ be a collection of Yes intervals. Define $B_1 = A_1$, $B_i = B_{i-1} \cap A_i$ for $i > 1$. From having $B_{i-1}$ is a Yes interval, we have that the interval $B_i$ exists and is a Yes interval by the proposition. Starting with $B_1$ being a Yes interval, we can then use a finite number of iterations to reach $B_n$ with the conclusion that it is non-empty and is a Yes interval. It is obviously the intersection of all of the $A_i$.
\end{proof}
For infinite collections of intervals, the intersection can be empty such as all of the Yes intervals for the Oracle of the $\sqrt{2}$ as discussed later. It can also fail to be an inclusive rational interval. For examples and related discussions, see Section \ref{sec:ni}.
\begin{corollary}\label{cor:disjoint-yes}
If $R$ is an oracle, $I$ is a Yes interval and $J$ is an interval disjoint from $I$, then $J$ is a No interval.
\end{corollary}
\begin{proof}
We can prove this in two ways. The first is that if $J$ was a Yes interval, it would have to intersect $I$. This is fine except it assumes $J$ has a Yes / No answer. To definitively have a conclusion, we can instead use the unionized interval of $I= a\lte b$ and $J = c\lte d$, namely $K = a \lte d$. This is a Yes interval by Consistency. Disjointness tells us that $b < c$. We can then apply Separation using $m$ and $\delta$ as in the proof of the proposition. This time, however, we conclude that $m+\delta:d$, which contains $c:d$, is a No interval since the interval $a:e$, containing $a:b$, must be a Yes interval and the Separation property affirmatively concludes the other two intervals are No intervals.
\end{proof}
When establishing that disjoint intervals cannot both be Yes intervals, we can be explicit.
\begin{proposition}
Given an oracle $R$ and four rational numbers $a \leq b < c \leq d$. Then it can be determined that either $R(a:b) =0$ or $R(c:d) = 0$.
\end{proposition}
\begin{proof}
Let $l = c-b$. By the bisection approximation, we can find a Yes interval $I$ whose length is less than $l$. This interval cannot intersect both $a:b$ and $c:d$ due to its length, i.e., for two points to be in $I$, then their difference must be less than or equal to the length of the interval. If $I$ overlaps both $a:b$ and $c:d$, then $b$ and $c$ both must be in it but they cannot be as that would require $b-c < l$ contradicting the length of $l$. Any interval not intersecting the Yes interval $I$ is a No interval, as we showed above. At least one of the two given intervals is disjoint from $I$ and thus is a No interval.
\end{proof}
\begin{corollary}\label{cor:disjoint}
If $R$ is an oracle and $a:b$ and $c:d$ are disjoint intervals, then at most one of them is a Yes interval.
\end{corollary}
Let us now establish that the union two overlapping No-intervals is a No interval.
\begin{proposition}\label{pr:union}
Let $R$ be an oracle and $I$ and $J$ two intersecting No intervals. Then $I \cup J$ is a No interval.
\end{proposition}
\begin{proof}
Let $I = a\lte b$, $J = c\lte d$ with $a \leq c$. This can be assumed without loss of generality due to relabelling.
Since $a:a$, $b:b$, $c:c$, and $d:d$ are contained in No intervals, they are also No intervals. This implies, by the Closed property, that there is a $\delta$ such that $a_\delta$, $b_\delta$, $c_\delta$, and $d_\delta$ are all No intervals. By the Bisection Approximation, we can find an $R$-Yes interval $e:f$ whose length is shorter than $\delta$. By this choice, if $e:f$ contained one of $a$, $b$, $c$, or $d$, then $e:f$ would be wholly contained in the $\delta$-halo for that endpoint as $q_\delta$ contains all intervals whose length is less than $\delta$ and contains $q$. But this is not possible because Consistency would demand that it be a No interval.
If $e:f$ intersects $a:d$, then it either contains one of the endpoints or is strictly contained in $a:b$ or $c:d$. We have ruled out the endpoints. Thus, it is either contained in $a:b$ or $c:d$. But those are No intervals and thus, $e:f$ would be a No interval. That contradicts $e:f$ being a Yes interval.
We therefore have $e:f$ is a Yes interval disjoint from the interval $a:d$. Thus, $a:d$ is a No interval.
\end{proof}
Notice how once we have the $\delta$ as guaranteed to be producible from the rule as stated in the Closed property, we can then be very explicit in using the Bisection Approximation to get an interval that is disjoint from the No intervals.
We have just used that one method of demonstrating that $R(a:b)=0$ for some given interval $a:b$ is to produce an interval $c:d$ disjoint from $a:b$ such that $R(c:d)=1$. On the other hand, if we could show that all neighborly $R$-Yes intervals intersect $a:b$, but none of them are strictly contained in $a:b$, then exactly one of $a$ or $b$ is contained in all such intervals. We could determine which one it is by the bisection approximation. Let's say $a$ is in all of them. Then $R(a:a)=1$ by the Closed property and thus $R(a:b)=1$ as well. This situation is where the usual computational difficulties arise.
\begin{proposition}\label{pr:down-to-one-halo}
Given an oracle $R$, an interval $a \lt b$, and a width $\delta$, then it can be established that one of the following holds: 1) $R(a : b)=0$; 2) $R(a : b) = 1$; 3) $R(b_\delta) = 1$; or 4) $R(a_\delta)=1$.
\end{proposition}
\begin{proof}
Let $l=|b-a|$ be the length of $a:b$. Let $c:d$ be an $R$-Yes interval of length less than $\delta$ and less than $l$. This exists by the Bisection Approximation. If $c:d$ is contained in $a:b$ or disjoint from $a:b$, then $a:b$ is Yes or No, respectively. The other case is that either $a$ is contained in $c:d$ or $b$ is contained in $c:d$. Note that because the length of $c:d$ is less than $l$, it cannot contain both endpoints. If $c:d$ contains $a$, then $a_\delta$, whose length is $2 \delta$, contains $c:d$. Thus $a_\delta$ is a Yes interval. Similarly, if $c:d$ contains $b$, then $b_\delta$ is a Yes interval. That is what we were to show.
\end{proof}
We can extend the buffer idea around a No singleton to a No interval. A $\delta$-halo of an interval $I= a\lte b$ is the interval $I_\delta = a - \delta:b+\delta$.
\begin{corollary}\label{cor:halo-for-no}
Let $R$ be an oracle and $I$ be a No interval. Then there exists a $\delta$-halo of $I$ which is a No interval.
\end{corollary}
\begin{proof}
Let $I = a:b$. Because $a$ and $b$ are in No intervals, we have that $a:a$ and $b:b$ are No singletons. Thus, there exists a width $\delta$ such that $a_\delta$ and $b_\delta$ are No intervals. We can then use the union proposition to say that $I_\delta = a_\delta \cup a:b \cup b_\delta$ is a No interval. That is what was to be shown.
\end{proof}
We will also find the following couple of propositions to be useful.
\begin{proposition}\label{pr:subinter}
Let $R$ be an oracle with an $R$-Yes neighborly interval $I$. Then $I$ contains a smaller interval that excludes any endpoint of $I$ which corresponds to a No singleton.
\end{proposition}
\begin{proof}
Let $a$ represent an endpoint which is a No singleton and $b$ be the other endpoint. Then there exists a $\delta$-halo of $a$ which is an $R$-No interval and, since we can always take $\delta$ smaller for this need, we can also assume $\delta < |b-a|$.
We are going to use the Separation property. We have two cases. If $a< b$, then we choose $c = a+ \delta < b$. If $a>b$, then we choose $c = a- \delta > b$. In either case, the width $\delta$ we choose is $\delta/2$.
By separation, we have the existence of an interval $e:f$ such that $a:e:c:f:b$ and exactly one of $a:e$, $e:f$, or $f:b$ is a Yes interval. Because $a:e$ is contained in the No interval $a_\delta$, Consistency requires that it is a No interval. This implies that $e:b$ is a Yes interval. This is what we were to show.
If both endpoints are No singletons, then we can apply this twice to get two smaller Yes intervals, each one excluding one endpoint. Since Yes intervals intersect in a Yes interval, their intersection is a Yes interval which simultaneously excludes both endpoints.
\end{proof}
Note that if we wish to be explicit about the size, we can take $\delta$ to be the minimum of half the length of the interval and the $\delta$'s from the Closed property for the No endpoint(s). Then $I$ shortened by $\delta/2$ away from any No endpoint is a Yes interval.
\begin{corollary}
The above proposition applies for all Yes intervals for a neighborly $R$ oracle.
\end{corollary}
This is immediate since all singletons are No intervals for neighborly oracles.
\begin{proposition}\label{pr:multi}
Given an oracle $R$ and an $R$-Yes interval $a\lt b$ and a $\delta>0$, any finite rational partition of $a:b$ will yield exactly one Yes interval that is strictly between the partition points, possibly including one of the two endpoints, or is an interval containing a partition point whose length is no more than $\delta$.
\end{proposition}
This is repeated application of the Separation property.
\begin{proof}
Let $a < c_1 < c_2 < c_3 < \cdots < c_n < b$ be a given rational partition of the interval $a:b$ where all of the $c_i$ are rationals.
Let $\delta_h$ be the minimum of $\delta$ and a third of the distances between the partition points, including the endpoints.
We start with looking at $a:c_1:b$. By the Separation property using a width of $\delta_h$, we have the existence of $e_1$ and $f_1$ such that exactly one of $a:e_1$, $e_1:f_1$, or $f_1:b$ is Yes.
If $a:e_1$ is Yes, then so is $a:c_1$ and we are done. If $e_1:f_1$ is Yes, then $(c_1)_\delta$ is Yes and we are done. If not, we iterate by applying Separation to $f_1:b$ using $c_2$ which is in $f_1:b$ due to the choice of $\delta_h$.
Let us then assume that we have $f_{i-1}:b$ is a Yes interval, where $f_{i-1} < c_i$. Then Separation using $c_i$ and $\delta_h$ leads to the existence of $e_i:f_i$ containing $c_i$ such that exactly one of $f_{i-1}:e_i$, $e_i:f_i$, or $f_i:b$. If either of the first two are Yes, we are done as $f_{i-1}:e_i$ is contained in $c_{i-1}:c_i$ and $e_i:f_i$ is contained in $(c_i)_\delta$. If $f_i:b$ is the Yes interval, then iterate again using it and Separation.
We do this until we are done or at $f_n:b$. At that point, we have established that $a:f_n$ is a No interval by being a union of overlapping No intervals and $f_n:b$, contained in $c_n:b$, is Yes, as desired.
\end{proof}
\begin{proposition}\label{pr:no-is-disjoint}
If an interval $I$ is a No interval for an oracle $R$, then there exists an $R$-Yes interval disjoint from $a:b$.
\end{proposition}
\begin{proof}
We established previously that there exists a width $\delta$ such that $I_\delta$ is a No interval. Using that $\delta$ and the Bisection Approximation, there is a Yes interval $J$ whose length is less than $\delta$.
The interval $J$ cannot be wholly contained in the No interval $I_\delta$ as $J$ is a Yes interval. Let $c$ be a number in $J$ which is not in $I_\delta$. Then $c_\delta$ contains $J$ and is disjoint from $I$ as the distance from $c$ to $I$ is greater than $\delta$. Thus $J$ is disjoint from $I$ as well as $c_\delta$ being a Yes interval.
\end{proof}
\begin{proposition}\label{pr:exclude-singleton}
If $a : b$ is a Yes neighborly interval and $a:a$ is a No singleton, then there exists a number $c$ in $a:b$, not equal to $a$ or $b$, such that $c : b$ is a Yes interval.
\end{proposition}
\begin{proof}
Let $\delta$ be such that $a_\delta$ is a No interval. This exists by the Closed property. Let us also take $\delta$ to be less than half of $|b-a|$. Pick a number $d$ that is strictly contained in both $a_\delta$ and $a:b$. Pick a width $\varepsilon$ such that $d_\varepsilon$ is strictly contained in $a_\delta$. Then Separation gives us a $d_\varepsilon$-compatible interval $e:f$ such that $a:e:d:f:b$ and exactly one of $a:e$, $e:f$, or $f:b$ is a Yes interval. But since $a:e$ and $e:f$ are contained in the No interval $a_\delta$, they must be No. Thus, $f:b$ is a Yes interval and $f$ is strictly contained in $a:b$.
\end{proof}
\subsubsection{Filters}
The set of closed (rational) intervals forms a partially ordered set where the ordering is that of inclusion. From this perspective, the set of Yes intervals for an oracle form a filter on this partially ordered set:
\begin{enumerate}
\item The set of Yes intervals is not empty thanks to the existence requirement.
\item Consistency is the second requirement of a filter, namely, if $A$ is Yes, and $A$ is contained in $B$, then $B$ is Yes.
\item The intersection of two Yes-intervals being a Yes-interval satisfies the filter requirement that for any two elements in the filter, there is a third in the filter which is contained in both.
\end{enumerate}
The set of Yes intervals for a resolvable oracle is also an ultrafilter which is a non-trivial filter that cannot be extended any further. This follows from the the fact that any No interval is disjoint from some Yes interval. For if we added a No interval $I$ to the set of Yes intervals, then the intersection of $I$ with at least one of the Yes intervals would be empty. Thus, either we need to add the empty interval to this filter, making it trivial as all intervals could be said to contain the empty interval, or we no longer have a filter. In either case, we no longer have an ultrafilter.
A singleton oracle would be a principal ultrafilter, meaning there is a smallest element in the filter. For a singleton oracle, this is the closed interval which consists of just that rational number. A neighborly oracle would correspond to the free ultrafilters, namely, there is no smallest element.
Sebastian Schöner wrote an excellent blog entry describing ultrafilters as a way of zooming in on a point and how this allows ultrafilters on Hausdorff topological spaces to be the mechanism for compacting them.\footnote{\url{https://blog.s-schoener.com/2019-01-05-compactness/}} In the realm of constructions and real numbers, often ultrafilters are used in the connection of creating a version of the reals with infinitesimals. Such a construction can then be quotiented out to obtain the reals. A very readable presentation is given by Lothar Sebastian Krapp.\footnote{\url{https://www.math.uni-konstanz.de/~krapp/research/Constructions_of_the_real_numbers.pdf}} There is also an approach based on minimal Cauchy filters; we discuss that in Section \ref{sec:mincauchy}.
While the set of oracles can be thought of as the set of sets of Yes intervals and thus as a set of ultrafilters, our approach is designed to be more focused on the mechanism of producing the Yes intervals. One can think of the oracles as doing the zooming into the neighborhood of the real number whereas the ultrafilter approach is more analogous to having a stack of prepared slides describing the zooming. In other words, oracles answer the question as to how to produce the ultrafilter for a given desired real number. We also do not require, in some sense, having the whole ultrafilter in our hands. We are content with the idea of being able to practically decide for any, possibly fuzzed out, given interval whether it is in the ultrafilter or not.
\subsection{Equality and Ordering}
Two oracles are equal if they agree on all inclusive rational intervals. To prove inequality, it is therefore sufficient to find a disagreement. The basic tool is to find two disjoint intervals that we can guarantee different results on.
If we have two different ``real numbers'', do we get different oracles for them? Since we are defining real numbers, this gets a little tricky, but we can imagine that what we mean by knowing the two numbers are different is that they are separated by a rational number. Let's assume $a < R < p < S < b$ where $R$ and $S$ are our two distinct real numbers, $p$ is a known rational that separates them, and $a$ and $b$ are two rationals we know sandwich the two reals. Then $a:p$ is a Yes-interval for the Oracle of $R$ while $p:b$ is a Yes-interval for the Oracle of $S$, and each of those intervals are No-intervals for the other oracle.
For example, if we we want to distinguish the square roots of 2 and 3 from one another,\footnote{We will discuss square roots later; just assume the usual ordering properties for now.} then $a = 1$, $p = \tfrac{3}{2}$, and $b = 2$ would suffice as $1 < \sqrt{2} < \tfrac{3}{2} < \sqrt{3} < 2$. Let $R$ be the Oracle of $\sqrt{2}$ and $S$ be the Oracle of $\sqrt{3}$, then we should have $R(1:\tfrac{3}{2}) = 1$, $R(\tfrac{3}{2}:2) = 0$, $S(\tfrac{3}{2}:2) = 1$, $S(1, \tfrac{3}{2}) = 0$. Thus, these oracles are not equal. Using Proposition \ref{pr:subinter}, we can shorten these intervals inwards away from the endpoints as we know that 1, $\frac{3}{2}$, and do not square to $2$ or $3$ and are thus No singletons. Therefore, we have disjoint intervals that they differ on and it would be reasonable to say $R < S$ which our definition below does say.
If the oracles $R$ and $S$ cannot find an interval on which they disagree, but we also cannot prove that they agree on all intervals, then we can talk about compatibility and the resolution of that compatibility.
Let $R$ and $S$ be two oracles. We adopt the following relational definitions:
\begin{enumerate}
\item $R=S$. $R$ and $S$ are equal if and only if they can be shown to agree on all intervals. Even for intervals that they are not defined on, if they can be shown that they would agree if defined on them, then we accept that they are equal.
\item $R < S$. $R$ is less than $S$ if and only if there exists $a:b < c:d$ such that $R(a:b) =1 = S(c:d)$. As $a:b$ and $c:d$ are disjoint, necessarily $R(c:d) = 0 = S(a:b)$.
\item $R > S$. $R$ is greater than $S$ if and only if there exists $a:b > c:d$ such that $R(a:b) =1 = S(c:d)$. As $a:b$ and $c:d$ are disjoint, necessarily $R(c:d) = 0 = S(a:b)$. This is equivalent to the statement that $R$ is greater than $S$ if and only if $S < R$.
\item $a:R?S:b$. $R$ and $S$ are $a:b$ compatible if $R(a:b)=S(a:b) = 1$.
\end{enumerate}
Those are expressions of what can be proven. We also have notations that can express some knowledge, but not definiteness. The expression $R \leq S$ would imply that we have compatibility between $R$ and $S$, but we also know that $R > S$ is impossible. Similarly, $R \geq S$ would imply that $R < S$ is not possible. For example, if we had an oracle $R$ such that $a:b$ is always No whenever $a$ and $b$ are both negative rational numbers, then $R < 0$ would not be possible. So we could write $R \geq 0$. This is similar to what is done in \cite{bridger}.
Another notation is $R?S$ which we would read as $R$ and $S$ are compatible. By this we mean that $R(a:b) = S(a:b)$ for all tested intervals $a:b$.
The interval $a:b$ is the \textbf{resolution of the compatibility of $R$ and $S$} if it is the shortest known interval which is both an $R$-Yes and an $S$-Yes interval. If we use intervals that are explicitly asked about, this would necessarily be a finite collection and thus, the intersection of all of them would be a Yes interval for both $R$ and $S$. As we will see, if we have an infinite collection of mutually Yes intervals that are arbitrarily small, then the two oracles are essentially equal.
If $R(a:b) = 1$, $S(c:d) = 1$, then the intervalized union of the two intervals is both $R$ and $S$ Yes intervals implying the resolution of the compatibility of $R$ and $S$ is contained in that union.
A useful proposition is if two oracles disagree on intervals that solely intersect at one endpoint, then those intervals can be shrunk away from that endpoint and definitive ordering can be deduced.
\begin{proposition}
If $R$ and $S$ are oracles such that $R(a:b)=1$, $R(b:c)=0$, $S(a:b) = 0$, and $S(b:c)=1$, then either $a < c$ and $R < S$ or $c < a$ and $S < R$.
\end{proposition}
\begin{proof}
Because $R(b:c) = 0$ and $S(a:b)=0$, $b:b$ is both an $R$-No singleton and an $S$-No singleton. Because $R(a:b)=1$ and $S(b:c)=1$, we have that $a \neq b$ and $c \neq b$ otherwise $b:b$ would be a Yes singleton. Because No intervals cannot contain Yes intervals, we have $R$ tells us that $c:a:b$ is not possible and $S$ tells us that $a:c:b$ is not possible. Thus, $a:b:c$ is what we have.
We have two cases. Either $a<c$ or $c>a$. We will use Proposition \ref{pr:subinter}.
If $a<c$, then there exists $\delta > 0$ such that $a \lte b-\delta$ is $R$-Yes, $S$-No while $b+\delta \lte c$ is $S$-Yes and $R$-No. These are disjoint with $b-\delta < b + \delta$. Therefore, $R < S$.
If $c<$, then there exists $\delta > 0$ such that $c \lte b-\delta$ is $S$-Yes, $R$-No while $b+\delta \lte a$ is $R$-Yes and $S$-No. These are disjoint with $b-\delta < b + \delta$. Therefore, $S < R$.
\end{proof}
As an example, we can show that $\sqrt{2} < \sqrt{3}$. As we will discuss in Section \ref{sec:roots}, the Oracle of the $\sqrt{n}$ has the rule that $0 \lte a\lte b$ is a Yes interval if $a^2 \leq b^2$. Thus, $1:\frac{3}{2}$ is a Yes interval of $\sqrt{2}$ but a No interval of $\sqrt{3}$ while $\frac{3}{2}:2$ is a Yes interval of $\sqrt{3}$ but not $\sqrt{2}$. Because $1 < 2$, we have $\sqrt{2} < \sqrt{3}$ by the above proposition.
In the constructive texts, they formulate the $\varepsilon$-Trichotomy proposition which states that two real numbers $\alpha$ and $\beta$ satisfy either $\alpha < \beta$, $\beta < \alpha$, or $|\alpha - \beta| < \varepsilon$ for all $\varepsilon > 0$. Their assertion is that this is what can be proven constructively, i.e., with enough finite resources, one can establish this to be true for two given real numbers and an $\varepsilon$. See \cite{bridger}, page 57. We will prove it below for oracles.
We now state and prove a couple of basic statements required for the definition above to be correct.
\begin{proposition}[Well-Defined]\label{pr:wd}
Both equality and inequalities are well-defined and exclusive to one another.
\end{proposition}
\begin{proof}
Equality is defined comprehensively across all intervals, leaving no room for differences.
Let us prove that if $R < S$ then we cannot have $R=S$ or have $R > S$. For both of these, we use Corollary \ref{cor:disjoint} which states that disjoint intervals cannot both be Yes-intervals.
Let us assume that $R<S$ with the implied Yes intervals $a:b < c:d$ where $R(a:b)=1 =S(c:d)$.
To show that they are not equal, we need to demonstrate that the rules give a different result on an interval. By the disjointness of these intervals, we know that $R(c:d) = 0 = S(a:b)$. $R$ and $S$ therefore differ on both $c:d$ and $a:b$ which establishes that they are not equal as oracles.
Now we look to prove that $R>S$ cannot also be true. If $R > S$, then we have intervals $e:f > g:h$ such that $R(e:f) = 1 = S(g:h)$. Since Yes intervals intersect, we have the existence of $p$ in common to both $a:b$ and $e:f$ as well as $q$ in common to both $c:d$ and $g:h$. From $e:f > g:h$, we have $p > q$, and from $a:b < c:d$, we have $p < q$. This is a contradiction and thus $R>S$ cannot hold true if $R<S$ holds true.
\end{proof}
\begin{proposition}
Given oracles $R$ and $S$, $R$-Yes interval $a\lte b$, and $S$-Yes interval $c\lte d$, we have $R ? S$ based on the intervalized union of the two intervals.
\end{proposition}
\begin{proof}
Let $e= \min(a,c)$ and $f = \max(b,d)$. Then, we have $e:a:b:f$ and $e:c:d:f$. Since $e:f$ contains both $a:b$ and $c:d$, it is a Yes interval for both $R$ and $S$. We therefore have $e:R?S:f$.
\end{proof}
We say that two oracles $R$ and $S$ are \textbf{$\varepsilon$-compatible} if there exists an interval $e:f$ of length not more than $\varepsilon$ such that $e: R ? S : f$. This is the same as saying that we can find an interval of length not more than $\varepsilon$ which is a Yes interval for both $R$ and $S$. We may denote this by $R \overset{\varepsilon}{\approx} S$.
\begin{proposition}[$\varepsilon$-Trichotomy]\label{pr:tri}
Given $\varepsilon > 0$, either $R < S$, $R > S$, or $R \overset{\varepsilon}{\approx} S$.
\end{proposition}
\begin{proof}
By the Bisection Approximation, we can find an $R$-Yes interval $a \lte b$ and $S$-Yes interval $c \lte d$ each of whose length is less than $\delta = \frac{\varepsilon}{2}$.
If $b < c$, then $a:b < c:d$ and $R < S$. If $d < a$, then $c:d < a:b$ and $S < R$.
We can therefore assume $b \geq c$ and $d \geq a$. This leads to two possible orderings. In the first, we have $a:c:b:d$ and the interval $a:d$ is a Yes interval for both oracles due to Consistency. The length of the interval is less than $2 \delta = \varepsilon$. The other option is $c:a:d:b$ whose common Yes interval, also of length $\varepsilon$, is $c:b$.
We have therefore established, explicitly, that one of these three options occurs.
\end{proof}
From the perspective of a single comparison of given Yes-intervals, the only way equality could be established is if those intervals were equal singletons. To establish equality, particularly for neighborly oracles, one must have an argument that somehow applies to an infinite number of intervals. We have some statements to that effect in Section \ref{sec:eq}.
\begin{proposition}[Transitive Law]\label{pr:transitive}
Let $R$, $S$, and $T$, be oracles that satisfy $R<S$ and $S < T$. Then $R < T$.
\end{proposition}
\begin{proof}
By the assumptions, we have the existence of $a:b < c:d$ where $R(a:b) = 1 = S(c:d)$ and $R(c:d) = 0 = S(a:b)$. We also have the existence of $e:f < g:h$ where $S(e:f) = 1 = T(g:h)$ and $S(g:h) = 0 = T(e:f)$. We will show $a:b < g:h$.
Let $m:n$ be the intersection of $c:d$ with $e:f$. This exists since Yes intervals for an oracle intersect in a Yes interval (Proposition \ref{pr:inter}) and thus $S(m:n) = 1$. Since $m:n$ is contained in $c:d$, it satisfies $a:b < m:n$. Similarly, $m:n$ is contained in $e:f$ which gives us $m:n < g:h$. Since the inequality of intervals is transitive, we have $a:b < g:h$ as was to be shown.
\end{proof}
We can also add in definitions of the customary real intervals. While we could rely on the customary definitions based on the ordering relations, we will cast it in the language of oracles. In what follows, we assume $\alpha < \beta$ are oracles, $a\lte b$ represents an almost generic $\alpha$-Yes interval, $c\lte d$ represents an almost generic $\beta$-Yes interval, and that the not-quite generic part are the requirements that $b < c$ and none of the endpoints are roots of $\alpha$ or $\beta$. Then:
\begin{enumerate}
\item The oracle $\gamma$ is in the closed interval $[\alpha, \beta]$ if $a \lte d$ is a $\gamma$-Yes interval for all such $\alpha$ and $\beta$-Yes intervals.
\item The oracle $\gamma$ is in the open interval $(\alpha, \beta)$ if $b\lte c$ is a $\gamma$-Yes interval for some such $\alpha$ and $\beta$-Yes intervals.
\item The oracle $\gamma$ is in $[\alpha, \beta)$ if $a\lte c$ is a $\gamma$-Yes interval for all such $\alpha$-Yes intervals and for some such $\beta$-Yes interval.
\item The oracle $\gamma$ is in $(\alpha, \beta]$ if $b\lte d$ is a $\gamma$-Yes interval for all such $\beta$-Yes intervals and for some such $\alpha$-Yes interval.
\item The oracle $\gamma$ is in the open interval $(\alpha, \infty)$ if $b$ is the lower endpoint for a $\gamma$-Yes interval for some $\alpha$-Yes interval.
\item The oracle $\gamma$ is in the open interval $(-\infty, \alpha)$ if $a$ is the upper endpoint for a $\gamma$-Yes interval for some $\alpha$-Yes interval.
\item The oracle $\gamma$ is in the half-closed interval $[\alpha, \infty)$ if for all $\alpha$-Yes intervals, $a$ is the lower endpoint for a $\gamma$-Yes interval.
\item The oracle $\gamma$ is in the open interval $(-\infty, \alpha]$ if for all $\alpha$-Yes intervals, $b$ is the upper endpoint for a $\gamma$-Yes interval.
\end{enumerate}
\subsubsection{Equality}\label{sec:eq}
\begin{proposition}\label{pr:reflexive}
The equality relation is reflexive, symmetric, and transitive.
\end{proposition}
\begin{proof}
This is immediate from the properties of equality of natural numbers, particularly the numbers 0 and 1. Indeed, the statements translated to intervals are the proofs:
\begin{itemize}
\item Reflexive ($R=R$): $R(a:b)=R(a:b)$ for all intervals $a:b$ and rules $R$.
\item Symmetric ($R=S \iff S=R)$: For all intervals $a:b$ and rules $R$, $S$, $R(a:b)=S(a:b)$ if and only if $S(a:b) = R(a:b)$
\item Transitive ($R=S \And S=T \implies R=T)$: If $R(a:b)=S(a:b)$ and $S(a:b) = T(a:b)$ then $R(a:b)=T(a:b)$. This holds for all intervals $a:b$ and rules $R$, $S$, $T$.
\end{itemize}
\end{proof}
If we have $a:R?S:b$, then they also agree (Yes) on all intervals that contain $a:b$ as well as all intervals disjoint from $a:b$ (No).
Thus, two oracles could be equal, unequal, or compatible. The latter is for rules that we cannot find an interval of disagreement, but we have not been able to establish equality.
We next prove that two oracles whose Yes intervals always overlap are essentially the same oracle.
\begin{proposition}\label{pr:overlap}
Let $R$ and $S$ be two oracles such that all of their Yes intervals intersect. Then $R$ and $S$ are $\varepsilon$-compatible for all $\varepsilon > 0$.
\end{proposition}
\begin{proof}
Let rational $\varepsilon > 0$ be given. By the Bisection Approximation, we have the existence of an $R$-Yes interval $a:b$ and an $S$-Yes interval $c:d$, both of which can be assumed to have lengths less than $\frac{\varepsilon}{2}$. Because of the assumption, $a:b$ and $c:d$ overlap. This implies that their union exists and has length no more than the sum of their lengths which is at most $\varepsilon$. Since the union contains both Yes intervals, by Consistency, it is a Yes interval for both $R$ and $S$. This is what was needed to be $\varepsilon$ compatible.
\end{proof}
The question then becomes whether these rules are exactly equal. There is the issue of not being able to establish a result for certain intervals. This prevents us from asserting total equality, but we can assert that if they both are defined, then they must agree.
\begin{proposition}
Let oracles $R$ and $S$ be $\varepsilon$-compatible for all $\varepsilon >0$. Given an interval $a\lt b$ and a width $\delta$, then it can be established that one of the following holds: 1) $R(a:b) = S(a:b) = 1$; 2) $R(a:b)=S(a:b)=0$; 3) $R(a_\delta) = S(a_\delta)$; or 4) $R(b_\delta)=S(b_\delta)= 1$.
\end{proposition}
This is essentially the same argument as Proposition \ref{pr:down-to-one-halo} though I fail to see how to use the proposition itself to prove it as we need to insert a mutually compatible interval.
\begin{proof}
Let $l=|b-a|$ be the length of $a:b$. By assumption, there exists an interval $c:d$ whose length is less than $\delta$ and $l$ which is both an $R$-Yes interval and $S$-Yes interval. If $c:d$ is contained in $a:b$, then $R(a:b)=S(a:b)=1$. If $c:d$ is disjoint from $a:b$, then $R(a:b)=S(a:b)=0$.
The other case is that either $a$ is contained in $c:d$ or $b$ is contained in $c:d$. Note that because the length of $c:d$ is less than $l$, it cannot contain both endpoints. If $c:d$ contains $a$, then $a_\delta$, whose length is $2 \delta$, contains $c:d$. Thus $R(a_\delta)=S(a_\delta) = 1$. If $c:d$ contains $b$, then $R(b_\delta)=S(b_\delta)=1$.
\end{proof}
An immediate corollary is that we can always get an answer on an interval if we expand it a bit:
\begin{corollary}
Let oracles $R$ and $S$ be $\varepsilon$-compatible for all $\varepsilon >0$. Then given an interval $I$ and $\delta > 0$, either $R(I)=S(I)$ or $R(I_\delta)=S(I_\delta)=1$.
\end{corollary}
\begin{proof}
If $R(I)$ and $S(I)$ cannot be related, then we are in the case of a $b_\delta$ or $a_\delta$ being a mutual Yes interval. Since both are included in $I_\delta$, we have that $I_\delta$ is a mutual Yes interval.
\end{proof}
While we have almost universal agreement, we can assert that they are equal if both are established to have results.
\begin{proposition}\label{pr:epsilon-compatible}
If the oracles $R$ and $S$ are $\varepsilon$-compatible for all $\varepsilon > 0$, then $R(I)=S(I)$ for all intervals $I$ upon which $R$ and $S$'s values have been established.
\end{proposition}
\begin{proof}
Let $I = a \lte b$.
Assume that $R(I)$ and $S(I)$ are established. We only need to show that the case of them being unequal is not possible. Without loss of generality, we may assume $S(I)=0$.
Since $S$ is No on $I$, by Corollary $\ref{cor:halo-for-no}$, there exists $\delta > 0$ such that $I_\delta$ is a $S$-No interval. We use $\varepsilon$-compatibility as we did above to generate an interval $J$ that is both $R$ and $S$ Yes with length less than $\delta$. The length of $J$ prevents it from containing $I_\delta$ and $J$ cannot be contained in $I_\delta$ as $I_\delta$ is a No interval. Thus either $J$ is disjoint from $I_\delta$ implying $I$ is a No interval for $R$ or $J$ strictly overlaps $I_\delta$. In that latter case, there is a portion of $J$ outside of $I_\delta$; let's pick a number in there and call it $c$. $c_\delta$ is disjoint from $I$ and so is $J$. Thus, $R$ must be No on $I$ as $I$ is disjoint from a Yes interval.
Hence, $R$ and $S$ agree if either of them is a No interval. If both are Yes intervals, then they obviously agree. The only case left is when at least one of their values is not established.
\end{proof}
The next statement is used in establishing the distributive rule for oracles.
\begin{corollary}
If $R$ and $S$ are two oracles such that whenever $R(a:b) = 1$, there exists an interval $c:d$ contained in $a:b$ such that $S(c:d) = 1$. Then $R=S$ on all intervals their values have been established on.
\end{corollary}
\begin{proof}
It should be clear that $R$ and $S$ are $\varepsilon$-compatible for all $\varepsilon$. Indeed, let $\varepsilon >0$ be given. Then choose an $R$-Yes interval $a:b$, by the Bisection Approximation, whose length is less than $\varepsilon$. By assumption, there exists an $S$-Yes interval $c:d$ contained in $a:b$. This makes $a:b$ $S$-Yes. Thus, $a:R,S:b$.
As this was for any $\varepsilon >0$, we can use the above statements to conclude that $R$ and $S$ agree on all intervals that they are defined on.
\end{proof}
\subsection{Exploring Equivalence Between Oracles, Cut Relations, and Exclusion Relations}
!Major changes needed
The Consistency, Existence, and Closed Properties are basically background properties, mostly flowing from the definition of the particular oracle. Both Consistency and Closed are often explicitly added in, thus ensuring the uniqueness of the oracle via maximality. Consistency is relatively trivial and mostly uninteresting, but the Closed property is, in many ways, at the heart of the promise and difficulties of real numbers, in whatever way they are defined.
The property that is more negotiable is the Separation property. It can be replaced with something else. I chose the Separation property because of the bisection and mediant approximation schemes. It seems that a good way of approximating is to pick a next number and then replace one of the endpoints with it. Unfortunately, it can be difficult or impossible to evaluate at just the partition point. Thus, we have the user needing to provide a width to allow for a little fuzziness around the partition point.
In the original version of this paper, the Separation property was phrased as having the partition point $c$ in the Yes interval $a:b$ leading to a choice between $a:c$, $c:c$, and $c:b$ as to which was the Yes version. If $c:c$ was Yes, then all three were Yes. This needed to be coupled with another property, the Rooted property, which said there was at most one Yes singleton. This was required because an entire interval could have all of its singletons be Yes with that version of the Separation property.
The reason for the change is largely that it may be impossible to answer the question of whether $c:c$ is a Yes or No interval. But we do insist that we should be able to answer that question for $c_\delta$, for any given $\delta > 0$. It also has the pleasant feature of having clear No intervals.
One equivalent version to the Separation property, which we will talk about later, is requiring Yes-intervals to always intersect and that, given a Yes-interval, we can always find a Yes subinterval of it whose length is less than any given length. This is what a family of overlapping, notionally shrinking intervals is as covered in Section \ref{sec:ni}.
Another equivalent version is to demand the ability to separate any two given points. Namely, the \textbf{Two Point Separation Property} is defined as, for a rule $R$: Given an $R$-Yes interval $a:b$ and two rationals $c < d$ in $a:b$, we can find an $R$-Yes interval $e:f$ contained in $a:b$ such that at least one of the two rationals is not in $e:f$. Furthermore, we also require the \textbf{Disjointness Property}: Any two disjoint intervals cannot both be Yes intervals.
We need to assume disjointness as No does not propagate upwards from the background properties, unlike Yes. For example, consider the rule which is Yes if an interval $a:b$ satisfies either $a^2:2:b^2$ or $a^2:3:b^2$. That is, they ought to contain either $\sqrt{2}$ or $\sqrt{3}$. Consistency and Existence are immediately satisfied. Closed follows since there is no rational number common to all such intervals. The Two Point Separation Property is satisfied since given any rational number, we can find a Yes interval that does not contain it. Yet we want this to fail as we want it to represent a unique answer. This example is ruled out only by the Disjointness property, by considering the intervals $1.4:1.5$ and $1.7:1.8$
In our definition of oracles, it is the Interval Separation Property which rules this out, particularly applying it to the interval $1.4:1.8$ and the separation point $1.6$ with a width of $0.5$. We would then have both $1.4:1.55$ and $1.65:1.8$ being Yes while only one of them ought to be a Yes by the Interval Separation property.
\begin{proposition}
Let $R$ be a rule that satisfies the Consistency, Existence, and Closed Properties. Then requiring the (Interval) Separation property is equivalent to requiring the properties of Two Point Separation and Disjointness.
\end{proposition}
\begin{proof}
Let us assume we have the Separating property holding. And let $a:b$ and $c < d$ be given as in the Two Point Separation Property. Apply the Separating property to the midpoint $m =\frac{c+d}{2}$ with a width of $\frac{d-c}{3}$. Let $e:f$ be the interval provided by that property such that exactly one of $a:e$, $e:f$, or $f:b$ is a Yes interval. Since $c$ is contained in $a:e$ and $d$ is contained in $f:b$, we have that there is a Yes interval that does not contain at least one of $c$ and $d$. This is what was required.
Corollary \ref{cor:disjoint} establishes the Disjointness Property.
For the other direction, let $a < b$ be a Yes interval, $c$ the partition point, and $\delta >0$ the width, as required to test the Interval Separation property. We will use the Two Point Separation property twice with $c$ being one of of the points used.
Note that if we ever come up with a Yes interval that excludes $c$, say, $u:v$, then we can let $L$ be the distance from $c$ to $u:v$ and we have that $c_{L/2}$ is disjoint from $u:v$. Thus, the Disjointness property tells us $c_{L/2}$ is a No interval. $u:v$ will sit on one side of $c$ implying by Disjointness that the other side is No. The $u:v$ side of $c$, outside of $c_{L/2}$ is therefore Yes. This will satisfy the Interval Separation property particularly as No travels downward, allowing a large $L$ to still meet the definition for a small $\delta$. If $L$ is small, then the $e:f$ portion applies that allows us to take the endpoints of $c_{L/2}$ as $e$ and $f$.
With that in mind, consider $c-\delta$ and $c$ as the two points. Apply the separation. If $c$ is not in the Yes interval, we are done as above. That order case is $c$ is in the Yes interval while $c-\delta$ is not. Let $I$ be the Yes interval. We know $c-\delta$ is not in $I$ while $c$ is. Thus, $I$ is disjoint from $a:c-\delta$ implying $a:c-\delta$ is a No interval. We also have $c-\delta:b$ containing $I$ and thus $c-\delta:b$ is a Yes interval.
Next we apply Two Point Separation to $c-\delta:b$ using $c$ and $c+\delta$. Again, if $c$ is excluded from the provided Yes interval $J$, we are done. We can therefore conclude that $c$ is in $J$ and $c+\delta$ is not. Thus, as before, $c+\delta:b$ is No. We therefore have $J$ strictly in $c-\delta:c+\delta$ and $c$ contained in $J$. the endpoints of $J$ are therefore can be taken to be the $e$ and $f$ of the Interval Separation property.
\end{proof}
The Two Point Separation Property generalizes in a straightforward way to other kinds of spaces. The Interval Separation property, on the other hand, feels inherently one dimensional. One might wonder why we focus on the Interval Separation. The reason is that it seems to more align with practical computations of real numbers. Two Point Separation feels a little more removed from the computations without a clear benefit when dealing with real numbers.
\subsection{No New Oracles from the Reals}
In our setup, we are trying to fill in the gaps between the rationals. The question arises, do we get new oracles using real number intervals?
The answer ought to be, and is, no. Let $\bar{R}$ be a meta-real oracle that affirms Yes or No on closed intervals of real numbers, following the same rules as the real oracle definition we have given. The properties are the same except now we are using more general intervals. We need to show that every meta-real oracle is rooted and, therefore, represents a real oracle. Of crucial importance is that the existence property implies the existence of a closed (finite) interval $[\alpha, \beta]$ of real numbers which is Yes for the given meta-real oracle.
We construct the root of a meta-oracle as follows. Define the real oracle rule $R$ as yielding a Yes exactly for rational inclusive intervals $a\lte b$ that satisfy: 1) $a$ is a lower endpoint of a Yes-interval for a lower endpoint real of an $\bar{R}$-Yes interval, e.g., a lower endpoint of an $\alpha$-Yes interval in the real interval above, and 2) $b$ is an upper endpoint of a Yes-interval for an upper endpoint real of an $\bar{R}$-Yes interval, e.g., an upper endpoint of a $\beta$-Yes interval in the real interval above. We will establish two things: $R$ is a real oracle and $\bar{R}$ is the meta-real oracle version of $R$. That is, $R$ and $\bar{R}$ are essentially the same. If we have a rational $p$, we will denote $P$ as the rational-based oracle version of that rational, i.e, the oracle that says yes to any rational interval that contains $p$. If we needed it, the meta-oracle version of it would be $\bar{P}$.
Note that $R(a:b) = 1$, with associated $[\alpha, \beta]$-$\bar{R}$ Yes interval, implies $\bar{R}([A, B]) = 1$ by Consistency since $[A, B]$ contains $[\alpha, \beta]$ as $A \leq \alpha \leq \beta \leq B$.
We first establish that $R$ is an oracle. It is a rule that for every rational interval does assign a Yes or No.
\begin{itemize}
\item Existence. The existence of a finite interval $[\alpha, \beta]$ for $\bar{R}$ and their existence of Yes intervals leads to our ability to make a rational inclusive interval as well.
\item Separation. Let $R(a\lte b) = 1$ and let $a < c < b$ be given along with rational width $\delta$. Since $R(a:b)= 1$, we have $\bar{R}([A, B]) = 1$ and thus, we can use $C$ as the partition point and $\delta/2$ as the width. This leads us to an $\alpha$ and $\beta$ inside of $C_{\delta/2}$ such that exactly one of $[A,\alpha]$, $[\alpha, \beta]$, $[\beta, B]$ is an $\bar{R}$-Yes interval with the others being No intervals. By replacing the Yes interval with bounds, we can translate this into the choice for $R$. For example, if $[A, \alpha]$ is the Yes interval, then $a:\alpha^+$ would be a Yes interval where $\alpha^+$ is a rational number that is an upper endpoint of $\alpha$ and chosen to be before $c$. The No intervals translate similarly, where No intervals being smaller is fine and Yes intervals being enlarged work as well. Enlarging $[\alpha, \beta]$ is why $\delta/2$ is used instead of $\delta$ for the width of $C$.
\item Consistency. If $c\lte a \lte b \lte d$ and $a \lte b$ is an $R$-Yes interval, then there exists a pair $[\alpha, \beta]$ such that $a$ is a lower endpoint of an $\alpha$-Yes interval, $b$ is an upper endpoint of a $\beta$-Yes interval. Thus $c$ is a lower endpoint of an $\alpha$-Yes interval and $d$ is an upper endpoint of a $\beta$-Yes interval by consistency with regards to the $\alpha$ and $\beta$ oracles.
We also have to show that if $c:d$ is No, then $a:b$ is No. If $c:d$ is No, then either $c$ is above all lower endpoints of all real lower endpoints $\alpha$ or $d$ is below all upper endpoints of all real upper endpoints $\beta$. Since $a$ is above $c$ and $b$ is below $d$, that same problematic behavior would transfer and so $a:b$ would be No.
\item Closed. Assume that each $c_\delta$ is a Yes interval of $R$ for all rational $\delta >0$. Given $\delta$, this means that there exists a $\bar{R}$-Yes interval $[\alpha, \beta]$ such that $c-\delta$ is a lower endpoint of $\alpha$ and $c+\delta$ is an upper endpoint of $\beta$. This implies that $C_\delta$ is a Yes interval for $\bar{R}$ which then implies $C$ is the root of the meta-oracle.
We also have to show that given $a:a$ being an $R$-No interval, then there exists $\delta>0$ such that $a_\delta$ is a No interval. The interval $[A,A]$ is a No interval of $\bar{R}$ since if it were a Yes interval, then $a:a$ would be Yes since $a$ is both an upper and lower endpoint of the $A$-Yes interval $[A,A]$, namely, $a:a$ is a $A$-Yes interval. By the Closed property of $\bar{R}$, there is a real $\delta > 0$ such that $A_\delta$ is a No interval. Let $c\lte d$ be a $\delta$-Yes interval such that $c > 0$; this is doable since $\delta >0$. Then we claim that $a_c$ is an $R$-No interval. Let $[\alpha, \beta]$ be a $\bar{R}$-Yes interval which is disjoint from the No interval $A_\delta$. Translate this to an interval $u:v$ where $u$ is a lower endpoint of $\alpha$, $v$ is an upper endpoint of $\beta$, and they are away from the representatives of the bounds of $A_\delta$ due to disjointness. Then $a_c$'s bounds are such that they are all to one side of $u:v$ and hence is a No interval.
\end{itemize}
The other part to establish is that $R$ is the root of $\bar{R}$. To establish this, we need to have that $R$ is in every $\bar{R}$-Yes interval. So let $[\alpha, \beta]$ be an $\bar{R}$-Yes interval. We need to find an $R$-Yes interval that is included in that interval. We can apply the bisection algorithm to either construct an $\bar{R}$-Yes interval that is contained in there or either $\alpha$ or $\beta$ is a root. If it is the latter, then we are done since $R$ will be that root as well given that the upper and lower endpoints of the singleton interval will lead to the upper and lower endpoints of $R$-Yes intervals being the root's Yes-intervals. Otherwise, we have a strictly smaller interval, say $[\gamma, \kappa]$ and we can then find a lower endpoint of $\gamma$-Yes and an upper endpoint of $\kappa$-Yes which is strictly above $\alpha$ and below $\beta$, respectively. Thus, that interval is in the $[\alpha, \beta]$ interval and so $R$ is as well. Since the interval was an arbitrary Yes interval, we have established our claim.
\section{Examples}
It is always good to have examples. In particular, how do we obtain various oracles in common situations?
We shall start with how the rational numbers appear. We then define oracles for $n$-th roots, numbers with more general approximation schemes, and least upper bounds of sets. We also investigate a couple of examples of indeterminate rules. For each of them, we will define the rule and then establish the properties by the definition.
\subsection{Rational Oracles}\label{sec:rat-ora}
Given a rational $q$, we define the Oracle of $q$ as the rule $R(a:b) = 1$ if and only if $q$ is contained in $a:b$. This includes the singleton $q:q$. We may call these rational oracles, rooted oracles, or singleton oracles. The number $q$ is the root of the oracle.
We can verify the properties of the rational Oracle of $q$ as follows:
\begin{enumerate}
\item Existence. $q$ is contained in $q:q$ so $R(q:q)=1$.
\item Separating. If $R(a \lt b) =1$, then $q$ is contained in $a : b$. Let $c$ be strictly in $a:b$ and $\delta > 0 $ given. We have the following scenarios:
\begin{enumerate}
\item $q> c + \delta$. Then $R(c_\delta) = R(a:c-\delta) = 0$, $R(c+\delta:b) = 1$.
\item $q < c- \delta$. Then $R(c_\delta) = R(c+\delta:b) = 0$, $R(a:c-\delta) = 1$.
\item $c-\delta < q < c + \delta$. Then $R(c_\delta)=1$, $R(b:c+\delta) = R(a:c-\delta) = 0$.
\item $q = c+\delta$. Let $e= c-\delta/2$ and $f=c+\delta/2$. Then $R(a:e)=R(e:f) = 0$, and $R(f:b) = 1$
\item $q = c-\delta$. Let $e= c-\delta/2$ and $f=c+\delta/2$. Then $R(f:b)=R(e:f) = 0$, and $R(a:e) = 1$.
\end{enumerate}
\item Consistency. If $R(a:b)=1$, then $q$ is contained in $a:b$. If $c:d$ contains $a:b$, then $q$ is contained in $c:d$. Thus, $R(c:d)=1$. If $R(c:d) = 0$, then $q$ is not in $c:d$ and thus not in any of its subintervals.
\item Closed. Assume $c_\delta$ is Yes for all $\delta > 0$. Yes means $q$ is in each of those intervals. That means $|c-q|<\delta$ for all $\delta > 0$. This is only possible for two rationals if $c-q = 0$ implying $c=q$ and thus, $c:c$ is Yes. If $c:c$ is a No interval, then $c \neq q$. Let $|q-c| = L$. We then have $c_{L/2}$ does not contain $q$ and thus is a No interval.
\end{enumerate}
We will see with the arithmetic operations that these oracles are the natural representatives of the rational numbers, obeying the arithmetic that we would want them to obey.
We also claim that if we have an oracle with rule $R$ such that there is a rational $q$ with $R(q:q)=1$, then it is the Oracle of $q$, whose rule we shall call $Q$. If $R$ and $Q$ are different, then there is an interval $a:b$ on which they disagree. Since $R(q:q) =1$, all the $Q$-Yes intervals are also $R$-Yes intervals by Consistency applied to $R$. Therefore, we need to prove that for a given $Q$-No interval $a:b$, we must also have it be an $R$-No interval. Because it is $Q$-No, it does not contain $q$. It is therefore disjoint from $q:q$. But by the disjoint property, Corollary \ref{cor:disjoint}, we have $R(a:b)=0$. Thus, the two oracles agree on all intervals and we have uniqueness. Notice that Consistency with the fact that $q:q$ is a Yes interval has led to the oracle being fully defined on all intervals.
The property of being closed also prevents having an oracle which agrees with all the $Q$-Yes intervals except $q:q$. Closed forces $R(q:q)=1$ if all $R$-Yes intervals contain $q$.
Now that we have defined the rationals as oracles and defined inequality of oracles, we can prove that Yes intervals do contain their oracles.
\begin{proposition}\label{pr:yes-trap}
If $a\lte b$ is a Yes interval for an oracle $R$, then $a \leq R \leq b$ as oracles. If $a:a$ and $b:b$ are known to be No singletons, then $a < R < b$.
\end{proposition}
\begin{proof}
We need to show that $R < a$ and $R > b$ are not possible.
Let $c\lte d$ be any $R$ Yes interval. Then it must intersect $a:b$ as they are both Yes intervals. If $a$ is in $c:d$, then we do not have $c:d < a:a$. If $a$ is not in $c:d$, then, since it intersects $a:b$, we must have that $a < c \leq b$ which implies $a:a < c:d$. Similarly, if $b$ is in $c:d$, then we do not have $c:d < b:b$. If $b$ is not in $c:d$m then $a \leq d < b$ and so $c:d < b:b$. We can therefore conclude that $a \leq R \leq b$.
If we further assume that $a:a$ and $b:b$ are no Singletons, we use Proposition \ref{pr:exclude-singleton} twice, first to find a $c$ such that $a < c < b$ with $c:b$ being a Yes interval, and then again to find a $d$ such that $c \leq d < b$ with $c:d$ being a Yes interval. By construction, we have that $a < c \leq d < b$ and so $a:a < c:d < b:b$. This establishes that $a < R < b$ if $a:a$ and $b:b$ are No singletons.
\end{proof}
\subsection{Roots}\label{sec:roots}
In this section, $n$ will be a natural number greater than 1. For the positive $n$-th root of a positive rational number $q$, the Oracle rule would be $R(a\lte b) = 1$ if and only if $b> 0$ and $q$ is contained in $\max(a,0)^n:b^n$. If $a\geq 0$, then this is the statement $a^n:q:b^n$. From this definition, if we have $a:a$, then $R(a:a) = 1$ if and only if $a>0$ and $a^n = q$.\footnote{For the $n$-th root of $0$, we can directly prove that the Oracle of 0 is the root. For negative $q$, if $n$ is odd, then we can defined the $n$-th root to be the negative of the $n$-th root of $-q$.}
We will use the monotonicity of $x^n$ for positive $x$ which follows from the basic inequality fact of $ 0 < a < b$ implying $0 < a^n < b^n$.\footnote{This, in turn follows from the fact that $0<a<b$ and $0<c<d$ implies $0<ac<ad$, $0<ad<bd$ and, by transitivity, $0<ac<bd$. Then we setup an induction using the result that $0 < a<b$ and $0 < a^{n-1} < b^{n-1}$ implies $0 < a^n < b^n$. The core inequality fact underlying this is if $0<c$, then $a<b$ implies $ac < bc$. That is, multiplying by a positive number preserves the direction. This is equivalent to asserting that $0 < c (b-a)$ which follows from the product of positive numbers being positive.}
We will need a couple of facts about the existence of rationals that satisfy a given property. If $p \geq 0$, and $p^n > q$, then there exists an $s$ such that $s<p$ and $s^n > q$ (well-known fact, but see Appendix \ref{app:A} Lemma \ref{app:greater}). Let $0 < \varepsilon \leq p-s$. Then $p_\varepsilon$ has the property that all of its elements raised to the $n$-th power are greater than $q$ due to the fact that $s$ is less than any of the elements and the $n$-th power operation is monotonically increasing for positive numbers.
Similarly, if $p \geq 0$ and $p^n < q$, we have the existence of an $s$ such that $s > p$ and $s^n < q$ (Appendix \ref{app:A} Lemma \ref{app:lesser}). This implies that every $0 < \varepsilon \leq s-p$ has the property that all elements of $p_\varepsilon$ raised to the $n$-th power are less than $q$.
We can verify the properties of the Oracle of $\sqrt[n]{q}$ as follows:
\begin{enumerate}
\item Existence. Let $M = \max(q, 1)$. Then we claim $0 < q \leq M^n$. If $q \geq 1$, then $q^{n-1} \geq 1^{n-1} = 1$ and $M^n = q^n \geq q \geq 1 > 0$. If $ q < 1$, then $M=1$ and $0 < q < M^n = 1$. Either way, $R(0:M) = 1$.
\item Separation. Let $a: c: b$ be given such that $R(a < b)=1$ and a width $\delta > 0$ is given. In what follows, part of our choice of $e:f$ will be to ensure that it is a $c_\delta$-compatible interval, something we will not generally comment on directly. Since we can always take a smaller $\delta$, we will assume $c_\delta$ is strictly contained in $a:b$ and that if $ c> 0$, then $c-\delta > 0$. We proceed by cases:
\begin{enumerate}
\item $c \geq 0$, $c^n <q$. Choose $c < f < c+ \delta$ such that $c^n < f^n<q$; this can be done as mentioned above. Let $e$ be such that $c-\delta < e < c$. Then $f^n:q:b^n$ and $R(f:b)=1$. Since we have $\max(a, 0)^n :f^n:q$, we have $R(a:e) = R(e:f) =0$.
\item $c > 0$, $c^n = q$.\footnote{Since we are taking $ q> 0$, we cannot have $ c= 0$ and $c^n = q$.} Since $c$ is not equal to the endpoints, there exists positive rational $e$ and $f$ such that $\max(a,0)^n < e^n < c^n=q < f^n < b^n$ with $ c-\delta:e:c:f:c+\delta$. Thus, $R(e:f)=1$ while $R(a:e)=R(f:b)=0$.
\item $c > 0$, $c^n > q$. Choose $c-\delta < e < c$ such that $c^n > e^n > q$; this can be done as mentioned above. Then $\max(a, 0)^n:q:e^n$ and $R(a:e) = 1$. We also have that $q:e^n:b^n$ implying $R(e:f) = R(f:b) =0$.
\item $c < 0$. This automatically forces $a < 0$. Choose $f <0$.\footnote{ Let $m = \min(|c|/2, \delta)$ and take $e = c-m$ and $f = c+m$. Then $a:e:f:0$ and $e:f$ is $c_\delta$-compatible.} Since $a:b$ is a Yes interval with $a < 0$, we know that $q$ is contained in $0:b^n$. Thus, $R(f:b) = 1$ and $R(a:e) = R(e:f) = 0$.
\end{enumerate}
\item Consistency. Because of the monotonicity of $x^n$ for positive $x$, consistency holds. Namely, assume $a\lte b$ is contained in $c \lte d$ and $R(a:b)=1$. If $c>0$, then so is $a$. We therefore have $c^n \leq a^n$ by monotonicity, $a^n \leq q \leq b^n$ by definition of $a:b$ being a Yes interval, and $b^n \leq d^n$ again by monotonicity. By transitivity, we have $c^n \leq q \leq d^n$ which is what we need for $R(c:d) = 1$. If $c<0$ then we need to show $0 \leq q \leq d^n$. Since $0 \leq q$, and $q \leq b^n$, and $b^n \leq d^n$, this holds.
For the other direction, if $0 < c\lte d$ is a No interval containing $a \lte b$, then that either means $c^n > q$ or $d^n < q$. Because of monotonicity, $a^n >c^n$ and $b^n < d^n$. Thus, the same issue will apply to $a:b$. If $c < 0$ and $c:d$ is a No interval, then either $d \leq 0$ or $d^n < q$. Because, $b < d$, $b$ will satisfy these as well, namely, either $b \leq 0$ or $b^n < d^n < q$. In either case, $a:b$ is a No interval.
\item Closed. Given a rational $c \geq 0$, we can compute $c^n$. If $c^n = q$, then $c:c$ is a Yes interval. If $c^n \neq q$, then $c:c$ is a No interval. As stated above, we can also find $s$, such that $q:s^n:c^n$ with none of them equal to one another. Consider $\delta = |c-s|/2$. Then $c_\delta$ does not include $s$, and by monotonicity, we would have $q : s^n : (c\pm\delta)^n$ which implies that $c_\delta$ is a No interval. Thus, if $c:c$ is a No interval we have a $\delta$ as required. For $c<0$, $c_{|c|/2}$ is entirely negative and is a No interval.
We can also deduce that if there is no such $\delta$, then $c> 0$ and $c^n = q$ implying $c:c$ is a Yes interval.
\end{enumerate}
Is this oracle the $n$-th root of $q$?
While we have not done the arithmetic of oracles yet, the short version is that taking an oracle to the $n$-th power means the new oracle consists of intervals that are the result of applying the $n$-th power to the Yes-intervals of the original oracle. Since $q$ is in $a^n:b^n$ for every $0<a:b$ $\sqrt[n]{q}$-Yes interval, we have that $(\sqrt[n]{q})^n$ does equal the oracle $q$.\footnote{For $n$-th root Yes \-intervals of the form $a:0:b$, the $n$-th powering of that interval will still include $q$ even if $-a>b$. See Section \ref{containment}, item \ref{natpow}.}
Finally, we can establish the ordering of square roots, namely that if $0 \leq p<q$, then $\sqrt[n]{p} < \sqrt[n]{q}$. We do this by narrowing the intervals sufficiently, using Proposition \ref{pr:short} so that the $n$-th power of the intervals are still disjoint. We then argue inequality based on the gap and translate it back down to oracle intervals via monotonicity.
\begin{proposition}
If $0 \leq p <q$, then $\sqrt[n]{p} < \sqrt[n]{q}$, $n > 1$.
\end{proposition}
\begin{proof}
Let $L = q-p > 0$, $M = (q+1)^n$, and $K = \frac{L}{3(n-1)M^{n-1}}$.\footnote{We add 1 to $q$ in case $q < 1$. We want $q < M$ and $M \leq M^m$ for natural $m > 1$. $M$ is in no way an optimal bound.} Since we have established that $n$-th roots are oracles, we can find intervals $a\lt b$ and $c \lt d$ such that $a^n:p:b^n$, $b-a < K$, $c^n:q:d^n$, $d-c < K$, and $d, b < M$. Then $b^n-a^n = (b-a) \sum_{i=0}^{n-1} b^i a^{n-1-i} < (b-a)(n-1) b^{n-1} < K (n-1) M^{n-1} = \frac{L}{3}$ using the fact that $b<M$ implies $b^{n-1} < M^{n-1}$. Similarly, $d^n-c^n < \frac{L}{3}$. This implies that $b^n < a^n + \frac{L}{3} \leq p + \frac{L}{3} = q - \frac{2 L }{3} \leq q - \frac{L}{3} < d^n - \frac{L}{3} < c^n$. Since $b^n < c^n$, we have $b < c$ thanks to the monotonicity of $x^n$ for positive $x$. We therefore have $a:b < c:d$ implying their respective oracles satisfy this as well, namely $\sqrt[n]{p} < \sqrt[n]{q}$.
\end{proof}
\subsection{Solving equations}
A large aspect of working with real numbers is to solve equations such as finding a real number $x$ that satisfies $f(x) = b$ for some real number $b$ or perhaps a fixed point such as $f(x) = x$. We will look at three examples of methods solving equations and how the oracle rule comes out of them. In particular, we will explore the Intermediate Value Theorem, Newton's Method via Kantorovich's Theorem, and a fixed point theorem. While we will not be reproducing their proofs, we will take their claims and weave them into an oracle, establishing existence.
In order to do this, we need to discuss functions. A full treatment of oracles and functions can be found in \cite{taylor23funora} in which I detail functions arising from an oracle process on Yes rectangles using, basically, Two Point Separation. One can also see \cite{bridger} for details and theorems about functions based on fonsis.
Here, we will simply state what we want to be true of the functions. We will be discussing functions continuous on their domain which allows what happens on rationals to inform us of what happens on the oracles. In addition, the output of the functions will be oracles. We will assume there is a mechanism by which if we input an oracle $x$ in the domain of the function $f$ along with an $\varepsilon > 0$, then we will receive back a Yes interval $J$ of the oracle $f(x)$ whose length is at most $\varepsilon$ as well as a Yes interval $I$ of $x$ such that if $\alpha$ is an oracle with $I_\alpha$ as a Yes interval, then $J_{f(\alpha)}$ is a Yes interval for the oracle $f(\alpha)$. That is, the box $I_\alpha \times J_{f(\alpha)}$ contains all the function values of the base. Note that narrowing $I_\alpha$ is always fine and possible.
It is the business of \cite{taylor23funora} to establish that this works and explore its implications. We will just assume it here for purposes of explorations. We will also assume that the results and notions of differential calculus can largely be established. One can take this section as more an intuitive guide as to how familiar results would be presented and worked with.
\subsubsection{Intermediate Value Theorem}\label{sec:ivt}
A well-known process that is a canonical example for defining an oracle based on the separation property, is that of finding solutions to equations using the process of the Intermediate Value Theorem.
In this section, we will assume we have a function $f$ defined on the rationals to the rationals, such as a polynomial with rational coefficients. The paper \cite{taylor23funora} has a different approach to functions and also generalizes the Intermediate Value Theorem in that context.
Let us say that we are trying to solve $f(x) = y$, for rational $y$, on the interval $u:v$ and we have $f(u):y:f(v)$. Then we define a rule $R$ for intervals in $u:v$ such that $R(a:b) = 1$ exactly when $f(a):y:f(b)$ holds true. If we have $a:b$ partially outside $u:v$, then the oracle pronounces Yes or No based on the pronouncement on the intersection of $a:b$ with $u:v$. It gives a No if $a:b$ does not intersect $u:v$ at all. This choice will yield consistency. If $f$ is strictly monotonic for all rationals, then the definition simplifies to $R(a:b)=1$ exactly when $f(c):y:f(d)$ without having to worry about intersecting an interval $u:v$. We would still need to establish the existence of one such interval.
For a random function $f$, this is not going to define an oracle. It will define a process that can certainly define an oracle. In particular, we can take the midpoint of the interval, make a choice of interval, take that midpoint, pick a new subinterval, etc. This is a sequence of narrowing, overlapping intervals and hence will define an oracle as explained in Section \ref{sec:ni}. But without more control on the function, different choices will potentially lead to different outcomes.
To make it independent of choices, we will follow the lead of \cite{bridger}, p. 74, in which they prove what they call the Inverse Function Theorem.\footnote{It was reading this proof that finally led me to the version of the Separation property with the halo.} In any event, our hypothesis on $f$ is that on the interval $u:v$, $f$ is two-sided Lipschitz, that is, there exist positive constants $L$ and $U$ such that $L (p-q) \leq f(p) - f(q) \leq U (p-q)$ and that $f(a):y:f(b)$. The lower inequality ensures monotonicity\footnote{If $p > q$, then $L(p-q) \leq f(p) - f(q)$ becomes $f(p) \geq f(q) + L(p-q)$ and $L(p-q)$ is a positive quantity.} while the upper inequality gives, among other things, continuity. These ensure that any subinterval in $u:v$ will give consistent results. In particular, it will satisfy
\begin{enumerate}
\item Existence. $u:v$ is a Yes interval.
\item Separating. Let $a \lte b$ be a Yes interval in $u:v$ and let $c$ be the partition point with $\delta>0$ being the given width.\footnote{If $a:b$ intersects $u:v$ and $c$ is in the intersection, then we can use the main argument. If $c$ is outside $u:v$, then pick an $E:F$ entirely outside of $u:v$ and the one closest to an endpoint of $u:v$ replaces the opposite side of $c$ endpoint outside of $u:v$. For example, if we have $a:E:c:F:u:(v?b)$, then $F:b$ would be the Yes interval.}
The fact that $a:b$ is Yes tells us that $f(a):y:f(b)$. By monotonicity, we know that $f(c - \delta/2) < f(c) < f(c+\delta)$. If $y < f(c-\delta/2 = E)$ then $a:E$ is Yes while $E:F$ and $F:b$ are No. If $y > f(c + \delta/2 = F)$, then $F:b$ is Yes and $c:E$ and $E:F$ are No. If $f(c-\delta) < y < f(c+\delta)$, then $c_\delta$ is Yes while $a:c-\delta$ and $c+\delta : b$ are No.
This satisfies the property. Note that while we are dealing with rationals here, it is not hard to imagine dealing with fuzzy values and really needing the ability to have fuzziness. For example, imagine we are using an algorithm to compute $f(c)$ such that we can control the uncertainty, but cannot make it 0. Then we presumably would need to dampen the uncertainty as $\delta$ got smaller and smaller.
\item Consistency. If we have the rational sandwiching $u:c:a:b:d:v$ and we have that $a:b$ is a Yes interval, then by monotonicity, we have $f(c):f(a):y:f(b):f(d)$ and so $c:d$ is a Yes interval. For intervals $c:d$ that are partially outside $u:v$, the definition of following the pronouncements of the intersection is what yields consistency.
If $c:d$ was No, then $y$ is not in $f(c):f(d)$. This implies, again by monotonicity, that $f(a):f(b)$ cannot contain $y$. So $a:b$ is No.
\item Closed. Let's assume that $c$ is such that $c_\delta$ is a Yes interval for every $\delta$. We need to show that $c:c$ is a Yes interval, that is, $f(c):y:f(c)$ which is the same as saying $f(c) = y$.
Since $c_\delta$ is a Yes interval and $f$ is monotonic, we have $f(c-\delta):(y? f(c)):f(c+\delta)$. We also have $f(c +\delta) - f(c-\delta) \leq U (2 \delta)$. Thus, $|f(c) - y| \leq U (2 \delta)$. Since this is true for all $\delta > 0$, this can only be true if $|f(c) -y| = 0$.
We also need to show that if $c:c$ is a No interval, then we can find a $\delta > 0$ such that $c_\delta$ is a No interval. $c:c$ being a No interval means that $f(c) \neq y$. Let $M = |f(c)-y|$. Then if we take $\delta = \frac{M}{2U}$, then $|f(c) - f(d)| \leq U |c-d| \leq U \frac{M}{2U} = \frac{M}{2}$ for all $d$ in $c_\delta$. Thus, $f(c_\delta)$ is contained in $f(c)_\frac{M}{2}$ which does not contain $y$. Therefore, $c_\delta$ is a No interval.
\end{enumerate}
So under those conditions we have a well-defined oracle. Under more general conditions, we can describe a method which will produce an oracle, possibly using the notion of a fonsi from the next section, though it might not be unique.