954:
404:
895:
143:
804:
744:
956:
of refutable formulas are computably inseparable. The inseparability of the sets of provable and refutable formulas holds for many other formal theories of arithmetic (Smullyan 1958).
365:
308:
334:
276:
250:
205:
77:
680:
473:
831:
652:
632:
612:
592:
572:
552:
516:
496:
448:
428:
228:
183:
163:
1059:
82:
1116:
900:
683:
844:
96:
370:
749:
689:
407:
655:
281:
31:
1068:
339:
313:
255:
233:
188:
50:
834:
614:
that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for
1088:
1055:
665:
46:. These sets arise in the study of computability theory itself, particularly in relation to
1080:
1023:
996:
838:
17:
1100:
1035:
1008:
1096:
1051:
1031:
1015:
1004:
807:
1022:, Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 1041–1176,
816:
574:
and its complement are computably inseparable. However, there are many examples of sets
453:
637:
617:
597:
577:
557:
537:
519:
501:
481:
433:
413:
213:
168:
148:
43:
1027:
1000:
1110:
1044:
995:, Stud. Logic Found. Math., vol. 140, Amsterdam: North-Holland, pp. 37–85,
47:
1092:
1084:
1073:
Zeitschrift für
Mathematische Logik und Grundlagen der Mathematik
81:. Computably inseparable sets also arise in the study of
1071:(1958), "Undecidability and recursive inseparability",
903:
847:
819:
752:
692:
668:
640:
620:
600:
580:
560:
540:
504:
484:
456:
436:
416:
373:
342:
316:
284:
258:
236:
216:
191:
171:
151:
99:
53:
949:{\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}
1050:, Graduate Texts in Mathematics, Berlin, New York:
1043:
948:
889:
825:
798:
738:
674:
646:
626:
606:
586:
566:
546:
510:
490:
467:
442:
422:
398:
359:
328:
302:
270:
244:
222:
199:
177:
157:
137:
71:
34:, two disjoint sets of natural numbers are called
1018:(1998), "A survey of recursive combinatorics",
450:itself is a separating set for the pair, as is
890:{\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}
138:{\displaystyle \mathbb {N} =\{0,1,2,\dots \}}
8:
943:
910:
884:
854:
793:
759:
733:
699:
654:to be computably inseparable, disjoint, and
132:
108:
399:{\displaystyle C'=\mathbb {N} \setminus C}
1020:Handbook of recursive mathematics, Vol. 2
902:
846:
818:
799:{\displaystyle B=\{e:\varphi _{e}(0)=1\}}
772:
751:
739:{\displaystyle A=\{e:\varphi _{e}(0)=0\}}
712:
691:
667:
639:
619:
599:
579:
559:
539:
503:
483:
455:
435:
415:
386:
385:
372:
341:
315:
283:
257:
238:
237:
235:
215:
193:
192:
190:
170:
150:
101:
100:
98:
63:
58:
52:
966:
390:
522:separating set, then the two sets are
42:if they cannot be "separated" with a
7:
991:classes in computability theory",
937:
913:
857:
820:
303:{\displaystyle B\cap C=\emptyset }
297:
55:
25:
897:of provable formulas and the set
993:Handbook of computability theory
682:be the standard indexing of the
93:The natural numbers are the set
27:Concept in computability theory
922:
916:
866:
860:
784:
778:
724:
718:
554:is a non-computable set, then
83:Gödel's incompleteness theorem
1:
1028:10.1016/S0049-237X(98)80049-9
1001:10.1016/S0049-237X(99)80018-4
360:{\displaystyle B\subseteq C'}
806:are computably inseparable (
684:partial computable functions
329:{\displaystyle A\subseteq C}
271:{\displaystyle A\subseteq C}
245:{\displaystyle \mathbb {N} }
200:{\displaystyle \mathbb {N} }
72:{\displaystyle \Pi _{1}^{0}}
18:Recursively inseparable sets
478:If a pair of disjoint sets
1133:
982:Cenzer, Douglas (1999), "Π
145:. Given disjoint subsets
1085:10.1002/malq.19580040705
1042:Monk, J. Donald (1976),
675:{\displaystyle \varphi }
40:recursively inseparable
973:Monk 1976, p. 100
950:
891:
827:
800:
740:
676:
648:
628:
608:
588:
568:
548:
524:computably inseparable
512:
492:
469:
444:
424:
400:
361:
330:
304:
272:
246:
224:
201:
179:
159:
139:
73:
36:computably inseparable
951:
892:
828:
801:
741:
677:
656:computably enumerable
649:
629:
609:
589:
569:
549:
513:
493:
470:
445:
425:
401:
362:
331:
305:
273:
247:
225:
202:
180:
160:
140:
74:
1117:Computability theory
1069:Smullyan, Raymond M.
901:
845:
837:for the formulas of
817:
810:1998, p. 1047).
750:
690:
666:
638:
618:
598:
578:
558:
538:
502:
482:
454:
434:
414:
371:
340:
314:
282:
256:
234:
214:
189:
169:
149:
97:
51:
32:computability theory
310:(or equivalently,
68:
1046:Mathematical Logic
946:
887:
826:{\displaystyle \#}
823:
796:
736:
672:
644:
624:
604:
584:
564:
544:
508:
488:
468:{\displaystyle B'}
465:
440:
420:
396:
357:
326:
300:
268:
242:
220:
197:
175:
155:
135:
69:
54:
1079:(7–11): 143–147,
1061:978-0-387-90170-1
647:{\displaystyle B}
627:{\displaystyle A}
607:{\displaystyle B}
587:{\displaystyle A}
567:{\displaystyle A}
547:{\displaystyle A}
511:{\displaystyle B}
491:{\displaystyle A}
443:{\displaystyle A}
430:). For example,
423:{\displaystyle C}
223:{\displaystyle C}
178:{\displaystyle B}
158:{\displaystyle A}
16:(Redirected from
1124:
1103:
1064:
1049:
1038:
1016:Gasarch, William
1011:
990:
989:
974:
971:
955:
953:
952:
947:
896:
894:
893:
888:
839:Peano arithmetic
832:
830:
829:
824:
805:
803:
802:
797:
777:
776:
745:
743:
742:
737:
717:
716:
686:. Then the sets
681:
679:
678:
673:
653:
651:
650:
645:
633:
631:
630:
625:
613:
611:
610:
605:
593:
591:
590:
585:
573:
571:
570:
565:
553:
551:
550:
545:
517:
515:
514:
509:
497:
495:
494:
489:
474:
472:
471:
466:
464:
449:
447:
446:
441:
429:
427:
426:
421:
405:
403:
402:
397:
389:
381:
366:
364:
363:
358:
356:
335:
333:
332:
327:
309:
307:
306:
301:
277:
275:
274:
269:
251:
249:
248:
243:
241:
229:
227:
226:
221:
206:
204:
203:
198:
196:
184:
182:
181:
176:
164:
162:
161:
156:
144:
142:
141:
136:
104:
78:
76:
75:
70:
67:
62:
21:
1132:
1131:
1127:
1126:
1125:
1123:
1122:
1121:
1107:
1106:
1067:
1062:
1052:Springer-Verlag
1041:
1014:
988:
985:
984:
983:
981:
978:
977:
972:
968:
963:
899:
898:
843:
842:
841:. Then the set
835:Gödel numbering
815:
814:
808:William Gasarch
768:
748:
747:
708:
688:
687:
664:
663:
636:
635:
616:
615:
596:
595:
576:
575:
556:
555:
536:
535:
532:
500:
499:
480:
479:
457:
452:
451:
432:
431:
412:
411:
374:
369:
368:
349:
338:
337:
312:
311:
280:
279:
254:
253:
232:
231:
230:is a subset of
212:
211:
187:
186:
167:
166:
147:
146:
95:
94:
91:
49:
48:
28:
23:
22:
15:
12:
11:
5:
1130:
1128:
1120:
1119:
1109:
1108:
1105:
1104:
1065:
1060:
1039:
1012:
986:
976:
975:
965:
964:
962:
959:
958:
957:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
833:be a standard
822:
811:
795:
792:
789:
786:
783:
780:
775:
771:
767:
764:
761:
758:
755:
735:
732:
729:
726:
723:
720:
715:
711:
707:
704:
701:
698:
695:
671:
643:
623:
603:
583:
563:
543:
531:
528:
507:
487:
463:
460:
439:
419:
395:
392:
388:
384:
380:
377:
355:
352:
348:
345:
325:
322:
319:
299:
296:
293:
290:
287:
267:
264:
261:
240:
219:
209:separating set
195:
174:
154:
134:
131:
128:
125:
122:
119:
116:
113:
110:
107:
103:
90:
87:
66:
61:
57:
44:computable set
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1129:
1118:
1115:
1114:
1112:
1102:
1098:
1094:
1090:
1086:
1082:
1078:
1074:
1070:
1066:
1063:
1057:
1053:
1048:
1047:
1040:
1037:
1033:
1029:
1025:
1021:
1017:
1013:
1010:
1006:
1002:
998:
994:
980:
979:
970:
967:
960:
940:
934:
931:
928:
925:
919:
907:
904:
881:
878:
875:
872:
869:
863:
851:
848:
840:
836:
812:
809:
790:
787:
781:
773:
769:
765:
762:
756:
753:
730:
727:
721:
713:
709:
705:
702:
696:
693:
685:
669:
661:
660:
659:
657:
641:
621:
601:
581:
561:
541:
529:
527:
525:
521:
505:
485:
476:
461:
458:
437:
417:
409:
393:
382:
378:
375:
353:
350:
346:
343:
323:
320:
317:
294:
291:
288:
285:
265:
262:
259:
217:
210:
172:
152:
129:
126:
123:
120:
117:
114:
111:
105:
88:
86:
84:
80:
64:
59:
45:
41:
37:
33:
19:
1076:
1072:
1045:
1019:
992:
969:
533:
523:
477:
406:denotes the
208:
92:
39:
35:
29:
252:such that
961:References
520:computable
408:complement
89:Definition
1093:0044-3050
941:ψ
938:¬
935:⊢
920:ψ
914:#
882:ψ
879:⊢
864:ψ
858:#
821:#
770:φ
710:φ
670:φ
391:∖
347:⊆
321:⊆
298:∅
289:∩
263:⊆
130:…
56:Π
1111:Category
530:Examples
462:′
379:′
367:, where
354:′
1101:0099293
1036:1673598
1009:1720779
518:has no
79:classes
1099:
1091:
1058:
1034:
1007:
1089:ISSN
1056:ISBN
813:Let
746:and
662:Let
634:and
594:and
498:and
336:and
278:and
207:, a
165:and
1081:doi
1024:doi
997:doi
658:.
534:If
410:of
185:of
38:or
30:In
1113::
1097:MR
1095:,
1087:,
1075:,
1054:,
1032:MR
1030:,
1005:MR
1003:,
526:.
475:.
85:.
1083::
1077:4
1026::
999::
987:1
944:}
932:A
929:P
926::
923:)
917:(
911:{
908:=
905:B
885:}
876:A
873:P
870::
867:)
861:(
855:{
852:=
849:A
794:}
791:1
788:=
785:)
782:0
779:(
774:e
766::
763:e
760:{
757:=
754:B
734:}
731:0
728:=
725:)
722:0
719:(
714:e
706::
703:e
700:{
697:=
694:A
642:B
622:A
602:B
582:A
562:A
542:A
506:B
486:A
459:B
438:A
418:C
394:C
387:N
383:=
376:C
351:C
344:B
324:C
318:A
295:=
292:C
286:B
266:C
260:A
239:N
218:C
194:N
173:B
153:A
133:}
127:,
124:2
121:,
118:1
115:,
112:0
109:{
106:=
102:N
65:0
60:1
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
