If and
are nonempty sets, then
,
,
mean which is injective, bijective, or surjective, respectively. We also define
,
to mean that an injection but no bijection, or a surjection but no bijection, from
to
. These relationships can be extended to the empty set by declaring that
and
for all
.
Proposition. iff
.
Proof. : If
is injective, pick an arbitrary
and define
by
if
,
otherwise. Then
is surjective.
: If
is surjective, the sets
are nonempty and disjoint, so any
is an injection from
to
.
Proposition. For any sets and
, either
or
.
Proof. Consider the set of all injections from subsets of
to
. The members of
can be regarded as subsets of
, so
is partially ordered by inclusion. Applying Zorn’s Lemma, then
has a maximal element
, with domain
and range
. If
and
, then
can be extended to an injection from
to
by setting
, contradicting maximality. Hence either
, in which case
, or
, in which case
is an injection from
to
and
.
Proposition. The Schroder-Bernstein Theorem. If and
, then
.
Proof. Let and
be injections. Consider a point
If
, we form
; if
, we form
; and so forth. Either this process can be continued indefinitely, or it terminates with an element of
(perhaps
itself), or it terminates with an element of
. In these three cases we say that
is in
,
, or
; thus
is the disjoint union of
,
, and
. In the same way,
is the disjoint union of three sets
,
, and
. Clearly
maps
onto
and
, whereas
maps
onto
. Therefore, if we define
by
if
and
if
, then
is bijective.
Proposition. For any set ,
.
Proof. On the one hand, the map is an injection from
to
. On the other, if
, let
. Then
, for if
for some
, any attempt to answer the question “Is
?” quickly leads to contradiction. Therefore
cannot be surjective.
“Friendship with one’s self is all important, because without it one cannot be friends with anyone else in the world.” ~ Eleanor Roosevelt
To be continued tomorrow 🙂
References
1] Gerald B. Folland, Real Analysis: Modern Techniques and Their Applications, 2ed, page 6-7.
[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.