## Quantum Computing Since Democritus Lecture 2: Sets

Cardinals, ordinals, and more. A whole math course compressed into one handwaving lecture, and a piping-hot story that’s only a century old.

The Blog of Scott Aaronson

*If you take just one piece of information from this blog:*

Quantum computers would not solve hard search problems

instantaneously by simply trying all the possible solutions at once.

Quantum computers would not solve hard search problems

instantaneously by simply trying all the possible solutions at once.

Comment #1 September 19th, 2006 at 10:12 am

I don’t understand why the axiom of choice leads to well-ordering. Let A=[0,1] and let f(B) be (1+lub(B))/2, where lub means least upper bound. (Define something else for the case when lub(B)=1 and 1in B. It doesn’t matter what you choose because this won’t come up in your proof.)

Then your sequence is 1/2, 3/4, 7/8, …, which can definitely go on forever without filling all of A.

Comment #2 September 19th, 2006 at 10:52 am

Sure it goes on forever; the point is that we’re willing to be

extremelypatient, and continue the sequence way up into the transfinite ordinals. So we will indeed get to 1, and from there to the rest of the unit interval.(I can guess the next question: how we do this without assuming the well-ordering we set out to prove? I think the point is that, for any fixed cardinal C, one can prove directly that there are more than C ordinals, by considering the set of ordinals with at most C predecessors and then taking the least sucessor. So we know that a “long enough well-ordering”

exists; the question is whether there’s a well-ordering with theexactcardinality of A, or whether in constructing a well-ordering we simply “skip over” that cardinality. Greg or someone else: did I screw up?)Comment #3 September 19th, 2006 at 12:44 pm

I did some series of notes on Democritus time ago, they are in the Physics section of the arxiv.

Note the vision of atoms of Democritus is more near of the vision of tangent and cotangent space of the matematicians than of the vision of molecules of the chemistrians. About atoms and vacuum, he told “Thing and No-thing do exist in the same way, and depend one from another”.

Also check the concept of “eidola”. There are kind of bosons, if you think atoms are fermions.

Comment #4 September 19th, 2006 at 3:12 pm

Thanks, Alejandro! I have nothing against reading more into the ancients than what they wrote explicitly (I’ve been known to do it myself), but that Democritus presaged the boson/fermion distinction is a bit much to swallow…

Comment #5 September 19th, 2006 at 6:37 pm

Off-topic, but I thought you might want to give a bit of attention to 2006 MacArthur Fellow Luis von Ahn and the ALADDIN Center in another post.

Comment #6 September 19th, 2006 at 7:59 pm

Have you bribed/blackmailed someone to be able to teach a course like this, or is Canada just an open-minded place, or.. what’s the story?

Comment #7 September 19th, 2006 at 9:51 pm

Scott sez: [i]So we know that a “long enough well-ordering” exists; the question is whether there’s a well-ordering with the exact cardinality of [C], or whether in constructing a well-ordering we simply “skip over” that cardinality.[/i]

Given that an ordinal W which is at least as large as C exists, consider an injection f: C –> W. The image of C in f is well-ordered by virtue of being a subset of W. Then, define

Comment #8 September 20th, 2006 at 1:28 am

Niel: How do we know such an injection exists?

Comment #9 September 20th, 2006 at 1:51 am

andy: Not only did I not have to bribe IQC; they should be paying me (and many of the faculty are sitting in). And while I’d love to credit Canada’s openmindedness, I taught an even crazier course through the DeCal program at Berkeley (“Physics, Philosophy, Pizza”). Maybe the bottom line is that, at a university, announcing a willingness to teach puts you in a strong position.

Comment #10 September 20th, 2006 at 1:56 am

If you construct in a formal language a sentence similar to Godel’s sentence but saying (informally) “This sentece can be proved” instead of “not be proved” like the Godel one, wouldn’t that qualify as an answer to your closing question?

My dusty memories from GEB are recalling something named the Henkin sentence, but I’m not sure it is exactly what you are asking for and I am too lazy to google it now.

Comment #11 September 20th, 2006 at 3:08 am

Alejandro: That’s a very good suggestion! But surprisingly, “This sentence can be proved”

canbe proved, as follows:Let F be our formal system, and let S = “This sentence can be proved in F.”

Then as you pointed out, we can prove in F that “if F proves S, then S.”

Taking the contrapositive, we can also prove in F that “if S is false, then F

can’tprove S.”But this implies that the theory F+not(S) can prove its own consistency (since saying that F+not(S) is inconsistent is equivalent to saying that F can prove S).

But we know from Godel that, if F+not(S) can prove its own consistency, then it must be

inconsistent.Therefore S is true. 🙂

(To give away the answer to the puzzle: one can generalize this result to show that

anystatement that can be proved by assuming its provability, can also be proved without assuming its provability.)Comment #12 September 20th, 2006 at 11:20 am

Scott…

Nice lecture style.

Reminds me of some other good pedagogues… quirky like Hofstadter, pithy like Feynman…

Most of all it reminds me of David Foster Wallace… are you familiar with him? He’s a novelist, but he wrote a nice little book on Cantor that you might want to check out.

Comment #13 September 20th, 2006 at 11:26 am

No, I haven’t read Wallace. I’ll take a look — thanks!

Comment #14 September 20th, 2006 at 11:47 am

How do we know such an injection exists?Is this not precisely what is meant by W being “at least as large as C”?

Comment #15 September 20th, 2006 at 12:22 pm

I think it means that for any

mappingthere are elements of W left over. But how do we ensure the mapping is an injection?Comment #16 September 20th, 2006 at 1:46 pm

Scott,

I am told that the axiom of choice is needed to prove the well-known theorem that a countable union of countable sets is countable. You use something similar in your argument assuming against the continuum hypothesis when you claim that set B has cardinality aleph_1. So I imagine that argument relies on choice.

Comment #17 September 20th, 2006 at 4:04 pm

I am told that the axiom of choice is needed to prove the well-known theorem that a countable union of countable sets is countable.Thanks! It seems you’re right. Or rather, we need the axiom of

countablechoice (which is much wimpier than AC itself).I suppose this is if we somehow know the sets are countable, but

don’thave explicit bijections between them and the positive integers? If we have such bijections, then we can easily prove that the union is countable without AC (or even countable AC), by the same trick used to show the denumerability of the rationals. But what does it mean to know a set is countable without having a bijection from it to the integers? Maybe I’m just tired, but I’d appreciate any help.Comment #18 September 20th, 2006 at 4:13 pm

But what does it mean to know a set is countable without having a bijection from it to the integers?That’s right, Scott, you have

abijection. Or rather, you have a non-empty set of bijections and you have the poewr to selection one. You need countable choice in order to select an infinite sequence of such bijections.It looks like the sort of thing that could be proven by induction, but for some subtle reason, formal induction is not logically enough.

Comment #19 September 20th, 2006 at 5:14 pm

Ah — thanks!

Also, Greg: is my understanding correct that even without AC, you can construct arbitrarily long well-orderings (just maybe not of the particular sets you’re interested in)?

