The usual proofs of the well-known set-theoretical theorem “Given one-one maps f: A → B and g:B → A, there exists a one-one onto map h:A → B” actually produce a map h:A → B contained in the relation f U g⁻¹. Considering Tarski's Fixpoint Theorem as the implicit basic ingredient of such proofs. We examine several classical proofs/starting with Dedekind (1887), and illuminate their common feature by means of the categorical notion of a natural fixpoint. We consider a categorical form (CBT) of the theorem (with h ⊆ f Ug⁻¹) in a variety of contexts, obtaining some examples of categories where CBT holds and others where it fails. Among other results we prove for a topos E, (1) CBT holds if E is Boolean, and conversely if E has a natural number object; (2) The Axiom of Choice in E implies a dual version of CBTI and conversely if E has splitting supports and a natural number object.