Skip to main content
added warning
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

This answer is incorrect since the function $f\colon\mathbb R \to\mathbb R$ is not computable. That said, it is possible that a similar idea could provide a counterexample.


There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $\varphi_0,\varphi_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $\varphi_{i,s}$ for the part of $\varphi_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} \varphi_{i,s}$, if $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} \varphi_{i,s}$ and $j < k$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} \varphi_{i,s}$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $\varphi_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $\varphi_i$ is not constant and if $\varphi_i(m) = 0$, $\varphi_i(n) = 1$ then $q_m < q_n$) then at some stage $\varphi_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $\varphi_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $\varphi_0,\varphi_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $\varphi_{i,s}$ for the part of $\varphi_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} \varphi_{i,s}$, if $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} \varphi_{i,s}$ and $j < k$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} \varphi_{i,s}$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $\varphi_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $\varphi_i$ is not constant and if $\varphi_i(m) = 0$, $\varphi_i(n) = 1$ then $q_m < q_n$) then at some stage $\varphi_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $\varphi_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

This answer is incorrect since the function $f\colon\mathbb R \to\mathbb R$ is not computable. That said, it is possible that a similar idea could provide a counterexample.


There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $\varphi_0,\varphi_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $\varphi_{i,s}$ for the part of $\varphi_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} \varphi_{i,s}$, if $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} \varphi_{i,s}$ and $j < k$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} \varphi_{i,s}$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $\varphi_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $\varphi_i$ is not constant and if $\varphi_i(m) = 0$, $\varphi_i(n) = 1$ then $q_m < q_n$) then at some stage $\varphi_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $\varphi_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

fixed variable confusion
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $f_0,f_1,\ldots$$\varphi_0,\varphi_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $f_{i,s}$$\varphi_{i,s}$ for the part of $f_i$$\varphi_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} f_{i,s}$$m, n \in \operatorname{dom} \varphi_{i,s}$, if $f_{i,s}(m) = 0$$\varphi_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$$\varphi_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} f_{i,s}$$m, n \in \operatorname{dom} \varphi_{i,s}$ and $j < k$ with $f_{i,s}(m) = 0$$\varphi_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$$\varphi_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} f_{i,s}$$m, n \in \operatorname{dom} \varphi_{i,s}$ with $f_{i,s}(m) = 0$$\varphi_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$$\varphi_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $f_i:\mathbb N \to \{0,1\}$$\varphi_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $f_i$$\varphi_i$ is not constant and if $f_i(m) = 0$$\varphi_i(m) = 0$, $f_i(n) = 1$$\varphi_i(n) = 1$ then $q_m < q_n$) then at some stage $f_{i,s}$$\varphi_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $f_i$$\varphi_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $f_0,f_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $f_{i,s}$ for the part of $f_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} f_{i,s}$, if $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} f_{i,s}$ and $j < k$ with $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} f_{i,s}$ with $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $f_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $f_i$ is not constant and if $f_i(m) = 0$, $f_i(n) = 1$ then $q_m < q_n$) then at some stage $f_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $f_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $\varphi_0,\varphi_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $\varphi_{i,s}$ for the part of $\varphi_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} \varphi_{i,s}$, if $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} \varphi_{i,s}$ and $j < k$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} \varphi_{i,s}$ with $\varphi_{i,s}(m) = 0$ and $\varphi_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $\varphi_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $\varphi_i$ is not constant and if $\varphi_i(m) = 0$, $\varphi_i(n) = 1$ then $q_m < q_n$) then at some stage $\varphi_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $\varphi_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.

Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

There is a computable closed set $C \subseteq [0,1]$ with positive measure that contains no computable real number. (This is well-known but I give a construction below.) The function $f\colon\mathbb R \to \mathbb R$ given by $f(x) = \mu(C \cap [0,x])$ has the property that $f'(x) = 0$ for every computable $x$ but it is not a constant function since $f(0) = 0$ and $f(1) = \mu(C) > 0$. If I understand the question correctly, this gives a counterexample in the effective topos.

To construct such a $C$, build a computable sequence $(a_0,b_0), (a_1,b_1),\ldots$ of open intervals with rational endpoints such that $\sum_{k=0}^\infty b_k - a_k \leq 1/2$ as described below and then let $C = [0,1] \setminus \bigcup_{k=0}^\infty (a_k,b_k)$, which is a closed set of measure at least $1/2$.

Let $f_0,f_1,\ldots$ be a computable enumeration of all partial computable functions $\mathbb N \to \{0,1\}$. Write $f_{i,s}$ for the part of $f_i$ which has converged by stage $s$. Also, fix a computable enumeration $q_0,q_1,\ldots$ of $\mathbb Q$.

At stage $s$ of the construction, suppose we have constructed $(a_0,b_0),\ldots,(a_{k-1},b_{k-1})$. Look for the first $i \leq s$ such that:

  1. For all $m, n \in \operatorname{dom} f_{i,s}$, if $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ then $q_m < q_n$ (i.e., this looks like part of a Dedekind cut so far).
  2. There are no $m, n \in \operatorname{dom} f_{i,s}$ and $j < k$ with $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ such that $a_j < q_m$ and $q_n < b_j$ (i.e., this Dedekind cut has not yet been covered by one of our intervals).
  3. There are $m, n \in \operatorname{dom} f_{i,s}$ with $f_{i,s}(m) = 0$ and $f_{i,s}(n) = 1$ such that $q_m - q_n < 1/3^{i+1}$ (i.e., we know enough about this Dedekind cut to cover it with a small interval).

If such an $i \leq s$ is found, then add the interval $(a_k,b_k = a_k + 1/3^{i+1})$ to the list where $a_k < q_m$ and $q_n < b_k$ for $m,n$ as in condition 3. Otherwise, do nothing and move to the next stage.

Note that if $f_i:\mathbb N \to \{0,1\}$ really is a Dedekind cut (i.e., $f_i$ is not constant and if $f_i(m) = 0$, $f_i(n) = 1$ then $q_m < q_n$) then at some stage $f_{i,s}$ will be large enough to meet requirements 1,2,3. Then the real number represented by $f_i$ will be covered by one interval in our list. Also, since our list contains at most one interval of length $1/3^{i+1}$ for each $i$, it follows that $\sum_{k=0}^\infty b_k - a_k \leq \sum_{i=0}^\infty 1/3^{i+1} = 1/2$.