On the effectiveness of the Schröder-Bernstein theorem

Remmel, J. B.

doi:10.1090/S0002-9939-1981-0624936-X

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

Un théorème sur les transformations biunivoques

6

Leçons sur la théorie des fonctions

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