<p>The question is not research-level but since some of the comments following it may be confusing, allow me to explain precisely how functions are defined by cases.</p>
<p>Suppose we would like to define a function <span class="math-container">$f : A \to B$</span> by cases, like this:
<span class="math-container">$$
f(x) =
\begin{cases}
e_1(x) &amp; \text{if $\phi(x)$},\\
e_2(x) &amp; \text{if $\psi(x)$},
\end{cases}
$$</span>
where expressions <span class="math-container">$e_1(x)$</span> and <span class="math-container">$e_2(x)$</span>may depend on <span class="math-container">$x$</span>.
When is this a valid definition? In set theory (and many other kinds of foundations) a function is the same thing as a functional relation, so let us recall what that means.</p>
<p><strong>Definition:</strong> A relation <span class="math-container">$R \subseteq A \times B$</span> is <em>functional</em> when for every <span class="math-container">$x \in A$</span> there exists exactly one <span class="math-container">$y \in B$</span> such that <span class="math-container">$(x, y) \in R$</span>. The function <span class="math-container">$f_R : A \to B$</span> determined by such a functional relation maps <span class="math-container">$x \in A$</span> to the (unique) <span class="math-container">$y \in B$</span> for which <span class="math-container">$(x,y) \in R$</span>.</p>
<p>The above definition by cases can be written in terms of functional relations, as follows. Define <span class="math-container">$R \subseteq A \times B$</span> by
<span class="math-container">$$R = \{(x,y) \in A \times B \mid (\phi(x) \Rightarrow y = e_1) \land (\psi(x) \Rightarrow y = e_2) \}.
$$</span>
The <span class="math-container">$f$</span> defined by cases is then precisely <span class="math-container">$f_R$</span>. But the question is, what condition must <span class="math-container">$\phi(x)$</span> and <span class="math-container">$\psi(x)$</span> satisfy in order for <span class="math-container">$R$</span> to be functional? A little exercise in logic shows that two conditions must be met:</p>
<ol>
<li><p><strong>Overlap:</strong> for all <span class="math-container">$x \in A$</span>, if <span class="math-container">$\phi(x)$</span> and <span class="math-container">$\psi(x)$</span> then <span class="math-container">$e_1 = e_2$</span>.</p>
</li>
<li><p><strong>Cover:</strong> for all <span class="math-container">$x \in A$</span>, <span class="math-container">$\phi(x)$</span> or <span class="math-container">$\psi(x)$</span>.</p>
</li>
</ol>
<p>Indeed, agreement on overlap guarantees that <span class="math-container">$R$</span> is single-valued, and the cover condition that it is total.</p>
<p>Now we look at the definition given by the OP:</p>
<p><span class="math-container">$$
\mathrm{UC}(\alpha) =
\begin{cases}
0 &amp; \text{if $M_\alpha(\alpha)$ is defined and $M_\alpha(\alpha) = 1$}\\
1 &amp; \text{if $M_\alpha(\alpha)$ is not defined or $M_\alpha(\alpha) \neq 1$}
\end{cases}
$$</span>
So in this case <span class="math-container">$\phi(x)$</span> is “<span class="math-container">$M_\alpha(\alpha)$</span> is defined and <span class="math-container">$M_\alpha(\alpha) = 1$</span>”
and
<span class="math-container">$\psi(x)$</span> is <span class="math-container">$\neg \phi(x)$</span>.
Clearly, the overlap condition is satisfied because there is no <span class="math-container">$\alpha$</span> satisfying both <span class="math-container">$\phi(\alpha)$</span> and <span class="math-container">$\neg \phi(\alpha)$</span>.
The cover condition holds because <span class="math-container">$\phi(\alpha) \lor \neg \phi(\alpha)$</span> is true by the law of excluded middle (this would be problematic if we worked in intuitionistic logic, where excluded middle is not accepted).
In conclusion, <span class="math-container">$\mathrm{UC}$</span> is well defined.</p>

