On the effectiveness of the Schröder-Bernstein theorem
HTML articles powered by AMS MathViewer
- by J. B. Remmel PDF
- Proc. Amer. Math. Soc. 83 (1981), 379-386 Request permission
Abstract:
The effectiveness of the classical equivalence theorem of Schröder and Bernstein is investigated using the tools of recursion theory. We prove one result which generalizes all the effective versions of the Schröder-Bernstein theorem which occur in the literature. In contrast, we show that Banach’s strengthening of the Schröder-Bernstein theorem fails to be effective.References
-
S. Banach, Un théorème sur les transformations biunivoques, Fund. Math. 6 (1924), 236-239.
E. Borel, Leçons sur la théorie des fonctions, Paris, 1898.
- Georg Cantor, Beiträge zur Begründung der transfiniten Mengenlehre, Math. Ann. 49 (1897), no. 2, 207–246 (German). MR 1510964, DOI 10.1007/BF01444205
- J. C. E. Dekker and J. Myhill, Recursive equivalence types, Univ. California Publ. Math. 3 (1960), 67–213. MR 0117155
- A. Korselt, Über einen Beweis des Äquivalenzsatzes, Math. Ann. 70 (1911), no. 2, 294–296 (German). MR 1511622, DOI 10.1007/BF01461161
- Alfred B. Manaster and Joseph G. Rosenstein, Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. (3) 25 (1972), 615–654. MR 314610, DOI 10.1112/plms/s3-25.4.615
- L. Mirsky and Hazel Perfect, Systems of representatives, J. Math. Anal. Appl. 15 (1966), 520–568. MR 204300, DOI 10.1016/0022-247X(66)90106-5
- John Myhill, Creative sets, Z. Math. Logik Grundlagen Math. 1 (1955), 97–108. MR 71379, DOI 10.1002/malq.19550010205
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Joseph R. Shoenfield, Degrees of unsolvability, North-Holland Mathematics Studies, No. 2, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1971. Dedicated to S. C. Kleene. MR 0340011
Additional Information
- © Copyright 1981 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 83 (1981), 379-386
- MSC: Primary 03D20
- DOI: https://doi.org/10.1090/S0002-9939-1981-0624936-X
- MathSciNet review: 624936