Not to nitpick or assume you we're saying this, but doesn't the cardinality of the evens and odds equalling the cardinality of the integers hold even without the axiom of choice?
However, to me the "basic principle" is a similar argument. The important thing (for me) was to understand this is an argument about slicing up infinities in an "Infinite comb" type way, rather than anything resembling a "cut".