Comment #20 September 20th, 2006 at 6:24 pm

I think this is relevant to Scott’s last question. My favorite statement equivalent to choice is that cardinals are totally ordered. (Incidentally, I think it’s true without choice that any totally ordered set of cardinals is well-ordered.)

For example, it is consistent with ZF to assume the existence of a “Dedekind-finite” set, which contains subsets of unbounded finite size, but does not contain the integers.

Comment #21 September 20th, 2006 at 8:40 pm

A very important paper has just come out.

http://www.arxiv.org/abs/cond-mat/0609441

Comment #22 September 20th, 2006 at 9:40 pm

Also, Greg: is my understanding correct that even without AC, you can construct arbitrarily long well-orderings (just maybe not of the particular sets you’re interested in)?This is what Munkres seems to say in his book, “Topology”. I am not expert in the construction.

Comment #23 September 20th, 2006 at 9:54 pm

Ah! I’ve realised that you used a slightly different definition in class than I am accustomed to. (I must have phased out for a moment at that point.) So: your definition is that

A is strictly larger than B if there are no surjections from B onto A.

Okay. Suppose W is at least as large as C, i.e. C is not larger than W. Then, there

isa surjection f from W onto C. If f is also injective, we’re done. Otherwise, for each c in C, consider the pre-image f*(c): this is a set of elements in W mapping to c. Each of these will have a minimal element, because W is an ordinal. Then, let g: C –> W be the function mapping g(c) = min f*(c): this is an injection from C to W, reducing to my previous argument.As a corollary, we find that your definition of the order on cadinals is at least as strong as the one I’m accustomed to, because we can always reduce the construction of an injection into a set B to construction of an injection into a cardinal of the same size as B.

Comment #24 September 21st, 2006 at 5:03 am

The aleph character ℵ can be written in HTML ℵ Might save you some time later

Comment #25 September 21st, 2006 at 8:09 am

Anonymous said:

A very important paper has just come out. http://www.arxiv.org/abs/cond-mat/0609441It’s an ingenious paper, a very good paper. But it flunks the “simply” test. Namely, if an article written by a theorist uses the word “simply”, then they are very commonly talking about something that is extraordinarily difficult to achieve in practice—so difficult that the author does not wish to talk about how it is to be accomplished.

In the case at hand:

The measurement in the phase basis can be performed by simply connecting leads 1 and 2 to a measuring circuit.There is nothing simple about connecting and disconnecting leads! Particularly since these particular leads, in their insolating state, need to achieve exponentially great isolation.

Comment #26 September 21st, 2006 at 8:09 am

The aleph character ℵ can be written in HTML ℵ Might save you some time laterThanks! But in my browser, it’s a pretty ugly aleph; it looks more like an R.

Comment #27 September 21st, 2006 at 8:13 am

Niel, Greg, Douglas, et al.:

I’ve had it! It seems clear that the consequences of not(AC) are

muchmore perverse than those of AC. From now on, I declare that we shall be working in ZFC.Comment #28 September 21st, 2006 at 10:20 am

Scott: I agree. It should just be said that, even though generalities of set theory are more intuitive with AC, specific examples are more intuitive without it. For instance, I have never seen a construction that depends on the axiom of choice that is of any real use in physics.

Here is one of the least intuitive examples based on AC that comes to mind: There exists a pair of functions y = f(x) and x = g(y) such that every point in the plane is uniquely written as either (x,f(x)) or (g(y),y), but never both. In other words, the plane is the disjoint union of the graph of a function and the sideways graph of another function.

As Niel explained, the prospect of ordering sets by size is radically different without AC. The standard definition of “B is bigger than A” is that there is an injection from A to B. This is popular because of the Schroder-Bernstein theorem, which establishes without AC that if there are injections in both directions, then there is a bijection. A different definition is that there is a surjection from B to A. The equivalence to the injection definition requires the axiom of choice and is indeed not very different from it. Without AC, there can be sets A and B with surjections in both directions but no bijection. There can be sets A and B with no injection, surjection, or bijection in either direction. In other words, cardinality becomes a partial ordering rather than a total ordering.

Even though I usually like the axiom of choice too, I think that it pays to be agnostic for some purposes, probably including some questions in complexity theory. If a theorem really needs the uncountable axiom of choice, then it somehow has a different flavor from most results in mathematics. If a proof needs it but the theorem doesn’t, then it may still be a great proof, but it is invariably morally incomplete.

Comment #29 September 21st, 2006 at 10:47 am

Here is one of the least intuitive examples based on AC that comes to mind: There exists a pair of functions y = f(x) and x = g(y) such that every point in the plane is uniquely written as either (x,f(x)) or (g(y),y), but never both. In other words, the plane is the disjoint union of the graph of a function and the sideways graph of another function.This seems wrong. Choose a triple (x1,x2,x3) and another triple (y1,y2,y3). Then AC or no AC, for any functions f and g, at most 3 of the 9 points (xi,yj) can be written as (x,f(x)) and at most 3 can be written as (g(y),y).

Comment #30 September 21st, 2006 at 10:55 am

Given the fact that the Continuum Hypothesis is undecidable anyway, do we really pay a heavy price for the cardinals not being totally ordered? I mean, except for set theorists, no-one really seems to encounter any infinite cardinalities except for the “Beth” cardinalities: i.e. B(n), where B(0) = ℵ_0, and B(n+1) = 2^B(n) for all n >= 0. These

canbe totally ordered, which is the really important thing.Having said that, it is sort of nice to have the AC around for taking arbitrary sections of non-injective functions… just in case I ever feel like doing it… and am dealing with a non-injective function on an uncountable set which has no structure I know about. Or something.

Comment #31 September 21st, 2006 at 2:00 pm

Scott: You are right. I misremembered the example. The real example is that if you assume the axiom of choice and the continuum hypothesis, then the plane can be partitioned into countably many graphs of functions, and sideways graphs of functions.

Both the axiom of choice and the continuum hypothesis are “intuitive”.

A remark: The criticism that life without the axiom of choice (which can include specific axioms that contradict it) is counterintuitive can be compared to the criticism that quantum probability is counterintuitive. Of course you and I love the latter and have no intention of parting with it just for that reason. The situation with AC is a little different because neither AC nor its absence are “realistic”. Even so, you have to say more to justify the axiom of choice than to say that its absence is perverse.

On that note, here is a typical example where the axiom of choice is not as inviolate as it first seems. You need it to know that every vector space has an algebraic basis. Certainly it seems perverse that any vector space shouldn’t have a basis. But then, if you look at vector spaces that actually need the axiom of choice to have a basis, for example an infinite-dimensional Hilbert space, the bases that you get are themselves perverse. They lead you to wonder why you wanted an algebraic basis in the first place. Usually there is no reason. Topological bases for Hilbert spaces are great; algebraic bases are junk.

Comment #32 September 21st, 2006 at 2:10 pm

