This Week's Finds in Mathematical Physics (Week 40)
Matthew P Wiener
>(I could be wrong about this, so if there are any linear logicians
>out there, they should correct me if I've got it wrong.)
The only thing I know of called linear logic is a system in between
classical and intuitionistic. Not all excluded middles are allowed
in, but I think "p=>q v q=>p" is, and that this characterizes linear
logic.
When Cohen invented forcing, he gave the most obvious treatment of
negation, and the forcing logic came out intuitionistic. Dana Scott
realized this was backwards, and the complications should be in the
way forcing handles negations, so that the logic comes out classical.
But Kripke exploited this initial clumsiness brilliantly, and showed
that the original Cohen forcing can be recast as a naturally intuitive
model theory ("Kripke semantics") for intuitionistic logic.
The point of this digression is that forcing involves partial orders.
If one restricts Kripke semantics to linear orders, one gets linear
logic. (Classical logic corresponds to the trivial order.)
--
-Matthew P Wiener (wee...@sagi.wistar.upenn.edu)
Mike Oliver
>In article <37vi3l$r...@galaxy.ucr.edu>, baez@guitar (john baez) writes:
>>(I could be wrong about this, so if there are any linear logicians
>>out there, they should correct me if I've got it wrong.)
>The only thing I know of called linear logic is a system in between
>classical and intuitionistic. Not all excluded middles are allowed
>in, but I think "p=>q v q=>p" is, and that this characterizes linear
>logic.
While it's conceivable that there's something that I'm missing, my belief
is that you're both wrong. Linear logic is *more* restrictive than
intuitionistic logic. In a Gentzen-style system you get intuitionistic
logic from classical by dropping the rule
(not A),Gamma |- False
-------------------------
Gamma |- A
(or something equivalent; it's been a while since I've done this). To get
linear logic you further drop the rules weakening and contraction;
i.e. you no longer have
A,Gamma |- B A,A,Gamma |- B
-------------- --------------
A,Gamma |- B,C A,Gamma |- B
Then you add rules for these other weird connectives like tensor, but
they don't allow you to prove all the things you could prove in intuitionistic
logic.
--
"Oh, sorry, Maggie. I'm sure you'd like to be alone with your manifestation."
John Baez
John Baez
When I was an undergraduate I was quite interested in logic and the
foundations of mathematics --- I was always looking for the most
mind-blowing concepts I could get ahold of, and Goedel's theorem, the
Loewenheim-Skolem theorem, and so on were right up there with quantum
mechanics and general relativity as far as I was concerned. I did my
undergrad thesis on computability and quantum mechanics, but then I sort
of lost interest in logic and started thinking more and more about
quantum gravity. The real reason was probably that my thesis didn't
turn out as interesting as I'd hoped, but I remember feeling at the time
that logic had become less revolutionary than in it was in the early
part of the century. It seemed to me that logic had become a branch of
mathematics like any other, studying obscure properties of models of the
Zermelo-Fraenkel axioms, rather than questioning the basic presumptions
implicit in those axioms and daring to pursue new, different approaches.
I couldn't really get excited about the properties of super-huge
cardinals. Of course, I knew a bit about intuitionistic logic and
various forms of finitism, but these seemed to be the opposite of
daring; instead, they seemed to appeal mainly to grumpy people who
didn't trust abstractions and wanted to do everything as conservatively
as possible. I was pretty interested in quantum logic, too, but I
tended to think of this more as a branch of physics than "logic" proper.
Anyway, it's now quite clear to me that I just hadn't been reading the
right stuff. I think Rota has said that the really interesting work in
logic now goes under the name of "computer science', but for whatever
reason, I didn't dig into the Journal of Philosophical Logic, other
logic journals, or proceedings of conferences on category theory,
computer science and the like and find the stuff that would have excited
me. It goes to show that one really needs to keep digging! Anyway, I
just went to a conference called the Lambda Calculus Jumelage up in
Ottawa, thanks to a kind invitation by Prakash Panangaden and Phil
Scott, who thought my ideas on category theory and physics might
interest (or at least amuse) the folks who attend this annual bash. It
became clear to me while up there that logic is alive and well!
Of course, I don't actually understand most of what these people are up
to, so take what I say with a large grain of salt. My goal here is more
to draw attention to some interesting-sounding ideas than to explain
them.
One interesting subject, which I think I'm finally beginning to get an
inkling of, is "linear logic". This was introduced in the following
paper (which I haven't gotten around to looking at):
1) Linear Logic, by Jean-Yves Girard, Theoretical Computer Science 50
(1987) pp. 1-102.
When I first heard about linear logic, it made utterly no sense. It
seemed to be a logic suitable for use in some completely different
universe than the one I inhabited! For example, there were the familiar
logical connectives "and" and "or", but they had weird alternate
versions called "tensor" and "par", the latter written with an
upside-down ampersand. There was also an alternate version of
the material implication "->", and a strange operation called "!"
(pronounced "bang") that somehow mediated between the logical
connectives I knew and loved and their eerie alter egos.
I understand a wee bit about these things now; one can get a certain
ways just by getting used to "tensor", since the rest of the weird
connectives are defined in terms of this one and the familiar ones.
(I won't worry about the "!" here.) One key idea, which finally
penetrated my thick skull, is that there is a good reason why "tensor"
does not satisfy the following deduction rule so characteristic of "and":
S |- p S |- q
-------------------
S |- p & q
meaning: if from the set of premisses S we can deduce p, and from S we
can also deduce q, then from S we can deduce p&q. The point is that in
linear logic one should not think of S as a *set* of premisses, but
rather as a *multiset*, meaning that the same premiss can appear twice.
The idea is that if we use one premiss in S to deduce something, we *use
it up*, and we can only use it again if S has several copies of that
premiss in it. As they say, linear logic is "resource-sensitive" (which
is apparently why computer scientists like it). So the idea is that in
linear logic,
S |- p&q
means something like "from the premisses S one can deduce p if one feels
like it, or alternatively one can deduce q if one feels like it, but not
necessarily both "at once", since there may not be enough copies of the
premisses to do that." On the other hand,
S |- p tensor q
is stronger, since it means something like "from the premisses S one can
deduce both p and q at once, since there are enough copies of all the
premisses in S to do it." Thus "&" satisfies the above deduction rule
in linear logic just as in classical logic, but "tensor" does not;
instead, it satisfies
S |- p T |- q
-------------------
S U T |- p tensor q
where S U T denotes the union of the multisets S and T (so that if both
S and T have one copy of a premiss, S U T has two copies of it).
Well, let me leave it at that. I should add that there is a paper
available online,
2) Linear logic for generalized quantum mechanics, by Vaughan Pratt,
available in LaTeX format (compressed) by anonymous ftp from
boole.stanford.edu, as the file pub/ql.dvi.Z,
which relates linear logic and quantum logic, and which is part of a body
of work relating linear logic and category theory, with the key idea
being that "linear logic is a logic of monoidal closed categories in
much the same way that intuitionistic logic is a logic of Cartesian
closed categories" --- here I quote
3) Hopf algebras and linear logic, by Richard Blute, to appear in
Mathematical Structures in Computer Science.
I suppose to most people, explaining linear logic in terms of monoidal
closed categories may seem like using mud to wipe ones windshield.
However, to some of us monoidal closed categories are rather familiar
things, and in fact anyone who knows about vector spaces, linear maps,
and the vector spaces Hom(V,W) and V tensor W knows a really good
example of a monoidal closed category. Thus monoidal closed categories
can be viewed as an abstraction of linear algebra, and indeed this is
how "linear logic" got its name.
It seems that I should read the following papers, too, before I really
understand the connection between linear logic and category theory:
4) Linear logic, *-autonomous categories and cofree coalgebras, by R. A. G.
Seely, in Categories in Computer Science and Logic, Contemp. Math.
92 (1989).
5) Quantales and (noncommutative) linear logic, by D. Yetter, Journal of
Symbolic Logic 55 (1990), 41-64.
A terse summary of linear logic in terms a categorist might like can be
found in Section 3.5 of Pratt's paper cited above. I should add that
Pratt has lots of other interesting papers available online (try the
file pub/README).
--------------------------------------------------------------------------
Previous issues of "This Week's Finds" and other expository articles on
mathematics and physics (as well as some of my research papers) can be
obtained by anonymous ftp from math.ucr.edu; they are in the
directory "baez." The README file lists the contents of all the papers.
On the World-Wide Web, you can attach to the address
http://info.desy.de/user/projects/Physics.html to access these files and
more on physics. Please do not ask me how to use hep-th or gr-qc;
instead, read the file preprint.info.
john baez
>However, one thing puzzles me. The linear logic you describe sounds like fun
>stuff. But whether you regard it as multi-set premised logic, or as computer
>science with non-reusable inputs for sentence derivation, or whatever, it still
>seems to me to be "a branch of mathematics like any other", and hardly the
>"mind-blowing concept" or "revolutionary" approach to foundations that we all
>yearned for as undergrads (and perhaps still do).
>This is in no way meant to be a put-down, (and indeed I'm grateful for the tip
>to read up on linear logic); but it seems there's no real connection between
>your initial plaint and your later (clearly justified) enthusiasm.
>Am I missing something here?
Hmm. Clearly (as various followup posts indicate) I don't understand
linear logic very well. But I think it's more than just classical logic
repackaged in a new way, as your two descriptions of it would make it
sound. I guess my description emphasized how I was trying to get a
handle on linear logic by relating it to classical logic. But there are
models of linear logic that are really different from any of the models
for classical or intuitionistic logic. (The paper by Blute I listed
starts going into this.) The main way I have of understanding this, to
the measly extent I do, is the slogan I quoted: intuitionistic logic is
to Cartesian closed categories as linear logic is to more general
monoidal categories. I sort of know how much, and in what ways,
monoidal categories are more general than Cartesian closed ones, so if
this slogan has any validity to it, linear logic should be quite a bit
different in flavor than intuitionistic (or classical) logic. This
sounds more revolutionary to me than worrying about the fine structure of
the recursive hierarchy, ineffable cardinals, and the like. Maybe my
enthusiasm is due to ignorance; maybe someone who really understands
linear logic well should post!!!
Bill Taylor
|> When I was an undergraduate I was quite interested in logic and the
|> foundations of mathematics --- I was always looking for the most
|> mind-blowing concepts I could get ahold of,
... ...
|> I remember feeling at the time
|> that logic had become less revolutionary than in it was in the early
|> part of the century. It seemed to me that logic had become a branch of
|> mathematics like any other,
Very well put! I remember feeling much the same; like a lot of folk, I expect.
|> I think Rota has said that the really interesting work in
|> logic now goes under the name of "computer science',
This sounds like a sensible view.
However, one thing puzzles me. The linear logic you describe sounds like fun
stuff. But whether you regard it as multi-set premised logic, or as computer
science with non-reusable inputs for sentence derivation, or whatever, it still
seems to me to be "a branch of mathematics like any other", and hardly the
"mind-blowing concept" or "revolutionary" approach to foundations that we all
yearned for as undergrads (and perhaps still do).
This is in no way meant to be a put-down, (and indeed I'm grateful for the tip
to read up on linear logic); but it seems there's no real connection between
your initial plaint and your later (clearly justified) enthusiasm.
Am I missing something here?
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
Watch out for my definitive series of books on Prime Numbers.
Just coming into print now... volume I: "The Even Primes"
-------------------------------------------------------------------------------
Paul Budnik
: This Week's Finds in Mathematical Physics (Week 40)
: John Baez
[...]
: It seemed to me that logic had become a branch of
: mathematics like any other, studying obscure properties of models of the
: Zermelo-Fraenkel axioms, rather than questioning the basic presumptions
: implicit in those axioms and daring to pursue new, different approaches.
: I couldn't really get excited about the properties of super-huge
: cardinals. [...]
In discussing such issues it is important to distinguish between different
ways of extending logic. One is to extend the framework of logic with
large cardinal axioms or other attempts to make it more powerful. It
is clear from Godel's theorem that this will always be possible.
Another way is to modify the rules of the propositional
calculus. When people talk about contraractual definiteness they are
talking about logic at the level of the propositional calculus. It is
a kind of physicists version of intuitionism where the excluded middle
is denied for possible experiments that were never performed. There is
little reason to change logic in this way. The only motivation for
doing this is to avoid some of the implications of QM about locality
that trouble some physicists.
[...]
From your discussion I take it that linear logic as something embedded
in classical logic and not an intended as a replacement for it.
: 2) Linear logic for generalized quantum mechanics, by Vaughan Pratt,
: available in LaTeX format (compressed) by anonymous ftp from
: boole.stanford.edu, as the file pub/ql.dvi.Z,
: which relates linear logic and quantum logic, and which is part of a body
: of work relating linear logic and category theory, with the key idea
: being that "linear logic is a logic of monoidal closed categories in
: much the same way that intuitionistic logic is a logic of Cartesian
: closed categories" --- here I quote
Is any of what you are talking about an attempt at replacing the basic
laws of logic at the level of the propositional calculus with something
different?
Paul Budnik
Matthew P Wiener
>In article <380oa0$9...@netnews.upenn.edu> wee...@sagi.wistar.upenn.edu (Matthew P Wiener) writes:
>>In article <37vi3l$r...@galaxy.ucr.edu>, baez@guitar (john baez) writes:
>>The only thing I know of called linear logic is a system in between
>>classical and intuitionistic. Not all excluded middles are allowed
>>in, but I think "p=>q v q=>p" is, and that this characterizes linear
>>logic.
>While it's conceivable that there's something that I'm missing, my belief
>is that you're both wrong.
I'm perhaps totally wrong.
I'm thinking of a system of Dummett's from 30 some years ago. I have
heard *that* one called linear logic, but I don't think that was its
official name, but it is obviously not the stuff in the Girard book.
Jamie Andrews
In article <380oa0$9...@netnews.upenn.edu>,
Matthew P Wiener <wee...@sagi.wistar.upenn.edu> wrote:
>The only thing I know of called linear logic is a system in between
>classical and intuitionistic. Not all excluded middles are allowed
>in, but I think "p=>q v q=>p" is, and that this characterizes linear
>logic.
The linear logic I know of is a sequent calculus-based
logic which removes most of the classical connectives and
replaces them with much weaker versions and some new
connectives. We can show that there is a translation of
intuitionistic logic into linear logic in the same sense that
there is a translation (e.g. Goedel's) of classical logic into
intuitionistic logic.
Linear logic is basically a relevance logic devised by
Jean-Yves Girard. (_Theoretical Computer Science_ v.50 1987
pp.1-102) It weakens traditional relevance logic in ways that
relevance logicians hadn't explored much.
A more sociological description might be that linear logic
is to 1990s computer science what category theory is to 1990s
mathematics... make of that what you will. :-)
--Jamie.
ja...@cs.sfu.ca
"Make sure Reality is not twisted after insertion"
james dolan
>From your discussion I take it that linear logic as something embedded
>in classical logic and not an intended as a replacement for it.
...
>Is any of what you are talking about an attempt at replacing the basic
>laws of logic at the level of the propositional calculus with something
>different?
you can study many sorts of "alternative logic" quite deeply without
making any ultimate commitment as to whether the "alternative logic"
is supposed to be more or less (or equally or "non-comparably")
fundamental than the "standard logic", reserving for yourself the
flexibility to adopt different attitudes whenever they seem
convenient, and to perhaps eventually make some ultimate commitment if
the things you discover move you to.
Timothy Y. Chow
Bill Taylor <w...@math.canterbury.ac.nz> wrote:
>ba...@ucrmath.ucr.edu (John Baez) writes:
>|> I remember feeling at the time
>|> that logic had become less revolutionary than in it was in the early
>|> part of the century. It seemed to me that logic had become a branch of
>|> mathematics like any other,
>
>Very well put! I remember feeling much the same; like a lot of folk, I expect.
Actually, I have a slightly different view of this. IMO, making logic a
branch of mathematics *was* the revolutionary idea. That's perhaps stating
it too strongly, but the key behind the revolutionary ideas was making the
methods of mathematical investigation (i.e., proofs) themselves the objects
of mathematical investigation. (This gives more credit to Hilbert than to
Goedel than is usual, I realize.)
Perhaps logic is less revolutionary now than before, but I don't think
this has anything to do with its "becoming a branch of mathematics like
any other."
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
john baez
>paul budnik writes:
>>From your discussion I take it that linear logic as something embedded
>>in classical logic and not an intended as a replacement for it.
It's not "embedded in it", in the sense that it's a "from scratch"
axiomatic system just like classical logic. I don't think anyone
expects it to "replace" classical logic, especially because - if I
understand it correctly - it's a conservative extension of classical
logic, meaning that any reasoning valid in classical logic is valid in
linear logic, and anything that's provable in linear logic which only
uses the connectives of classical logic is in fact provable in classical
logic. (I could be wrong about this, so if there are any linear
logicians out there, they should correct me if I've got it wrong.) So
the proper thing to say is that linear logic "subsumes" classical logic.
>>Is any of what you are talking about an attempt at replacing the basic
>>laws of logic at the level of the propositional calculus with something
>>different?
>you can study many sorts of "alternative logic" quite deeply without
>making any ultimate commitment as to whether the "alternative logic"
>is supposed to be more or less (or equally or "non-comparably")
>fundamental than the "standard logic", reserving for yourself the
>flexibility to adopt different attitudes whenever they seem
>convenient, and to perhaps eventually make some ultimate commitment if
>the things you discover move you to.
I think most of the people I was talking to take an attitude like that
which James describes here. I don't think these folks are moralizing
firebrands trying to convert the world to linear logic. That sort of
evangelical impulse seems to be confined to puritanical movements like
finitism and intuitionism, which would *restrict* our forms of
reasoning. I think people interested in linear logic are interested in
exploring various systems of logic and not too interested in picking one
system and decreeing it to be "fundamental".
Lee Rudolph
>The point is that in
>linear logic one should not think of S as a *set* of premisses, but
>rather as a *multiset*, meaning that the same premiss can appear twice.
>The idea is that if we use one premiss in S to deduce something, we *use
>it up*, and we can only use it again if S has several copies of that
>premiss in it. As they say, linear logic is "resource-sensitive" (which
>is apparently why computer scientists like it).
This sounds like what Yesenin-Volpin was talking about, 20 years ago
and more. Is it? (I plead ignorance.)
Lee Rudolph
Paul Budnik
: In article <37vecn$9...@ucrmath.ucr.edu> jdo...@ucrmath.ucr.edu (james dolan) writes:
[...]
: >>Is any of what you are talking about an attempt at replacing the basic
: >>laws of logic at the level of the propositional calculus with something
: >>different?
: >you can study many sorts of "alternative logic" quite deeply without
: >making any ultimate commitment as to whether the "alternative logic"
: >is supposed to be more or less (or equally or "non-comparably")
: >fundamental than the "standard logic", reserving for yourself the
: >flexibility to adopt different attitudes whenever they seem
: >convenient, and to perhaps eventually make some ultimate commitment if
: >the things you discover move you to.
: I think most of the people I was talking to take an attitude like that
: which James describes here. I don't think these folks are moralizing
: firebrands trying to convert the world to linear logic. That sort of
: evangelical impulse seems to be confined to puritanical movements like
: finitism and intuitionism, which would *restrict* our forms of
: reasoning. I think people interested in linear logic are interested in
: exploring various systems of logic and not too interested in picking one
: system and decreeing it to be "fundamental".
Of course to study a system is not to insist that it is the only valid
system. However the distinction I was asking about is valid regardless
of how little or much commitment you make to what you study. The
distinction is particularly important in this context because only a
change in logic at the level of the propositional calculus can deal
with the question of whether quantum mechanics predicts nonlocal
causal effects. I get the impression that none of the technical work
you are referring to changes logic at this level but I am still not sure.
Since I advocate a from of finitism I want to respond to your comment
about restricting our forms of reasoning. My goal is not restrict but
to expand the forms of our reasoning. Mathematics has had a historical
tendency to adopt goals that were overly ambitious. We have Frege's
set theory that produced Russell's paradox and Hilbert's program that
led to Godel's incompleteness theorem. It is reasonable to assume that
that there are other errors of this nature that do not lead to absolute
contradictions but still lead to overly ambitious programs. I think Zermelo
Frankel set theory and large cardinal axioms are an example of this.
They are a way of developing and extending mathematics
that *seem* enormously powerful but in fact limit ones ability to
extend mathematics because they put the focus on structures that we can
never understand. They are structures that have no connection to anything
in our universe and I think no connection to anything that exists. I believe
there are structures that can model ZF but these structures are not
what one wants to mean by ZF because among other things they are
countable. What we need to do is study those structures directly and
not study a phantom image of them in the form cardinal numbers.
Paul Budnik
james dolan
->paul budnik writes:
-
->>From your discussion I take it that linear logic as something embedded
->>in classical logic and not an intended as a replacement for it.
-
-It's not "embedded in it", in the sense that it's a "from scratch"
-axiomatic system just like classical logic. I don't think anyone
-expects it to "replace" classical logic, especially because - if I
-understand it correctly - it's a conservative extension of classical
-logic, meaning that any reasoning valid in classical logic is valid in
-linear logic, and anything that's provable in linear logic which only
-uses the connectives of classical logic is in fact provable in classical
-logic. (I could be wrong about this, so if there are any linear
-logicians out there, they should correct me if I've got it wrong.) So
-the proper thing to say is that linear logic "subsumes" classical logic.
even if it did "subsume" classical logic in some sense, that wouldn't
seem to rule out the possibility that it could also be "embedded in"
classical logic in some sense. (and furthermore, composing the
"subsuming" process with the "embedding" process, in either order,
need not, even if it makes sense, produce the identity
transformation.)
-I think most of the people I was talking to take an attitude like that
-which James describes here. I don't think these folks are moralizing
-firebrands trying to convert the world to linear logic. That sort of
-evangelical impulse seems to be confined to puritanical movements like
-finitism and intuitionism, which would *restrict* our forms of
-reasoning. I think people interested in linear logic are interested in
-exploring various systems of logic and not too interested in picking one
-system and decreeing it to be "fundamental".
in line with the idea that there can be lots of different ways of
embedding different logics inside of each other, it seems possible
that the question of which sorts of logical systems deserve to be
considered "restrictive" (and their advocates "puritanical") may be
Patrick Lincoln
> Date: 19 Oct 1994 06:38:51 GMT
> ...
> Hmm. Clearly (as various followup posts indicate) I don't understand
> linear logic very well. But I think it's more than just classical logic
> repackaged in a new way, as your two descriptions of it would make it
> sound.
First of all, when you say linear logic I assume that you are speaking
about Girard's linear logic, as described in the theoretical computer
science journal (vol 50 1987). This logic is closely related to
previous work, like *-autonomous categories (studied by M.Barr) and
the Lambek Calculus (developed by J.Lambek for natural language
parsing and understanding: a noncommutative precursor to LL).
Girard developed linear logic as part of his analysis of the
semantics of intuitionistic logic. In particular, Girard
found that intuitionistic implication A => B decomposes nicely
into two separate operations as !A -o B, where ! means
'reuse at will' and -o means 'linearly implies'.
Linear logic can be seen as a multiset logic, where
the multiplicity of formulas on both sides of the |- is
important (contraction and weakening are allowed everywhere in LK,
only on the left in LJ, and nowhere in LL).
In this setting conjunction separates into two
versions, one which shares context (the additive 'with' &)
and one which splits the context (the multiplicative 'tensor' *).
Two disjunctions also arise dual to the conjunctions: the additive
'plus' + and the multiplicative 'par' (upside-down &).
Linear implication A -o B is defined as (not A) par B.
The exponentials ('of course' ! and its dual 'why not' ?) complete
the set of propositional connectives of linear logic. One can
add the usual first and/or higher-order quantifier rules as well.
I posted a note to sci.logic in early sept giving informal readings of all
the linear connectives and giving some starting points for reading.
Linear logic is more detailed than classical or intuitionistic
logic. One can decompose LK or LJ connectives into several orthogonal
linear operations. Linear logic is very expressive: propositional
linear logic is undecidable. Surprisingly small fragments have
surprisingly huge complexity: validity of formulas written in just
{*,-o,1,bottom} (no propositional literals, no additives, no
exponentials, no quantifiers, just multiplicative connectives and
true and false, something like linear circuit evaluation) is NP-complete.
Intuitionistic logic embeds via !A -o B into linear logic preserving
most interesting proof-theoretic properties. Girard developed two
semantics for linear logic which give rise to semantics for
intuitionistic logic (seen through his embedding). One can
of course embed classical logic into intuitionistic logic using double
negation. One can use linear logic in the study of other logics:
propositional intuitionistic logic embeds into propositional linear
logic without exponentials: that is, the use of structural rules
(contraction and weakening) in prop LJ isn't always necessary. All these
embeddings preserve provability: eg. A => B in LJ iff !A -o B in LL,
but the classical and intuitionistic connectives do not appear
native in linear logic. One cannot easily translate formulas
the other way, from LL to LJ or LK, since LK forgets how many
copies of formulas you have, and so LL-unprovable formulas may
be translated to LK-provable formulas. Complexity considerations
also dictate the impossibility of such translations.
There are now many available semantics that can confer understanding
of the strange linear sequent calculus, some based on games (Abramsky
and Jagadeesan solved a long-standing open problem regarding full
completeness for PCF using game semantics from linear logic, see also
A.Blass,P.Curien), event spaces (Pratt), probabilities (see
file://ftp.cis.upenn.edu/pub/papers/scedrov/ip.dvi.Z), Lauchli
semantics (new work by Blute & Scott), and *-autonomous categories
(Seely &c), in addition to Girard's original two semantics,
As for why computer scientists have taken a liking to LL, there are
many reasons. Functional programming languages (S.Abramsky, P.Wadler,
P.Lincoln, J.Mitchell, N.Benton, G.Bierman, V.DePaiva, M.Hyland,
I.Mackie, J.Chirimar, C.Gunter, J.Riecke, &c) compilers (P.O'Hearn,
D.Wakeling, P.Lincoln, H.Baker, Y.Lafont, &c), constraint systems
(V.Saraswat, P.Lincoln, V.Gupta, M.Okada, A.Yonezawa, N.Kobayashi,&c),
inheritance (Girard), databases (N.Bidoit, S.Cerrito, C.Froidevaux,&c),
and other CS topics have been considered using linear logic
as a tool of analysis.
The proof theory is rich. Too many authors to list here.
Recently V.Pratt, P.Panangaden, and others have been exploring
connections between linear logic and some physics related things.
Pratt's 'linear logic for generalized quantum mechanics' and
other papers (see file://boole.stanford.edu/pub/ABSTRACTS), and
Panangaden's work on connections between linear proof nets and
Feynman diagrams are interesting, but are certainly in the very
early stages, and I'm not an expert on those things.
For some pointers to wwwebable and ftpable papers and bibliographies
see http://www.csl.sri.com/linear/sri-csl-ll.html.
pdl.
Henry G. Baker
>This Week's Finds in Mathematical Physics (Week 40)
>John Baez
>
>inkling of, is "linear logic". This was introduced in the following
>paper (which I haven't gotten around to looking at):
>
>1) Linear Logic, by Jean-Yves Girard, Theoretical Computer Science 50
>(1987) pp. 1-102.
Linear logic is also useful for thinking about (and performing)
computation. Linear logic leads directly into the concept of
'use-once' variables, which have to be explicitly copied to be used
more than once, and have to be explicitly deleted. Of course, certain
_types_ of these variables may have to be conserved, and may not be
deleted OR copied -- e.g., the I/O stream which talks to the user.
Thus, it is possible to start putting conservation laws into computer
software using some of the ideas behind linear logic. These conservation
laws are useful (among other things) the same way that strong typing and
physical units are useful -- as consistency checks on the software.
There are a number of papers in my ftp directory about using linear
logic ideas in computation.
Henry Baker
Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
Bill Taylor
|> Bill Taylor <w...@math.canterbury.ac.nz> wrote:
|> >ba...@ucrmath.ucr.edu (John Baez) writes:
|> >|> I remember feeling at the time
|> >|> that logic had become less revolutionary than in it was in the early
|> >|> part of the century. It seemed to me that logic had become a branch of
|> >|> mathematics like any other,
|> >Very well put! I remember feeling much the same; like a lot of folk, I expect.
|> Actually, I have a slightly different view of this. IMO, making logic a
|> branch of mathematics *was* the revolutionary idea.
Very astute and pithy!
|> That's perhaps stating
|> it too strongly, but the key behind the revolutionary ideas was making the
|> methods of mathematical investigation (i.e., proofs) themselves the objects
|> of mathematical investigation. (This gives more credit to Hilbert than to
|> Goedel than is usual, I realize.)
As usual, Tim, you have got to the heart of it so simply and easily. I agree
with this view totally. (And if any others object that I also agreed with
John Baez totally, and that John and Tim say different things, then...
I will also agree with them totally!)
Thanks for your take on this one Tim.
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
My opinion may have changed, but not the fact that I am right.
-------------------------------------------------------------------------------
Matthew P Wiener
>Is there some reason why intuitionism et al are singled out for gratuitous
>top-of-the-head commentary?
Yes. Its practitioners made strong universal claims at one point.
> I mean, you don't often hear disabusals of
>algebraic geometry as *restrictive* in its reliance on polynomials, or how
>combinatorics is a Luddite conspiracy to take away our toys.
These folks have just secretly tried to take over mathematics.
john baez
>Is there some reason why intuitionism et al are singled out for gratuitous
>top-of-the-head commentary?
Probably because some of them, like Bishop, attack classical mathematics
as "schizophrenic". The only intuitionist I know well personally,
Christer Hennix --- actually an "ultraintuitionist" follower of
Yesenin-Volpin --- seriously puts down classical mathematics as a bunch
of mistaken junk that's not worth learning. In short, there really
*are* puritanical intuitionists, finitists, constructivists and the
like, who think a kind of revolution is required to bring mathematics to
its senses. (I have no idea what Brouwer's exact opinion about this
was; while Hilbert said he was trying to expel us from the paradise
Cantor built, deprive mathematicians of proof by contradiction like
depriving a boxer of his gloves, etc. I don't know whether *Brouwer*
said explicitly that people should *stop doing* classical mathematics.)
After having argued with Hennix for a long time, I decided that in
certain cases the only sensible response to such positions was to make
fun of them. And I like joking around. This has *nothing* to do with
people who are interested in studying alternative forms of logic, or
even "restricted" forms of logic, as part of the general goal of
mathematics to understand everything in all possible ways. In fact,
right now I am busily struggling to understand Mac Lane and Moerdijk's
book on topoi in an effort to see how intuitionistic logic is related to
cartesian closed categories, and I think it's fascinating stuff.
Note also that as Dolan pointed out, some forms of logic are not really
as restrictive as they seem! One can prove not(not(P)) in
intuitionistic logic, and the distinction between not(not(P)) and P
makes it in a sense more expressive than classical logic.
"Restrictiveness" often has more to do with the emotional tone of a
certain body of work than with the mathematics itself. Thus, while I
have nothing against algebraic geometry (except a certain frustration at
my own ignorance of it), I would gladly make fun of algebraic geometers
who insisted that the only functions we can "really comprehend" are
polynomials.
Randall Holmes
Tal Kubo (ku...@brauer.harvard.edu) wrote:
: Is there some reason why intuitionism et al are singled out for gratuitous
: top-of-the-head commentary? I mean, you don't often hear disabusals of
: algebraic geometry as *restrictive* in its reliance on polynomials, or how
: combinatorics is a Luddite conspiracy to take away our toys. But with
: intuitionism there is somehow a recurring need to Cast Out The Heretics, or
: at least to paint them as crackpots (grumpy malcontents, as Baez put it in
: week 40's Finds). The review of van Stigt's book on Brouwer in the most
: recent American Mathematical Monthly, for example, refers to Bishop and
: Kronecker as "constructivist-fascists" -- this in an article with a
: *favorable* assessment of Brouwer and his philosophy. So who is
: puritanical, anyway?
Certainly there is a reason. Many intuitionists are not just studying a
particular class of mathematical models. They claim the mathematics
that other mathematicians know and love is not sound.
I suspect it is sound in the sense of being consistent and in the
stronger sense that the conclusions we can draw from it about recursive
processes are correct. On the other hand I think most of the objects
it aims to talk about do not exist. It is sound because those objects
have a countable model in a universe that talks only about properties
of Turing Machines (and thus properties of the integers). Even this model
does not exist as physical objects exist but all the properties of TMs
within this model have a objective meaning in a potentially infinite
universe.
It is not just taking away their toys that mathematicians resent.
Taking away their illusions about the metaphysical status of
those toys also draws their ire.
Paul Budnik
Holmes:
A case in point regarding my remark in a parallel post about
the incompatibility between a correct view of mathematical objects and
the spirit of the age. There is no coherent account of mathematics in
terms of properties of physical objects. There isn't even a coherent
account of physical objects in terms of the properties of physical
objects (alone): all actual accounts involve mathematical objects,
and the attempt to eliminate the fundamental role of these (and
possibly other universals) is generally not actually attempted in
practice; an appeal to prevailing prejudices is usually taken to be
sufficient.
--
The opinions expressed | --Sincerely,
above are not the "official" | M. Randall Holmes
opinions of any person | Math. Dept., Boise State Univ.
or institution. | hol...@math.idbsu.edu
Jamie Andrews
Paul Budnik <pa...@mtnmath.mtnmath.com> wrote:
> Many intuitionists are not just studying a
>particular class of mathematical models. They claim the mathematics
>that other mathematicians know and love is not sound.
I would say rather that they claim that some of the
mathematics that other mathematicians do is meaningless.
Brouwer, Weyl and so on were really just articulating
a discomfort with non-constructive proofs that was quite common
at the time. Proponents and opponents of non-constructive
proofs were equally dogmatic back then, I would say.
Over time, as with many minor traditions in academic
disciplines, some of the ideas of intuitionism got integrated
into the mainstream, and the minor tradition attracted its share
of crackpots that pushed it to the limits. That doesn't mean we
can dismiss any intuitionist as a crackpot.
90 years from now, I'm sure there will be people ranting
about category theory being the basis of all human thought,
but that doesn't mean we should dismiss it. Completely, at least. :-)
Ron Maimon
|> In article <1994Oct26.0...@hulaw1.harvard.edu> ku...@brauer.harvard.edu (Tal Kubo) writes:
|>
|> >Is there some reason why intuitionism et al are singled out for gratuitous
|> >top-of-the-head commentary?
|>
|> Probably because some of them, like Bishop, attack classical mathematics
|> as "schizophrenic"
Well, classical math is pretty schitzophrenic.
You have one theorem that says that the real numbers admit a well ordering,
and then you have another theorem that says that any ordering of the real
numbers you will be given ever in your entire life will _not_ be a well
ordering.
You have one theorem that says that you can chop up a grape into a finite
number of peices and rotate these peices and glue them together disjointly
to form a set as big as the sun, but you have another theorem that says
that no set of grape-peices that anyone will ever present to you will have
this property.
You have a theorem that says that every vector space has a basis, and you
have a theorem that says that no one will ever write down a basis for
the vector space of real valued functions on Z.
This is schitsophrenia with a vengence. The only way to sort these things
in your mind is to realize that it is a qualitatively different thing to
prove a statement that to prove it's contrapositive and it is a
qualitatively different thing to prove a theorem using finitistic axioms
vs. proving it using the axiom of choice.
How hard can it be to take these two facts into account?
--
Ron Maimon
! You're a star bellied sneetch, you suck like a leech
Jello ! you want everyone to act like you
Biafra ! kiss ass while you bitch so you can get rich
! but your boss gets richer off you
Matthew P Wiener
>|> Probably because some of them, like Bishop, attack classical mathematics
>|> as "schizophrenic"
>Well, classical math is pretty schitzophrenic.
>You have one theorem that says that the real numbers admit a well ordering,
>and then you have another theorem that says that any ordering of the real
>numbers you will be given ever in your entire life will _not_ be a well
>ordering.
There are finitistic theorems that are just as "schizophrenic". For
example, Goedel's first incompleteness theorem says--even constructs--
ought-to-be-true statements with no proofs.
A dyed-in-the-wool finite purist may perhaps not officially believe in
the ought-to-be-true part--but do any of them seriously try to prove
PA inconsistent?
Neil Rickert
>In article <38mic6$n...@galaxy.ucr.edu>, ba...@guitar.ucr.edu (john baez) writes:
>Well, classical math is pretty schitzophrenic.
>You have one theorem that says that the real numbers admit a well ordering,
Right.
>and then you have another theorem that says that any ordering of the real
>numbers you will be given ever in your entire life will _not_ be a well
>ordering.
There ain't no such theorem. "Ever in your entire life" is not
suitable mathematical terminology for use in a theorem.
>You have one theorem that says that you can chop up a grape into a finite
>number of peices and rotate these peices and glue them together disjointly
>to form a set as big as the sun,
Again, there is no such theorem. The Banach-Tarski paradox is not
about dissecting grapes.
> but you have another theorem that says
>that no set of grape-peices that anyone will ever present to you will have
>this property.
Again, there is no such theorem, although that is a plausible
consequence of various theorems. Theorems are not about grape
pieces. If intuitionists think that theorems are about grape pieces,
then they have been drinking too much fermented grape juice.
>You have a theorem that says that every vector space has a basis,
Right.
> and you
>have a theorem that says that no one will ever write down a basis for
>the vector space of real valued functions on Z.
Wrong again. Such statements are not the proper content of
theorems. The question of what a person will or will not actually
write down is a question of psychology or sociology, or perhaps
biology. It is not a question of mathematics.
>This is schitsophrenia with a vengence.
You may happen to be schizophrenic, but there is no need for you to
inappropriatly attribute your own schizophrenia to others.
> The only way to sort these things
>in your mind is to realize that it is a qualitatively different thing to
>prove a statement that to prove it's contrapositive and it is a
>qualitatively different thing to prove a theorem using finitistic axioms
>vs. proving it using the axiom of choice.
No. The way to sort this out is to realize that mathematics is not
about real world objects, such as grapes.
Paul Budnik
: A case in point regarding my remark in a parallel post about
: the incompatibility between a correct view of mathematical objects and
: the spirit of the age. There is no coherent account of mathematics in
: terms of properties of physical objects. There isn't even a coherent
: account of physical objects in terms of the properties of physical
: objects (alone): all actual accounts involve mathematical objects,
: and the attempt to eliminate the fundamental role of these (and
: possibly other universals) is generally not actually attempted in
: practice; an appeal to prevailing prejudices is usually taken to be
: sufficient.
All either mathematics or physics can ever accomplish is to describe
complex structures in terms of simpler structures. The most fundamental
elements in any such analysis can be equally well regarded as mathematical
or physical. Describing more complex physical structures in terms of more
fundamental ones is applied mathematics.
If you want to understand what the fundamental `building blocks of existance'
are you have to go outside of both mathematics and physics. My philosophcial
speculation is that the essense of everything that exists is a form of
consciousness or self awareness not in the sense of the complex structure
of human consciousness but in the sense of say a single point in a visual
field. Human consciousness and self awareness is what it means for a
physical object to exist and be structured as the human mind and body
is and to interact with the world as we do. There are no `building blocks'.
There is a diffuse form of unviersal consciouness out of which individuals
are carved as if by some cosmic stone mason.
These individual structures are finite because consciouness is
specific and finite. Unlike infinite sets if you add something to a conscious
gestalt it is always different. There may no fixed limit to the number of
conscious experiences that can evolve but each of them is finite. That
is what I mean by a potentially infinite universe and why I think most
of the objects mathematicians reason about do not exist although most
of them have an interpretation in terms of how structures in a potentially
infinite universe might evolve.
Paul Budnik
Matthew MacIntyre
: Is there some reason why intuitionism et al are singled out for gratuitous
: top-of-the-head commentary? I mean, you don't often hear disabusals of
: algebraic geometry as *restrictive* in its reliance on polynomials,
I would, if it were not for Chow's theorem.
Ramsay-MT
Ron Maimon writes:
|You have one theorem that says that the real numbers admit a well ordering,
|numbers you will be given ever in your entire life will _not_ be a well
|ordering.
No, there isn't a theorem that says that. One can give a formula F(x,y)
which defines a well-ordering of the reals, if a certain statement (known
as V=L) is true. By a result of Godel, there is no proof of V<>L in ZFC.
To show that there isn't an explicit well-ordering of the reals you will
at least have to disprove V=L, and I suspect quite a bit more (even if we
grant you that by "explicitly giving" a well-ordering we mean defining the
well-ordering in some fixed language like first-order set theory).
Keith Ramsay
Paul Budnik
: I believe that a more fundamental distinction (than that between complexity
: and simplicity) is that between informal and formal objects. The universe
: is ultimately ineffable in the sense that we can't give a complete formal
: description of it - it can't be reduced absolutely to the tidy world of
: discrete symbols; "The Tao that can be said is not the true Tao." Even
: mathematics is more than just the formal systems used to express it.
: Nonetheless, by some magic - which, I'm afraid, I cannot explain but must
: accept as an article of faith - it seems possible and useful to use formal
: symbols to give approximate expression to aspects of the informal real
: world. What physics accomplishes is to set up a formal system that we can
: (informally) relate to the real world and - if it is a successful physics -
: thereby know better what the real world does.
: Here's a simpler example: the true specification of a computer program is
: "ineffable" or informal. Fundamentally, it's quality and fitness for
: purpose, but these depend on users' needs and expectations, and these are
: incompletely understood and indeed change with time. A formal specification
: is good insofar as programs satisfying it (a formal relation) have quality
: and fitness for purpose (informal notions).
You seem to be saying that reality is not reducible to a formal description
and that is more fundamental than the difference between simplicity and
complexity. I certainly agree. In fact I agree so much that it would never
occur to me to make a posting about it.
This does not imply that it is impossible *even in theory* to give a
formal description that *models* physical reality in complete detail.
I suspect it is possible in theory (but not in practice) to fully
characterize any finite space time volume with a formal description that
will fully model what happens in the collapsing light cone for that volume.
However this is a very limited characterization. For example it says
nothing about what "user's needs and expectations are" even
thought it may be able to fully model their behavior.
Paul Budnik
Neil Rickert
>You seem to be saying that reality is not reducible to a formal description
>and that is more fundamental than the difference between simplicity and
>complexity. I certainly agree. In fact I agree so much that it would never
>occur to me to make a posting about it.
>This does not imply that it is impossible *even in theory* to give a
>formal description that *models* physical reality in complete detail.
Any formal model which models physical reality in complete detail
would have to include within that model, the existence of a modeler
modeling the model in complete detail. There would appear to be a
problem of an infinite chain of models and modelers.
>I suspect it is possible in theory (but not in practice) to fully
>characterize any finite space time volume with a formal description that
>will fully model what happens in the collapsing light cone for that volume.
One might imagine that one could escape from the universe, but this
can never be more than imagination. Then, in one's imagined
existence outside the universe, one might in theory model that
universe as an external observer. But any idea that one could model
the universe while remaining within that universe seems obviously
wrong.
unknown mail address
>From: wee...@aries.wistar.upenn.edu (Matthew P Wiener)
>Subject: Re: This Week's Finds in Mathematical Physics (Week 40)
>Date: 26 Oct 1994 14:43:15 GMT
hhu.forum Y 0
hhu.gibs Y 0
hhu.linux Y 0
hhu.mach Y 0
hhu.modem Y 0
hhu.netadmins Y 0
hhu.rzinfos Y 0
hhu.software Y 0
Lawrence McKnight
writes:
>Mind you, I don't buy it myself (I'm rather fond of measurable
cardinals).
>But I listen with respect.
>
Oh, no. Think how confusing things will get if those who cannot
understand finite induction start trying to understand Ulam
measureability.
--
----------------------------------------------------------
Larry McKnight...........
Tal Kubo
Even if you care only about smooth projective complex manifolds,
the odious finitistic considerations impose themselves. e.g., computing
Betti numbers of interesting analytic spaces by counting points on
the reduction mod p.
Ron Maimon
|> Ron Maimon babbles:
|>
|> Well, classical math is pretty schitzophrenic.
|>
|> You have one theorem that says that the real numbers admit a well ordering,
|> and then you have another theorem that says that any ordering of the real
|> numbers you will be given ever in your entire life will _not_ be a well
|> ordering.
|>
|>
why is this ridiculous?
It's not just a dumb example- there are good reasons why _in principle_ you
cannot well order the real numbers. It makes no difference if you assume
you can or you can't, except to whether the axiom of choice holds or not,
and you can't verify this at all.
|> Ho hum.
|>
|> With equal justice, I could say:
|>
|> Finitistic math is pretty schizophrenic. You have one theorem
|> that says there is a natural number 10^10^10^10, and you have
|> another theorem that says that never in your entire life will
|> anybody give you such a large number.
well, you can't say that- you just gave me such a large number.
but I understand your point. You are right- both finitistic and classical
math are idealizations, except finitistic math is a much more _useful_
idealization.
And I think it's prettier too.
|>
|> Maybe you'd like to be a mite more explicit about your term, "given"?
I meant that you can't construct one without using the axiom of choice-
you can't, given a series of rationals that converges to x associate
with x a position in some uncountable well ordered set based on the
approximating series alone, and expect that to be a well ordering of
the reals.
This is true even though you can construct an uncountable well ordered
set with no problem.
|>
|> More to the point: why do you post things like this? For some newbie,
|> it might be the first Ron Maimon post they see. They might easily
|> lump you in with the raving lunatics
every one of my posts has someone reading it who lumps me in with the
raving lunatics.
It's just the way I write- I'm sorry if it is offensive, I can't change
now, its too ingrained.
|> I happen to know you are an admirer of H. Edwards' works.
|>
|> [nice Edwards quote deleted]
|>
|> Mind you, I don't buy it myself (I'm rather fond of measurable cardinals).
|> But I listen with respect.
I do too.
I have no problem with classical mathematics, I just wish people understood
that a theorem like the well ordering theorem is more of a statement about
your axiom system then a statement about the real numbers.
I find the real numbers to be far more interesting objects then the axiom
system for set theory.
Paul Budnik
: I find the real numbers to be far more interesting objects then the axiom
: system for set theory.
If you consider *the* real numbers to be *objects* that you are not
a finitist it all but are only deluding yourself into thinking your are.
In contrast formal axiom sytems are objects and refer to something.
However they do not refer to mythical objects like the set of *all* real
numbers. That set requires completed infinite totalities.
Paul Budnik
Michael Weiss
mathematics boils down to you asserting that some set-theoretic
consequence in ZFC isn't "real". And your justification is always
that no one can tell you what it "really" means, to your satisfaction.
Paul Budnik has been saying the same sort of thing about standard
quantum mechanics for years.
But you do start a new line of argument with one of your remarks:
both finitistic and classical math are idealizations, except
finitistic math is a much more _useful_ idealization.
Really? Hasn't Sidney Coleman brought out the usual arsenal of
Hilbert spaces and wavefunctions and Lie groups and other infinite
objects, to do QFT? When you learned GR, didn't you play in the usual
differential geometry sandbox? *As idealizations*, I'll bet you've
used classical mathematics in all its unfettered glory a lot more than
Peano arithmetic (the idealization of finitism that tells us that
10^10^10^10 exists).
I find the real numbers to be far more interesting objects then the axiom
system for set theory.
Art appreciation makes a poor foundation for a philosophy of mathematics.
Ron Maimon
|> In <39dhql$o...@scunix2.harvard.edu> rma...@husc9.Harvard.EDU (Ron Maimon) writes:
|>
|> >I have no problem with classical mathematics, I just wish people understood
|> >that a theorem like the well ordering theorem is more of a statement about
|> >your axiom system then a statement about the real numbers.
|>
|> understood that a statement about the real numbers is more of a
|> statement about your axiom system than a statement about reality.
|>
This is _not_ true
There is a sense in which a statement about the real numbers _is_ a statement
about reality, that has absolutely nothing to do with what axioms you use
to get the real numbers.
Those statements are the ones that provide you with constructions of real
numbers that you can carry out to arbitrary accuracy.
For example, there is a theorem that there exists a real number x such
that x^2=2. One way to prove this is to use the intermediate value theorem
to say that the function x^2 passes through the value 2 in between
x=1 and x=2. The intermediate value theorem is a consequence of the least
upper bound principle, which is one of the standard axioms about the real
numbers.
This is a statement about your axiom system, it says that you have been
brought up in a world that likes to axiomatize its real numbers with the
least upper bound principle.
Another way to prove the same statement is to start from the fact that
there are arbitrarily large integers m and n such that
m^2 - 2 n^2 = 1
or | m^2/n^2 - 1 | < 1/n^2
this says that if you have a computer, and you calculate the decimal
digits of m/n to some accuracy, square them, then you end up with a
number very close to 2, and by choosing larger and larger solutions,
you end up with more and more digits of sqrt(2).
This is a statement about a construction you can do on a computer, and
has absolutely nothing to do with your axiom system for the real numbers,
it's a statement about "reality", about what you can or cannot compute.
There is a way to phrase the intermediate value theorem so that it is
a statement about "reality" and not just about your axioms for the real
numbers, but its more subtle then the usual statement. Most people ignore
it, even though this is the more important theorem.
Neil Rickert
>In article <39e17d$b...@mp.cs.niu.edu>, ric...@cs.niu.edu (Neil Rickert) writes:
>|> In <39dhql$o...@scunix2.harvard.edu> rma...@husc9.Harvard.EDU (Ron Maimon) writes:
>|>
>|> >I have no problem with classical mathematics, I just wish people understood
>|> >that a theorem like the well ordering theorem is more of a statement about
>|> >your axiom system then a statement about the real numbers.
>|>
>|> I have no problem with intuitionist mathematics. I just wish people
>|> understood that a statement about the real numbers is more of a
>|> statement about your axiom system than a statement about reality.
>This is _not_ true
Are you a mind reader, that you can assign truth values to my wishes?
>There is a sense in which a statement about the real numbers _is_ a statement
>about reality, that has absolutely nothing to do with what axioms you use
>to get the real numbers.
Yes, indeed, there is such a sense. But this sense can only make
sense to those who are confused and think that mathematics is
reality.
>Those statements are the ones that provide you with constructions of real
>numbers that you can carry out to arbitrary accuracy.
These constructions only construct rational numbers. To say that
they are constructions of real numbers is merely a manner of speaking
which only makes sense when interpreted in a suitable axiom system.
>For example, there is a theorem that there exists a real number x such
>that x^2=2.
Right. But this theorem exists in an axiom system. The real numbers
only exist in an axiom system.
> One way to prove this is to use the intermediate value theorem
>to say that the function x^2 passes through the value 2 in between
>x=1 and x=2. The intermediate value theorem is a consequence of the least
>upper bound principle, which is one of the standard axioms about the real
>numbers.
>This is a statement about your axiom system, it says that you have been
>brought up in a world that likes to axiomatize its real numbers with the
>least upper bound principle.
At least you agree that this part is only a statement in the axiom
system.
>Another way to prove the same statement is to start from the fact that
>there are arbitrarily large integers m and n such that
>m^2 - 2 n^2 = 1
>or | m^2/n^2 - 1 | < 1/n^2
Arbitrarily large integers only exist by virtue of an axiom system.
>this says that if you have a computer, and you calculate the decimal
>digits of m/n to some accuracy, square them, then you end up with a
>number very close to 2, and by choosing larger and larger solutions,
>you end up with more and more digits of sqrt(2).
In reality, the computer runs out of memory and cannot represent
these large numbers as they get larger and larger. But, quite apart
from that, the construction of arbitrarily large integers does not in
any way guarantee the existence of a real number. The existence of
the real number requires an axiom system.
>This is a statement about a construction you can do on a computer, and
>has absolutely nothing to do with your axiom system for the real numbers,
>it's a statement about "reality", about what you can or cannot compute.
It is clearly not a construction I can do on my computer, since my
computer has finite memory. It is a construction I can do on a
Turing machine. But a TM does not exist in reality; it is a
theoretical device which operates according to its own axiom system,
usually referred to as a transition table.
>There is a way to phrase the intermediate value theorem so that it is
>a statement about "reality" and not just about your axioms for the real
>numbers, but its more subtle then the usual statement.
Such a phrasing, as a statement about "reality", is only possible for
people who have already incorporated some of the axioms systems into
their personal view of reality.
Mike Oliver
>I meant that you can't construct one without using the axiom of choice-
>you can't, given a series of rationals that converges to x associate
>with x a position in some uncountable well ordered set based on the
>approximating series alone, and expect that to be a well ordering of
>the reals.
Ron, you either haven't specified well enough what you mean, or else you're
just wrong.
There is no theorem (you did say "theorem" in an earlier post) from any
standard axioms of (choice-ful) set theory which excludes the existence of
a definable wellorder of the reals. In fact Shelah has shown that
ZFC+large cardinals cannot refute the existence of a Delta^2_2 definable
wellorder of the reals.
Now, there are several possible things you *might* have meant that would
be true. But if you're going to continue to use this argument you ought
to figure out which one it is.
Mike Oliver
>I have no problem with classical mathematics, I just wish people understood
>that a theorem like the well ordering theorem is more of a statement about
>your axiom system then a statement about the real numbers.
I know I'm making a pest of myself on this subject, but I really can't let
this one go.
The theorem that the reals can be wellordered is a statement about the
*reals* (or more precisely, about an even more complex object, namely
an ordering of the reals).
This applies even if you don't believe that the reals really exist, or
you believe that they exist but can't be wellordered, or if you believe
that they're a useful fiction, or if you believe that the reals themselves
exist but arbitrary orderings of them don't, or that all we're *really*
doing is proving formal theorems, or whatever.
Statements about the axiom system do *not* have the form "there exists
a wellordering of ..." but rather "axiom system T can prove statement S"
or "for any S if T proves S then T proves S', where you get S' from S
in the following manner" or something like that.
Now I think I know what you meant. I think you meant, more or less, that
the *importance* of the statement that the reals can be wellordered is
primarily formal, and lies in what you can prove with it. But the way
you stated it suggests a deplorably common type confusion which is not
counter-conventional but just sloppy.
Neil Rickert
>I have no problem with classical mathematics, I just wish people understood
>that a theorem like the well ordering theorem is more of a statement about
>your axiom system then a statement about the real numbers.
I have no problem with intuitionist mathematics. I just wish people
understood that a statement about the real numbers is more of a
statement about your axiom system than a statement about reality.
>I find the real numbers to be far more interesting objects then the axiom
>system for set theory.
Many classical mathematicians would agree with this.
Randall Holmes
In <39gnhb$d...@scunix2.harvard.edu> rma...@husc9.Harvard.EDU (Ron Maimon) writes:
[...]
>There is a sense in which a statement about the real numbers _is_ a statement
>about reality, that has absolutely nothing to do with what axioms you use
>to get the real numbers.
Yes, indeed, there is such a sense. But this sense can only make
sense to those who are confused and think that mathematics is
reality.
Mathematics, the human activity part of which consists in constructing
and manipulating axiom systems, is certainly part of reality. This is
not, of course, the view which Rickert is branding as "confused" here.
But I would like to know what Rickert thinks mathematics is about, if
its subject matter is not (part of) reality. (which it is; Rickert is
confused -- I hasten to add "but not in any way unique to himself"!).
>Those statements are the ones that provide you with constructions of real
>numbers that you can carry out to arbitrary accuracy.
These constructions only construct rational numbers. To say that
they are constructions of real numbers is merely a manner of speaking
which only makes sense when interpreted in a suitable axiom system.
I'm afraid history gives this the lie. The axiom systems were
formulated to express clearly an understanding of the reals which
already existed (in a somewhat confused form). This understanding
can't be explained in terms of axiom systems.
>For example, there is a theorem that there exists a real number x such
>that x^2=2.
Right. But this theorem exists in an axiom system. The real numbers
only exist in an axiom system.
I would like an explanation of this doctrine of relative existence in
rigorous philosophical terms.
[...]
Arbitrarily large integers only exist by virtue of an axiom system.
Tell me how an axiom system can make _anything_ exist :-)
[...]
In reality, the computer runs out of memory and cannot represent
these large numbers as they get larger and larger.
Can't represent _what_, exactly?
[...]
Such a phrasing, as a statement about "reality", is only possible for
people who have already incorporated some of the axioms systems into
their personal view of reality.
We should certainly avoid as far as possible speaking from a personal
view of reality :-)
It would also be nice for Rickert to give an explanation of what an
axiom system is along the lines he suggests here. An axiom system is
a mathematical object itself, if it is scrutinized closely enough; so
by Rickert's criteria cannot exist, and this would cast serious doubt
on the ability of an axiom system to bestow the benison of relative
existence on mathematical objects.
Ron Maimon
|> Ron, everyone of these discussions about the reality of classical
|> mathematics boils down to you asserting that some set-theoretic
|> consequence in ZFC isn't "real". And your justification is always
|> that no one can tell you what it "really" means, to your satisfaction.
|>
On the other hand, the statement that given a and b integers a+b
is "real" makes perfect sense, since I can construct it with my fingers
or a computer from a and b.
|> Paul Budnik has been saying the same sort of thing about standard
|> quantum mechanics for years.
Well, Paul Budnik is wrong.
|>
|> But you do start a new line of argument with one of your remarks:
|>
|> both finitistic and classical math are idealizations, except
|> finitistic math is a much more _useful_ idealization.
|>
|> Really? Hasn't Sidney Coleman brought out the usual arsenal of
|> Hilbert spaces and wavefunctions and Lie groups and other infinite
|> objects, to do QFT?
Well, yes, but those are perfectly sensible, constructively defined
objects. A separable Hilbert space (the one people do field theory
with) is precisely that linear space that you can do approximate
computations in by choosing larger and larger finite dimensional
subspaces. What's wrong with that?
If quantum field theory had required a nonseparable hilbert space, as
some workers in the field used to suggest in the early days, I would
have left the classroom in disgust. Constructing a theory with a
nonseparable Hilbert space is not constructing a theory, its playing
a game with ZFC.
When you learned GR, didn't you play in the usual
|> differential geometry sandbox?
Again, what's wrong with differential geometry? That's a perfectly
constructive field of mathematics. Every result in general relativity
is a theorem about manipulating little numbers you can actually get an
intuition for.
Einstein was just saying that the behavior of electrons at a point can
be computed from some numbers that depend on the geometry of space near
that point, and can be approximately calculated from approximate initial
conditions.
On the other hand, if einstein claimed that the behavior of electrons
depended in some way on the index of the point they were at relative to
some well ordering of the manifold of space time, he would have been a
very silly man.
*As idealizations*, I'll bet you've
|> used classical mathematics in all its unfettered glory a lot more than
|> Peano arithmetic (the idealization of finitism that tells us that
|> 10^10^10^10 exists).
it's the same difference. Everything we do we can model on a computer, and
computers only know how to count.
|>
|> I find the real numbers to be far more interesting objects then the axiom
|> system for set theory.
|>
|> Art appreciation makes a poor foundation for a philosophy of mathematics.
Art appreciation makes the only foundation for a philosophy of mathematics.
Ron Maimon
|>
|> Now I think I know what you meant. I think you meant, more or less, that
|> the *importance* of the statement that the reals can be wellordered is
|> primarily formal, and lies in what you can prove with it. But the way
|> you stated it suggests a deplorably common type confusion which is not
|> counter-conventional but just sloppy.
|>
go ahead and call me sloppy.
I _hate_ having to phrase statements boring.
I'd rather be sloppy then boring.
Hell, I'd rather be _wrong_ then boring
Ron Maimon
|>
|> >I meant that you can't construct one without using the axiom of choice-
|> >you can't, given a series of rationals that converges to x associate
|> >with x a position in some uncountable well ordered set based on the
|> >approximating series alone, and expect that to be a well ordering of
|> >the reals.
|>
|> Ron, you either haven't specified well enough what you mean, or else you're
|> just wrong.
|>
|> There is no theorem (you did say "theorem" in an earlier post) from any
|> standard axioms of (choice-ful) set theory which excludes the existence of
|> a definable wellorder of the reals. In fact Shelah has shown that
|> ZFC+large cardinals cannot refute the existence of a Delta^2_2 definable
|> wellorder of the reals.
Then I'm just wrong, I assumed from the confidence of a professor who
made a bet with me once that it had been proven.
I should have said, that it seems to be true that it is impossible to
associate a position in a well ordered set to every cauchy sequence of
rationals in a way that associates the same element to every equivalent
pair of cauchy sequences.
But all I really wanted to say was that it is not possible to use the
usual proof of the well ordering theorem to get such a map. This is
certainly true.
Angi Long
Pierre Asselin
>In <39gnhb$d...@scunix2.harvard.edu>
>rma...@husc9.Harvard.EDU (Ron Maimon) writes:
>>For example, there is a theorem that there exists a real number x such
>>that x^2=2.
>Right. But this theorem exists in an axiom system. The real numbers
>only exist in an axiom system.
What about geometry?
--
--Pierre Asselin, Santa Barbara, California
p...@verano.sba.ca.us
l...@rain.org
John S. McGowan
A totally ordered set is well ordered if every non empty subset contains
a smallest element.
Standard ordering of the rationals or reals is not a well ordering (the
set {x>0:x*x<2} doens not contain a largest element.
The natural numbers are well ordered.
A well ordered set has a smallest element (take as the non empty set, the
set itself).
IF one knows that: Property P being true for all x<y implies P(y) is true
on a well ordered set, then it is always true.
(note: for the smallest element, P is true for all x<smallest vaccuously,
so for the smallest element, we need to know that P is true)
(if not... let S be the set on which P is not true... it has a smallest
element, z... then P(x) is true for all x<z so P(z) is true... a
contradiction)
So, one can do proof by induction on a well ordered set.
Regards,
--
John S. McGowan | jmcg...@bigcat.missouri.edu [COIN] (preferred)
| j.mcg...@genie.geis.com [GEnie]
| jom...@eis.calstate.edu [CORE]
----------------------------------------------------------------------
Lawrence McKnight
writes:
>
>What is the definition of a "well-ordering?"
>
>
>
A 'well-ordering' is an ordering such that every non-empty subset has a
least element.
Can't somebody in the math department (I KNOW that there used to be good
professors there) answer that?
If A. Yandl is still there, say hello to him for me.
--
----------------------------------------------------------
Larry McKnight...........
Frank Stephan
any subset B of A has a minimum, i.e. there is an
element b in B with b < c for all c in B-{b}.
Examples are:
- The ordering < and the set of natural numbers.
- The class of all polynomials with non-zero
coeffitients. If p = a_0x^0+a_1x^1+.. and
q=b_0x^0+b^1x^1+.. are polynomials (with only
finitely many nonzero coeffitients) then
p < q iff there is an n with a_n < b_n and
a_m = b_m for all m > n.
- The class of all finite sets of natural numbers.
Then F < G iff there is some x in G-F with
y in F <=> y in G for all y > x.
Nonexamples are:
- The natural ordering < is not a well-ordering on
the integer numbers (...,-3,-2,-1,0,1,2,3,...).
- The natural ordering < is not a well-oredring on
the rational numbers between 0 and 1.
Existence-Theorem:
For every set A there is an ordering < on A such
that < is a well-ordering on A. But somehow there
is no intuitive scheme for such a well-order if A
is uncountable, so we know of its existence but can
not construct it as in the examples above.
This theorem fails, if you do not supply the axiom
of choice to set-theory. Indeed it is equivalent to
this axiom.
The axiom of choice means, that for class of nonempty
sets there is a function which assigns to each set some
element of this set.
Frank Stephan
Tal Kubo
>[...schizophrenia in classical vs. finitistic math]
>
>More to the point: why do you post things like this? For some newbie,
>it might be the first Ron Maimon post they see. They might easily
Why don't you pose the same question to Prof. Baez? He introduced the red
herring about "schizophrenia" into this thread. Ron then pointed out that
as far as the mathematics is concerned Bishop's use of the term was
on-point.
So you disagree with Ron on the math, BFD. This doesn't make his remarks
into lunatic rants -- unless you want to serve as another unfortunate
example of the Establishment/Heretic paradigm I mentioned earlier.
>if dogmatic statements were enough to the carry the day, the
^^^^^^^^
No comment.
Tal Kubo
wee...@aries.wistar.upenn.edu (Matthew P Wiener) writes:
>
>>Is there some reason why intuitionism et al are singled out for gratuitous
>>top-of-the-head commentary?
>
>Yes. Its practitioners made strong universal claims at one point.
So did formalism, Bourbaki, categorists, CS, topology, etc.
None are dismissed in the same way.
>> I mean, you don't often hear disabusals of
>>algebraic geometry as *restrictive* in its reliance on polynomials, or how
>>combinatorics is a Luddite conspiracy to take away our toys.
>
>These folks have just secretly tried to take over mathematics.
They're the vanguard.
Tal Kubo
>
>Ron, everyone of these discussions about the reality of classical
>mathematics boils down to you asserting that some set-theoretic
>consequence in ZFC isn't "real".
It's easy to pick on selectionist set theory for its egregious
nonconstructiveness. But the same point could be made in more
down-to-earth settings.
>And your justification is always
>that no one can tell you what it "really" means, to your satisfaction.
Meanwhile his interlocutors have been going through all sorts of
nitpicking to dismiss the issue about "no definable well orderings".
The point still stands, as far as this foundationally-challenged
reader can tell.
> both finitistic and classical math are idealizations, except
> finitistic math is a much more _useful_ idealization.
>
>Really? Hasn't Sidney Coleman brought out the usual arsenal of
>Hilbert spaces and wavefunctions and Lie groups and other infinite
>objects, to do QFT? [...]
Huh? Since when are any of these less constructive than, say, an
infinite series for Pi?
Matthew P Wiener
>In article <38lpu3$8...@netnews.upenn.edu>
>wee...@aries.wistar.upenn.edu (Matthew P Wiener) writes:
>>>Is there some reason why intuitionism et al are singled out for
>>>gratuitous top-of-the-head commentary?
>>Yes. Its practitioners made strong universal claims at one point.
>So did formalism, Bourbaki, categorists, CS, topology, etc.
>None are dismissed in the same way.
Let's see.
Formalism is a trivially correct philosophy that didn't change try to
anything, just to say it was right. The Hilbert program was a glorious
idea, shot down by Goedel, and formalists pretty much retired--in good
form--from trying to run the mathematical universe at that point.
Bourbaki was a much needed but over extended housecleaning more regarding
style than mathematics itself. They went too far and have indeed been
reviled in some corners.
Category theorists get no respect. When the subject gets nicknamed
"generalized abstract nonsense", and when a very significant subset
of it (topos theory--created by Grothendieck even!) gets nicknamed
"generalized abstract category theory", you know its supporters have
a long uphill battle.
CS? Topology? News to me.
Neil Rickert
>ric...@cs.niu.edu (Neil Rickert) writes:
>>In <39gnhb$d...@scunix2.harvard.edu>
>>rma...@husc9.Harvard.EDU (Ron Maimon) writes:
>>>For example, there is a theorem that there exists a real number x such
>>>that x^2=2.
>>Right. But this theorem exists in an axiom system. The real numbers
>>only exist in an axiom system.
>What about geometry?
I don't understand your point. Geometry is the classic example of
a subject based on an axiom system.
Paul Budnik
: Ron, everyone of these discussions about the reality of classical
: mathematics boils down to you asserting that some set-theoretic
: consequence in ZFC isn't "real". And your justification is always
: that no one can tell you what it "really" means, to your satisfaction.
: Paul Budnik has been saying the same sort of thing about standard
: quantum mechanics for years.
I have not been saying anything like that about QM. I have no doubts
about the `reality' of QM in the sense that it makes accurate
predictions. I just happen to think there is much more reality to
the quantum mechanical behavior or nature then is revealed by our
existing models. Given the lessons of history about such questions
this would seem to be the conservative position to take on this issue.
My arguments about mathematics are also quite different than this.
I think there is an underlying reality to ZFC, i. e. a countable
model for it based on properties of TM's. There is an objective
reality to those properties of TM's. I just do not think there is
an objective reality that corresponds to what many logicians
want to mean by the reality underlying ZFC. Beyond this I think we
need to understand the countable model for ZF in terms of properties
of TMs if we are to have any hope of extending logic beyond ZFC
with some confidence that we are doing it correctly.
: But you do start a new line of argument with one of your remarks:
: both finitistic and classical math are idealizations, except
: finitistic math is a much more _useful_ idealization.
It is much more complicated than that. As you explain the techniques
from classical mathematics are much more powerful then those from existing
finitistic mathematics. There is a rich combinatorial
content to classical mathematics that we are not yet capable of
understanding directly in terms of combinatorics. I think all
classical mathematicians would agree that it would be good to gain
such an understanding. Some may think it impossible to do so. Few
would agree with me that gaining that understanding is the real
key to extending the foundations of mathematics.
Paul Budnik
Karl Hahn
> What is the definition of a "well-ordering?"
A set is well ordered if it has a well ordering relation. A relation takes
any pair of elements of the set (and the order of the pair is significant)
and assigns either TRUE or FALSE to it. So, the relation, greater than
(among the set of integers), for example, is TRUE for (2, 1) but FALSE
for (1, 2).
If R is a relation, we will say that a R b signifies that (a, b) is TRUE
under relation R.
An ordering relation, <, has the following properties:
it never happens that a < a (irreflexivity)
if a < b then it never happens that b < a (antisymmetry)
if a < b and b < c then a < c (transitivity)
If < is an ordering relation and X is a set, then x is the least
element of the set, X, under the ordering, <, if it is true that
x < y for all y in X whenever y not equal to x.
An ordering, <, is a well ordering of the set X, if every nonempty
subset of X has a least element under the ordering, <.
Example: The natural numbers are well ordered under the relation,
less than. Every set of natural numbers has a least element.
Interesting topic for further reading: It has been shown that if
you accept the Axiom of Choice (which states that from any collection
of nonempty sets you can generate a representative set containing one
element from each of the sets in the collection) then there must exist
a well ordering for every nonempty set. This would, of course, include
the real numbers, although nobody has found a well ordering for them --
and it may be that such a well ordering cannot be described in any
finite description.
Recommended book: _Set Theory and Logic_ by Stoll (available from Dover).
--
| (V) | "Tiger gotta hunt. Bird gotta fly.
| (^ (`> | Man gotta sit and wonder why, why, why.
| ((\\__/ ) | Tiger gotta sleep. Bird gotta land.
| (\\< ) der Nethahn | Man gotta tell himself he understand."
| \< ) |
| ( / | Kurt Vonnegut Jr.
| | |
| ^ ha...@lds.loral.com my opinions need not be Loral's
Michael Weiss
Meanwhile his interlocutors have been going through all sorts of
nitpicking to dismiss the issue about "no definable well orderings".
The point still stands, as far as this foundationally-challenged
reader can tell.
Do you mean that you believe it to be a theorem of ZF that there is no
definable well-ordering of the reals? This was shown to be false
(assuming the consistency of ZF) already by Goedel when he defined the
universe of constructible sets. As Mike Oliver has pointed out, much
stronger results have since been obtained by Shelah.
Backing up in the thread a bit, Ron had written:
both finitistic and classical math are idealizations, except
finitistic math is a much more _useful_ idealization.
and I replied:
Really? Hasn't Sidney Coleman brought out the usual arsenal of
Hilbert spaces and wavefunctions and Lie groups and other infinite
objects, to do QFT? [...]
and Tal Kubo replied:
Huh? Since when are any of these less constructive than, say, an
infinite series for Pi?
These are familiar figures in the idealization that is classical
mathematics, which Ron was rejecting as less useful than finitistic
mathematics.
Now, if you or Ron want to say that Cantor's theory of ordinal numbers
will never find application in physics, I won't argue. Who knows?
For Ron this may be a conclusive argument--- "Useless for physics?
Throw it in the trash!" Permit some of us mathematicians (or
ex-mathematicians) to take a wider viewpoint.
In another post, Tal Kubo writes:
So you disagree with Ron on the math, BFD.
I don't know that we *do* disagree on the math. We disagree on the
philosophy behind the math.
And finally:
>if dogmatic statements were enough to the carry the day, the
^^^^^^^^
No comment.
This is cute, because Tal's "no comment" is really a comment.
I suppose I could try and defend myself, but I think I'll give it a
rest.
Benjamin J. Tilly
wee...@sagi.wistar.upenn.edu (Matthew P Wiener) writes:
> In article <39naup$2...@decaxp.harvard.edu>, kubo@math (Tal Kubo) writes:
> >In article <38lpu3$8...@netnews.upenn.edu>
> >wee...@aries.wistar.upenn.edu (Matthew P Wiener) writes:
[...]> >>Yes. Its practitioners made strong universal claims at one
point.
>
> >So did formalism, Bourbaki, categorists, CS, topology, etc.
> >None are dismissed in the same way.
>
> Let's see.
>
> Formalism is a trivially correct philosophy that didn't change try to
> anything, just to say it was right. The Hilbert program was a glorious
> idea, shot down by Goedel, and formalists pretty much retired--in good
> form--from trying to run the mathematical universe at that point.
[...]
Is formalism a trivially correct philosophy? I thought so at one point,
however I have now been convinced that in a very real sense it does not
correspond to what we really think of math as. To see my point see some
of my posts in the "Proof that a number is irrational" thread. In no
sense that can described from the formalist view that I can think of
does it make sense to talk about an irrational which cannot be shown to
be irrational in ZFC. However it does make sense in a very real way to
talk about it...
Ben Tilly
Ralph Loader
In article <1994Nov6.0...@math.ucla.edu>, oli...@oak.math.ucla.edu (Mike Oliver) writes:
|>
|> There is no theorem (you did say "theorem" in an earlier post) from any
|> standard axioms of (choice-ful) set theory which excludes the existence of
|> a definable wellorder of the reals. In fact Shelah has shown that
|> ZFC+large cardinals cannot refute the existence of a Delta^2_2 definable
|> wellorder of the reals.
What is the case is that there is no formula phi(x,y) such that ZFC proves
that "phi(x,y) well orders the reals". If I remember correctly, it's
fairly easy to show using forcing. Of course, there is a formula phi such
that ZFC does not prove "phi(x,y) does not well order the reals" (let phi
be the usual well ordering of L).
I think people are getting their knickers^H^H^H^H^H^H^H^Hdefinabilities in
a twist---do we mean ZFC definable or ZFC-provably definable ...
R.
Matthew P Wiener
>> Formalism is a trivially correct philosophy that didn't change try to
>Is formalism a trivially correct philosophy? I thought so at one point,
>however I have now been convinced that in a very real sense it does not
>correspond to what we really think of math as. [...]
If it helps clarify things, I am an unabashed ultrafanatic Platonist.
Ah buhLEEV in supper commupact cadrinals.
So what I mean when I say formalism is a (as in _a_) trivially correct
philosophy, is that it defines things to suit itself and then happily
shuts the door.
Neil Rickert
>In article <39gsdo$b...@mp.cs.niu.edu> ric...@cs.niu.edu (Neil Rickert) writes:
> In <39gnhb$d...@scunix2.harvard.edu> rma...@husc9.Harvard.EDU (Ron Maimon) writes:
> >There is a sense in which a statement about the real numbers _is_ a statement
> >about reality, that has absolutely nothing to do with what axioms you use
> >to get the real numbers.
> Yes, indeed, there is such a sense. But this sense can only make
> sense to those who are confused and think that mathematics is
> reality.
>Mathematics, the human activity part of which consists in constructing
>and manipulating axiom systems, is certainly part of reality. This is
>not, of course, the view which Rickert is branding as "confused" here.
Agreed, on both points.
>But I would like to know what Rickert thinks mathematics is about, if
>its subject matter is not (part of) reality. (which it is; Rickert is
>confused -- I hasten to add "but not in any way unique to himself"!).
The subject matter of mathematics is the study of the processes for
precisely determining the consequences of precise assumptions. The
real numbers are not the subject matter of mathematics. We invent
imaginary real numbers (and imaginary imaginary numbers) to assist us
in analyzing equations, inequalities, etc.
> >Those statements are the ones that provide you with constructions of real
> >numbers that you can carry out to arbitrary accuracy.
> These constructions only construct rational numbers. To say that
> they are constructions of real numbers is merely a manner of speaking
> which only makes sense when interpreted in a suitable axiom system.
>I'm afraid history gives this the lie.
Ron Maimon was using "constructions" in a narrow sense, related to
computation. You appear to be basing your objection on a different
usage of "construct."
> The axiom systems were
>formulated to express clearly an understanding of the reals which
>already existed (in a somewhat confused form). This understanding
>can't be explained in terms of axiom systems.
Mathematicians did things in the past that would not be acceptable as
mathematics today. Are we arguing about today's meaning of
"mathematics", or an older meaning?
> >For example, there is a theorem that there exists a real number x such
> >that x^2=2.
> Right. But this theorem exists in an axiom system. The real numbers
> only exist in an axiom system.
>I would like an explanation of this doctrine of relative existence in
>rigorous philosophical terms.
Discussion only makes sense when terms have meaning. Meaning depends
on a frame of reference. Humans are prone to quickly switch from one
frame of reference to another, depending on context to alert those
with whom they are conversing. Existence is not unlike other words,
in having its meaning dependent on the frame of reference. It is
quite common for people to declare that unicorns exist, and at
another time declare that they do not exist. We do not see this as
contradictory, because we understand that there has been a change in
the frame of reference, from mythology to reality.
For mathematicians, in this current era, the frame of reference for
mathematical discussions is determined by the system of axioms. Some
of these axioms may be implicit, although traditional mathematicians
use a different implicit frame from intuitionists. It is true, as
you suggest, that historically mathematicians were more informal
in specifying their frame of reference. But historically, mathematics
was more closely tied to physics, and that tie made physical intuition
available as part of the implied frame of reference.
> In reality, the computer runs out of memory and cannot represent
> these large numbers as they get larger and larger.
>Can't represent _what_, exactly?
Ron was discussing a particular form of representation. In essence,
he was referring to a standard binary or decimal representation of
the numbers. My reply was made in the context of that discussion.
>It would also be nice for Rickert to give an explanation of what an
>axiom system is along the lines he suggests here. An axiom system is
>a mathematical object itself, if it is scrutinized closely enough; so
>by Rickert's criteria cannot exist, and this would cast serious doubt
>on the ability of an axiom system to bestow the benison of relative
>existence on mathematical objects.
If an axiom system is scrutinized closely enough, it is evident that
it is not a mathematical object. Axiom systems very precisely define
what is permissible as a valid operation under that axiom system.
But most axiom systems themselves are written partly in ordinary
language, and use terminology that has a well understood meaning but
has no precise definition.
Jake Donham
Karl> Interesting topic for further reading: It has been shown
Karl> that if you accept the Axiom of Choice (which states that
Karl> from any collection of nonempty sets you can generate a
Karl> representative set containing one element from each of the
Karl> sets in the collection) then there must exist a well
Karl> ordering for every nonempty set. This would, of course,
Karl> include the real numbers, although nobody has found a well
Karl> ordering for them -- and it may be that such a well ordering
Karl> cannot be described in any finite description.
Why isn't "less-than" a well-ordering for the real numbers? Is it
because of things like .999... == 1? (But in that case are .999... and
1 actually two different numbers or two ways of writing the same
number?).
Please clue me in.
Thanks,
Jake
Lawrence McKnight
jdo...@hadron.us.oracle.com (Jake Donham) writes:
>Why isn't "less-than" a well-ordering for the real numbers? Is it
>because of things like .999... == 1? (But in that case are .999... and
>1 actually two different numbers or two ways of writing the same
>number?).
>
>Please clue me in.
>
>Thanks,
>
>Jake
>
Note the precise definition of a well-ordered... every non-empty set has
a least element. Not a greatest lower bound, but a least elemeent. The
open interval (0,1) has a greatest lower bound, namely 0, but that is not
an element of the set. The well ordering of of the reals would look
nothing like the usual order. Consider the following:
Let a be an element of the well-ordered set. Then, either a is
the greatest element of the set, or there is an element a+ such that
1)a+>a and 2) if b>a, then b>=a+. (This is saying that every element of
a has a unique successor).
The proof is fairly trivial: Let A'={x|x>a. If A' is empty, then a is
the greatest element. If a' is not empty, its (unique) least element is
the desired a+.
--
----------------------------------------------------------
Larry McKnight...........
Benjamin J. Tilly
wee...@sagi.wistar.upenn.edu (Matthew P Wiener) writes:
> In article <39pjfd$g...@dartvax.dartmouth.edu>, Benjamin.J.Tilly@dartmouth (Benjamin J. Tilly) writes:
> >> Formalism is a trivially correct philosophy that didn't change try to
> >> anything, just to say it was right. [...]
>
> >Is formalism a trivially correct philosophy? I thought so at one point,
> >however I have now been convinced that in a very real sense it does not
> >correspond to what we really think of math as. [...]
>
> If it helps clarify things, I am an unabashed ultrafanatic Platonist.
> Ah buhLEEV in supper commupact cadrinals.
>
HERETIC!!! :-)
> So what I mean when I say formalism is a (as in _a_) trivially correct
> philosophy, is that it defines things to suit itself and then happily
> shuts the door.
In that case I agree with you. However I would put the wedge in the
door by saying that it is an illusion to think that it agrees with the
way that we actually think about math. Even the way that all but the
most extreme formalists think about math.
Ben Tilly
Steve Linton
>"Karl" == Karl Hahn <ha...@newshost.lds.loral.com> shouts:
>Why isn't "less-than" a well-ordering for the real numbers? Is it
>because of things like .999... == 1? (But in that case are .999... and
>1 actually two different numbers or two ways of writing the same
>number?).
>Please clue me in.
No. Consider the non-empty set of numbers larger than 0. What is it's
least element?
Tal Kubo
In article <39o30p$7...@netnews.upenn.edu>
>
>>>>Is there some reason why intuitionism et al are singled out for
>>>>gratuitous top-of-the-head commentary?
>
>>>Yes. Its practitioners made strong universal claims at one point.
>
>
>Formalism is a trivially correct philosophy that didn't change try to
"Math is a game of symbols" is a strong universal claim.
>Bourbaki was a much needed but over extended housecleaning more regarding
>style than mathematics itself.
"Mathematics can and should be developed from ZFC" is a strong universal
claim.
> They went too far and have indeed been
>reviled in some corners.
"Reviled"? News to me.
>Category theorists get no respect. When the subject gets nicknamed
>"generalized abstract nonsense", and when a very significant subset
>of it (topos theory--created by Grothendieck even!) gets nicknamed
>"generalized abstract category theory", you know its supporters have
>a long uphill battle.
This is an inaccurate summary of popular opinion on category theory.
I could just as glibly point out that its apostles make statements like
"category theory is the language of the universe"... and instead of being
called crackpots, are taken seriously.
>
>CS? Topology? News to me.
What planet have you been on? The death of proof, experimental
mathematics, probabilistic proof, etc. Intuitionism is small
potatoes compared to this.
Tal Kubo
>
> Meanwhile his interlocutors have been going through all sorts of
> nitpicking to dismiss the issue about "no definable well orderings".
> The point still stands, as far as this foundationally-challenged
> reader can tell.
>
>Do you mean that you believe it to be a theorem of ZF that there is no
I believe that there is no definable well ordering of the reals which can
be proved to be a well-ordering within ZFC. This was a theorem the last I
heard, and I believe that it's what Ron was alluding to. I believe that
nobody can give anything even close to a "construction" or "definition" of
a well-ordering without invoking additional axioms like V=L. I believe
that none of these axioms are in any danger of being added to the standard
repertoire anytime soon. I believe that no matter how many extra axioms
one adds to ZFC, any "definition" of a well-ordering using these axioms is
all but worthless because it cannot settle the most rudimentary questions
such as whether or not 5 precedes 7 in the ordering. I believe that all
this bears out Ron's original point, even though he wasn't really talking
about set-theoretic arcana.
>[...]
> Huh? Since when are any of these [math tools used in QFT]
> less constructive than, say, an infinite series for Pi?
>
>These are familiar figures in the idealization that is classical
>mathematics, which Ron was rejecting as less useful than finitistic
>mathematics.
His claim was "less useful", not "useless". I was just pointing
out that Lie groups, Hilbert space etc used in QFT, are equally parts of
finitistic math, so they're unsuitable for making such comparisons.
>Now, if you or Ron want to say that Cantor's theory of ordinal numbers
>will never find application in physics, I won't argue. Who knows?
>For Ron this may be a conclusive argument--- "Useless for physics?
>Throw it in the trash!" Permit some of us mathematicians (or
>ex-mathematicians) to take a wider viewpoint.
I think the issue was not Ludditism, but that some things, like
well-orderings of the reals, are *in principle* unusable.
>
>In another post, Tal Kubo writes:
>
> So you disagree with Ron on the math, BFD.
>
>I don't know that we *do* disagree on the math. We disagree on the
>philosophy behind the math.
Same difference. My concern was not about the particulars of your
discussion but about the way in which such discussions are carried
out.
Joerg Winkelmann
I don't feel really at home with logic, and hence I am not absolutely sure
but isn't the following a proof that there can not exist a well-ordering
on the reals which can be described by finitely many words:
Proof: Since there are only countably many words, only countably many
real numbers can be described by a finite description.
Let D denote the set of all such numbers.
The complement R-D is non-empty, because the set of real numbers
is uncountable.
Now assume that there exists a well-ordering on R which can be described
in finitely many words. Then R-D admits a minimal element m.
But since the well-ordering has a finite description, we obtain
a finite description for this element m !
This is a contradiction, since D is the set of all numbers admitting
a finite descroiption.
Hence the assumption must be wrong, ie. no well-ordering on the set
of reals can be described with finitely many words.
QED
: Recommended book: _Set Theory and Logic_ by Stoll (available from Dover).
Matthew P Wiener
>> If it helps clarify things, I am an unabashed ultrafanatic Platonist.
>> Ah buhLEEV in supper commupact cadrinals.
>HERETIC!!! :-)
Not yet. Ah tried to upsplane at the Elvis misshun about how a
interreer mahdel of supper commupact cadrinals is coded in "Love
Me Tender" when you play it bakwords, but they fell asleep first.
Matthew P Wiener
>>>So did formalism, Bourbaki, categorists, CS, topology, etc. [...]
>>Formalism is a trivially correct philosophy that didn't change try to
>>anything, just to say it was right. [...]
>"Math is a game of symbols" is a strong universal claim.
I meant that I was revising my original statement, per your questioning,
to point out that I should have including more than "strong universal
claim", but "strong universal claim with a sense of mission about it".
Ludwig is reviled for being annoying, not for strong universal claims.
>>Bourbaki was a much needed but over extended housecleaning more regarding
>>style than mathematics itself.
>"Mathematics can and should be developed from ZFC" is a strong universal
>claim.
Sure this really isn't the essense of Bourbaki.
>> They went too far and have indeed been
>>reviled in some corners.
>"Reviled"? News to me.
See the historical appendix of Miles Reid UNDERGRADUATE ALGEBRAIC TOPOLOGY.
>>Category theorists get no respect. When the subject gets nicknamed
>>"generalized abstract nonsense", and when a very significant subset
>>of it (topos theory--created by Grothendieck even!) gets nicknamed
>>"generalized abstract category theory", you know its supporters have
>>a long uphill battle.
>This is an inaccurate summary of popular opinion on category theory.
Today maybe. Ten years ago, it was a career killer.
>I could just as glibly point out that its apostles make statements like
>"category theory is the language of the universe"... and instead of being
>called crackpots, are taken seriously.
Because they're showing that this view is good for you.
>>CS? Topology? News to me.
>What planet have you been on?
Trantor?
> The death of proof, experimental
>mathematics, probabilistic proof, etc. Intuitionism is small
>potatoes compared to this.
Come on. "The death of proof" was all SciAm hype. Experimental mathematics
and probabilistic proof are not universal claims about mathematics, but calls
for new social acceptance about research that is independently interesting
without fitting in to the current proof paradigm. Ie, what was often good
enough for Euler, Riemann, Poincare, and is often good enough for Witten,
should be more acceptable when done by ordinary mortals.
Benjamin J. Tilly
ric...@cs.niu.edu (Neil Rickert) writes:
> In <HOLMES.94...@catseye.idbsu.edu> hol...@diamond.idbsu.edu (Randall Holmes) writes:
> >In article <39gsdo$b...@mp.cs.niu.edu> ric...@cs.niu.edu (Neil Rickert) writes:
> > In <39gnhb$d...@scunix2.harvard.edu> rma...@husc9.Harvard.EDU (Ron Maimon) writes:
[...]
> >But I would like to know what Rickert thinks mathematics is about, if
> >its subject matter is not (part of) reality. (which it is; Rickert is
> >confused -- I hasten to add "but not in any way unique to himself"!).
>
> The subject matter of mathematics is the study of the processes for
> precisely determining the consequences of precise assumptions. The
> real numbers are not the subject matter of mathematics. We invent
> imaginary real numbers (and imaginary imaginary numbers) to assist us
> in analyzing equations, inequalities, etc.
>
Oh? Earlier this fall in the geometry seminar we realized that a number
of geometers here, including some who had written papers on something
called orbifolds (the idea is that it is locally R^n mod a finite
group), had never really gone through a technical definition. On top of
that the definition given on one of the classic papers on the topic had
flaws in it.
Yet nobody there had any problem in actually working with orbifolds
despite the lack of technical details.
In addition in math we frequently get periods where people have to do
work and think about the construction of new sets of definitions. In
that period the work is not so much determining what follows from
definitions as it is figuring out what definitions let us do what and
then arguing about which definitions are best. This process is most
definitely math...
[...]
> > The axiom systems were
> >formulated to express clearly an understanding of the reals which
> >already existed (in a somewhat confused form). This understanding
> >can't be explained in terms of axiom systems.
>
> Mathematicians did things in the past that would not be acceptable as
> mathematics today. Are we arguing about today's meaning of
> "mathematics", or an older meaning?
>
In an unrelated thread on irrationals (which is not in sci.physics but
is in the other groups) I was talking at some length about irrationals
which ZFC cannot prove are irrationals. Despite the fact that the
concept is NOT one that can be formalized in standard set theory (by
which I mean ZFC) it was one which turned out to be meaningful and in
the end I provided an explicit construction of something which in any
reasonable way you look at it is such a number. Read that thread and
then you tell me whether or not the way that we understand such things
as the number system really follow from the axioms.
Since that will take a while, let me provide you with a simpler
example. If ZFC is consistent then Goedel proved that the Goedel
statement (which is a very specific statement) for ZFC is unprovable.
Therefore it is clear that if we write a program to do a brute force
search through all of the possible proofs and disproofs from the axioms
of ZFC of this statement then it will never halt. This statement makes
perfect sense in mathematics. But it cannot be proven in ZFC.
HOWEVER I can prove that there are models of ZFC in which this program
DOES halt. But we know that those models are ones which do not really
correspond with the actual number system that we are interested in
math. But that knowledge does not change the fact that the axiom system
that we use does not rule these things out.
And it is not just ZFC, thanks to Goedel's help I can do the same thing
with any "interesting" axiom system that you care to name for me.
[...]
> >I would like an explanation of this doctrine of relative existence in
> >rigorous philosophical terms.
>
> Discussion only makes sense when terms have meaning. Meaning depends
> on a frame of reference. Humans are prone to quickly switch from one
> frame of reference to another, depending on context to alert those
> with whom they are conversing. Existence is not unlike other words,
> in having its meaning dependent on the frame of reference. It is
> quite common for people to declare that unicorns exist, and at
> another time declare that they do not exist. We do not see this as
> contradictory, because we understand that there has been a change in
> the frame of reference, from mythology to reality.
>
> For mathematicians, in this current era, the frame of reference for
> mathematical discussions is determined by the system of axioms. Some
> of these axioms may be implicit, although traditional mathematicians
> use a different implicit frame from intuitionists. It is true, as
> you suggest, that historically mathematicians were more informal
> in specifying their frame of reference. But historically, mathematics
> was more closely tied to physics, and that tie made physical intuition
> available as part of the implied frame of reference.
>
Please try to reconcile this claim with my example of the program that
I mentioned. There is no explicit axiom system that you can describe
which can get around that sort of behavior that we do not want, and
claiming that it is implicit does not help since if we are using any
axiom system, implicitly or explicitly, then the same problem does
arise. (Unless you want an axiom system that gives you the worse
problem of proving contradictions, but that is kind of boring.)
[...]
> >It would also be nice for Rickert to give an explanation of what an
> >axiom system is along the lines he suggests here. An axiom system is
> >a mathematical object itself, if it is scrutinized closely enough; so
> >by Rickert's criteria cannot exist, and this would cast serious doubt
> >on the ability of an axiom system to bestow the benison of relative
> >existence on mathematical objects.
>
> If an axiom system is scrutinized closely enough, it is evident that
> it is not a mathematical object. Axiom systems very precisely define
> what is permissible as a valid operation under that axiom system.
> But most axiom systems themselves are written partly in ordinary
> language, and use terminology that has a well understood meaning but
> has no precise definition.
What the terms mean does not matter. It is the relations. And most of
the axiom systems in use in math today (the axioms for a group, ring,
field, set, category theory, for the real numbers, and so on) have
precisely defined relations which does allow them to be formalized
perfectly well. Once formalized they are amenable to mathematical
analysis. Which leads to the pathological behavior that I mentioned
above.
It is true that in doing mathematics we operate at a meta-mathematical
level, but the rules that we use there are themselves amenable to
mathematical analysis which returns us to the previous problem...
Ben Tilly
Neil Rickert
>In article <39rcr9$g...@mp.cs.niu.edu>
>ric...@cs.niu.edu (Neil Rickert) writes:
>> The subject matter of mathematics is the study of the processes for
>> precisely determining the consequences of precise assumptions. The
>> real numbers are not the subject matter of mathematics. We invent
>> imaginary real numbers (and imaginary imaginary numbers) to assist us
>> in analyzing equations, inequalities, etc.
>Oh? Earlier this fall in the geometry seminar we realized that a number
>of geometers here, including some who had written papers on something
>called orbifolds (the idea is that it is locally R^n mod a finite
>group), had never really gone through a technical definition. On top of
>that the definition given on one of the classic papers on the topic had
>flaws in it.
I have no problem with that. A great deal of mathematics is
initially done with informal assumptions (informal and incompletely
specified axioms, if you like) which are never formally stated. The
formal axiomatization comes rather late in the mathematical
development of an area. To say that assumptions are not formally
specified is not necessarily to say that the assumptions are
imprecise.
I'm afraid that the above comments, and most of the rest of your
article completely miss what I was discussing. I am by no means a
formalist. The discussion arose from comments on intuitionism, which
is terribly fussy about existence, and then wandered into Platonism,
which insists on a Platonic existence of mathematical objects such as
real numbers, strongly innaccessible cardinals, etc. I disagree with
both of those views. In my view the real numbers only exist in the
mind of the mathematician for the brief duration that he is using
them.
As far as I am concerned, mathematics can perfectly well be done on
real numbers without insisting that the real numbers have to exist.
I would rather say that the objects of mathematics don't exist at
all, and that the generality of mathematics is due it its use of
non-existent objects. If mathematics were about existent objects,
then mathematics would only apply to those objects. If mathematics
is not about any existing objects at all, but is about the
implications of relationships (such as specified by axiom systems),
then mathematics can apply to every application area where the right
relationships occur.
As far as I can tell, many of the arguments about existence are due
to the views of some epistemologists, who claim that there cannot be
mathematical knowledge unless real numbers, well orderings of the
reals, etc, actually exist. In my opinion, they have the wrong idea
as to what constitutes knowledge.
>In addition in math we frequently get periods where people have to do
>work and think about the construction of new sets of definitions. In
>that period the work is not so much determining what follows from
>definitions as it is figuring out what definitions let us do what and
>then arguing about which definitions are best. This process is most
>definitely math...
You have just summarized my objection to formalism. As I see it, the
axioms are closer to being the finished product rather than the
starting point. I am troubled that our pedagogy has greatly suffered
by an excessive insistence on axiomatic development throughout much
of the curriculum. I fear that we have made mathematics look silly
to many students, and that as a result many students study far less
math than they could and should.
>> For mathematicians, in this current era, the frame of reference for
>> mathematical discussions is determined by the system of axioms. Some
>> of these axioms may be implicit, although traditional mathematicians
>> use a different implicit frame from intuitionists. It is true, as
>> you suggest, that historically mathematicians were more informal
>> in specifying their frame of reference. But historically, mathematics
>> was more closely tied to physics, and that tie made physical intuition
>> available as part of the implied frame of reference.
>Please try to reconcile this claim with my example of the program that
>I mentioned. There is no explicit axiom system that you can describe
>which can get around that sort of behavior that we do not want, and
>claiming that it is implicit does not help since if we are using any
>axiom system, implicitly or explicitly, then the same problem does
>arise. (Unless you want an axiom system that gives you the worse
>problem of proving contradictions, but that is kind of boring.)
I am quite happy to accept informal axiom systems. In fact, I
explicitly said in that paragraph that some of the axioms may be
implicit.
Please keep in mind that the discussion was not about doing
mathematics, but about philosophical views on the *existence* of
mathematical objects. As mentioned above, I see no difficulty with
doing mathematics on non-existent objects. The only condition we
need is that the objects could potentially exist. That is, we don't
want to waste our efforts proving something that could logically only
be about members of the empty set. I contend that when
mathematicians use the word 'exist' it does not have the same meaning
as that intended by philosophers, and is often referring to no more
than the potential existence just mentioned.
>What the terms mean does not matter. It is the relations. And most of
>the axiom systems in use in math today (the axioms for a group, ring,
>field, set, category theory, for the real numbers, and so on) have
>precisely defined relations which does allow them to be formalized
>perfectly well.
Then I am not sure why we are debating. You are largely agreeing
with my views. Namely, the mathematical objects don't have to exist,
because it is the relations rather than the objects that matter.
Tal Kubo
>>can be proved to be a well-ordering within ZFC. This was a theorem
>>the last I heard, and I believe that it's what Ron was alluding to.
>
>models of ZFC where it holds and models where it fails.
Well yes, but in this context insisting on anything other than
a psychological distinction is... schizophrenic. If theoremhood =
ZFC provability, why should well-orderings defined through extra axioms
like V=L count as evidence against "no definable well-orderings" any
more than independence results weigh in its favor?
Tal Kubo
>to point out that I should have including more than "strong universal
>claim", but "strong universal claim with a sense of mission about it".
No matter how you gerrymander it, I don't see how it singles out
intuitionism, finitism and the like for ridicule.
>
>Ludwig is reviled for being annoying, not for strong universal claims.
>
More of this fixation with crackpots. I repeat myself.
>>>Bourbaki was a much needed but over extended housecleaning more regarding
>>>style than mathematics itself.
>
>>"Mathematics can and should be developed from ZFC" is a strong universal
>>claim.
>
>Sure this really isn't the essense of Bourbaki.
Yes, I should have said "(set-based) structures".
>
>>> They went too far and have indeed been
>>>reviled in some corners.
>
>>"Reviled"? News to me.
>
>See the historical appendix of Miles Reid UNDERGRADUATE ALGEBRAIC TOPOLOGY.
I read it years ago and don't remember any Bourbakistas being reviled.
The worst was a reference to the Grothendieck cult as "intellectual
terrorism".
>>>Category theorists get no respect. When the subject gets nicknamed
>>>"generalized abstract nonsense", and when a very significant subset
>>>of it (topos theory--created by Grothendieck even!) gets nicknamed
>>>"generalized abstract category theory", you know its supporters have
>>>a long uphill battle.
>
>>This is an inaccurate summary of popular opinion on category theory.
>
>Today maybe. Ten years ago, it was a career killer.
This is fashion (or if you prefer: discrimination by field of research).
Finitism et al feel the brunt of this as well, but it wasn't the
point being raised.
>>I could just as glibly point out that its apostles make statements like
>>"category theory is the language of the universe"... and instead of being
>>called crackpots, are taken seriously.
>
>Because they're showing that this view is good for you.
Nothing succeeds like success.
>
>>>CS? Topology? News to me.
>
>>What planet have you been on?
>
>Trantor?
Greetings from Terra. We come in peace.
>
>> The death of proof, experimental
>>mathematics, probabilistic proof, etc. Intuitionism is small
>>potatoes compared to this.
>
>Come on. "The death of proof" was all SciAm hype.
Except that it's also proclaimed by some actual mathematicians.
> Experimental mathematics
>and probabilistic proof are not universal claims about mathematics, but calls
>for new social acceptance about research that is independently interesting
>without fitting in to the current proof paradigm.
Acceptance of which would make philosophical differences with intuitionism
look like peanuts (while moving in that direction anyway).
Matthew P Wiener
>I believe that there is no definable well ordering of the reals which
>can be proved to be a well-ordering within ZFC. This was a theorem
>the last I heard, and I believe that it's what Ron was alluding to.
A theorem? I think you meant it's an independence result, as there are
models of ZFC where it holds and models where it fails.
Ron Maimon
|>
|> Proof: Since there are only countably many words, only countably many
|> real numbers can be described by a finite description.
theorem: there is no well ordering on the integers
proof: since there are only finitely many words, only finitely many integers
can be ordered by such a description, and there are an infinite number of
integers.
What's wrong with this? Only that in the way we define the integers, we say
that given any integer we can construct the next one. So that any definition
which can be made in such a way that when you know it on the set {1,2...,n}
you know it on {1,2,....,n,n+1} is a good definition too, and some of these
descriptions can be described in finitely many words, and reduce to true
statements when you look at small sets, like {1,2,3}.
The reals are also defined in terms of a construction. We are given a real
number when we are given an approximation to it in terms of finite fractions.
For instance, we can say that a real number is a sequence of numbers between
0 and 9, one for each integer (or, more precisely, some sort of rule by
which we can calculate the digits of this real number as far as we please)
This real number is the number .digit1 digit2 digit3 digit4 etc
given two such rules, we can find the rule for the sum- it's easy, if you
want the 40th decimal place in the sum, calculate the 400th decimal place
in each real and add the two fractions you get. Then look at the 40th
decimal place of this sum.
Given two such rules, we can find the rule for the product- it's also easy,
just push out enough digits of the two real numbers, and you will get
enough digits of the product. In order to complete this proof that it
makes sense to talk about multiplication, I need to tell you how much
is "enough", but it's easy, so everything works out.
then we can ask a question- is it possible, when given two real numbers
(two rules about digits) to say which one is "smaller" in such a way that
given any collection of real numbers ( a collection of rules about digits)
one can pick out the smallest (one can say which rule is "smallest") in
a consistent way?
The answer is _no_
there is a theorem, however, that uses the axiom of choice, that tells
you that although you can't compare sequences of rational numbers in such
a way that you can say there is always a smallest element in every
collection of such sequences, there "exists" such a method of comparison,
just we are too small to ever see it.
Mathematicians get off on this. I don't. If I am too small to see god
then god doesn't exist
--
Ron Maimon
! You're a star bellied sneetch, you suck like a leech
Jello ! you want everyone to act like you
Biafra ! kiss ass while you bitch so you can get rich
! but your boss gets richer off you
Timothy Y. Chow
The pendulum is indeed swinging back in the direction of favoring category
theory, but IMO this is because the early "strong universal claims" have
been tempered somewhat.
The average mathematician typically has respect only for things that have
an impact on things that he is already interested in. If someone else makes
grand claims, the tendency is to secretly sneer and say, "It can't be that
great if it doesn't have anything to do with *my* work!"
Intuitionism may eventually prove to have a stunning impact on important
areas of classical math. Then (but only then) it will get respect.
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
Laura Helen
Someone told me that the set of well-orderings of a countable set is an
uncountable set which can be well-ordered. Is this well-ordering
specifiable if so what is it?
Laura
Pierre Asselin
>[...]
Geometry goes a long way, and it started out as an applied science.
Euclid's compilation, the foremost example of an axiomatic theory from
ancient times to this day, proved to be unsatisfactory from a formal
standpoint because of hidden assumptions etc. Not that it mattered for
Euclid's purpose: he was leading the reader from self-evident truths
to nontrivial conclusions.
More to the point: Eudoxus' theory of proportion was predicated on the
independent existence of geometric quantities. In modern language,
one would say that the real numbers had to be given a priori; only
then could incommensurable ratios be handled via approximating
rationals. Even late in the 19th century, this represented the only
approach to analysis. Whatever its shortcomings, the construction of
the real line from arbitrary sets of integers represents genuine
progress. Anyone who rejects it must face the task of rebuilding the
foundations of geometry. For a more complete discussion and many
references see Fraenkel, Bar-Hillel and Levy, "Foundations of Set
Theory" pp.211ff (thank you, Mikhail).
With my physicist's formation, the notion that a mathematical object
abstracted from the real world exists only by reference a formal system
seems too anthropocentric to be credible.
--
--Pierre Asselin, Santa Barbara, California
p...@verano.sba.ca.us
l...@rain.org
james dolan
>I think the issue was not Ludditism, but that some things, like
>well-orderings of the reals, are *in principle* unusable.
it seems obvious to me that ron maimon is in no position at all to
validly conclude that well-orderings of the reals are in principle
unusable. maimon is a physicist, and physicists are in the position
of viewing the physical world as an oracle revealing new information
over time. maimon has not the slightest clue as to whether this
oracle will someday say stuff that leads us to intelligently guess
that it is revealing some kind of knowledge about a particular
well-ordering of the reals. (i suppose you could try to prove that no
oracle that reveals only a finite amount of information over a finite
time can possibly say anything non-trivial about a particular
well-ordering of the reals, but clearly maimon has no such proof, and
anyway maimon is silly to believe that there's any solid proof that
the oracle's rate of information delivery is and always will be really
finite.)
notice i'm not saying that the idea of the physical-world oracle
revealing knowledge about a particular well-ordering of the reals has
non-zero aesthetic attractiveness or gut-level plausibility. but the
idea of the physical-world oracle revealing knowledge about _some_
aspect of mathematics that's often written off by some constructivists
as "information unusable in principle" is a much broader and more
plausible idea, requiring a significant degree of closed-mindedness to
shut out completely. (on the evidence, i'm sure maimon is up to the
task.)
the funny thing about this is that i (a mathematician with only a very
limited understanding and appreciation of various sorts of
"constructivist" or "finitist" philosophies of mathematics) have a
strong feeling that the reasoning i'm using here is inspired by things
i have learned from constructivists about peculiar aspects of trying
to reason about oracles that reveal their knowledge only over time,
and yet i gather that some constructivists here don't agree with me.
john baez
>[...] physicists are in the position
>of viewing the physical world as an oracle revealing new information
>over time. maimon has not the slightest clue as to whether this
>oracle will someday say stuff that leads us to intelligently guess
>that it is revealing some kind of knowledge about a particular
>well-ordering of the reals.
To change the subject a bit, as a mathematical physicist I think of the
physical world as a kind of oracle that reveals stuff far more potent
and mysterious than a well-ordering of the reals. Namely, it reveals
*interesting mathematical objects* to study. This might seem circular
if by "interesting" I only meant "interesting for physics," but I don't.
For example, Mrowka's new proof of the Thom conjecture for CP^2 (more on
which soon) uses mathematics discovered in physics. (Here it's a rather
odd case, since it uses magnetic monopoles, which may not even exist,
physically! But still we would not have been so quick to think about
them as mathematical objects had there not been magnets, charged
objects, etc. around.)
james dolan
>> Formalism is a trivially correct philosophy that didn't change try to
>> anything, just to say it was right. The Hilbert program was a glorious
>> idea, shot down by Goedel, and formalists pretty much retired--in good
>> form--from trying to run the mathematical universe at that point.
>[...]
>
>Is formalism a trivially correct philosophy? I thought so at one point,
>however I have now been convinced that in a very real sense it does not
>correspond to what we really think of math as. To see my point see some
>of my posts in the "Proof that a number is irrational" thread. In no
>sense that can described from the formalist view that I can think of
>does it make sense to talk about an irrational which cannot be shown to
>be irrational in ZFC. However it does make sense in a very real way to
>talk about it...
you are committing the same kind of violence against the philosophy of
formalism as people like michael clive price commit against bohr's
philosophy of quantum mechanics when they caricature it as "the
copenhagen interpretation". formalism says that "mathematics is a
game"; nowhere does it say that "mathematics is _just_ a game". only
"pet formalists" serving as willing straw men are stupid enough to say
that "mathematics is _just_ a game".
similarly, bohr's philosophy of quantum mechanics was basically that
there were a lot of questions to which bohr didn't know the answer,
including a lot of questions about whether certain other questions
even _have_ answers. in the caricatured version of bohr's philosophy
known as "the copenhagen interpretation", questions about which bohr
professed (an admittedly rather sophisticated form of) ignorance are
taken as forbidden questions about which you're not allowed to think.
(of course the situation is confusing because there are also people
who use the name "copenhagen interpretation" to describe bohr's real
philosophy rather than the caricatured version.)
james dolan
>In article <39sqrt$p...@decaxp.harvard.edu>,
>Tal Kubo <ku...@math.harvard.edu> wrote:
>>>Category theorists get no respect.
>>
>>This is an inaccurate summary of popular opinion on category theory.
>
>The pendulum is indeed swinging back in the direction of favoring category
>theory, but IMO this is because the early "strong universal claims" have
>been tempered somewhat.
i'm only a category theorist, but i get the impression that the
pendulum swings back and forth on category theory so often that it's
hard to tell which way it's leaning at any particular time unless
you're one of those people who really keep their ear to the ground.
in fact what with the relativity of simultaneity, category theory is
always unfashionable somewhere.
>The average mathematician typically has respect only for things that have
>an impact on things that he is already interested in. If someone else makes
>grand claims, the tendency is to secretly sneer and say, "It can't be that
>great if it doesn't have anything to do with *my* work!"
>
>Intuitionism may eventually prove to have a stunning impact on important
>areas of classical math. Then (but only then) it will get respect.
well, from what i hear it already _did_ have a fairly stunning impact
(resulting in "topos theory") on category theory, at least. didn't it
also have an impact on classical math in general by opening people's
eyes to the usefulness of proving "constructive" versions of theorems,
even when you're working in a completely classical context?
john baez
>I believe that there is no definable well ordering of the reals which can
>be proved to be a well-ordering within ZFC. This was a theorem the last I
>heard, and I believe that it's what Ron was alluding to. I believe that
>nobody can give anything even close to a "construction" or "definition" of
>a well-ordering without invoking additional axioms like V=L. I believe
>that none of these axioms are in any danger of being added to the standard
>repertoire anytime soon. I believe that no matter how many extra axioms
>one adds to ZFC, any "definition" of a well-ordering using these axioms is
>all but worthless because it cannot settle the most rudimentary questions
>such as whether or not 5 precedes 7 in the ordering. I believe that all
>this bears out Ron's original point, even though he wasn't really talking
>about set-theoretic arcana.
Well, I too am foundationally impaired, but here's a naive comment.
Given a well-ordering in which 7 precedes 5, it's easy to construct one
in which 5 precedes 7 --- just switch 'em. So the heavy-duty axioms
certainly imply there is a well-ordering in which 5 precedes 7.
Anything else you want to know about it? :-)
I agree completely that there seems to be *some* sense in which ZFC plus
fancy axioms doesn't give you an "explicit" well-ordering of the reals,
but I am unable to make this precise. Note that most real numbers are
not computable anyway, so doing anything "explicitly" with the reals is
a bit of a challenge unless there is some kind of continuity or
something to deal with the silent majority of uncomputable reals. E.g.
we feel the usual ordering of the reals is "explicit" but not any
well-ordering. Here's a question: can one or can't one "explicitly"
order the computable reals? I might be willing to settle for that, and
just put all the uncomputable ones AFTER the computable ones in my
well-ordering! Procrastination solves many of life's problems.... :-)
There are countably many computable reals, each "named" by some
algorithm --- but I fear one might have trouble telling when two
algorithms name the same computable real, hence trouble writing a
program that tells you, for any 2 computable reals, which comes first in
the well-ordering.
Are there any experts in logic out there who could tell me some
definitions and theorems that might clarify my notions on this subject!
Herman Rubin
Laura Helen <laura...@delphi.com> wrote:
This statement is only partially correct. It is not the well-orderings
which can be well-ordered, but the order types of the well-orderings
which can be; the difference is that the order types ARE automatically
well-ordered, but that the equivalence classes themselves are not.
For example, consider the well-orderings of the integers which are
of type \omega_0; these are the enumerations of the integers. These
all have ONE order type. But well-ordering these would be equivalent
to well-ordering the reals.
The correct statement is a special case of a more general, and useful
theorem, due to Hartogs more than 80 years ago. The theorem is
Let X be any set. Then there is a well-ordered set Y such
that Y cannot be put in 1-1 correspondence with any subset
of X. Also, Y can be put in 1-1 correspondence with a
subset of the power set of the product of X with itself.
Proof: Any relation on a subset of X can be considered a subset
of the product of X with itself. So any order type is
a subset of this product, or an element of the power set
of the product. So the set of all order types of relations,
is a subset, and the well-ordered order types is a subset of
that subset. If we call this Y, the last sentence is proved.
Now all order types of well-ordered sets are naturally ordered
by isomorphism into an initial segment, and this is a well-
ordering. So Y is well-ordered. But if Y can be put into a
one-one correspondence with a subset of X, the order type of
Y would be an element of Y, as well as all smaller order types.
This is impossible.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hru...@stat.purdue.edu (Internet, bitnet)
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
Karl Hahn
> Karl Hahn (ha...@newshost.lds.loral.com) wrote:
[deletia]
Interesting. If your definition of "description" of a well ordering
is that you require a rule or algorithm that identifies the least
element of any subset you can describe, then your proof certainly
holds. And this is not, in my mind, an unreasonable definition. In
the case of the set R-D, you have a set which is describable, but
none of its elements are. Herein lies a connection back to the axiom
of choice, since if R-D were a member of a collection of sets, it
would be impossible to _construct_ a representative set of that
collection. But whether or not you can say that such a representative
set does not exist because of its nonconstructability -- well that is
a matter of philosophical debate. If you say that it doesn't, you
are denying the axiom of choice, and hence denying the certainty that
a well ordering exists on R.
Paul Budnik
: Here's a question: can one or can't one "explicitly"
: order the computable reals? I might be willing to settle for that, and
: just put all the uncomputable ones AFTER the computable ones in my
: well-ordering!
Its pretty trivial to order the computable reals. Just use any Goedel
numbering of TMs that compute them.
Paul Budnik
Neil Rickert
>Neil Rickert (ric...@cs.niu.edu) wrote:
>>[...]
>>In <lpa.784267699@coyote> l...@coyote.rain.org (Pierre Asselin) writes:
>>>What about geometry?
>>I don't understand your point. Geometry is the classic example of
>>a subject based on an axiom system.
>Geometry goes a long way, and it started out as an applied science.
>Euclid's compilation, the foremost example of an axiomatic theory from
>ancient times to this day, proved to be unsatisfactory from a formal
>standpoint because of hidden assumptions etc. Not that it mattered for
>Euclid's purpose: he was leading the reader from self-evident truths
>to nontrivial conclusions.
>More to the point: Eudoxus' theory of proportion was predicated on the
>independent existence of geometric quantities.
I have not closely studied Eudoxus. Perhaps you are correct, but
that does not mean Eudoxus was correct. But is it possible that the
geometric quantities did not have to exist independently? That is,
perhaps they only had to exist after you had constructed them.
Geometry was a highly constructive theory.
> In modern language,
>one would say that the real numbers had to be given a priori; only
>then could incommensurable ratios be handled via approximating
>rationals.
We should not impose modern language on the Greek geometers. They
used geometry precisely because they had trouble with the questions
of the existence of real numbers.
> Even late in the 19th century, this represented the only
>rationals. Even late in the 19th century, this represented the only
>approach to analysis. Whatever its shortcomings, the construction of
>the real line from arbitrary sets of integers represents genuine
>progress. Anyone who rejects it must face the task of rebuilding the
>foundations of geometry.
I am not denying the value of the construction of mathematics from
ZFC or PA. But that still does not give the real numbers an
independent existence. When the last mathematician dies, there will
be no real numbers.
As for the foundations of geometry, we can only say that arithmetic
provides such a foundation by extreme abuse of language. It provides
a formal foundation, of the form expected by mathematicians. But in
the natural language meaning of "foundation", one first constructs
the foundation, and then erects the building on that foundation.
Most of geometry had already been constructed before the set
theoretic foundation had been thought of. The real foundation for
geometry lies in our intuitive ideas of space and distance. What
mathematicians refer to as a foundation, should more properly be
named a formalization.
>With my physicist's formation, the notion that a mathematical object
>abstracted from the real world exists only by reference a formal system
>seems too anthropocentric to be credible.
With my mathematician's viewpoint, the notion that mathematical
objects have an existence independent of man seems too
anthropocentric to be credible.
Michael Barr
"well, from what i hear it already _did_ have a fairly stunning impact
(resulting in "topos theory") on category theory, at least. didn't it
also have an impact on classical math in general by opening people's
eyes to the usefulness of proving "constructive" versions of theorems,
even when you're working in a completely classical context?"
The really stunning impact was the proof by Grothe, er Deligne, er
well whoever, of the Weil conjectures in number theory. What is
really galling is that a number theorist will typically say, "Well,
one subject that category theory cannot possibly have an effect on
is number theory." Of course that was 30 years ago. What category
theory is having at least some impact on is computer theory and, to
return to where this thread began (with John Baez' Week 40 post), in
theoretical physics.
Even Wiles uses a universal construction (the universal
deformation ring). Would that have seemed like a natural
thing to do if Eilenberg & Mac Lane hadn't sat down 50+ years
ago and discovered category theory?
Michael Barr
Benjamin J. Tilly
wee...@sagi.wistar.upenn.edu (Matthew P Wiener) writes:
> In article <39r65o$h...@dartvax.dartmouth.edu>, Benjamin.J.Tilly@dartmouth (Benjamin J. Tilly) writes:
> >> If it helps clarify things, I am an unabashed ultrafanatic Platonist.
> >> Ah buhLEEV in supper commupact cadrinals.
>
> >HERETIC!!! :-)
>
> Not yet. Ah tried to upsplane at the Elvis misshun about how a
> interreer mahdel of supper commupact cadrinals is coded in "Love
> Me Tender" when you play it bakwords, but they fell asleep first.
The fact that you had to play it REEEAAAALLLLY slowly to fit the entire
thing in may have had something to do with that...
Ben Tilly
Benjamin J. Tilly
jdo...@math.UCR.EDU (james dolan) writes:
> benjamin j. tilly writes:
[...]
> >Is formalism a trivially correct philosophy? I thought so at one point,
> >however I have now been convinced that in a very real sense it does not
> >correspond to what we really think of math as. To see my point see some
> >of my posts in the "Proof that a number is irrational" thread. In no
> >sense that can described from the formalist view that I can think of
> >does it make sense to talk about an irrational which cannot be shown to
> >be irrational in ZFC. However it does make sense in a very real way to
> >talk about it...
>
>
> you are committing the same kind of violence against the philosophy of
> formalism as people like michael clive price commit against bohr's
> philosophy of quantum mechanics when they caricature it as "the
> copenhagen interpretation". formalism says that "mathematics is a
> game"; nowhere does it say that "mathematics is _just_ a game". only
> "pet formalists" serving as willing straw men are stupid enough to say
> that "mathematics is _just_ a game".
>
I am not caricaturing it. What formalism says is that we construct an
axiom system (which we hope is nice and consistent) in which we can
construct formal symbols that we correspond to statements about the
objects that we are interested in, and then we can prove things about
what we are *really* interested in by proving things from the axioms.
This reduces all sorts of nasty questions about what really exists to
(hopefully) more tractable questions about the axioms. That hope had a
major setback delivered by Goedel, but the philosophy is still useful.
The example that I am talking about (read the thread on sci.math or
sci.logic, really, you do not need to know anything to follow it) shows
that it is possible to talk in a way that mathematicians find
meaningful about properties of things like the real numbers that do NOT
just follow from some axiom system. (My comments were directed at ZFC,
no matter what the axiom system, I could have pulled the same trick.)
If you want to complain about caricatures of formalism, then respond to
some of the things that Neil Rickert is saying!
> similarly, bohr's philosophy of quantum mechanics was basically that
> there were a lot of questions to which bohr didn't know the answer,
> including a lot of questions about whether certain other questions
> even _have_ answers. in the caricatured version of bohr's philosophy
> known as "the copenhagen interpretation", questions about which bohr
> professed (an admittedly rather sophisticated form of) ignorance are
> taken as forbidden questions about which you're not allowed to think.
>
Bringing physics back into the thread are we? Well, the reason that I
do not like his philosophy is that it implies that the present approach
to physics cannot say anything meaningful about what causes the
properties of measurement (resulting in fundamental questions about the
nature of conciousness), which puts an unneeded boundary on the topics
that physics can think about that I find distasteful. Which is a large
part of the reason that I have a preference for the Everett
interpretation. :-)
> (of course the situation is confusing because there are also people
> who use the name "copenhagen interpretation" to describe bohr's real
> philosophy rather than the caricatured version.)
Is there any sophisticated philosophy about an important issue that
does not get caricatured? (Both by opponents and, sadly, by
supporters.)
Ben Tilly
Neil Rickert
>If you want to complain about caricatures of formalism, then respond to
>some of the things that Neil Rickert is saying!
Thanks :-( .
What I have been saying cannot possibly have been a caricature of
formalism, for it had nothing to do with formalism.
While I agree with Matthew Wiener's comment that formalism is
trivially correct, most formalists don't look at it from that point
of view. My disagreement with Platonism, which I was discussing, is
no more than a minor difference of opinion. My disagreement with
formalism, as it is practiced, is more serious.
Benjamin J. Tilly
hru...@b.stat.purdue.edu (Herman Rubin) writes:
> In article <Zo52EsQ.l...@delphi.com>,
> Laura Helen <laura...@delphi.com> wrote:
>
> >Someone told me that the set of well-orderings of a countable set is an
> >uncountable set which can be well-ordered. Is this well-ordering
> >specifiable if so what is it?
>
> This statement is only partially correct. It is not the well-orderings
> which can be well-ordered, but the order types of the well-orderings
> which can be; the difference is that the order types ARE automatically
> well-ordered, but that the equivalence classes themselves are not.
>
For those who do not know, a well-ordering of a set is an ordering such
that each subset has a unique smallest element. Thus the ordinary
ordering of the reals, rationals, and integers are not well-orderings,
but the ordinary orderings of the positive integers and any ordering of
a finite set (total ordering, partial orders can leave now:-) is a
well-ordering.
An equivalent of the axiom of choice is that any set can be
well-ordered. This allows us to use "transfinite induction".
> For example, consider the well-orderings of the integers which are
> of type \omega_0; these are the enumerations of the integers. These
> all have ONE order type. But well-ordering these would be equivalent
> to well-ordering the reals.
>
> The correct statement is a special case of a more general, and useful
> theorem, due to Hartogs more than 80 years ago. The theorem is
>
> Let X be any set. Then there is a well-ordered set Y such
> that Y cannot be put in 1-1 correspondence with any subset
> of X. Also, Y can be put in 1-1 correspondence with a
> subset of the power set of the product of X with itself.
>
Let X be the positive integers. Then this would appear to imply the
existence of an uncountable well-ordered set. Without using choice!!!
> Proof: Any relation on a subset of X can be considered a subset
> of the product of X with itself. So any order type is
> a subset of this product, or an element of the power set
> of the product. So the set of all order types of relations,
> is a subset, and the well-ordered order types is a subset of
> that subset. If we call this Y, the last sentence is proved.
>
I have an idea what you mean by "order type". My guess is that two
orderings of X said to be of the same order-type iff there is a
bijection from X to X such that it carries the one ordering to the
other ordering. Is that right?
If so then the demonstration that it is in the power set of XxX seems
to involve the axiom of choice. (How do you decide which example of
each well-ordering to include in Y?) But for me that is not the
interesting part.
> Now all order types of well-ordered sets are naturally ordered
> by isomorphism into an initial segment, and this is a well-
> ordering.
Right. For any two of them just define the isomorphism recursively then
use the well-ordering of each to show that it sends the initial segment
of one into the other. Note that there is (show this by recursion) no
other way to construct this isomorphism.
> So Y is well-ordered. But if Y can be put into a
> one-one correspondence with a subset of X, the order type of
> Y would be an element of Y, as well as all smaller order types.
> This is impossible. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The contradiction took me a bit to see. There are two cases of
interest. One case is where X is finite, say n. Then we note that the
well-orderings of a 0-element subset, 1-element subset,..., n-element
subset are the members of Y, so Y has n+1 elements. The other case is
where X is infinite. Then what we do is note that if we take the
well-ordering for Y, then alter it by taking the first element and
changing it to the last element, then we have a well-ordering on Y that
is strictly larger than the one that we had before, and this is a
well-ordering of a subset of X. Therefore it is an element of Y, and
therefore has order-type at most that of Y. However the uniqueness
property of maps of well-orderings mentioned above shows that this
element cannot be a member of Y since it is too big. Contradiction.
I just thought that some people (like me:-) would like to have some of
those details filled in.
Ben Tilly
Jon Leonard
>> Karl Hahn (ha...@newshost.lds.loral.com) wrote:
>[deletia]
>> : Interesting topic for further reading: It has been shown that if
>> : you accept the Axiom of Choice (which states that from any collection
>> : of nonempty sets you can generate a representative set containing one
>> : element from each of the sets in the collection) then there must exist
>> : a well ordering for every nonempty set. This would, of course, include
>> : the real numbers, although nobody has found a well ordering for them --
>> : and it may be that such a well ordering cannot be described in any
>> : finite description.
>>
>> I don't feel really at home with logic, and hence I am not absolutely sure
>> but isn't the following a proof that there can not exist a well-ordering
>> on the reals which can be described by finitely many words:
>>
>> Proof: Since there are only countably many words, only countably many
>> real numbers can be described by a finite description.
I've always thought that this was the whole point of the Axiom of Choice:
That you *can* do an infinite amount of choosing even though you may not
be able to describe *how* you are going to do it. In other words, the
proof begins by denying AC (and is correct in a world without AC).
Jon
--
------------------------------------------------------------------------
Jon Leonard |
| Rock music doesn't have to be good to be good.
dad...@xs4all.nl |
------------------------------------------------------------------------
Alan Smaill
I have not closely studied Eudoxus. Perhaps you are correct, but
that does not mean Eudoxus was correct. But is it possible that the
geometric quantities did not have to exist independently? That is,
perhaps they only had to exist after you had constructed them.
Geometry was a highly constructive theory.
Every account I have read of the history of this (OK it's not many)
says that the axioms of geometry were taken to be clearly
true statements about the physical world, until non-standard
geometries came on the scene.
I am not denying the value of the construction of mathematics from
ZFC or PA. But that still does not give the real numbers an
independent existence. When the last mathematician dies, there will
be no real numbers.
I have still not worked out what you mean when you say that mathematical
objects exist only within a formal system. Can you say a bit more?
Will there also be no more formal systems when the last mathematician
dies?
Maybe you mean that the only meaning of existence for a mathematician
working in a particular formal system is that of provable existence
in that system. This is contrary to the understanding of platonists,
of intuitionists, and of formalists, as far as I can see. The usual
understanding of incompleteness results, for example, is that the
axioms fail to describe completely the intended structure.
It seems to me quite common that mathematicians give some axiomatisation
which they realise full well is incomplete, and distinguish between the
things they can prove exist in the theory, and the things that may exist
without there being a proof of this.
--
Alan Smaill JANET: sma...@uk.ac.ed.lfcs
LFCS, Dept. of Computer Science UUCP: ..!mcvax!ukc!lfcs!smaill
University of Edinburgh ARPA: sma...@lfcs.ed.ac.uk
Edinburgh EH9 3JZ, UK. Tel: 031-650-2710
Tal Kubo
>
>Well, I too am foundationally impaired, but here's a naive comment.
>Given a well-ordering in which 7 precedes 5, it's easy to construct one
>in which 5 precedes 7 --- just switch 'em. So the heavy-duty axioms
>certainly imply there is a well-ordering in which 5 precedes 7.
>Anything else you want to know about it? :-)
Sure, I'd like the omega'th real number and an order of fries.
The game I had in involves an Orderer *fixing* a well-ordering and an
Interrogator asking questions about it. Obviously if the questions are
submitted in advance the Orderer suddenly has a chance of winning.
>I agree completely that there seems to be *some* sense in which ZFC plus
>fancy axioms doesn't give you an "explicit" well-ordering of the reals,
>but I am unable to make this precise. Note that most real numbers are
>not computable anyway, so doing anything "explicitly" with the reals is
>a bit of a challenge unless there is some kind of continuity or
>something to deal with the silent majority of uncomputable reals. E.g.
>we feel the usual ordering of the reals is "explicit" but not any
>well-ordering.
Notice though that the extra axioms might (must?) let you describe
real numbers that you couldn't before. As an analogy, there are
definable orderings of Q(t) using only rational numbers, but any
way of defining additional orderings, say by growth in a neighborhood of
Pi, must give a way of talking about certain irrational numbers as well.
> Here's a question: can one or can't one "explicitly"
>order the computable reals?
Among other things this would give a philosopher's stone for solving
halting problems, since well-ordering would provide a way of testing
such numbers for equality.
Neil Rickert
>In article <3a0edp$1...@mp.cs.niu.edu> ric...@cs.niu.edu (Neil Rickert) writes:
>Every account I have read of the history of this (OK it's not many)
>says that the axioms of geometry were taken to be clearly
>true statements about the physical world, until non-standard
>geometries came on the scene.
That is probably correct. If the social constructivists are right,
then perhaps the axioms of geometry were indeed true statements about
the physical world, as that world was constructed by that society.
> I am not denying the value of the construction of mathematics from
> ZFC or PA. But that still does not give the real numbers an
> independent existence. When the last mathematician dies, there will
> be no real numbers.
>I have still not worked out what you mean when you say that mathematical
>objects exist only within a formal system. Can you say a bit more?
We need to put all of this in perspective. The discussion originated
with comments about intuitionism. Roughly speaking, the intuitionist
say "ours is the one and only true way of doing mathematics, and
those who disagree are infidels." Randall Holmes then made a comment
that platonism is the one and only true way. Fortunately most
platonists avoid labelling their opponents as infidels. My earlier
posting, to which you are responding, was a disagreement with the
platonist position.
Ben Tilly has misinterpreted my comments to the extent of assuming
that I am a formalist. I am not. If one must choose between
intuitionism, formalism, or platonism, I would prefer the latter.
But why must one choose? In my opinion, these philosophies misdirect
the attention of mathematicians. We can perfectly well manage
without any such philosophy.
I would rather say that the interest of the mathematician is with our
systems of weights and measures (broadly interpreted). But the
mathematical analysis of these practical systems is awkward at best.
We would have to deal with interval arithmetic, with the loss of the
associative rule (due to roundoff error), and with imprecision.
Instead, we idealize. But our main interest is in developing
procedures which can be used with our systems of weights and
measures. We construct the real numbers from axioms, because this
provides us with a model that we can use to show that the set of
procedures we develop is consistent. But we don't actually need the
real numbers to exist, except in a formal sense for the brief
duration when we are ensuring the consistency of our procedures.
>Maybe you mean that the only meaning of existence for a mathematician
>working in a particular formal system is that of provable existence
>in that system.
I would say that the only important meaning of existence is that of
demonstrating the consistency of the mathematician's procedures.
> This is contrary to the understanding of platonists,
>of intuitionists, and of formalists, as far as I can see.
Since I am neither a platonist nor an intuitionist nor a formalist,
this does not particularly concern me.
> The usual
>understanding of incompleteness results, for example, is that the
>axioms fail to describe completely the intended structure.
Here is my understanding. The incompleteness results demonstrate
that, ultimately, we cannot demonstrate the consistency of our
procedures. However, based on long use, we have strong intuitive
feelings that PA, and probably ZFC are consistent. These intuitions
are probably based on the empirical evidence of the correctness of
testable conclusions derived from PA or ZFC. If we can use this to
demonstrate that our usual mathematical procedures are consistent,
provided that PA (or ZFC) is consistent, then we allow our intuition
about PA and ZFC to be carried over into the rest of our mathematics.
Historically, whenever an inconsistency has been found in
mathematician's assumptions, it has been possible to modestly revise
those assumptions in such a way that most mathematics remained valid
under the new assumptions. It seems likely that this will continue
to be the case. If this assessment is correct, then the Goedel
result is not particularly disturbing.
>It seems to me quite common that mathematicians give some axiomatisation
>which they realise full well is incomplete, and distinguish between the
>things they can prove exist in the theory, and the things that may exist
>without there being a proof of this.
Perhaps the following example will illustrate where and why I differ
with the platonists.
The platonist claims that the real numbers have an existence independent
of the mathematician. Given this set of platonic real numbers, one
can ask whether the continuum hypothesis is true for this set. The
platonist argues that this is a genuine, and perhaps interesting
question, even though it cannot be resolved. But in my opinion,
this question is quite devoid of content, and is thus meaningless.
Ron Maimon
Paul Budnik <pa...@mtnmath.mtnmath.com> wrote:
>john baez (ba...@guitar.ucr.edu) wrote:
>
>Its pretty trivial to order the computable reals. Just use any Goedel
>numbering of TMs that compute them.
>
how do you know when two turing machines are computing the same real
number?
Ron Maimon
john baez
>john baez (ba...@guitar.ucr.edu) wrote:
>
>Its pretty trivial to order the computable reals. Just use any Goedel
>numbering of TMs that compute them.
>how do you know when two turing machines are computing the same real
>number?
As I suggested in the post you quote, and as others confirmed, you
can't know that. So the well-ordering of computable reals given by
"x < y iff the Goedel number of the Turing machine with smallest Goedel
number computing x is less than that of y" is not computable, even
though it can be shown to be a well-ordering by ZFC.
Other people have told me by email still other senses in which
well-ordering reals is tough. Luckily, in all the analysis I've ever
done, I have never yet felt the slightest need for an "explicit"
well-ordering of the reals.
john baez
>In article <3a3b83$s...@decaxp.harvard.edu> rma...@scws27.harvard.edu (Ron Maimon) writes:
>>john baez (ba...@guitar.ucr.edu) wrote:
(No I didn't, Budnik did!)
>>Its pretty trivial to order the computable reals. Just use any Goedel
>>numbering of TMs that compute them.
>>how do you know when two turing machines are computing the same real
>>number?
>As I suggested in the post you [DID NOT] quote, and as others confirmed, you