[tuatoru]

This (no smallest positive element of Q) is sensible. But how can you have a procedure that requires making an infinite number of choices?[1] It's not an algorithm; they have to terminate.

1. Wikipedia explanation of the axiom of choice.

[tsimionescu]

I was only pointing out the problem with your argument not arguing that the AoC is necessary or intuitive.

Also, algorithms that don't terminate are still algorithms - especially if they keep emitting pieces of a solution, instead of producing the whole solution at the end.

For example, here is an algorithm for printing all of the natural numbers:

  i <- 0
  while true:
    print(i) 
    i <- successor(i)

Finally, computability is not typically considered necessary for a mathematical construct to exist or be useful. Just like geometry sometimes studies shapes that can't be constructed in the physical world, other kinds of mathematics sometimes studies concepts that can't be computed (at least not given known models of computation).