Oh also, to answer the original question addressed to me: Well-ordered sets can’t skip any cardinalities. If A is well-ordered and there is an injection from B to A, then B is also well-ordered (trivially). Then the set of well-ordered sets is fully ordered by cardinality, again using injections for the ordering. As I said, the Schroder-Bernstein theorem tells you that injections are a completely healthy way to partially order cardinalities, even without AC.

But what you can see without AC is other sets that cannot be well-ordered, and are not smaller than any well-ordered set. I do not know whether these unorderable sets have to be bigger than all well-ordered sets, or whether they can be non-comparable with some of them. I would guess that both are possible.

Well-ordering leads naturally to the continuum hypothesis, the question of whether there are any cardinalities between the countable ordinal aleph_0, and the continuum, which is also 2^(countable). You can’t really put faith in the axiom of choice without at least asking this question. But of course, Paul Cohen showed that it is independent of the axioms of set theory. Cohen has been quoted as saying that the falsehood of the continuum hypothesis is a more interesting and useful class of worlds than the one in which it is true.

Certainly this business of partitioning the plane into countably many graphs of functions (both regular and sideways) is strange. It could be taken as an argument against the continuum hypothesis.

Comment #33 September 21st, 2006 at 3:30 pm

Greg: Yes, I assumed you meant countably many functions. In that case, it’s basically the same problem as I gave at the end of Lecture 1.

If I understand what you’ve written, the situation without AC is even worse than I thought. Sure, a well-ordering doesn’t “skip over” any cardinalities, but that’s just within one chain in a poset! The other cardinalities, the ones not in that chain, are certainly “skipped.”

I agree that we’re often forced, by theorems or experiments, to accept things that seem perverse. But in the case of AC and CH, is there really much more to do than work out the consequences of their truth and falsehood, and decide which seem less perverse to us?

Comment #34 September 22nd, 2006 at 4:16 am

I would argue that any result contingent on the axiom of choice is an uninteresting result, and any result that is independent of the axiom of choice should be proved without it. I think postulating or not postulating the axiom of choice is a bit like postulating the existence of God or not. You will never get a contradiction if you do, but really what’s the point? And as with the existence of God, it is often psychologically useful to assume it for your internal thoughts, but to use it in an argument in public is a bit embarrassing, and certainly beneath the dignity of a real mathematician.

I agree completely with GK’s comments about ridiculous bases in infinite-dimensional vector spaces.

The traditional scheme-theoretic foundations of algebraic geometry apparently rely heavily on the axiom of choice — if a ring has no maximal ideals, then its spectrum has no points, and then your theory goes nowhere. But this is really only a problem if you want your spaces to be sets of points equipped with extra structure. It is possible to get around this (using sheaves on Grothendieck topologies), in which case the large (=interesting) part of the theory could be made independent of choice. When you do this, you find everything looks much nicer. Unfortunately, there are no expositions from this point of view.

Finally, it is often useful to excise the AC for geometric purposes. If you believe the AC, then surjective maps of sets have right inverses. But this is not true geometrically. If you have a surjective map of families of sets (say, discrete fiber bundles), it usually does not have a right inverse.

Comment #35 September 22nd, 2006 at 1:04 pm

James,

Your abstract position is probably common, but your application of it to algebraic geometry is

bizarre. I would guess that a more typical application would be to insist on restricting to rings that can be proved to have points.Sure, constructive logic can be modeled by topoi, but do constructivists like this point of view? Isn’t this the part where Grothendieck’s invocations of higher cardinals come densest?

Do you know how to do homological algebra without choice, even for abelian groups? Do injective objects cease to exist, but objects adapated to pushforward functors do exist, and are all we need? How about constructively?

Comment #36 September 22nd, 2006 at 10:34 pm

Douglas Knight,

I should come clean and say my opinions are based on gut feelings and a bit of thought as a worker with some interest in foundations. I certainly haven’t gone through things systematically.

Regarding your questions:

– I have no idea if constructivists like this point of view.

– I also don’t know about the higher cardinals. I am pretty atheistic regarding set-theoretic subtleties, but even more I’m practical, so perhaps that’s is an unattainable ideal.

– What is the problem with homological algebra? With abelian groups, you have canonical free resolutions. In general, there is supposedly a theorem that any Grothendieck topos has enough injectives, so it seems unlikely you need points to construct them (because it appears to be true for toposes without enough of them). Is it true that to prove such a theorem you need choice? If so, I would still bet you could do it with Cech cohomology and hyper-coverings, as in SGA4.

Whatever the case in general, I would definitely think that if you have both a sheaf and a space defined without using choice, you should be able to write down the cohomology groups without using choice. But if you put up a really good argument, you might be able to convince me that even if you can do this in any explicitly given situation, you still won’t be able to develop a general, black-box theory. Maybe, but I still doubt it.

If you know of any specific subtleties I’m overlooking, I would love to know them. (Who says reading blogs is a waste of time?)

Comment #37 September 23rd, 2006 at 12:59 am

-In response to Greg (about relevance of AC for physics): If my understanding is correct, the Hahn-Banach theorem (which depends on Zorn’s Lemma, and thus on AC) is very useful for proving certain existence results in PDE theory. To be sure, this is more relevant for “understanding” PDEs than actually using them, but I think this deserves to be counted at least as an indirect application.

-In response to James: I disagree that any result that depends on AC is, ipso facto, uninteresting. But even if that were the case, it is hardly grounds for throwing away the axiom. I think we are entitled to use uninteresting technical results if they are useful for something–such as constructing an aesthetically satisfying theory.

All that the Axiom of Choice says is that the Cartesian product of a family of nonempty sets is nonempty. That seems like a perfectly reasonable axiom of set theory to me. Now, I think we should, as a general principle, try to get as many results as possible with as few axioms as possible. But this is only because I favor a sort of Occam’s razor, or “efficiency” criterion of mathematical aesthetics. It is not because I have any doubts about the “soundness” of AC, or because I find the Axiom itself unpleasant. In other words, I would treat AC just like any other axiom.

Here’s a situation that I think would be very interesting (and it applies just as much to any axiom as it does to AC): a theorem with two different proofs, one of which was short, simple and using AC, and the other of which was long and complex but avoided AC. The interesting question about such a result would be not which proof was better (though I personally would prefer the short, nice one), but what it is about the result that would cause it to be true for two (apparently independent) reasons.

I’m sure there are actual examples of this–does anyone know any?

Comment #38 September 23rd, 2006 at 2:42 am

James,

The only proof I know that Q is an injective Z-module uses Baer’s criterion, and Baer’s criterion definitely uses choice. I would say that the theory of homological algebra by injective resolutions is an interesting theory that uses choice. Grothendieck’s theorem that topoi have injective objects is a corollary of a theorem with the same conclusion for abelian categories satisfying an axiom about infinite products. That does not sound choice-safe to me. Not to mention that it surely reduces things to abelian groups, which are already hopeless.

I see two ways around injective objects.

One is to redefine injective objects so that they exist, but don’t have the lifting property. I don’t know if this is adequate for proving theorems. For noetherian rings, where choice isn’t needed to get maximal ideals, there’s a characterization of injective modules in terms of localizations.

