Is it assumed in the given proof for the Schoeder-Bernstein theorem that A and B are the ranges of t

lilmoore11p8

lilmoore11p8

Answered question

2022-07-03

Is it assumed in the given proof for the Schoeder-Bernstein theorem that A and B are the ranges of the injective functions f and g?
Preamble: I'm referring to the proof given in Art of Problem solving to the Schoeder-Bernstein Theorem. Namely, the claim is that
Let A and B be sets and f : A B, g : B A be injective functions. Then there exists a bijective function h : A B.
Then in order to prove the theorem, a function h is defined as h = { g 1 ( a ) : f ( a )  is a descendant of a lonely point   f ( a ) :  otherwise
My immediate thought was that: What if g 1 ( a ) is not defined? Namely given that g : B A is injective, why should necessarily g [ B ] = A? To which I answered an example in a finite case that if the cardinality of A is greater than B, and g is injective, then by the pigeonhole principle f cannot be injective. However it is not immediately obvious to me how the case of A and B being countable/uncountable should be handled, as A and B are just sets.
Question: Is it assumed in the aforementioned proof behind the link that f [ A ] = B and g [ B ] = A?. Or does it follow from somewhere else that g 1 ( a ) is necessarily defined, given the portion of the proof up to the definition of the function h?

Answer & Explanation

Keegan Barry

Keegan Barry

Beginner2022-07-04Added 18 answers

Step 1
g 1 ( a ) is necessarily defined. b B is lonely if b f [ A ] and is a descendant of b 0 B if ( f g ) n ( b 0 ) = b for some n 0.
So suppose f(a) is a descendant of a lonely point, let's call it b, so there is an n 0 such that ( f g ) n ( b ) = f ( a ). f(a) is clearly not lonely, so it must be the case that n 1. But then f ( a ) = f ( g ( ( f g ) n 1 ( b ) ) ) .
Step 2
The injectivity of f implies a = g ( ( f g ) n 1 ( b ) ) , so a g [ B ]. (Namely, g 1 ( a ) = ( f g ) n 1 ( b ).)

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?