That validates my earlier point that among all models of the real numbers, the standard (ZF) reals are privileged by virtue of being Cauchy complete. — fishfry
What do you mean by "the standard (ZF) reals"?
Maybe I am saying obvious things, but at risk of being pedantic, I prefer to make everything clear about some basic facts. (That's one of the reasons why I like computer-based formal systems: everything has to be declared. No implicit assumptions!)
Fakt N.1. ZFC is NOT an axiomatic theory of real numbers. ZFC is an axiomatic theory of SETS.
In fact, in first order logic all functions and relations can be applied to all variables, and there cannot be some functions (like addition and multiplication) applied only to numbers and other functions (like union and interception) applied only to sets. In ZFC, all variables are interpreted as SETS.
Fakt N.2. The standard representation of real numbers in ZFC is the following: (
https://www.quora.com/How-is-the-set-of-real-numbers-constructed-by-using-the-axiomatic-set-theory-ZFC-set-theory)
- Natural numbers are sets
- Integers are pairs of natural numbers (a pair is a function with two arguments)
- Rational numbers are pairs of integers
- Real numbers are sets of rational numbers
Here's the definition of real numbers in ZFC in Bourbaki:
https://math.stackexchange.com/questions/2210592/in-which-volume-chapter-does-bourbaki-define-the-real-numbers
Fakt N.3. There is a more "usable" definition of real numbers given by Tarski (usable in the sense that the demonstrations are simpler):
https://en.wikipedia.org/wiki/Tarski%27s_axiomatization_of_the_reals
- Tarski's real numbers are defined axiomatically, and make use of set relations (similar to the ones of ZFC). But they are not based on first order logic.
The difference is that it is allowed the quantification on all subsets of a given set (and not only on all elements of the universe), but the meaning of the subset relations is encoded in the rules of logic, and not given axiomatically.
The use of a second-order logic is essential to be able to express the property of being Dedekind-complete (Axiom 3)
So, going back to what you wrote:
The constructivists agree! They are trying to develop a context in which they can say that the constructive reals are complete.
[From now on complete means Cauchy complete and not any other mathematical meaning of complete]. — fishfry
OK, let's check the definition of being "Cauchy complete":
"Cauchy completeness is the statement that every Cauchy sequence of real numbers converges." (
https://en.wikipedia.org/wiki/Completeness_of_the_real_numbers)
What's a Cauchy sequence? "a Cauchy sequence (French pronunciation: [koʃi]; English: /ˈkoʊʃiː/ KOH-shee), named after Augustin-Louis Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses." (
https://en.wikipedia.org/wiki/Cauchy_sequence)
As you said, in the Coq formalization of real numbers there is this axiom:
completeness ∀f : N → R. ∃x ∈ R.(∀n ∈ N. near(f(n), f(n + 1), n + 1)) →(∀m ∈ N. near(f(m), x, m))
In the logic of Coq, "completeness" IS A FUNCTION, at the same way as "near" is a function and "+" is a function.
The function "completeness" takes as input a sequence of real numbers "f" and returns two things:
1. a real number "x" -- let's call it "first_part"
2. a proof that IF "f" is a Cauchy sequence, THEN "x" is the limit of "f" -- let's call it "second_part"
So, for every sequence of real numbers "f", the term "(completeness f).first_part" is a real number. If I have a proof that "f" is a Cauchy sequence, then I can use "(completeness f).second_part" (that is a proof) to obtain a proof that the Cauchy sequence "f" converges to the real number "completeness f".
That's all I need to get a COMPLETE field of real numbers: for all sequences "f", if you have a proof that "f" is a Cauchy sequence, you can produce a proof that "f" is convergent to the real number "(completeness f).first_part".
However, you can't explicitly compute it, because axioms are functions that cannot be reduced (
https://stackoverflow.com/questions/34140819/lambda-calculus-reduction-steps)
Then, IF you ASSUME that you can get a real number for every Cauchy sequence, THEN you can prove that there is a real number for every Cauchy sequence. Magic!
:-)
* How can the constructive reals be complete? If they are complete they must contain many noncomputable reals. How can that be regarded as constructive? — fishfry
Yes, that's the same old question that I thought I just answered many times...
:-)
Here's the "computation" of pi:
Definition my_sequence := func n -> sum of 1/n bla bla...
Definition pi := "(completeness my_sequence).first_part"
Here's the proof that my_sequence converges to pi:
1. proof that my_sequence is a Cauchy sequence (let's call this proof my_proof)
2. from "(completeness my_sequence).second_part" (the proof that IF "f" is a Cauchy sequence, THEN "x" is the limit of "f") and "my_proof" (the proof that my_sequence is a Cauchy sequence) I get a proof that "x" is the limit of "f"
(by applying the rule of cut)
I "computed" the noncomputable real number pi, and the result is "(completeness "func n -> sum of 1/n bla bla...").first_part
If "completeness" were a theorem instead of an axiom, I should have provided the implementation of the program that computes the function "completeness". But an axiom is treated as an "external function" of a programming language:
I ASSUME to have some external machine that is able to compute the function "completeness", but I don't have to show how that machine works. That's cheating!
:-)
However, remember that this is an AXIOMATIC DEFINITION of what real numbers are, NOT A MODEL of real numbers.
Axiomatic definitions, in whatever logic (intuitionistic or not), are not guaranteed to be consistent: you have to be careful on what axioms you assume to be true.
So, in principle it's not guaranteed that the real numbers that you defined make sense in some concrete model.
And that is true even for Tarski's real numbers, that are described using classical (non intuitionistic) logic.
Instead, this is not true for the description of real numbers in ZFC. In that case, real numbers are a model built from sets, and completeness is PROVED as a theorem, and not assumed as an axiom. Real numbers are concrete objects made of sets!
The problem is that sets are defined axiomatically in ZFC. So, IF sets make sense (are not contradictory), then real numbers make sense. But IT'S NOT GUARANTEED THAT THE SETS DEFINED IN ZFC MAKE SENSE IN SOME CONCRETE MODEL.
So, again, to be sure about the sets of ZFC you should define them as a model in some other axiomatic theory that you trust more than ZFC. Or you could use a FINITE MODEL: in a finite model you can verify a proposition "by hand" (as one of my favourite professors of analysis used to say) simply inspecting the model!
But, obviously, there is no finite model that verifies all the axioms of ZFC. The best that you can do is to verify ZFC axioms on a model built from natural numbers. But natural numbers are NOT a finite model (you cannot check theorems on natural numbers "by hand"). And, as Godel proved, there is no axiomatic definition of natural numbers, in any formal logic, that is guaranteed to make sense.
OK, I'll stop it here because it's just become too long and I am only at the first question.
* Does their formulation actually imply standard Cauchy completeness? — fishfry
Let me rephrase this question: "if a given Cauchy sequence has a limit in intuitionistic logic, does it have a limit even in ZFC?"
The answer is YES, because the axioms of intuitionistic logic correspond to theorems in ZFC, and the rules of intuitionistic logic are just a subset of the rules of classical logic. So, if you can prove that a given sequence is convergent in intuitionistic logic, you can use EXACTLY THE SAME PROOF in classical logic. You can map any proposition of one logic to a corresponding proposition of the other logic and every rule of one logic to a corresponding rule of the other logic. It doesn't matter what's the interpretation of the rules: if the rules are the same (or a subset of them), whatever you can prove in intuitionistic logic you can prove even in classical logic: just apply the same rules!
* In what sense is their formulation constructive? I gather this may have something to do with the rate of convergence, in which case perhaps the theory of computational complexity may come into play. Big-O, P = NP and all that. I'm a big fan of Scott Aaronson's site. — fishfry
Nothing to do with the rate of convergence! Constructive, in the particular interpretation of Coq, means that every object (every real number in this case) can be built using recursive functions ( except axioms...
:-) )
* And if the constructive reals are Cauchy complete, they must contain a lot of noncomputable real numbers. How can that be called constructive? — fishfry
This sentence has a hidden presupposition: that real numbers are a concrete set of objects and you can check if a given noncomputable real number is present or not. This is not true: any model of real numbers is ultimately based on an axiomatic theory that cannot be checked "by hand".
[ I know, I wanted to use formulas to be more precise and at the end I didn't do it (mostly for lack of time). And probably I still wasn't able to be clear enough on what I meant. So, please repeat the questions that I wasn't able to be clear about, or where you thing that I am wrong. Maybe in that way will be easier to arrive at some conclusion ]