The other is to hope to find other resolutions to define derived functors. Again, the proofs need to be completely done over. One can define Ext using projective resolutions and derived pushforwards using (hyper)czech resolutions. That covers Ext of modules, but Ext of coherent sheaves is trickier. If you have enough vector bundles, you could resolve the left variable by them and the right variable by Czech methods. If you don’t, maybe you can resolve by sheaves that aren’t coherent.

Comment #39 September 23rd, 2006 at 3:28 pm

Often it is actually not necessary to use to full axiom of choice. For many of the common applictions one can instead use the “Axiom of dependent choice”, DC, which is a weakend form of AC that still lets you do many of the nice AC-based proofs but does not let you construct some of the unpleasent things AC give rise to, e.g non-measurable sets.

DC is sufficient for proving that a countable union of coutable sets is countable.

There is a short wikipedia entry on DC

http://en.wikipedia.org/wiki/

Axiom_of_dependent_choice

One can construct a quite nice set theory by replacing the full AC by DC and also adding the determined games axiom. Again I’ll refer to wikipedia for a statment of this axiom

http://en.wikipedia.org/wiki/

Axiom_of_determinacy

Comment #40 September 23rd, 2006 at 6:23 pm

About Hamel bases in infinite-dimenional vector spaces: they don’t disappear if we remove AC. The only thing that changes is that we’re not allowed call them “sets” any more. But the elements don’t go anywhere!

For example: take a vector in your favorite infinite-dimensional Hilbert space. Now take a countable set of linearly independent vectors, and call it S. Now take a vector x_1 outside S such that S’ := S union {x_1} is a linearly independent set (this is possible by a Baire category argument–remember we’re only considering finite linear combinations). Now take a vector x_2 outside S’ such that S” := S’ union {x_2} is a linearly independent set. Et cetera. There’s nothing to stop us from continuing this process a countable number of times. But there are an uncountable number of vectors in the space; you have to accept that whether or not you accept AC. So why shouldn’t we be allowed to put “enough” elements in the set so that it will become linearly dependent if another element is added? You can’t argue that uncountably many elements in the set is too many, because we’re talking about something that would be a

subsetof an uncountable set that you are already acknowledge to exist, namely the underlying Hilbert space!If you don’t like Hamel bases, you don’t have to use them. But throwing out AC because it would force us to acknowledge their status as “sets” is rather silly, in my opinion.

Comment #41 September 23rd, 2006 at 8:20 pm

Douglas Knight,

OK, you’ve made some good points. And I concede that, for now, I cannot put up a good defense of mine. In particular, thanks for pointing out that injective objects are as trustworthy as I might have thought. The ideal resolution would probably be to change the definition to something that is equivalent under AC, but still useful without it. Something to think about in the shower. Maybe by the time of Scott’s next post on set theory, I will have something more to say.

As to James Cook’s point, maybe it is better to say that if the truth of your favorite statement A depends on choice, then usually either it is uninteresting, or there is a closely related statement A’ that doesn’t depend on choice, and after you think about it, you’ll realize you like A’ more, usually because it’s a more precise statement. For simple statements, you can often find A’ by getting rid of the existential quantifiers.

For example, A = the product of non-empty sets S_i is non-empty. A’ = if for each i, s_i is an element of S_i, then (s_i) is an element of the product. Similarly, you fix the statement about a countable product of countable sets by talking about an accounted product of accounted sets, where accounted means you are actually given the bijection with N.

This certainly hasn’t prevented me from explicitly using choice in papers, but I view that as a compromise between wanting to think about mathematics more interesting than set theory and wanting to have the perfect paper.

I just think that a theory that relies on choice is probably not the best theory that does what you want. Similarly, a proof of a fact X in number theory that relies on the Riemann Hypothesis is less than ideal, even though the Riemann Hypothesis is certainly true. As with choice, I think the proper response is to say OK, X is true, but we still don’t understand it well. I would argue that it is understanding that we are after, not check marks next to theorem statements.

Comment #42 September 23rd, 2006 at 11:13 pm

“I would argue that it is understanding that we are after, not check marks next to theorem statements.”

I agree wholeheartedly!

“For example, A = the product of non-empty sets S_i is non-empty. A’ = if for each i, s_i is an element of S_i, then (s_i) is an element of the product.”

I don’t immediately see how this is any different. Without choice, how are we allowed to produce the function (s_i) in the first place?

In other words, what does the expression “(s_i)” mean, if not an element of the product?

Comment #43 September 23rd, 2006 at 11:25 pm

Klas M.,

I’m really surprised that countable choice is unable to get you unmeasurable sets. I guess I’m mainly surprised that no one has mentioned it before.

Why would you want DC rather than countable choice? (not that I see how it’s stronger at all, let alone in an interesting way).

James Cook,

Two ways I can interpret what you’re doing are transfinite induction and Zorn’s lemma. When you state them clearly like that, they really aren’t all that intuitive.

James,

Avoiding existential quantifiers has many benefits, seemingly unrelated. I don’t understand why.

Comment #44 September 24th, 2006 at 2:20 am

Douglas Knight,

I’m not quite sure what you mean. I find transfinite induction/Zorn’s Lemma very intuitive, for basically the reason I explained. The denial of Zorn’s Lemma, by contrast, seemingly amounts to nothing more than a refusal to discuss certain kinds of sets.

On one side, you have the people who accept Zorn’s Lemma. These people are able to take a certain uncountable subset of a Hilbert space and call it a basis. As far as I’m concerned, the fact that Zorn’s Lemma is consistent with ZF set theory is enough to show that this set “exists out there” in the Mathiverse (to borrow a term from Ian Stewart). In other words, because the ZL people have been able to create this set, it necessarily corresponds to some actual part of the kind of psychological reality we call “mathematical”.

On the other side, you have the people who refuse to accept Zorn’s Lemma. These people may think that the “basis” in question doesn’t exist, but if so, they’re deluding themselves. It does exist, as a mathematical object; the ZL people have already grasped a hold onto it. What’s really going on is that the ZL-deniers are refusing to discuss or refer to it, because they are not interested in mathematical objects of that type. This is perfectly fine, if such objects are never relevant for their investigations. But they should acknowledge that what they are doing is no different than the disallowing of numbers greater than 100 by someone who never has to deal with such numbers.

Comment #45 September 24th, 2006 at 4:26 am

Douglas Knight:

DC is sometimes preferable to countable choice since it is exactly what is needed to make some cases of transfinite induction work.

DC is also equivalent to the vailitidy of the Baire category theorem for several useful classes of metric and/or topological spaces.

James Cook:

Just a short comment. You need to be a bit careful about using the Baire category theorem here. The standard proofs of the Baire category theorem uses AC, and the theorem that every vector space has a basis is equivalent to AC.

Comment #46 September 24th, 2006 at 7:31 am

I’m delighted that much of this debate has gotten too technical for me to follow! But there’s one argument of James Cook that I understand and disagree with:

