Saturday, November 12, 2016

logic - Axiom of Choice - Type Theory (Proof)

Background



In Intuitionistic Type Theory (p. 27-28), Martin Löf provides a proof of the axiom of choice that is constructively valid. This version is considerably weaker than the ordinary set theory version, since there are no quotient types. Now, quotients can to a certain extent be simulated using setoids, and thus the axiom of choice may be reformulated to what Martin Löf (2004) calls Zermelo's axiom of choice. This axiom is non-constructive, as it implies PEM (Diaconescu's theorem). Nonetheless, there are special cases of Zermelo's axiom of choice, which are provable in type theory. I have heard that one of these is the so-called axiom of dependent choice, which can be stated as:




For every set $A$ and for every binary relation $R$ on $A$:

\begin{equation}
(\forall x:A)(\exists y:A)R(x,y) \supset (\forall x:A)(\exists f:N \to A)I(A,\text{Ap}(f,0),x) \land (\forall n:N)R(\text{Ap}(f,n),\text{Ap}(f,S(n)))
\end{equation}




Now, my question is how exactly would one go about proving this result constructively? Would it be to any help to use the version of axiom of choice which Martin Löf proved in Intuitionistic Type Theory?

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...