Use the Cantor Solution The Cantor-Bernstein theorem in the category of sets (A

Question

Explanation / Answer

The Cantor-Bernstein theorem in the category of sets (A injects in B, B injects in A => A, B equivalent) holds in other categories such as vector spaces, compact metric spaces, Noetherian topological spaces of finite dimension, and well-ordered sets. Whenever the objects in your category can be classified by a bounded collection of cardinal invariants, then you should expect to have the Schroeder-Bernstein property. For example, vector spaces (over some fixed field K) or algebraically closed fields (of some fixed characteristic) can each be classified by a single cardinal invariant: the dimension of the vector space, or the transcendence degree of the field. More interesting example: countable abelian torsion groups. Suppose A and B are two such groups, A is a direct summand of B, and vice-versa; are they isomorphic? By Ulm's Theorem, A and B are determined up to isomorphism by countable sequences of cardinal numbers -- namely, the number of summands of Z_p^infty and the "Ulm invariants," which are dimensions of some vector spaces associated with A and B. All of these invariants behave nicely with respect to direct sum decompositions, so it follows that A and B are isomorphic. (See Kaplansky's Infinite Abelian Groups for a very nice, and elementary, proof of all this.) If you like model theory, I could tell you a lot about when the categories of models of a complete theory have the Schroeder-Bernstein property (under elementary embeddings). If not, at least I can tell you this: Categories of structures with "definable" partial orderings with infinite chains (e.g. real-closed fields, atomless Boolean algebras) will NOT have the S-B property. Again, I need some model theory to make this statement precise... Let C be a first-order axiomatizable class of structures (in a countable language) which is "categorical in 2^{aleph_0}" -- i.e. any two structures in C of size continuum are isomorphic. Then C has the S-B property with respect to elementary embeddings. (This generalizes the cases of vector spaces and algebraically closed fields.) First note that a real number can be identified with a set of natural numbers by declaring that the binary expansion of the real corresponds to the characteristic sequence set of natural numbers. (Of course, some reals have non-unique binary expansion, so this identification doesn't always make sense, but any such real gives rise to a computable set no matter which binary expansion is taken, so insofar as we're concerned, this is irrelevant.) Now, the definition of computable you gave is what's known as limit computable or ?02, though since the notation ?02 is a priori reserved for sets defined by formulas that are both S02 and ?02 in the arithmetical hierarchy, it must be proven that the two notions coincide. This is exactly Schoenfield's limit lemma together with Post's theorem. Regarding your request for a "concrete" example of a real that is not ?02 (i.e. one that can be "picked by defining it"), the number--let's call it a--given in the paper cited in the answer you accepted is defined only relative to some fixed (incomputable!) enumeration of all ?02 reals; different enumerations give rise to different a's. However, such an enumeration is inherently not ?02 (it can be ?03 as @Carl points out in the comments to @Mahmud's answer) in the arithmetical hierarchy, so I do think that it is an acceptable example (contrary to my comments) . Given that, though, it's evident that a much better (i.e. less complex) real can be given: take any strictly S02 or ?02 real. For example, the set of indices of total computable functions Tot:={e:?n?s[fe,s(n)?]} is a well-known ?02-complete.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.