But they should acknowledge that what they are doing is no different than the disallowing of numbers greater than 100 by someone who never has to deal with such numbers.Despite my own strong pro-AC leanings (fueled by burning hunger for a total ordering on cardinals), I don’t think this is fair to the not(AC) camp. The existence of numbers greater than 100 follows by consistently applying the same rules used to manipulate the first 100 numbers. But to get unmeasurable sets and well-orderings of the reals, you need to introduce a new rule.

I suppose your position also forces you to accept not(CH) and as many large cardinal axioms as set theorists care to invent? (Not that there’s anything wrong with that!)

Comment #47 September 24th, 2006 at 1:05 pm

I suppose your position also forces you to accept not(CH)Mathematical platonism forces you to have an opinion on the continuum hypothesis, but which opinion? Maybe it’s just out of a desire to play the devil’s advocate, but I’d take the opposite interpretation. The sets in question are just subsets of the real line. We don’t need any new axioms for them to exist, so not(CH) isn’t building any more sets. But CH is building more bijections!

Of course, you can think of bijections as special subsets of the product, so both aximos become statements about the existence of special subsets.

Similarly, I could reverse James Cook’s argument, and insist that the consistency of the existence of a measure on all subsets of the real line really exists, “out there,” and it’s the AC people who refuse to acknowledge it.

But I think mathematical platonists tend to accept AC and higher cardinal axioms, but be undecided (at least collectively) on CH. On the other hand, if you want really big cardinals, you have to reject AC.

Comment #48 September 24th, 2006 at 1:49 pm

I find that in general people, at least those who are not set-theorists, tend to try to give AC and CH to priviliged a role. Both these axioms are best viewed in the same way as the parallel axiom is in classical geometry. None of them are true or false, they just give you a choice regarding which kind ot set theory you want to work with.

If you choose to use AC you find that non-measurable sets exists, however you instead choose e.g. the determiend games axiom you can prove that such sets do not exist.

This is not a matter of just saying that some thing are not sets, they really dont exist in the latter kind of set theory. This is again a bit like comparing axiomatic planar geometry with axiomatic spherical geometry. In the first geometry parallel lines do not intersect, in the latter they always have intersection points. However the intersection points of spherical geometry are not lurking around somewhere in the planar geometry, they do not exist at all.

Now I should probably not say to much more since axiomatic set theory is not really my area of research. I’m a graph theorist who have stumbled into set theory on occasion.

Comment #49 September 24th, 2006 at 3:57 pm

Scott:

Suppose I defined my mathematical universe by the following two rules:

(1)There are the following basic objects: 0,1,2,3,4,5,6,7,8,9

(2) any two basic objects may be juxtaposed to form a new object: 32, 08, 99, etc.

I then have a world of exactly 110 “numbers”. No rule of my system will allow me to go beyond that.

My analogy works better with a person who insists on sticking to a system like this, rather than one who stops applying the successor function at some point.

Klas M:

I must confess that I wasn’t aware that the Baire Category Theorem depended on AC. (Where exactly is it used in the proof?) But if it does, I think that’s a good reason for keeping the axiom around!

Scott, Douglas Knight, and Klas M., regarding CH:

I used “platonist” language because such language usually appeals to me, but it’s not really necessary. The point is that you have two systems, A and B, such that A is “strictly richer” than B in the sense that it allows the construction of all mathematical objects that B does, but not vice-versa. I deny that the “extra” objects of A are “suspect” merely because they are not part of the universe generated by B. If A is at least as consistent as B, then it is just as “valid” mathematically as B, and the “adherents” of B should acknowledge this. They should also acknowledge that the only reason for “rejecting” A is that one is not interested in the objects allowed by A but not by B.

Whether or not the analogy between AC or CH on the one hand, and the parallel postulate on the other, is a good one depends on the comparative “richness” of the various theories. The not-CH world, for example, is at least as rich as the CH-world, because (for example) you can get obtain the latter from the former simply by “removing” all the “weird” sets.

Euclidean geometry is at least as “rich” as spherical geometry, because spherical geometry can be “embedded” within Euclidean geometry (in fact that’s how they proved it was at least as consistent as Euclidean geometry). I admit that I don’t remember, off the top of my head, whether it also works in reverse. If it does, then the analogy fails, because then the two geometries are equally rich, whereas the two set theories are not.

Some axioms add objects, others remove them, so one has to be careful about this when comparing “richness”. (Of course, I realize that sorting out what a given axiom does can be tricky at times.)

Comment #50 September 24th, 2006 at 4:10 pm

Addendum:

The sets in question are just subsets of the real line. We don’t need any new axioms for them to exist, so not(CH) isn’t building any more sets. But CH is building more bijections!Similarly, I could reverse James Cook’s argument, and insist that the consistency of the existence of a measure on all subsets of the real line really exists, “out there,” and it’s the AC people who refuse to acknowledge it.These are examples of the sort of subtlety I was talking about. It seems to me that the symmetry is illusory: the existence of a measure on the real line is possible only if certain sets are absent from “the real line”. The AC people have to admit the non-AC real line into their theory, as a

subsetof their own “real line”.Similarly, CH doesn’t build more bijections, I don’t think. All the bijections in CH-land are still around in not-CH-land; they just don’t involve all the sets.

Comment #51 September 24th, 2006 at 4:34 pm

the existence of a measure on the real line is possible only if certain sets are absent from “the real line”.I meant, of course, “a measure defined on all subsets of the real line”.

Comment #52 September 24th, 2006 at 5:17 pm

James:

The Baire proof I remember uses transfinite induction, although some books are not very explicity about it. Here one can actually get a long way if you use DC instead of AC, i.e. you can prove the theorem for most sensible kinds of spaces. That actually seems to be the case for many of the analysis applications of AC.

I googled a bit and found this if you are interested

http://www.emis.de/journals/CMUC/pdf/

cmuc9904/herkerem.pdf

The paper discusses different versions of the Baire category theorem and their relation to various forms of choice.

Comment #53 September 24th, 2006 at 5:48 pm

I agree that we’re often forced, by theorems or experiments, to accept things that seem perverse. But in the case of AC and CH, is there really much more to do than work out the consequences of their truth and falsehood, and decide which seem less perverse to us?I would say, as some other commenters here have also suggested, that there is actually less to do than that. You should work out the consequences of their truth and their falsehood, but you shouldn’t bother to decide which is less perverse. That last part is ultimately a wild goose chase. It’s akin to “explaining” quantum probability instead of simply probing its consequences.

It could be fair to say that the axiom of choice

simplifiesmany questions in mathematics, without passing judgment on whether the simplifications are natural or perverse. All cardinalities are comparable, every vector space has a basis, the Hahn-Banach theorem is fully general, injective abelian groups exist, infinite products of compact spaces are compact, etc.But note that some of these simplifications only require countable choice in most cases of interest.

