146:
with the axiom of choice included are sufficient to prove the well-ordering theorem, and conversely, the
Zermelo–Fraenkel axioms without the axiom of choice but with the well-ordering theorem included are sufficient to prove the axiom of choice. (The same applies to
386:
155:, however, the well-ordering theorem is strictly stronger than the axiom of choice: from the well-ordering theorem one may deduce the axiom of choice, but from the axiom of choice one cannot deduce the well-ordering theorem.
704:
437:
89:
introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem. One can conclude from the well-ordering theorem that every set is susceptible to
611:
637:
128:
491:
464:
287:
108:
considered the well-ordering theorem to be a "fundamental principle of thought". However, it is considered difficult or even impossible to visualize a well-ordering of
260:
551:
1063:
contains uncountably many sets, making all uncountably many choices is not allowed under the axioms of
Zermelo-Fraenkel set theory without the axiom of choice.
1061:
1041:
1021:
1001:
981:
961:
937:
917:
897:
877:
857:
837:
817:
797:
777:
757:
737:
657:
571:
531:
511:
307:
237:
217:
197:
1350:
312:
662:
391:
1308:
1193:
1153:
1093:
20:
1280:
1247:
1220:
1123:
1003:
separately would not work, since the theorem only asserts the existence of a well-ordering, and choosing for each
93:, which is considered by mathematicians to be a powerful technique. One famous consequence of the theorem is the
576:
1355:
162:
The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about
143:
616:
94:
1345:
158:
There is a well-known joke about the three statements, and their relative amenability to intuition:
111:
469:
442:
265:
27:
1183:
1113:
1210:
1143:
1083:
943:
An essential point of this proof is that it involves only a single arbitrary choice, that of
245:
90:
82:
1023:
a well-ordering would require just as many choices as simply choosing an element from each
536:
8:
1300:
513:
that have not yet been assigned a place in the ordering (or undefined if the entirety of
1215:, History of Mathematics, vol. 25, American Mathematical Society, pp. 23–30,
1109:
1046:
1026:
1006:
986:
966:
946:
922:
902:
882:
862:
842:
822:
802:
782:
762:
742:
722:
642:
556:
516:
496:
292:
222:
202:
182:
152:
62:
1330:
142:
the well-ordering theorem is equivalent to the axiom of choice, in the sense that the
1304:
1276:
1243:
1216:
1189:
1149:
1119:
1089:
139:
46:
1268:
381:{\displaystyle a_{\alpha }\ =\ f(A\smallsetminus \{a_{\xi }\mid \xi <\alpha \})}
134:
claimed to have proven that such a well-ordering cannot exist. A few weeks later,
1235:
163:
148:
135:
78:
74:
1272:
1209:
Plotkin, J. M. (2005), "Introduction to "The
Concept of Power in Set Theory"",
240:
130:; such a visualization would have to incorporate the axiom of choice. In 1904,
131:
19:"Zermelo's theorem" redirects here. For Zermelo's theorem in game theory, see
1339:
1263:
Krantz, Steven G. (2002), "The Axiom of Choice", in Krantz, Steven G. (ed.),
715:
The axiom of choice can be proven from the well-ordering theorem as follows.
86:
70:
1326:
1168:
1079:
105:
77:
are the most important mathematical statements that are equivalent to the
34:
16:
Theoretic principle in mathematics stating every set can be well-ordered.
50:
1085:
An introduction to the theory of functional equations and inequalities
175:
The well-ordering theorem follows from the axiom of choice as follows.
699:{\displaystyle \sup\{\alpha \mid a_{\alpha }{\text{ is defined}}\}}
1240:
Foundations
Without Foundationalism: A Case for Second-Order Logic
432:{\displaystyle A\smallsetminus \{a_{\xi }\mid \xi <\alpha \}}
719:
To make a choice function for a collection of non-empty sets,
138:
found a mistake in the proof. It turned out, though, that in
639:(in the usual well-order of the ordinals) is a well-order of
219:
be a choice function for the family of non-empty subsets of
73:
under the ordering. The well-ordering theorem together with
1265:
Handbook of Logic and Proof
Techniques for Computer Science
1049:
1029:
1009:
989:
969:
949:
925:
905:
885:
865:
845:
825:
805:
785:
765:
745:
725:
665:
645:
619:
579:
559:
539:
519:
499:
472:
445:
394:
315:
295:
268:
248:
225:
205:
185:
114:
963:; applying the well-ordering theorem to each member
1331:
http://mizar.org/version/current/html/wellord2.html
819:be such an ordering. The function that to each set
1055:
1035:
1015:
995:
975:
955:
931:
911:
891:
871:
851:
831:
811:
791:
771:
751:
731:
698:
651:
631:
605:
565:
545:
533:has been successfully enumerated). Then the order
525:
505:
485:
458:
431:
380:
301:
281:
254:
231:
211:
191:
122:
1337:
666:
170:
693:
669:
426:
401:
372:
347:
1188:. Cambridge University Press. p. 174.
710:
179:Let the set we are trying to well-order be
1351:Theorems in the foundations of mathematics
1108:
919:, is a choice function for the collection
606:{\displaystyle a_{\alpha }<a_{\beta }}
116:
1181:
1115:Encyclopaedia of Mathematics: Supplement
1267:, Birkhäuser Boston, pp. 121–126,
1234:
1208:
1141:
1338:
1262:
1078:
493:is chosen from the set of elements of
1297:Set Theory (Third Millennium Edition)
1242:. New York: Oxford University Press.
1148:. Norderstedt: Springer. p. 23.
1137:
1135:
1294:
879:, as ordered by (the restriction to
859:associates the smallest element of
13:
1132:
779:. There exists a well-ordering of
83:Axiom of choice § Equivalents
14:
1367:
1320:
1118:. Berlin: Springer. p. 458.
632:{\displaystyle \alpha <\beta }
1088:. Berlin: Springer. p. 14.
739:, take the union of the sets in
21:Zermelo's theorem (game theory)
1288:
1256:
1228:
1202:
1175:
1162:
1102:
1072:
375:
338:
1:
466:undefined if it is. That is,
65:if every non-empty subset of
123:{\displaystyle \mathbb {R} }
7:
1273:10.1007/978-1-4612-0115-1_9
486:{\displaystyle a_{\alpha }}
459:{\displaystyle a_{\alpha }}
282:{\displaystyle a_{\alpha }}
81:(often called AC, see also
10:
1372:
1182:Sheppard, Barnaby (2014).
659:as desired, of order type
171:Proof from axiom of choice
100:
25:
18:
1212:Hausdorff on Ordered Sets
1142:Thierry, Vialar (1945).
1066:
711:Proof of axiom of choice
26:Not to be confused with
1145:Handbook of Mathematics
255:{\displaystyle \alpha }
144:Zermelo–Fraenkel axioms
28:Well-ordering principle
1057:
1037:
1017:
997:
977:
957:
933:
913:
893:
873:
853:
833:
813:
793:
773:
753:
733:
708:
700:
653:
633:
607:
567:
547:
527:
507:
487:
460:
439:is nonempty, or leave
433:
382:
303:
283:
256:
233:
213:
193:
168:
124:
1295:Jech, Thomas (2002).
1185:The Logic of Infinity
1170:Mathematische Annalen
1058:
1038:
1018:
998:
978:
958:
934:
914:
894:
874:
854:
834:
814:
794:
774:
754:
734:
701:
654:
634:
608:
568:
548:
528:
508:
488:
461:
434:
383:
304:
284:
257:
234:
214:
194:
177:
160:
125:
95:Banach–Tarski paradox
91:transfinite induction
39:well-ordering theorem
1356:Axioms of set theory
1047:
1027:
1007:
987:
967:
947:
923:
903:
883:
863:
843:
823:
803:
783:
763:
743:
723:
663:
643:
617:
577:
557:
546:{\displaystyle <}
537:
517:
497:
470:
443:
392:
313:
293:
266:
262:, define an element
246:
223:
203:
183:
112:
45:, states that every
1110:Hazewinkel, Michiel
1043:. Particularly, if
388:if this complement
1053:
1033:
1013:
993:
973:
953:
929:
909:
889:
869:
849:
829:
809:
789:
769:
749:
729:
696:
649:
629:
603:
563:
543:
523:
503:
483:
456:
429:
378:
299:
279:
252:
229:
209:
189:
153:second-order logic
120:
63:strict total order
1310:978-3-540-44085-7
1195:978-1-1070-5831-6
1155:978-2-95-519901-5
1095:978-3-7643-8748-8
1056:{\displaystyle E}
1036:{\displaystyle S}
1016:{\displaystyle S}
996:{\displaystyle E}
976:{\displaystyle S}
956:{\displaystyle R}
932:{\displaystyle E}
912:{\displaystyle R}
892:{\displaystyle S}
872:{\displaystyle S}
852:{\displaystyle E}
832:{\displaystyle S}
812:{\displaystyle R}
792:{\displaystyle X}
772:{\displaystyle X}
752:{\displaystyle E}
732:{\displaystyle E}
691:
652:{\displaystyle A}
566:{\displaystyle A}
526:{\displaystyle A}
506:{\displaystyle A}
334:
328:
302:{\displaystyle A}
232:{\displaystyle A}
212:{\displaystyle f}
192:{\displaystyle A}
140:first-order logic
43:Zermelo's theorem
1363:
1315:
1314:
1292:
1286:
1285:
1260:
1254:
1253:
1236:Shapiro, Stewart
1232:
1226:
1225:
1206:
1200:
1199:
1179:
1173:
1172:21, pp. 545–591.
1166:
1160:
1159:
1139:
1130:
1129:
1106:
1100:
1099:
1076:
1062:
1060:
1059:
1054:
1042:
1040:
1039:
1034:
1022:
1020:
1019:
1014:
1002:
1000:
999:
994:
982:
980:
979:
974:
962:
960:
959:
954:
938:
936:
935:
930:
918:
916:
915:
910:
898:
896:
895:
890:
878:
876:
875:
870:
858:
856:
855:
850:
838:
836:
835:
830:
818:
816:
815:
810:
798:
796:
795:
790:
778:
776:
775:
770:
758:
756:
755:
750:
738:
736:
735:
730:
705:
703:
702:
697:
692:
690: is defined
689:
687:
686:
658:
656:
655:
650:
638:
636:
635:
630:
612:
610:
609:
604:
602:
601:
589:
588:
572:
570:
569:
564:
552:
550:
549:
544:
532:
530:
529:
524:
512:
510:
509:
504:
492:
490:
489:
484:
482:
481:
465:
463:
462:
457:
455:
454:
438:
436:
435:
430:
413:
412:
387:
385:
384:
379:
359:
358:
332:
326:
325:
324:
308:
306:
305:
300:
288:
286:
285:
280:
278:
277:
261:
259:
258:
253:
238:
236:
235:
230:
218:
216:
215:
210:
198:
196:
195:
190:
129:
127:
126:
121:
119:
41:, also known as
1371:
1370:
1366:
1365:
1364:
1362:
1361:
1360:
1346:Axiom of choice
1336:
1335:
1323:
1318:
1311:
1293:
1289:
1283:
1261:
1257:
1250:
1233:
1229:
1223:
1207:
1203:
1196:
1180:
1176:
1167:
1163:
1156:
1140:
1133:
1126:
1107:
1103:
1096:
1077:
1073:
1069:
1048:
1045:
1044:
1028:
1025:
1024:
1008:
1005:
1004:
988:
985:
984:
968:
965:
964:
948:
945:
944:
924:
921:
920:
904:
901:
900:
884:
881:
880:
864:
861:
860:
844:
841:
840:
824:
821:
820:
804:
801:
800:
784:
781:
780:
764:
761:
760:
744:
741:
740:
724:
721:
720:
713:
688:
682:
678:
664:
661:
660:
644:
641:
640:
618:
615:
614:
613:if and only if
597:
593:
584:
580:
578:
575:
574:
558:
555:
554:
538:
535:
534:
518:
515:
514:
498:
495:
494:
477:
473:
471:
468:
467:
450:
446:
444:
441:
440:
408:
404:
393:
390:
389:
354:
350:
320:
316:
314:
311:
310:
294:
291:
290:
273:
269:
267:
264:
263:
247:
244:
243:
224:
221:
220:
204:
201:
200:
184:
181:
180:
173:
136:Felix Hausdorff
115:
113:
110:
109:
103:
79:axiom of choice
31:
24:
17:
12:
11:
5:
1369:
1359:
1358:
1353:
1348:
1334:
1333:
1322:
1321:External links
1319:
1317:
1316:
1309:
1303:. p. 48.
1287:
1281:
1255:
1248:
1227:
1221:
1201:
1194:
1174:
1161:
1154:
1131:
1124:
1101:
1094:
1070:
1068:
1065:
1052:
1032:
1012:
992:
972:
952:
941:
940:
928:
908:
888:
868:
848:
828:
808:
788:
768:
748:
728:
712:
709:
695:
685:
681:
677:
674:
671:
668:
648:
628:
625:
622:
600:
596:
592:
587:
583:
562:
542:
522:
502:
480:
476:
453:
449:
428:
425:
422:
419:
416:
411:
407:
403:
400:
397:
377:
374:
371:
368:
365:
362:
357:
353:
349:
346:
343:
340:
337:
331:
323:
319:
298:
276:
272:
251:
228:
208:
188:
172:
169:
118:
102:
99:
15:
9:
6:
4:
3:
2:
1368:
1357:
1354:
1352:
1349:
1347:
1344:
1343:
1341:
1332:
1328:
1325:
1324:
1312:
1306:
1302:
1298:
1291:
1284:
1282:9781461201151
1278:
1274:
1270:
1266:
1259:
1251:
1249:0-19-853391-8
1245:
1241:
1237:
1231:
1224:
1222:9780821890516
1218:
1214:
1213:
1205:
1197:
1191:
1187:
1186:
1178:
1171:
1165:
1157:
1151:
1147:
1146:
1138:
1136:
1127:
1125:1-4020-0198-3
1121:
1117:
1116:
1111:
1105:
1097:
1091:
1087:
1086:
1081:
1080:Kuczma, Marek
1075:
1071:
1064:
1050:
1030:
1010:
990:
970:
950:
926:
906:
886:
866:
846:
826:
806:
786:
766:
746:
726:
718:
717:
716:
707:
683:
679:
675:
672:
646:
626:
623:
620:
598:
594:
590:
585:
581:
560:
540:
520:
500:
478:
474:
451:
447:
423:
420:
417:
414:
409:
405:
398:
395:
369:
366:
363:
360:
355:
351:
344:
341:
335:
329:
321:
317:
296:
274:
270:
249:
242:
226:
206:
186:
176:
167:
165:
159:
156:
154:
150:
145:
141:
137:
133:
107:
98:
96:
92:
88:
87:Ernst Zermelo
84:
80:
76:
72:
71:least element
68:
64:
60:
56:
52:
48:
44:
40:
36:
29:
22:
1327:Mizar system
1296:
1290:
1264:
1258:
1239:
1230:
1211:
1204:
1184:
1177:
1169:
1164:
1144:
1114:
1104:
1084:
1074:
942:
759:and call it
714:
239:. For every
178:
174:
164:Zorn's lemma
161:
157:
149:Zorn's lemma
106:Georg Cantor
104:
75:Zorn's lemma
66:
59:well-ordered
58:
54:
51:well-ordered
42:
38:
32:
573:defined by
309:by setting
289:that is in
132:Gyula KĹ‘nig
35:mathematics
1340:Categories
199:, and let
684:α
676:∣
673:α
627:β
621:α
599:β
586:α
479:α
452:α
424:α
418:ξ
415:∣
410:ξ
399:∖
370:α
364:ξ
361:∣
356:ξ
345:∖
322:α
275:α
250:α
1301:Springer
1238:(1991).
1112:(2001).
1082:(2009).
53:. A set
1329:proof:
241:ordinal
101:History
49:can be
1307:
1279:
1246:
1219:
1192:
1152:
1122:
1092:
799:; let
333:
327:
151:.) In
69:has a
37:, the
1067:Notes
61:by a
1305:ISBN
1277:ISBN
1244:ISBN
1217:ISBN
1190:ISBN
1150:ISBN
1120:ISBN
1090:ISBN
899:of)
624:<
591:<
541:<
421:<
367:<
1269:doi
983:of
839:of
667:sup
553:on
85:).
57:is
47:set
33:In
1342::
1299:.
1275:,
1134:^
97:.
1313:.
1271::
1252:.
1198:.
1158:.
1128:.
1098:.
1051:E
1031:S
1011:S
991:E
971:S
951:R
939:.
927:E
907:R
887:S
867:S
847:E
827:S
807:R
787:X
767:X
747:E
727:E
706:.
694:}
680:a
670:{
647:A
595:a
582:a
561:A
521:A
501:A
475:a
448:a
427:}
406:a
402:{
396:A
376:)
373:}
352:a
348:{
342:A
339:(
336:f
330:=
318:a
297:A
271:a
227:A
207:f
187:A
166:?
117:R
67:X
55:X
30:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.