CC BY-SA 4.0
2022-04-13T19:02:44.150Z
2022-04-14T08:10:39.013Z
2022-04-14T08:10:39.013Z
Andrej Bauer
<p>The following is from Arora and Barak's &quot;Computational Complexity.&quot; I think one does not have to read the second paragraph of the proof to answer this question.</p>
<blockquote>
<p><strong>Theorem 1.10</strong> There exists a function <span class="math-container">$\operatorname{UC}:\{0,1\}^*\to\{0,1\}$</span> that is not computable by any TM (turing machine).</p>
<p>Proof: The function <span class="math-container">$\operatorname{UC}$</span> is defined as follows: For every <span class="math-container">$\alpha\in\{0,1\}^*$</span>, if <span class="math-container">$M_\alpha(\alpha)=1$</span>, then <span class="math-container">$\operatorname{UC}(\alpha)=0$</span>; otherwise (if <span class="math-container">$M_\alpha(\alpha)$</span> outputs a different value or enters an infinite loop), <span class="math-container">$\operatorname{UC}(\alpha)=1$</span>.</p>
<p>Suppose for the sake of contradiction that <span class="math-container">$\operatorname{UC}$</span> is computable and hence there exists a TM <span class="math-container">$M$</span> such that <span class="math-container">$M(\alpha)=\operatorname{UC}(\alpha)$</span> for every <span class="math-container">$\alpha\in\{0,1\}^*$</span>. Then, in particular, <span class="math-container">$M(\lfloor M\rfloor) = \operatorname{UC}(\lfloor M\rfloor)$</span>. But this is impossible: By the definition of <span class="math-container">$\operatorname{UC}$</span>,
<span class="math-container">\begin{equation}
\operatorname{UC}(\lfloor M\rfloor)=1 \Leftrightarrow M(\lfloor M\rfloor)\neq 1
\end{equation}</span></p>
</blockquote>
<p>My question is, how can one be sure that <span class="math-container">$\operatorname{UC}$</span> is well-defined? What if the result of <span class="math-container">$M_\alpha(\alpha)$</span> is mathematically undetermined (i.e., Both <span class="math-container">$M_\alpha(\alpha)=1$</span> and its negation are not provable from the axioms)?</p>
<hr />
<p><strong>Notations.</strong> <span class="math-container">$\{0,1\}^*$</span> is the set of all strings composed of <span class="math-container">$0$</span> and <span class="math-container">$1$</span>. <span class="math-container">$M_\alpha$</span> is the turing machine represented by the string <span class="math-container">$\alpha$</span>. <span class="math-container">$\lfloor M\rfloor$</span> is a string representing the turing machine <span class="math-container">$M$</span>.</p>