If you want to simplify your life without AC, then you can’t just remove the axiom, because then you will only be able to prove less. Instead, you would have to find some use in some competing axiom (or axioms) that contradicts AC. I think that logicians have some credible alternatives, but I don’t know much about it.

Comment #54 September 24th, 2006 at 5:49 pm

Klas M.,

Thanks! I’ll have a look.

Comment #55 September 24th, 2006 at 7:18 pm

James Cook:

The not-CH world, for example, is at least as rich as the CH-world, because (for example) you can get obtain the latter from the former simply by “removing” all the “weird” sets.I’m not sure what you mean by this, but one interpretation is Goedel’s proof of the consistency of AC and CH by, so to speak, removing the weird sets. But if you take this as an argument in favor of not(CH), you should also be in favor of not(AC).

Comment #56 September 24th, 2006 at 8:51 pm

Douglas Knight,

My meaning is simply this: not-CH is just like CH except that there are some extra objects (sets with intermediate cardinalities) thrown in.

On the other hand, not-AC is just like AC except that some objects (choice functions) have been taken away.

Comment #57 September 24th, 2006 at 9:55 pm

James Cook,

as far as I can make sense of what you’re saying, which is Goedel’s construction, you are wrong: the negated versions have more sets (functions are just special sets). But, I don’t think that what you’re saying is really meaningful.

Comment #58 September 25th, 2006 at 1:10 pm

How does the addition of AC to ZF result in fewer sets?

Comment #59 September 25th, 2006 at 11:29 pm

I don’t think it’s really meaningful to talk about the addition of an axiom creating or destroying sets. An addition of an axiom reduces the collection of models, but I don’t think models are directly comparable, so I don’t think it’s meaningful to say that the big models go away and the small models stay. In fact, models are sets, so you might be nervous talking about them without fixing set theory first, at least if your model is uncountable.

Goedel showed how, given a model of ZF, you could build a model for ZFC+GCH by taking some, but not all of the sets, keeping the given element relation. This construction keeps the given ordinals. So you can say that the new model is smaller than the old model. But I don’t think that entitles you to a general statement that not(AC) has more sets than AC. I imagine that are lots of models not obtainable this way, and this says nothing about their size.

The idea of an “inner model” sounds quite close to your statements: ‘The not-CH world, for example, is at least as rich as the CH-world, because (for example) you can get obtain the latter from the former simply by “removing” all the “weird” sets…spherical geometry can be “embedded” within Euclidean geometry.’

The geometry example is not so convincing to me. When you model spherical geometry in euclidean, the terms all change their meaning. Also, the dimension goes up. I think the provability of the undeciability of AC in ZF amounts to claim that you can build models for ZFC and ZF(notAC) inside ZF. Certainly that’s how Goedel and Cohen did it. But you can do it both ways. I suspect that either way can be done by throwing out sets, which makes Goedel’s construction more impressive than the geometry, more likely to impact my choice of axioms (thought it hasn’t yet). But things drastically change. It’s not obvious to me that cardinalities don’t change, that bijections cease to exist.

My understanding is that it is possible to build a model for set theory by taking countably many countable sets, and the usual element relation. Here cardinalities really will change–we have a countable set that satisfies the axioms for the power set of the integers, but in the model there is no bijection with the integers.

I am sympathetic to platonic language, but I have no idea what the countable model tells me about platonic set theory. I cannot deduce ought from is. Let me repeat: my understanding is that most platonists believe in AC and higher cardinals. At least collectively, they are undecided on CH.

Comment #60 September 26th, 2006 at 7:55 pm

Some day, perhaps, I’ll figure out a decent way to formalize what I am saying. For now I’ll just note that I don’t think my ideas are contradicted by anything you mentioned.

Philosophically speaking, my thesis is that there are no “epistemological” grounds for rejecting the Axiom of Choice. Some people seem to think that using AC is a form of cheating, and that results that depend on it should always be listed with an asterisk next to them, as if they weren’t quite genuine mathematical theorems. I think this point of view is wrong.

This is not the same thing as saying that AC (or CH or its negation) is somehow “true” independently of the formal system one is working in. (In fact, my view is entirely compatible with the view that “truth” is a meaningless notion outside the context of a formal system!) It is more like saying that

we are entitled to consider it true if we wish, where the sense of truth here is as strong as it would be for anything else. I should mention, for the record (and I think this comment makes this clearer) that I’m not a “platonist”, except perhaps in my way of speaking on certain occasions. I let my actual philosophical view slip out when I wrote:the kind of psychological reality we call “mathematical”.Comment #61 September 27th, 2006 at 7:55 pm

James Cook,

Before formalizing what you mean, it might be easier to say why Goedel’s constructive universe isn’t relevant to your point of view.

I have some sympathy with the point of view that nonconstructive results are cheating. But AC is just part of the game.

Comment #62 September 28th, 2006 at 6:28 pm

Before formalizing what you mean, it might be easier to say why Goedel’s constructive universe isn’t relevant to your point of view.I never said it wasn’t relevant. It may be. But determining exactly how my point of view relates to Goedel’s results, if it does, would require a more precise statement of some of my claims than I am currently able to give.

I have some sympathy with the point of view that nonconstructive results are cheating. But AC is just part of the game.I actually believe (or at least strongly suspect) that the traditional distinction between “constructive” and “nonconstructive” is misguided, and rather similar in nature to the distinction between “elementary” and “nonelementary” functions. It stems, in my opinion, from a failure to appreciate just how abstract certain kinds of mathematical objects (like integers) really are. (People have an erroneous feeling that a number like 2 is somehow “more real” than a choice function.)

Comment #63 September 29th, 2006 at 6:20 pm

Constructive results give algorithms. Arguments which use the axiom of exluded middle don’t.

I’m not sure I’ve seen an example where it really bothered me, but Hilbert’s Basissatz might be a serious example of an algorithm postdating a theorem by decades.

Comment #64 September 30th, 2006 at 11:31 am

Constructive results give algorithms. Arguments which use the axiom of exluded middle don’t.In order to work, an algorithm surely must use the Law of the Excluded Middle, in some form:

“If A satisfies property P, then do X. If A does not satisfy property P, then do Y.”

I’m not sure I’ve seen an example where it really bothered me, but Hilbert’s Basissatz might be a serious example of an algorithm postdating a theorem by decades.The way I would interpret this is as follows: an algorithm is just an existence proof that gives more information about the object. So it occasionally happens that, decades after an object is proven to exist, it is shown to satisfy other properties besides the one that defined it in the first place.

Comment #65 September 30th, 2006 at 6:47 pm

If that wasn’t clear, I was making a precise claim: from an existence proof that doesn’t use the axiom of the excluded middle, one can extract an algorithm. Some computer proof-checkers do this.

Comment #66 September 30th, 2006 at 11:52 pm

from an existence proof that doesn’t use the axiom of the excluded middle,But I don’t think there’s any such thing; that was my point! I am

