# Function that have values that we can't determine (in principle - not because they are to difficult to compute)

I know that in some cases one has to exhibit functions like $f\equiv1$ if some famous conjecture is true and $f\equiv0$ else.

With this I don't have a problem, because I perceive this function as well-defined, since although at present we can't compute it, our mathematical knowledge not being to substantial enough, but we will "some day", i.e. it has a definite (but presently unknown) value.

But in the same spirit as above, we could define the following function $g$: $g\equiv1$ if the continuum hypothesis is true and $g\equiv0$ else. Now the CH is known to be independent of ZFC, so this function can't be computed in principle (in ZFC). Of course we could have used any other result that is independent of ZFC.

Somehow this makes me feel uneasy, since my mathematical eduction-long experience taught me that all functions should be computable in the sense that they have a definite value, even if we presently don't know it - whereas the above function $g$ could have any value in $\{ 0,1\}$. So is this second function well-defined ?

(My guess would be yes, since its description, if we think formal about it, can be given strictly in the formal language of first-order logic, just as the description of the function $f$ be. Since $f$ is accepted as a well-defined functions, my naive reasoning would be, that so should $g$.)

• This function has a perfectly well-defined value in any particular model of ZFC. It just doesn't have the same value across all such models. – Qiaochu Yuan Sep 30 '12 at 18:56
• "All functions should be computable in the sense that they have a definite value." Why so? Surely some functions are partial, undefined for some arguments in their domain. Trivially, the two-place function $x/y$ is undefined for $y = 0$. Books on computability theory are full of more interesting examples of partial function. – Peter Smith Sep 30 '12 at 18:58
• Bah, $g$ isn't the problem, it's 0, since we can't figure out which element of $\{ g, 1-g \}$ that 0 is equal to! – Hurkyl Sep 30 '12 at 19:35

## 2 Answers

In any particular model of ZFC, the definition "$z = 1$ if CH is true, $z = 0$ if CH is false" is a perfectly good definition.

More generally, suppose that we have a theory $T$ and a formula $\phi$ in the language of $T$ such that $T$ proves "there is a unique $x$ such that $\phi(x)$ holds". Then we can treat $\phi$ as a definition of some object - namely, the unique object that has the property defined by $\phi$. Of course, $T$ may not be strong enough to tell us anything else about that object other than "it's the one that satisfies $\phi$". This is a general phenomenon in classical logic. But we can reason about this object nevertheless; sometimes we can use $\phi$ and $T$ to deduce other properties of the object.

In many constructive logics, things are different. In these logics, if a formula $\phi(x)$ is true of exactly one object, there is actually a term $t$ - a concrete name for an object - such that $\phi(t)$ holds. This property of a logic is called the "existence property".

Of course classical theories usually do not have the existence property. But we work in them nevertheless. The key point is that whenever a classical statement talks about truth values, this has to be interpreted as talking about truth in a particular structure - and in that structure, every sentence will be either true or false. The fact that the truth value of a sentence may be different in different structures does not affect the fact that its truth value is well defined in each particular structure.

• Great answer, but something is puzzling me: Does this mean, if we think in terms of the "spital" analogy of Hurkyls answer from here math.stackexchange.com/questions/173735/… ,that in set theory #4, the statement is true or false depending on the way in which we model set theory #4 within set theory #2 ? If so, what happens in set theory #2 ? For this version of set theory, it seem to me, we actually don't have a model, since it's just a syntactic construction ? – temo Oct 1 '12 at 15:22
• @temo: at every level that we have classical logic, we have "CH or not CH" as a logical axiom, and thus we can prove there is a unique $x$ such that "$x=0$ if not CH and $x=1$ if CH". This is just syntactic. At the levels where we can work semantically, it can be easier to visualize, but even syntactically we can use a "definition by extensions" to add a new symbol $x$ with the property above. The problem is just that we may not be able to prove anything else about $x$. This idea is related to Hilbert's $\epsilon$ calculus plato.stanford.edu/entries/epsilon-calculus . – Carl Mummert Oct 1 '12 at 19:43

No, your $g$ is not well defined. It's definition contains the phrase "... if the continuum hypothesis is true." But the continuum hypothesis is neither true nor untrue - in a sense, you can choose "true" or "untrue" for the continuum hypothesis, depending on which best suits your current needs.

• Although CH is independent of ZFC, a definition such as "1 if CH, 0 if not CH" is still a perfectly good definition (it's the same as the truth value of CH). CH is true in some settings (models of set theory) and false in others, but in any setting that definition still defines a single, and thus is a definition. Similarly, "0 if the characteristic is 2, 1 otherwise" is a perfectly good definition in any ring, even though the "the characteristic is 2" is neither true nor false in the same way CH is neither true nor false. – Carl Mummert Sep 30 '12 at 23:47