Could someone explain what the S-B theorem is.

Thanks
Henry

I am not sure how much set theory you have done, but you probably do not understand 'injective function' or 'cardinality'. We say a function f:A® B is injective if and only if we have a=b whenever f(a)=f(b). Likewise, we say a function f:A® B is surjective if every member of B can be written as f(a) for some a in A. We say a function is bijective if it is both surjective and injective, i.e. it is one-to-one.

Cardinality is a bit more subtle. We say two sets A, B have the same cardinality if and only if there exists a bijective function from A to B. Formally, the cardinality of a set A is defined as a (proper) class of all sets which bijects with A.

Kerwin

Thanks Kerwin

Let f:A® B, g:B® A be our injections. Now for each element a in A, either it is g(b) for some unique b, or it is not in the image of g. Similarly, every element b of B is either f(a) for some unique a, or not in the image of f. Now we construct a backward chain for an element a in A:-

a, b, c, d,...

in such a way that a=g(b), b=f(c), c=g(d), chain may terminate or it may go on forever. Similarly, we construct the chain for each element of B. Given this chain, can we identify some bijection?

Yes, first, we note the set A can be split into three disjoint subsets - those with infinite chain, those with finite odd-length chain (i.e. those terminates at some elements of A), and those with finite even-length chain. Similarly, B can be split into three subsets. Now we see that an element a of A has odd (even) length chain if and only if f(a) has even (odd) length chain, and similarly for B. Further, f(a) (g(b)) has infinite chain if and only if a (b) has infinite chain. Hence we can form a one-one correspondence between those in A with odd length chain with those in B with even length chain by bijecting f(a) with a, and bijecting a with b if a has finite even length chain with a=g(b), and for those with infinite chain, we can have a bijection a with f(a) (or g(b) with b, just be consistent!).

Kerwin