challengingthe standard distinction between proofs that provide algorithms and proofs that do not! On my view, the difference is not fundamental or qualitative; it’s simply a question of how many additional properties are shown to be entailed by a given property.Let me try to explain further; this may help clear up any misunderstanding. When people say that an existence proof is “constructive”, what they mean is that it provides a provides a procedure for “constructing” the object that is being alleged to exist. Now what does it mean to “construct” an object? Well, I suppose that what it really means is that the object can be

specified. However, the only way to specify a mathematical object is to state properties that it satisfies. This is because mathematical objects are abstract in nature–they’re defined only as things that satisfy properties! (So actually, it’s the properties themselves that are of interest, with the idea of actual “objects” satisfying them being really only a mental crutch.) Even something apparently “concrete”, like the number 2, is defined as “the set of all x such that…”This has long been recognized, but what doesn’t seem to be widely recognized is the following implication: since we can never hope to give an

exhaustivelist of an object’s properties (after all, every object satisfies an infinite number of properties), the very notion of “specificity” of mathematical objects is entirely relative! A statement to the effect that an argument is “nonconstructive” amounts to a complaint thatnot enough informationis being given about the object(s) in question. For example, perhaps all we are able to say about a choice function used in some proof is the fact that it’s a choice function. We might not know anything about the image of a particular element. But who is to decide how much information is “enough”? If a single property is not enough, what about two? Three?In effect, those who insist upon “constructive” arguments are insisting that any argument purporting to answer a mathematical question must also answer other questions as well. For example, if I want to claim that a fixed point of some self-map of the unit disc in R^2 exists, I had better be able to say also under what circumstances its first coordinate is greater than 0.256.

Such a demand strikes me as arbitrary and ill-justified.

Comment #67 October 1st, 2006 at 3:17 am

Me:

from an existence proof that doesn’t use the axiom of the excluded middle,James Cook:

But I don’t think there’s any such thingThe axiom of the excluded middle is part of propositional logic. It is uncontestable whether a particular

formalproof uses it. You may not care about algorithms, but you can’t deny that some systems have more axioms than others.Comment #68 October 1st, 2006 at 2:35 pm

Please tell me exactly where I err, keeping in mind that even if I am somehow wrong about Point 1, I could still be right about Point 2 (which is the more important point):

Me (Point 1):

In order to work, an algorithm must use the Law of the Excluded Middle:“If A satisfies property P, then do X. If A does not satisfy property P, then do Y.”-Corollary: NO formal proof, even (or especially!) those with “algorithms”, fails to use the Law of the Excluded Middle.

Me (Point 2):

an algorithm is just an existence proof that gives more information about the object.-Corollary 1: “Nonconstructive” existence proofs yield “algorithms” as well–it’s just that their algorithms don’t provide enough information to satisfy some people.

-Corollary 2: Quite apart from whether a proof uses the Law of the Excluded Middle or not, the fact that it gives an “algorithm” can not be used to distinguish it qualitatively from other proofs.

Comment #69 October 2nd, 2006 at 2:30 am

I imagine the issue is that in describing the algorithm, a constructivist would call it a theorem that (P or not P) for a particular proposition. In constructive logic, the axiom of the excluded middle isn’t false, it’s just sometimes undecidable. But sometimes it is, and then a constructivist would allow an algorithm to branch on it.

But I don’t want to talk about constructivists talking about algorithms. I want to talk about constructive proofs and nonconstructive proofs. From a constructive proof it is possible to extract something that everyone will agree is an algorithm. From a nonconstructive proof it is not possible to extract an algorithm at all, not even an algorithm that constructivists don’t think can be proven to terminate.

There is a formal procedure to turn a proof that doesn’t use the axiom of the excluded middle into an algorithm. If you’re really skeptical, that’s the claim you should doubt. If you like, you can, as you have done, also doubt my claim that there exist such proofs. But I can imagine no way to justify your claim that all proofs give rise to “algorithms”–except the scare quotes. By algorithm, I mean Turing machine. OK?

Comment #70 October 2nd, 2006 at 5:22 pm

But I can imagine no way to justify your claim that all proofs give rise to “algorithms”–except the scare quotes. By algorithm, I mean Turing machine. OK?Perfect. Here’s how you justify it. Program your computer (which I am assuming is equivalent to a Turing machine) to perform the following task. When an input like “SET FAMILY = {X_i, i in R} CHOICE FUNCTION=?” is typed in, the computer will produce the following output:

“f: i -> Union {X_i, i in R}, f(i) in X_i for each i”. Then you can also program the computer to respond to queries like “f(3.5)=?” with answers like “x, where x in X_3.5”. Then you’ve programmed your computer to construct choice functions. And since you were able to do this, there is an algorithm for constructing choice functions!

Not satisfied? Of course not! That’s because, as I have been trying to point out, algorithms are a red herring. Obviously there exists an algorithm for writing down any mathematical object we care to dream up (including some that don’t exist, like 6/0). That’s what I meant when I said that every proof yields an algorithm–if we know there’s a choice function, well, then we can program a computer to produce a choice function!

Algorithms would only be relevant if the discussion were about how many symbols could be written down. But it’s not, as I hope the above example shows. What it’s about is the mathematical constructs

referred toby those symbols. Specifically, the issue on the table iswhether or not there is an ontological hierarchy of mathematical objects based on “specificity”. In other words, whether the mathematical object denoted by “2” should or should not be regarded as “more real” than the mathematical object denoted by the sequence of symbols “f, where f(i) is an element of X_i”. The constructivists say yes. I say no. In my comment of Saturday, September 30, 2006 11:52:47 PM, I gave an argument for why the constructivist position is untenable. If you agree with the constructivists and disagree with me, please address that argument.Comment #71 October 2nd, 2006 at 6:40 pm

Your example of 6/0 suggests that your definition of algorithm is pretty worthless.

It’s not just constructivist vs your position. If you’re incapable of recognizing that the mainstream, nonconstructive community acknowleges a concept of algorithm, then I don’t think I can communicate with you.

Comment #72 October 2nd, 2006 at 9:36 pm

It’s not just constructivist vs your position. If you’re incapable of recognizing that the mainstream, nonconstructive community acknowleges a concept of algorithmWho said I was incapable of recognizing that? I recognize full well that they acknowledge such a concept. That doesn’t mean that

Ihave to acknowledge the concept! And it certainly doesn’t mean that the concept is relevant here. Indeed, I have repeatedly given arguments for why itisn’trelevant here. I don’t understand why you insist on simply restating the mainstream view over and over again without addressing my arguments. Just in case it wasn’t clear: yes, I’m aware of the mainstream view. I don’t necessarily agree with it!then I don’t think I can communicate with you.Well, maybe there is an insurmountable communication problem. But I will try one more time to state my argument, as clearly as I can manage. I invite you to pinpoint the claims with which you do no agree, and explain why you do not agree with them. Please, however, try to stick as closely as possible to the terms and concepts that I explicitly invoke (in order to facilitate communication).

Consider an existence theorem, i.e. a theorem of the form:

(T) X is a nonempty set.

Principal Claim: The distinction between a “constructive” proof and a “nonconstructive” proof of (T) is arbitrary.

