That said, when you only admit a universe of mathematical objects that admit of a finite construction, it is not unreasonable that you can have a computer program that, at least in principle, will enumerate all possible constructions and proofs of statements about them. Given that, you can create a construction which is literally for each set Y, the primary x in Y is the first x which in that enumeration a statement of the form "x is in Y" is proved.
This construction give a choice function of the kind that the Axiom of Choice says exists. However that said, the bizarre consequences of the Axiom of Choice that you find in classical set theory can't be proven for other reasons.