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−1. 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−1) 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 toposE, (1) CBT holds ifEis Boolean, and conversely ifEhas a natural number object; (2) The Axiom of Choice inEimplies a dual version of CBTI and conversely ifEhas splitting supports and a natural number object.