Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have seen Troelstra's Uniformity Principle stated as: $\forall x \exists n R(x,n) \rightarrow \exists n \forall x R(x,n)$ where $x$ ranges over $\mathbb{P(N)}$ and $n$ ranges over $\mathbb{N}$.

Unless I'm misunderstanding something, this is obviously false in classical mathematics. For example, take $R$ to be the relation $R(x,n)$ iff $n$ is the smallest element of $x$, or $x$ is the empty set and $n=0$.

What is it about constructive mathematics that makes this counterexample invalid there?

Would the principle be classically valid if $x$ was restricted to recursive sets?

Or am I misunderstanding something?

share|improve this question
add comment

2 Answers

up vote 8 down vote accepted

You have stated Troelstra's Uniformithy Principle correctly (contrary to François's claim). There are two reasons why your counterexample does not work. First, we cannot show that every $X \subseteq \mathbb{N}$ is empty or not. Second, we cannot show that every inhabited subset of $\mathbb{N}$ has a minimal element. And we do not need any story about constructivism here. As soon as we assume the Uniformity Principle, it follows that:

  1. Not every $X \subseteq \mathbb{N}$ is empty or not, because that would allows us to form the non-uniform total relation $(X = \emptyset \implies n = 1) \land (X \neq \emptyset \implies n = 42)$.

  2. Not every inhabited subset $X \subseteq \mathbb{N}$ has a minimal element, because that would allow us to form the non-uniform total relation $\min (X \cup \lbrace 42 \rbrace) = n$.

[I added this paragraph later.] Even without the uniformity principle we cannot expect the two statements to be constructively valid because they imply (a restricted form of) excludded middle:

  1. If every set is empty or not, given any truth value $p \in \Omega$, consider the set $\lbrace \star \mid p \rbrace$: it is either empty or not, therefore either $\lnot p$ or $\lnot\lnot p$, which is a restricted form of excluded middle. [EDIT: thanks to Andreas Blass for pointing out an error here.]

  2. If every inhabited set of natural numbers has a minimum, given any truth value $p \in \Omega$, the minimum of the set $\lbrace n \in \mathbb{N} \mid n > 1 \lor p\rbrace$ is either $0$ or not, therfore either $p$ or $\lnot p$, which is excluded middle.

There is no hope to make the Uniformity Principle classically valid, even if we try to restrict to a subfamily of sets:

Theorem: Suppose excluded middle holds and $S \subseteq \mathcal{P}(\mathbb{N})$ is an inhabited family which satisfies the uniformity principle $(\forall X \in S \exists n \in \mathbb{N} . R(X,n)) \implies \exists n \in \mathbb{N} \forall X \in S . R(X, n)$. Then $S$ contains exactly one set.

Proof. Easy exercise. But let's do it anyway. There is an inhabitant $X_0 \in S$. Define the map $f : S \to \mathbb{N}$ by (use of excluded middle coming up...) $$f(X) = \begin{cases} 42 & \text{if $X = X_0$} \\\\ 23 & \text{if $X \neq X_0$} \end{cases}$$ Let $R(X,n)$ be the relation $f(X) = n$. Since $n = 42$ is the only $n$ related to $X_0$, by Uniformity Principle for $S$ we have $\forall X \in S . f(X) = 42$, therefore $\forall X \in S . X = X_0$. QED.

That is, Troelstra's Uniformity Principle is a very non-classical axiom. I disagree that it is a continuity principle. It does not allow one to prove any of the usual continuity statements "all maps are continuous".

share|improve this answer
    
You are absolutely correct, Andrej. Thank you for the correction. –  François G. Dorais Feb 16 '13 at 8:33
2  
In the second item numbered 1, where you consider $\{*|p\}$, should "empty or not" be "empty or inhabited"? Or do you generally take "not empty" to mean inhabited? With just "empty or negation of empty," all I can deduce from your example is $(\neg p)\lor(\neg\neg p)$. –  Andreas Blass Feb 16 '13 at 21:41
    
@Andreas: you are correct, this only proves $\lnot p \lor \lnot\lnot p$. Hmm, can we do better than that? –  Andrej Bauer Feb 16 '13 at 23:27
add comment

The reason why your proposed example is invalid is that equality of sets is not constructively decidable and, in particular, one cannot constructively check whether a set is empty or not. Indeed, checking that $X = \varnothing$ amounts to checking that $n \notin X$ for every $n$, which is not a finite process. Restricting to computable sets does not help. For example, define $X_e$ to be the set of all $s \in \mathbb{N}$ such that the $e$-th Turing machine halts (with blank input) in at most $s$ steps. Deciding whether $X_e = \varnothing$ is equivalent to the halting problem.

That said, your formulation for Troelstra's Uniformity Principle is not correct since it is invalid when $R(X,n)$ is the statement $(0 \in X \rightarrow n = 0) \land (0 \notin X \rightarrow n = 1)$. (I understand that $X$ is a complemented subset of $\mathbb{N}$, which is the usual convention in this context.) The mantra for uniformity principles is that every total function is continuous. Thus your statement is correct if $X$ ranges over $[0,1]$ or $\mathbb{R}$ (which are connected) but not over $\mathcal{P}(\mathbb{N})$ or $\mathbb{N}^\mathbb{N}$ (which are totally disconnected). Thus all continuous functions $[0,1]\to\mathbb{N}$ are constant but there are a larger variety of continuous functions on $\mathcal{P}(\mathbb{N})$. Namely, if $f:\mathcal{P}(k)\to\mathbb{N}$ is any function where $k = \lbrace 0,\dots,k-1\rbrace$, then $F(X) = f(X \cap k)$ defines a continuous function on $\mathcal{P}(\mathbb{N})$ and every continuous function $\mathcal{P}(\mathbb{N})\to\mathbb{N}$ is of this form for some $k$. Thus a correct version of the uniformity principle for $\mathcal{P}(\mathbb{N})$ has the weaker conclusion where the $n$ satisfying $R(X,n)$ is given by such a function.

As Andrej pointed out, the above was confusing the Uniformity Principle with the Continuity Principle. Though they are similar in some ways they occur in different constructive systems and, in particular, the Uniformity Principle does not not occur in contexts where subsets of $\mathbb{N}$ are complemented.

share|improve this answer
2  
You misunderstand. The principle is stated correctly, and sets are not assumed to be completemnted. The complemented subsets are $2^\mathbb{N}$, while $\mathcal{P}(\mathbb{N}) = \Omega^\mathbb{N}$ is much larger. So your example does not work. Troelstra's Uniformity principle is an orhogonality condition, not a continuity principle. –  Andrej Bauer Feb 16 '13 at 7:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.