20:
277:
382:
123:
of real analysis, even when considering only computable sequences. A common way to resolve this difficulty is to consider only sequences that are accompanied by a
138:, where the exact strength of this principle has been determined. In the terminology of that program, the least upper bound principle is equivalent to ACA
150:, is readily obtained from the textbook proof (see Simpson, 1999) of the non-computability of the supremum in the least upper bound principle.
625:
could be enumerated. To complete the decision procedure, check these in an effective manner and then return 0 or 1 depending on whether
131:
to the least upper bound principle, i.e. a construction that shows that this theorem is false when restricted to computable reals.
520:
that no additional binary digits in that segment could ever be turned on, which leads to an estimate on the distance between
202:
324:
119:. The fact that such sequences exist means that the collection of all computable real numbers does not satisfy the
127:; no Specker sequence has a computable modulus of convergence. More generally, a Specker sequence is called a
703:
698:
120:
146:. In fact, the proof of the forward implication, i.e. that the least upper bound principle implies ACA
416:
is not a computable real number. The proof uses a particular fact about computable real numbers. If
638:
163:
124:
105:
86:
74:
8:
421:
135:
116:
82:
650:
Douglas
Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
54:
665:
97:
657:, American Mathematical Society, Translations of Mathematical Monographs v. 60.
167:
50:
692:
171:
109:
669:
90:
134:
The least upper bound principle has also been analyzed in the program of
681:
E. Specker (1949), "Nicht konstruktiv beweisbare Sätze der
Analysis"
591:) to increase by 2, but this cannot happen once all the elements of (
101:
93:
158:
The following construction is described by
Kushner (1984). Let
19:
557:
were computable, it would lead to a decision procedure for
621:(2). This leaves a finite number of possible places where
108:. The first example of such a sequence was constructed by
660:
Jakob G. Simonsen (2005), "Specker sequences revisited",
499:
causes a single binary digit to go from 0 to 1 each time
115:
The existence of
Specker sequences has consequences for
396:) is bounded above by 1. Classically, this means that
327:
205:
309:has no repetition, it is possible to estimate each
291:is nonnegative and rational, and that the sequence
376:
272:{\displaystyle q_{n}=\sum _{i=0}^{n}2^{-a_{i}-1}.}
271:
690:
377:{\displaystyle \sum _{i=0}^{\infty }2^{-i-1}=1.}
655:Lectures on constructive mathematical analysis
300:is strictly increasing. Moreover, because
507:where a large enough initial segment of
503:increases by 1. Thus there will be some
18:
613:, it must be enumerated for a value of
600:) are within 2 of each other. Thus, if
187:without repetition. Define a sequence (
691:
420:were computable then there would be a
676:Subsystems of second-order arithmetic
196:) of rational numbers with the rule
13:
582:), this would cause the sequence (
473:, compare the binary expansion of
344:
14:
715:
183:) be a computable enumeration of
573:were to appear in the sequence (
486:for larger and larger values of
604:is going to be enumerated into
511:has already been determined by
153:
1:
644:
561:, as follows. Given an input
477:with the binary expansion of
662:Mathematical Logic Quarterly
16:Sequence of rational numbers
7:
632:
121:least upper bound principle
10:
720:
683:Journal of Symbolic Logic
639:Computation in the limit
129:recursive counterexample
87:monotonically increasing
23:A Specker sequence. The
553:If any such a function
65:steps; otherwise it is
670:10.1002/malq.200410048
664:, v. 51, pp. 532–540.
378:
348:
282:It is clear that each
273:
239:
164:recursively enumerable
125:modulus of convergence
106:computable real number
70:
685:, v. 14, pp. 145–158.
653:B.A. Kushner (1984),
379:
328:
274:
219:
22:
704:Sequences and series
490:. The definition of
325:
203:
75:computability theory
699:Computable analysis
674:S. Simpson (1999),
422:computable function
387:Thus the sequence (
318:against the series
136:reverse mathematics
117:computable analysis
374:
269:
71:
412:It is shown that
711:
383:
381:
380:
375:
367:
366:
347:
342:
278:
276:
275:
270:
265:
264:
257:
256:
238:
233:
215:
214:
98:rational numbers
79:Specker sequence
53:in a computable
719:
718:
714:
713:
712:
710:
709:
708:
689:
688:
647:
635:
612:
599:
590:
581:
537:
528:
519:
498:
485:
448:
439:
405:has a supremum
404:
395:
353:
349:
343:
332:
326:
323:
322:
317:
308:
299:
290:
252:
248:
244:
240:
234:
223:
210:
206:
204:
201:
200:
195:
182:
168:natural numbers
156:
149:
145:
141:
57:halts on input
55:Gödel numbering
32:
17:
12:
11:
5:
717:
707:
706:
701:
687:
686:
679:
672:
658:
651:
646:
643:
642:
641:
634:
631:
608:
595:
586:
577:
533:
524:
515:
494:
481:
469:). To compute
444:
435:
400:
391:
385:
384:
373:
370:
365:
362:
359:
356:
352:
346:
341:
338:
335:
331:
313:
304:
295:
286:
280:
279:
268:
263:
260:
255:
251:
247:
243:
237:
232:
229:
226:
222:
218:
213:
209:
191:
178:
155:
152:
147:
143:
139:
51:Turing machine
28:
15:
9:
6:
4:
3:
2:
716:
705:
702:
700:
697:
696:
694:
684:
680:
677:
673:
671:
667:
663:
659:
656:
652:
649:
648:
640:
637:
636:
630:
628:
624:
620:
616:
611:
607:
603:
598:
594:
589:
585:
580:
576:
572:
568:
564:
560:
556:
551:
549:
545:
541:
536:
532:
527:
523:
518:
514:
510:
506:
502:
497:
493:
489:
484:
480:
476:
472:
468:
464:
460:
456:
452:
447:
443:
438:
434:
431:) such that |
430:
426:
423:
419:
415:
410:
408:
403:
399:
394:
390:
371:
368:
363:
360:
357:
354:
350:
339:
336:
333:
329:
321:
320:
319:
316:
312:
307:
303:
298:
294:
289:
285:
266:
261:
258:
253:
249:
245:
241:
235:
230:
227:
224:
220:
216:
211:
207:
199:
198:
197:
194:
190:
186:
181:
177:
173:
169:
165:
161:
151:
137:
132:
130:
126:
122:
118:
113:
111:
110:Ernst Specker
107:
103:
99:
95:
92:
88:
84:
80:
76:
68:
64:
60:
56:
52:
48:
44:
40:
36:
31:
26:
21:
682:
675:
661:
654:
626:
622:
618:
614:
609:
605:
601:
596:
592:
587:
583:
578:
574:
570:
566:
562:
558:
554:
552:
547:
543:
539:
534:
530:
525:
521:
516:
512:
508:
504:
500:
495:
491:
487:
482:
478:
474:
470:
466:
462:
458:
454:
450:
445:
441:
436:
432:
428:
424:
417:
413:
411:
406:
401:
397:
392:
388:
386:
314:
310:
305:
301:
296:
292:
287:
283:
281:
192:
188:
184:
179:
175:
170:that is not
159:
157:
154:Construction
133:
128:
114:
78:
72:
66:
62:
58:
46:
42:
38:
34:
29:
24:
678:, Springer.
174:, and let (
693:Categories
645:References
629:is found.
617:less than
565:, compute
112:(1949).
83:computable
27:digit of x
449:| < 1/
361:−
355:−
345:∞
330:∑
259:−
246:−
221:∑
172:decidable
104:is not a
633:See also
569:(2). If
453:for all
142:over RCA
102:supremum
94:sequence
45:and the
166:set of
162:be any
91:bounded
100:whose
61:after
546:>
461:>
81:is a
538:for
529:and
77:, a
666:doi
550:.
409:.
96:of
73:In
49:th
37:if
33:is
695::
440:-
372:1.
89:,
85:,
41:≤
668::
627:k
623:k
619:r
615:i
610:i
606:a
602:k
597:i
593:q
588:i
584:q
579:i
575:a
571:k
567:r
563:k
559:A
555:r
548:n
544:j
542:,
540:i
535:j
531:q
526:i
522:q
517:n
513:q
509:x
505:n
501:i
496:i
492:q
488:i
483:i
479:q
475:x
471:r
467:n
465:(
463:r
459:j
457:,
455:i
451:n
446:i
442:q
437:j
433:q
429:n
427:(
425:r
418:x
414:x
407:x
402:n
398:q
393:n
389:q
369:=
364:1
358:i
351:2
340:0
337:=
334:i
315:n
311:q
306:i
302:a
297:n
293:q
288:n
284:q
267:.
262:1
254:i
250:a
242:2
236:n
231:0
228:=
225:i
217:=
212:n
208:q
193:n
189:q
185:A
180:i
176:a
160:A
148:0
144:0
140:0
69:.
67:3
63:k
59:n
47:n
43:k
39:n
35:4
30:k
25:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