CC BY-SA 4.0
2022-04-12T10:54:52.403Z
The assumption here is that even if something is unprovable, it can still be either true or false.
Peter Shor 
CC BY-SA 4.0
2022-04-12T15:08:55.747Z
$\mathsf{UC}$ is well-defined by excluded middle: either $M_\alpha(\alpha) = 1$ or not. The whole thing has nothing to do with provability, nor is the assumption "even if something is unprovable it can still be true or false" present anywhere (and it's a really strange "assumption" to make in the first place).
Andrej Bauer
CC BY-SA 4.0
2022-04-12T23:27:41.463Z
@PeterShor: it is not an assumption that statements are either true or false, even when unprovable. That's just the law of excluded middle. Or are you talking about intuitionistic mathematics?
Andrej Bauer
CC BY-SA 4.0
2022-04-13T00:06:45.173Z
@Andrej Bauer: The law of the excluded middle **is** an assumption.
Peter Shor 
CC BY-SA 4.0
2022-04-13T05:34:23.727Z
@PeterShor: Thank you for making your position clear. It is of course a valid possibility, namely making every mathematical statement you ever utter contingent on all the laws of logic. I am not sure this is the best way to explain the current question, however.
Andrej Bauer
CC BY-SA 4.0
2022-04-13T17:08:05.350Z
@AndrejBauer Conceptually, how is uncomputable function related to Godel's true (but unprovable) statements from first Incompleteness Theorem?
Ajax
CC BY-SA 4.0
2022-04-13T18:42:06.977Z
@Ajax: I do not understand your question.
Andrej Bauer
CC BY-SA 4.0
2022-04-13T19:06:37.537Z
@AndrejBauer Is "uncomputability" behind Incompleteness?
Ajax
CC BY-SA 4.0
2022-04-13T19:28:50.027Z
@Ajax: If you would like to ask a precise, I recommend you do it on math.stackexchange.com. These comments cannot serve that purpose.
Andrej Bauer
CC BY-SA 4.0
2022-04-14T12:58:15.127Z
The *existence* of uncomputable functions follows trivially from cardinality arguments (computable functions are a countable set). The *interesting* result is that there are Recursively Enumerable yet undecidable languages.
Aryeh
CC BY-SA 4.0
2022-04-17T14:40:01.907Z
@Andrej Bauer: one way I expressed my comment the way I did is that I didn't want to tell the OP that he was completely wrong when there are (intuitionist) mathematicians who reason the same way that he intuitively did.
Peter Shor 
CC BY-SA 4.0
2022-04-17T14:51:31.327Z
@PeterShor:  You must be thinking of intuitionistic explanations of truth that equate truth with provability (which I disagree with when I pretend to be an intuitionist). It would be helpful if the OP gave some feeback. On the other hand, I don't think it's worth dwelling on this particular question any longer.
Andrej Bauer
<computability><turing-machines><undecidability>
Understanding the construction of an uncomputable function
zxcv
# Understanding the construction of an uncomputable function

(Asked by: username_0 on 2022-04-12)

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question.

> **Theorem 1.10** There exists a function $\operatorname{UC}:\{0,1\}^\*\to\{0,1\}$ that is not computable by any TM (turing machine).
>
> Proof: The function $\operatorname{UC}$ is defined as follows: For every $\alpha\in\{0,1\}^\*$, if $M\_\alpha(\alpha)=1$, then $\operatorname{UC}(\alpha)=0$; otherwise (if $M\_\alpha(\alpha)$ outputs a different value or enters an infinite loop), $\operatorname{UC}(\alpha)=1$.
>
> Suppose for the sake of contradiction that $\operatorname{UC}$ is computable and hence there exists a TM $M$ such that $M(\alpha)=\operatorname{UC}(\alpha)$ for every $\alpha\in\{0,1\}^\*$. Then, in particular, $M(\lfloor M\rfloor) = \operatorname{UC}(\lfloor M\rfloor)$. But this is impossible: By the definition of $\operatorname{UC}$,
> \begin{equation}
> \operatorname{UC}(\lfloor M\rfloor)=1 \Leftrightarrow M(\lfloor M\rfloor)\neq 1
> \end{equation}

My question is, how can one be sure that $\operatorname{UC}$ is well-defined? What if the result of $M\_\alpha(\alpha)$ is mathematically undetermined (i.e., Both $M\_\alpha(\alpha)=1$ and its negation are not provable from the axioms)?

---

**Notations.** $\{0,1\}^\*$ is the set of all strings composed of $0$ and $1$. $M\_\alpha$ is the turing machine represented by the string $\alpha$. $\lfloor M\rfloor$ is a string representing the turing machine $M$.

**Tags:** computability, turing-machines, undecidability

> **Comments:**
> **username_1**: The assumption here is that even if something is unprovable, it can still be either true or false.  
> **username_2**: $\mathsf{UC}$ is well-defined by excluded middle: either $M_\alpha(\alpha) = 1$ or not. The whole thing has nothing to do with provability, nor is the assumption "even if something is unprovable it can still be true or false" present anywhere (and it's a really strange "assumption" to make in the first place).  
> **username_2**: @PeterShor: it is not an assumption that statements are either true or false, even when unprovable. That's just the law of excluded middle. Or are you talking about intuitionistic mathematics?  
> **username_1**: @username_2: The law of the excluded middle **is** an assumption.  
> **username_2**: @PeterShor: Thank you for making your position clear. It is of course a valid possibility, namely making every mathematical statement you ever utter contingent on all the laws of logic. I am not sure this is the best way to explain the current question, however.  
> **username_3**: @AndrejBauer Conceptually, how is uncomputable function related to Godel's true (but unprovable) statements from first Incompleteness Theorem?  
> **username_2**: @username_3: I do not understand your question.  
> **username_3**: @AndrejBauer Is "uncomputability" behind Incompleteness?  
> **username_2**: @username_3: If you would like to ask a precise, I recommend you do it on math.stackexchange.com. These comments cannot serve that purpose.  
> **username_4**: The *existence* of uncomputable functions follows trivially from cardinality arguments (computable functions are a countable set). The *interesting* result is that there are Recursively Enumerable yet undecidable languages.  
> **username_1**: @username_2: one way I expressed my comment the way I did is that I didn't want to tell the OP that he was completely wrong when there are (intuitionist) mathematicians who reason the same way that he intuitively did.  
> **username_2**: @PeterShor:  You must be thinking of intuitionistic explanations of truth that equate truth with provability (which I disagree with when I pretend to be an intuitionist). It would be helpful if the OP gave some feeback. On the other hand, I don't think it's worth dwelling on this particular question any longer.  

---

## 1 answers

### Answer by username_2 on 2022-04-13. Score: 1

The question is not research-level but since some of the comments following it may be confusing, allow me to explain precisely how functions are defined by cases.

Suppose we would like to define a function $f : A \to B$ by cases, like this:
$$
f(x) =
\begin{cases}
e\_1(x) & \text{if $\phi(x)$},\\
e\_2(x) & \text{if $\psi(x)$},
\end{cases}
$$
where expressions $e\_1(x)$ and $e\_2(x)$may depend on $x$.
When is this a valid definition? In set theory (and many other kinds of foundations) a function is the same thing as a functional relation, so let us recall what that means.

**Definition:** A relation $R \subseteq A \times B$ is *functional* when for every $x \in A$ there exists exactly one $y \in B$ such that $(x, y) \in R$. The function $f\_R : A \to B$ determined by such a functional relation maps $x \in A$ to the (unique) $y \in B$ for which $(x,y) \in R$.

The above definition by cases can be written in terms of functional relations, as follows. Define $R \subseteq A \times B$ by
$$R = \{(x,y) \in A \times B \mid (\phi(x) \Rightarrow y = e\_1) \land (\psi(x) \Rightarrow y = e\_2) \}.
$$
The $f$ defined by cases is then precisely $f\_R$. But the question is, what condition must $\phi(x)$ and $\psi(x)$ satisfy in order for $R$ to be functional? A little exercise in logic shows that two conditions must be met:

1. **Overlap:** for all $x \in A$, if $\phi(x)$ and $\psi(x)$ then $e\_1 = e\_2$.
2. **Cover:** for all $x \in A$, $\phi(x)$ or $\psi(x)$.

Indeed, agreement on overlap guarantees that $R$ is single-valued, and the cover condition that it is total.

Now we look at the definition given by the OP:

$$
\mathrm{UC}(\alpha) =
\begin{cases}
0 & \text{if $M\_\alpha(\alpha)$ is defined and $M\_\alpha(\alpha) = 1$}\\
1 & \text{if $M\_\alpha(\alpha)$ is not defined or $M\_\alpha(\alpha) \neq 1$}
\end{cases}
$$
So in this case $\phi(x)$ is “$M\_\alpha(\alpha)$ is defined and $M\_\alpha(\alpha) = 1$”
and
$\psi(x)$ is $\neg \phi(x)$.
Clearly, the overlap condition is satisfied because there is no $\alpha$ satisfying both $\phi(\alpha)$ and $\neg \phi(\alpha)$.
The cover condition holds because $\phi(\alpha) \lor \neg \phi(\alpha)$ is true by the law of excluded middle (this would be problematic if we worked in intuitionistic logic, where excluded middle is not accepted).
In conclusion, $\mathrm{UC}$ is well defined.


---

