"There exists" versus "we can construct": computability and the axiom of choice

Question

I know that "we can construct" is a stronger claim than "there exists" because sometimes existence is known but explicit examples/constructions are not known.

I am looking for a deeper understanding of this. Is this difference always related in some way to the axiom of choice? Or maybe it is always related to the concept of computability?

My thoughts about the connection with the axiom of choice

I have a superficial understanding of the axiom of choice: I know that it is necessary in some situations about picking elements of set(s), i.e., it is not always true that we can simply "pick" an element (usually when the set in question is very big or it lacks a clear method of choosing). Intuitively this might be related to my question because it seems that "there exists" is weaker statement in the sense that "it exists" but "we don't know how to pick it".

My thoughts about the connection with computability

There are several examples of things that exist but are uncomputable, and therefore there is not an explicit way to "obtain", "pick" or "construct" them, such as chaitin's constant. This is why I think this is related, but I'm not sure, because perhaps it is more related to "definability" than computability (several uncomputable numbers are at least definable).

The question

For all situations in which "there exists" applies but "we can construct" doesn't:

• Is the axiom of choice (in any of its forms) necessarily being used?

• Is the thing that exists but can't be constructed always an example of an incomputable thing?

Answer 1

I think this is the kind of example you are looking for, related to a comment by Robert Israel:

There is a number $n$ so that $n = 0$ if the Riemann hypothesis holds and $n = 1$ if the Riemann hypothesis does not hold.

This defines a number $n$, although we don't know which value it has. No form of the axiom of choice is used. Whichever value $n$ has, that value is just a single natural number and as such is "computable" in a trivial sense.

The underlying logical axiom being used here is the law of the excluded middle. If we did not have the excluded middle, there is no obvious way we could establish that ("The Riemann hypothesis holds" or "The Riemann hypothesis does not hold") and thus we could not prove that the first sentence actually defines a number $n$ in all cases.