Here is my argument:

1. Every “constructive” proof of (T) takes the following form:

(1a) Y is a subset of X

(1b) Y is a nonempty set

(1c) Therefore, X is a nonempty set.

(Example: X might be the set of all positive integers satisfying some property. Y might be the set of all positive integers greater than 10 and less than 12. Thus X is shown to be nonempty by showing that 11 satisfies the defining property of X.)

2. In order for a proof to be considered “constructive”, it suffices that it take the form described above, for some “preferred” choice of Y.

(A proof of (T) would be called “constructive” if we could “specify” an element x of X. But “specify x” just means “show that x is an element of Y” where Y is a set whose elements we “already know” or “can construct”.)

3. There is no nonarbitrary reason for “preferring” any particular choice of Y.

(If our set theory proves that a subset S of X is nonempty, then we should be able to let Y=S. If we don’t like this, we are free to choose another set theory. However, unless the alternative set theory is more likely to be consistent than the original, we have no business criticizing the original set theory on epistemological grounds, in which case the choice of set theory will itself be basically arbitrary.)

4. Therefore, a preference for a “constructive” proof of (T) is an arbitrary preference.

Comment #73 October 2nd, 2006 at 11:07 pm

James Cook,

The constructivists say yes. I say no.That sure makes it sound like you think you’re arguing with the constructivists, not with the mainstream.

The difference between constructivists and the mainstream is that mainstream believe its possible to know that a number exists without being able to answer the question “Is it even or odd?” Constructivists believe that you don’t know the number exists unless you are capable of answering that question. You seem to believe that “it is what it is” is a legitimate answer to that question.

Comment #74 October 2nd, 2006 at 11:09 pm

Also, this is a strange blog on which to not acknowlege the concept of algorithm. As far as I can see, from your definition, all languages have constant complexity.

Comment #75 October 3rd, 2006 at 1:55 am

That sure makes it sound like you think you’re arguing with the constructivists, not with the mainstream.I am arguing with anyone who thinks the difference between a “constructive” argument and a “nonconstructive” argument is important. Why is that so hard to understand?

The difference between constructivists and the mainstream is that mainstream believe its possible to know that a number exists without being able to answer the question “Is it even or odd?” Constructivists believe that you don’t know the number exists unless you are capable of answering that question. You seem to believe that “it is what it is” is a legitimate answer to that question.In case you missed it, I wrote:

those who insist upon “constructive” arguments are insisting that any argument purporting to answer a mathematical question[e.g. whether a number exists]must also answer other questions as well[e.g. whether it is even or odd]…Such a demand strikes me as arbitrary and ill-justified.So, on this point, I agree with the mainstream.

Also, this is a strange blog on which to not acknowlege the concept of algorithm. As far as I can see, from your definition, all languages have constant complexity.Nonsense. What I do not acknowledge is the concept of “algorithm”

as a distinct class of mathematical proof,not the computability-theoretic concept of algorithm. The latter, as I have repeatedly emphasized, is of no relevance to this discussion. In other words,contrary to what some people believe, the distinction between constructive and nonconstructive proofs has nothing to do with algorithms or Turing machines. Frankly, I don’t know why you keep bringing the subject up, when (1) your only answer to my claim of irrelevance is “well, the mainstream view is that it is relevant”, and (2) I gave a detailed argument for my position–an argument you have yet to address–in which I formulated the distinction in a way that did not use these concepts at all.Also please note that I never gave, nor intended to give, any definition of “algorithm”. This is understandable, given that I don’t believe the notion belongs in this discussion.

Perhaps in response to your statement that “constructive arguments give algorithms”, I should simply have asked “algorithms for what?” That way, maybe, the discussion would have gotten a lot more quickly to where it needs to be.

Comment #76 October 3rd, 2006 at 1:32 pm

I am arguing with anyone who thinks the difference between a “constructive” argument and a “nonconstructive” argument is important. Why is that so hard to understand?I originally brought up algorithms to say that the inclusion of some axioms has more impact than others. I don’t know how to express the importance of the axiom of choice, except in terms of the theorems proved by the formal system, but I do not an external way of expressing the importance of the axiom of the excluded middle.

At that point, you could have said that you don’t care about algorithms, and the conversation would have been over, but instead you seemed to deny my claim, eventually redefining algorithm. I think the problem is that we think we’re part of different conversations. I don’t want to discuss whether algorithms are “more real” than other descriptions, because I don’t think that can go anywhere. So I didn’t respond to that. I pursued my claim about algorithms because you seemed to respond to it. But I wasn’t pursuing it to convince you of its importance, only to convince you that it was precise, since you seemed to deny that.

Perhaps in response to your statement that “constructive arguments give algorithms”, I should simply have asked “algorithms for what?”Yes, that’s a good question, and perhaps your answer would be: algorithms for whether an integer purported to exist is even or odd. I think that constructivists today, despite the name, do not stress algorithms, but stress the status of the provability of being even or odd. In fact, it seems to me, although I can’t make it precise, that there’s a particular practice of the mainstream that you agree with the constructivists in rejecting.

Comment #77 October 3rd, 2006 at 5:10 pm

I don’t want to discuss whether algorithms are “more real” than other descriptions, because I don’t think that can go anywhere.But the problem, as I see it, is that I don’t understand the difference between an “algorithmic” description and any other type of description. As far as I can tell, an algorithmic description is just a description with more information–information of the same type used in every description. Yet everyone (constructivists and mainstream) speaks and acts as if an algorithmic descriptions provided information of a qualitatively different type. (Otherwise, what would be the foundation of a claim to the effect that only objects with an algorithmic description should be permitted to exist?)

The difference between what everyone refers to as an algorithmic description and other descriptions can’t simply be that the former can be written down by a Turing machine. After all, any description provided by any formal mathematical proof can be written down by a Turing machine. Right? Isn’t that at least part of what it means to be “formal”? Thus, I concluded, algorithms in this sense are not what we are talking about. Rather, it seems to me, we are really talking about something like the

information contentof the description–specifically how much information a description has to provide before it can be considered “constructive” in nature. My central claim was that any such numerical boundary we draw will be arbitrary, and therefore there’s really no good reason for drawing that kind of boundary at all. So the question of whether “constructive” is a useful category of mathematical descriptions, as I saw it, was an instance of the general question of whether it’s a good idea to draw arbitrary numerical boundaries. It wasn’t a question about what an algorithm is.In fact, it seems to me, although I can’t make it precise, that there’s a particular practice of the mainstream that you agree with the constructivists in rejecting.This surprises me; I’m not sure what you mean here. My own interpretation of my position is that the mainstream is willing to concede too much to the constructivists. (Perhaps that’s not inconsistent with what you say.)

Comment #78 October 3rd, 2006 at 5:14 pm

This post has been removed by the author.

Comment #79 October 3rd, 2006 at 9:57 pm

What you have in common with the constructivists is that you don’t like the idea of two kinds of description.

One thing about algorithms is that the numbers they produce are part of the standard model of the natural numbers.