2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ "We can't construct" might mean "we don't know how to construct" rather than "we can prove that it is impossible to construct". If so, Axiom of Choice might not be involved. $\endgroup$
    – Robert Israel
    Oct 15, 2018 at 1:13
  • $\begingroup$ Chaitin’s constant is, according to the Wikipedia article you link to, also called “Chaitin’s construction”, so it seems the premise of your question isn’t necessarily widely agreed upon. That is, I can see why you might consider the notion of “construction” as stronger than the notion of “existence”, and perhaps there are fields that formally define the former where this is true, but my (possibly mistaken) impression is that in many (most?) fields we treat the two notions as the same. $\endgroup$
    – Theoretical Economist
    Oct 15, 2018 at 1:24
  • 1
    $\begingroup$ There are lots of subtleties here. Consider an undecidable statement $P$: that is, $P$ is either true or false, but it is impossible (in a given axiom system) to prove which it is. We can't construct the truth value of $P$, i.e. we can't specify a construction of that value, but it's either "true" or "false" so it's not an incomputable thing. $\endgroup$
    – Robert Israel
    Oct 15, 2018 at 1:31
  • $\begingroup$ Aren't things related to (non standard) models of PA exist but are not definable ? $\endgroup$
    – reuns
    Oct 15, 2018 at 2:09
  • 1
    $\begingroup$ @reuns: some nonstandard models of PA, at least, are very definable. For example, there is a computable tree $T$ on $2^{<\omega}$ so that every path through the tree canonically gives a nonstandard model of PA. The leftmost path of this tree thus gives a definable nonstandard model, namely the model given by the leftmost path of $T$. $\endgroup$
    – Carl Mummert
    Oct 15, 2018 at 13:34

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ While very likely not the perspective the OP was taking, the Law of the Excluded Middle itself can be viewed as a form of the Axiom of Choice. If we drop the Law of the Excluded Middle, we then get (Bishop-style) constructive logic which is compatible with everything being computable. (In fact, we can prove more things if we formalize "everything is computable".) $\endgroup$
    – Derek Elkins left SE
    Oct 15, 2018 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .