Justifying transfinite induction in ZF
Baudouin Le Charlier
induction as granted (obvious). I would like to read a clear
justification of this principle, based on the axioms of ZF. I am also
interested in a proof of the existence of ordinals in this setting (ou
possibly in a less formal one). Is there a proof of the existence of a
first uncountable ordinal ?
I am also interested in getting a reference to a good (clear and
rigorous) book on this topic.
MoeBlee
This is covered in just about any textbook on set theory.
Personally, the two books I most like to combine in study are Suppes's
'Axiomatic Set Theory' and Enderton's 'Elements Of Set Theory'.
MoeBlee
Jan Burse
Think there is a distinction between:
- Transfinite induction.
And:
- Transfinite recursion.
Transfinite recursion is stronger I believe.
Bye
MoeBlee
> Think there is a distinction between:
> - Transfinite induction.
> And:
> - Transfinite recursion.
>
> Transfinite recursion is stronger I believe.
Right, transfinite induction is provable in Z set theory, but
transfinite recursion requires the axiom schema of replacement from ZF
set theory.
MoeBlee
ju...@diegidio.name
<baudouin.lecharl...@uclouvain.be> wrote:
> In all articles I found on the web, people seems to accept transfinite
> induction as granted (obvious). I would like to read a clear
> justification of this principle, based on the axioms of ZF.
Induction does NOT require any justification. Actually asking for such
justification is a logical mistake. Then you can have axiomatic
systems where induction is put into some axiom or axiom schema, but
that is an a posteriori. Induction simply *cannot* be justified, it is
a rational a priori.
Strawson, in Introduction to Logical Theory, dedicates a last chapter
to "the 'justification' of induction" (I am translating from an
Italian edition actually, so there might be slight differences from
the original). Here is a relevant quote:
<<It is so a contingent and factual matter that sometimes it is
possible to form rational opinions regarding what specifically has
happend or will happen is such or such circumstances (I); it is a non-
contingent and a priori matter that the only way to do so is inductive
(II).>>
-LV
ju...@diegidio.name
Have a look at this one also:
THE EVILS OF INDUCTIVE SKEPTICISM
Donald Cary Williams
From The Ground of Induction, 1947, pp. 15-20.
http://web.maths.unsw.edu.au/~jim/williams.html
-LV
Daryl McCullough
>
>On 4 Aug, 11:27, Baudouin Le Charlier
><baudouin.lecharl...@uclouvain.be> wrote:
>> In all articles I found on the web, people seems to accept transfinite
>> induction as granted (obvious). I would like to read a clear
>> justification of this principle, based on the axioms of ZF.
>
>Induction does NOT require any justification. Actually asking for such
>justification is a logical mistake. Then you can have axiomatic
>systems where induction is put into some axiom or axiom schema, but
>that is an a posteriori. Induction simply *cannot* be justified, it is
>a rational a priori.
Although I don't agree with that, I don't want to argue against
it here because that isn't the meaning of "induction" at issue.
There are two different definitions of the word "induction":
(1) Inductive reasoning, in which one makes generalizations
based on individual instances, and (2) Mathematical induction,
in which a well-founded relation is used to prove a universal
statement. These two notions both involve ways to derive a
universal statement, but are not at all the same. Mathematical
induction has nothing to do with inductive reasoning.
--
Daryl McCullough
Ithaca, NY
MoeBlee
> Induction does NOT require any justification. Actually asking for such
> justification is a logical mistake. Then you can have axiomatic
> systems where induction is put into some axiom or axiom schema, but
> that is an a posteriori. Induction simply *cannot* be justified, it is
> a rational a priori.
As a matter of fact, we do prove the induction schemata in set theory.
You may consider not needing a proof, fine. But still we do happen to
have the axioms to prove it in set theory.
> Strawson, in Introduction to Logical Theory, dedicates a last chapter
> to "the 'justification' of induction" (I am translating from an
> Italian edition actually, so there might be slight differences from
> the original). Here is a relevant quote:
>
> <<It is so a contingent and factual matter that sometimes it is
> possible to form rational opinions regarding what specifically has
> happend or will happen is such or such circumstances (I); it is a non-
> contingent and a priori matter that the only way to do so is inductive
> (II).>>
Not that it matters to the issue of proving inductive schemata in set
theory, but is the above quote about empirical induction or about
mathematical induction?
MoeBlee
MoeBlee
On Aug 4, 11:42 am, ju...@diegidio.name wrote:
> THE EVILS OF INDUCTIVE SKEPTICISM
> Donald Cary Williams
> From The Ground of Induction, 1947, pp. 15-20.http://web.maths.unsw.edu.au/~jim/williams.html
You think that has anything to do with MATHEMATICAL induction?
Do you have ANY idea as to the difference between empirical induction
and mathematical induction?
MoeBlee
Baudouin Le Charlier
> On 4 Aug, 11:27, Baudouin Le Charlier
>
> <baudouin.lecharl...@uclouvain.be> wrote:
> > In all articles I found on the web, people seems to accept transfinite
> > induction as granted (obvious). I would like to read a clear
> > justification of this principle, based on the axioms of ZF.
>
> Induction does NOT require any justification. Actually asking for such
> justification is a logical mistake. Then you can have axiomatic
> systems where induction is put into some axiom or axiom schema, but
> that is an a posteriori. Induction simply *cannot* be justified, it is
> a rational a priori.
>
By transfinite induction, I want to say here : "a proof by transfinite
induction". I agree with you that the principle of induction over the
natural numbers does not need a justification since the justification
would use the very principle anyway. However, I think that transfinite
induction is much less obvious. I find it rather obvious when it is
used for a clearly identified "initial segment" of the class of
ordinals. However I am not sure that the whole class of ordinals is a
well defined concept.
My discussion in the above paragraph assumes that I consider sets as
"real objects" independently of any formalization. Thus the other part
of my question is more specific : how ordinals are they defined in ZF
and how transfinite induction is it justified in ZF ? Because they are
not primitive notions or axioms in ZF and I do not see a priori how to
justify them formally in that system. Notice that my motivation is to
get a better understanding of ordinals and transfinite induction "in
the real world" although I do not particularly believe that ZF (or
ZFC) is the real world of mathematics.
David C. Ullrich
That quote has no relevance whatever, because the meaning
of the word "induction" there is totally different from what
we're talking about.
>-LV
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
Balthasar
<baudouin....@uclouvain.be> wrote:
>
> I agree with you that the principle of induction over the
> natural numbers does not need a justification since the
> justification would use the very principle anyway.
>
Nope. In ZFC we actually can and do PROVE induction. Actually, this
principle in essence just states that there are ONLY 0 and the
successors of 0 in N (omega) (i.e. that N is minimal in this respect).
The proof is rather easy, after N (omega) has been defined (as usual).
B.
--
"For every line of Cantor's list it is true that this line does not
contain the diagonal number. Nevertheless the diagonal number may
be in the infinite list." (WM, sci.logic)
MoeBlee
<baudouin.lecharl...@uclouvain.be> wrote:
> By transfinite induction, I want to say here : "a proof by transfinite
> induction". I agree with you that the principle of induction over the
> natural numbers does not need a justification since the justification
> would use the very principle anyway. However, I think that transfinite
> induction is much less obvious. I find it rather obvious when it is
> used for a clearly identified "initial segment" of the class of
> ordinals. However I am not sure that the whole class of ordinals is a
> well defined concept.
(1) Transfinite induction is provable in Z set theory (don't even need
ZF). (2) The proof is very simple and obvious. (3) We don't need to
assert that there is a set of all ordinals to state and prove
transfinite induction in Z, and, of course, in Z there are no proper
classes.
> My discussion in the above paragraph assumes that I consider sets as
> "real objects" independently of any formalization. Thus the other part
> of my question is more specific : how ordinals are they defined in ZF
> and how transfinite induction is it justified in ZF ?
Ordinals are defined in Z (don't even need ZF) in any number of
equivalent ways. One common definition is:
x is an ordinal <-> (membership is transitive in x and the membership
relation on x is a well ordering of x)
Then transfinite induction is easily proven in Z.
> Because they are
> not primitive notions or axioms in ZF and I do not see a priori how to
> justify them formally in that system.
We prove in Z that there exist ordinals and even that there exists a
limit ordinal. But I keep forgetting whether we need ZF or only Z to
prove Hartogs's theorem that gives us the existence of ordinals that
are not countable.
MoeBlee
ju...@diegidio.name
<baudouin.lecharl...@uclouvain.be> wrote:
> On 4 août, 20:24, ju...@diegidio.name wrote:
> > On 4 Aug, 11:27, Baudouin Le Charlier
> > <baudouin.lecharl...@uclouvain.be> wrote:
> >
> > > In all articles I found on the web, people seems to accept transfinite
> > > induction as granted (obvious). I would like to read a clear
> > > justification of this principle, based on the axioms of ZF.
>
> > Induction does NOT require any justification. Actually asking for such
> > justification is a logical mistake. Then you can have axiomatic
> > systems where induction is put into some axiom or axiom schema, but
> > that is an a posteriori. Induction simply *cannot* be justified, it is
> > a rational a priori.
>
> By transfinite induction, I want to say here : "a proof by transfinite
> induction". I agree with you that the principle of induction over the
> natural numbers does not need a justification since the justification
> would use the very principle anyway. However, I think that transfinite
> induction is much less obvious. I find it rather obvious when it is
> used for a clearly identified "initial segment" of the class of
> ordinals. However I am not sure that the whole class of ordinals is a
> well defined concept.
Even in principle (I am not talking the specifics of mathematical
induction), the leap between "a class" of ordinals and "the whole
class" of ordinals is very little, once you assume the ordering. To
get to transfinite induction you only need assuming the existence of a
limit ordinal (an infinity, or an "omega"), and you've got it. (In
mathematics they have axioms to build many kind of infinities of
different cardinalities. That adds nothing to the concept of infinity,
but adds a lot to the tricks of contemporary mathematics.)
> My discussion in the above paragraph assumes that I consider sets as
> "real objects" independently of any formalization. Thus the other part
> of my question is more specific : how ordinals are they defined in ZF
> and how transfinite induction is it justified in ZF ? Because they are
> not primitive notions or axioms in ZF and I do not see a priori how to
> justify them formally in that system. Notice that my motivation is to
> get a better understanding of ordinals and transfinite induction "in
> the real world" although I do not particularly believe that ZF (or
> ZFC) is the real world of mathematics.
Given that you are trying to understand how it works "in the real
world", I'd suggest you keep in mind that mathematical induction is
quite another beast: the links of mathematics to the underlying
principles and rationale, are in general inscribed into the axioms.
They say they "prove induction": what a ridiculous statement. They of
course just have it in the axioms. The only mathematics they can
conceive nowadays is indeed only tautologies. But this is another and
quite longer story, about our idiotic contemporary and forcingly
globalized society, along with the educational system it is promoting
("diarrea: get a pils!" is my favourite about cluelessness and how "we
save the world").
-LV
MoeBlee
> Even in principle (I am not talking the specifics of mathematical
> induction), the leap between "a class" of ordinals and "the whole
> class" of ordinals is very little, once you assume the ordering. To
> get to transfinite induction you only need assuming the existence of a
> limit ordinal (an infinity, or an "omega"),
WRONG. The proof of transfinite induction does NOT require proving the
existence of a limit ordinal, or of an infinite set, or of the set of
all natural numbers. Indeed, the proof of transfinite induction does
not require the axiom of infinity in any way.
> They say they "prove induction": what a ridiculous statement. They of
> course just have it in the axioms.
Of course we mean prove from the axioms! (And transfinite induction is
not itself an axiom.) Sheesh. That's not ridiculous.
> The only mathematics they can
> conceive nowadays is indeed only tautologies.
Non sequitur you just committed. That wouldn't even be true of strict
consequentialism (since it's not usually the case that we find someone
proposing that what we conceive of and what we axiomatize is the
same). Moreover, lots of mathematicians, realists, structuralists,
fictionalists, intuitionists, and others conceive of mathematics not
only in terms of consequentialism.
MoeBlee
ju...@diegidio.name
> On Aug 6, 12:41 pm, ju...@diegidio.name wrote:
>
> > Even in principle (I am not talking the specifics of mathematical
> > induction), the leap between "a class" of ordinals and "the whole
> > class" of ordinals is very little, once you assume the ordering. To
> > get to transfinite induction you only need assuming the existence of a
> > limit ordinal (an infinity, or an "omega"),
>
> WRONG. The proof of transfinite induction does NOT require proving the
> existence of a limit ordinal, or of an infinite set, or of the set of
> all natural numbers. Indeed, the proof of transfinite induction does
> not require the axiom of infinity in any way.
You guys are wrong on the whole line, always misreading,
misinterpreting and misquoting. Here, as I said, I am not talking the
specifics of mathematical induction.
> > They say they "prove induction": what a ridiculous statement. They of
> > course just have it in the axioms.
>
> Of course we mean prove from the axioms! (And transfinite induction is
> not itself an axiom.) Sheesh. That's not ridiculous.
It is ridiculous because you are actually conflating primitive and
derived notions. Typical of the general cluelessness about principles
and methods, and typical of your always upside logic and math.
> > The only mathematics they can
> > conceive nowadays is indeed only tautologies.
>
> Non sequitur you just committed. That wouldn't even be true of strict
> consequentialism (since it's not usually the case that we find someone
> proposing that what we conceive of and what we axiomatize is the
> same). Moreover, lots of mathematicians, realists, structuralists,
> fictionalists, intuitionists, and others conceive of mathematics not
> only in terms of consequentialism.
You freely and unconsciously float from categoricall notions to the
technicalities and back. Deduction as the only conceivable logical way
of reasoning is what I was talking about: the very blindness.
-LV
> MoeBlee
MoeBlee
> On 6 Aug, 21:20, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > On Aug 6, 12:41 pm, ju...@diegidio.name wrote:
>
> > > Even in principle (I am not talking the specifics of mathematical
> > > induction), the leap between "a class" of ordinals and "the whole
> > > class" of ordinals is very little, once you assume the ordering. To
> > > get to transfinite induction you only need assuming the existence of a
> > > limit ordinal (an infinity, or an "omega"),
>
> > WRONG. The proof of transfinite induction does NOT require proving the
> > existence of a limit ordinal, or of an infinite set, or of the set of
> > all natural numbers. Indeed, the proof of transfinite induction does
> > not require the axiom of infinity in any way.
>
> You guys are wrong on the whole line, always misreading,
> misinterpreting and misquoting. Here, as I said, I am not talking the
> specifics of mathematical induction.
Then what ARE you talking about when you say, "To
get to transfinite induction you only need assuming the existence of a
limit ordinal (an infinity, or an "omega")"?
It is not the case, contrary to what you wrote, that transfinite
induction requires the existence of a limit ordinal, infinite set, or
set of all natural numbers.
> > > They say they "prove induction": what a ridiculous statement. They of
> > > course just have it in the axioms.
>
> > Of course we mean prove from the axioms! (And transfinite induction is
> > not itself an axiom.) Sheesh. That's not ridiculous.
>
> It is ridiculous because you are actually conflating primitive and
> derived notions.
No we're not. We're being FASTIDIOUS to say exactly what is primitive
and what is derived.
> Typical of the general cluelessness about principles
> and methods, and typical of your always upside logic and math.
Right, those who devote a lifetime of study to principles of logic -
from the broadest philosophical sense to the minutest details of
technicalities - are clueless and upside down while you have it
correctly. Note I don't say that a lifetime of study in itself makes
one correct or wise; but rather just to question how PROBABLE is the
scenario you claim.
> > > The only mathematics they can
> > > conceive nowadays is indeed only tautologies.
>
> > Non sequitur you just committed. That wouldn't even be true of strict
> > consequentialism (since it's not usually the case that we find someone
> > proposing that what we conceive of and what we axiomatize is the
> > same). Moreover, lots of mathematicians, realists, structuralists,
> > fictionalists, intuitionists, and others conceive of mathematics not
> > only in terms of consequentialism.
>
> You freely and unconsciously float from categoricall notions to the
> technicalities and back.
Whatever the heck that is supposed to mean.
> Deduction as the only conceivable logical way
> of reasoning is what I was talking about: the very blindness.
Then that is what you should have written. Not MY fault that you did
not correctly express yourself when you said that for such people
"mathematics can only be conceived [in a certain way]", which is
vastly different from saying that such people take deduction as the
only method of mathematical REASONING. Even for those who do take
mathematical REASONING to be deductive, it does not follow that such
people take mathematical CONCEPTION to be limited to reasoning. As
best I can from memory, a line I saw qouted of Poincare: "Logic is
only the means by which we sanction the fruits of intuition."
MoeBlee
Balthasar
wrote:
>>
>> Deduction as the only conceivable logical way of reasoning is what
>> I was talking about: the very blindness. [Crank]
>>
> Then that is what you should have written. Not MY fault that you did
> not correctly express yourself when you said that for such people
> "mathematics can only be conceived [in a certain way]", which is
> vastly different from saying that such people take deduction as the
> only method of mathematical REASONING. Even for those who do take
> mathematical REASONING to be deductive, it does not follow that such
> people take mathematical CONCEPTION to be limited to reasoning. As
> best I can from memory, a line I saw qouted of Poincare: "Logic is
> only the means by which we sanction the fruits of intuition."
>
Right. But after having chosen some axioms we are indeed mainly
interested in the theorems that can be proven in this framework. No?
What Mr. Crank doesn't seem to get: In math a claim that is not itself
an axiom has to be proved (from the axioms and definitions).
ju...@diegidio.name
> On Wed, 6 Aug 2008 13:50:14 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> wrote:
>
> >> Deduction as the only conceivable logical way of reasoning is what
> >> I was talking about: the very blindness. [Crank]
>
> > Then that is what you should have written. Not MY fault that you did
> > not correctly express yourself when you said that for such people
> > "mathematics can only be conceived [in a certain way]", which is
> > vastly different from saying that such people take deduction as the
> > only method of mathematical REASONING. Even for those who do take
> > mathematical REASONING to be deductive, it does not follow that such
> > people take mathematical CONCEPTION to be limited to reasoning. As
> > best I can from memory, a line I saw qouted of Poincare: "Logic is
> > only the means by which we sanction the fruits of intuition."
>
> Right. But after having chosen some axioms we are indeed mainly
> interested in the theorems that can be proven in this framework. No?
Right: in general, a system is of as much interest as there are some
interesting applications, abstract or concrete, that may be.
> What Mr. Crank doesn't seem to get: In math a claim that is not itself
> an axiom has to be proved (from the axioms and definitions).
Your idea of math is quite restricted, and overall inadequate.
Deduction as the queen of logical reasoning is part of the
monodimensionality of our epoch. From there, it is easy to give
preminence to calculation vs. reasoning, technicalities vs.
comprehension. It's in fact a specific educational model.
-LV
MoeBlee
> Your idea of math is quite restricted, and overall inadequate.
> Deduction as the queen of logical reasoning is part of the
> monodimensionality of our epoch. From there, it is easy to give
> preminence to calculation vs. reasoning, technicalities vs.
> comprehension. It's in fact a specific educational model.
After all your boasts, you couldn't prove that there is a set that
maps onto its power set. So now you're reduced to foaming about the
evils of deductive logic itself. Nicely done.
As I explained, not all of mathematical ideation is deductive
reasoning. But ORDINARY mathematical PROOF is deductive. And that does
not disallow that mathematicians can also give probabilisitic
arguments for propositions. Nor disallowed is research that gives only
reasonable (but not conclusive) basis only for accepting certain
principles.
Why don't you get out of your self-contained system of your own
thoughts for a change and instead actually READ some mathematics and
philosophy of mathematics - you know, find out what many other people
have accomplished and thought about and how very wide the range of
thinking is. Just maybe you'd find yourself rewarded if you actually
familiarized yourself with some mathematics and philosophy of
mathematics. The alternative - knowing virtually nothing about the
subject while yet staunch in your opinions about it - doesn't make you
quite the source of open-minded humanistic wisdom.
MoeBlee
Balthasar
wrote:
>
> As I explained, not all of mathematical ideation is deductive
> reasoning. But ORDINARY mathematical PROOF is deductive. And that does
> not disallow that mathematicians can also give probabilistic
> arguments for propositions.
>
Right. Though /probability theory/ itself again is a deductive theory.
>
> Nor disallowed is research that gives only reasonable (but not
> conclusive) basis only for accepting certain principles.
>
Right. Though this principles then may be considered as additional
axioms.
>
> Why don't you get out of your self-contained system of your own
> thoughts for a change and instead actually READ some mathematics and
> philosophy of mathematics - you know, find out what many other people
> have accomplished and thought about and how very wide the range of
> thinking is.
>
A crank is a crank is a crank...
MoeBlee
> On Wed, 6 Aug 2008 15:07:31 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
> wrote:
> > As I explained, not all of mathematical ideation is deductive
> > reasoning. But ORDINARY mathematical PROOF is deductive. And that does
> > not disallow that mathematicians can also give probabilistic
> > arguments for propositions.
>
> Right. Though /probability theory/ itself again is a deductive theory.
Of course. But I meant giving probabilistic arguments for certain
mathematical propositions. (I don't know much of anything of the
specifics of such research, but I have heard of it and even, I think,
of theory about it.)
> > Nor disallowed is research that gives only reasonable (but not
> > conclusive) basis only for accepting certain principles.
>
> Right. Though this principles then may be considered as additional
> axioms.
Sure (additional or just diffferent), most famously, as in discussions
of what would be reasonable axioms to add to set theory to settle such
matters as the continuum hypothesis. Also, even more fundamentally, as
in research for predicative, finitistic, or constructivistic
foundations.
MoeBlee
Balthasar
wrote:
>>>
>>> As I explained, not all of mathematical ideation is deductive
>>> reasoning. But ORDINARY mathematical PROOF is deductive. And that does
>>> not disallow that mathematicians can also give probabilistic
>>> arguments for propositions.
>>>
>> Right. Though /probability theory/ itself again is a deductive theory.
>>
> Of course. But I meant giving probabilistic arguments for certain
> mathematical propositions. (I don't know much of anything of the
> specifics of such research, but I have heard of it and even, I think,
> of theory about it.)
>
Same with me. IIRC there are probabilistic arguments supporting the idea
that the Goldbach conjecture might be true. (And consequently most
mathematicians actually think, or believe, that it is true.) Still now
mathematician would claim that the Goldbach conjecture _actually_ is
true (on that basis). Probabilistic arguments are no replacements for
proofs.
http://en.wikipedia.org/wiki/Goldbach's_conjecture
>>>
>>> Nor disallowed is research that gives only reasonable (but not
>>> conclusive) basis only for accepting certain principles.
>>>
>> Right. Though this principles then may be considered as additional
>> axioms.
>>
> Sure (additional or just different), most famously, as in discussions
> of what would be reasonable axioms to add to set theory to settle such
> matters as the continuum hypothesis. Also, even more fundamentally, as
> in research for predicative, finitistic, or constructivistic
> foundations.
>
Right. Exactly that was what I had in mind here. But without stating
your basis, or at least some basic principles your math will degenerate
to some sort of WMism.
Chris Menzel
said:
> ...
> We prove in Z that there exist ordinals and even that there exists a
> limit ordinal. But I keep forgetting whether we need ZF or only Z to
> prove Hartogs's theorem that gives us the existence of ordinals that
> are not countable.
I think you need ZF. The usual proof of Hartogs' theorem (for the
special case of omega) involves the construction of a mapping f that
takes each member of the set of all reflexive well-orderings of subsets
of omega to its corresponding ordinal. (Reflexive well-orderings are
used so you can reconstruct the domain of the ordering in the case where
the domain is a singleton.) Since the domain of f is a subset of
P(omega x omega), the range of f is a set (specifically, of course, w_1)
by Replacement. It is easy then to show that this set is uncountable.
(I'm implicitly using class talk in this proof by referring to f as an
object before I know it's a set, but that is of course eliminable in
terms of more kosher talk about formulas.)
I'm not certain whether this use of Replacement is essential for the
theorem, but I don't see any obvious way to avoid it.
Baudouin Le Charlier
There is a point that I am unable to understand. With such a
definition of ordinals, you cannot speak of all ordinals (i.e., you
cannot prove that there exists a set of all ordinals). Thus you cannot
state (i.e., write as a formula) that a given proposition is true for
all ordinals. So I do not understand exactly how transfinite induction
can be actually stated in Z (ZF, ZFC...). It seems that it is very
different that the case of simple induction over integers.
Thanks,
Baudouin
Aatu Koskensilta
> I'm not certain whether this use of Replacement is essential for the
> theorem, but I don't see any obvious way to avoid it.
In case of questions like this it is instructive to recall the natural
model of Zermelo set theory is V_omega+omega, and that all (von
Neumann) ordinals in the model are below omega+omega.
--
Aatu Koskensilta (aatu.kos...@uta.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta
> Notice that my motivation is to get a better understanding of
> ordinals and transfinite induction "in the real world" although I do
> not particularly believe that ZF (or ZFC) is the real world of
> mathematics.
What does it mean for a formal theory to be "the real world of
mathematics"? Perhaps the above is just a curious way of expressing
disbelief in the usual principles of set theory, that you do not
believe that every set has a power-set, that every set of non-empty
sets has a choice function, and so on?
Aatu Koskensilta
> In ZFC we actually can and do PROVE induction. Actually, this
> principle in essence just states that there are ONLY 0 and the
> successors of 0 in N (omega) (i.e. that N is minimal in this
> respect). The proof is rather easy, after N (omega) has been
> defined (as usual).
Sure. But the idea that anyone who doesn't already possess a clear
understanding of the naturals could make anything of their set
theoretic representation, or, say, the separation scheme of ZFC, is
mere fantasy. In a very clear sense induction is a basic principle,
that is, something we must accept as compelling based on our grasp of
the notions involved, without a mathematical proof.
MoeBlee
<baudouin.lecharl...@uclouvain.be> wrote:
> There is a point that I am unable to understand. With such a
> definition of ordinals, you cannot speak of all ordinals (i.e., you
> cannot prove that there exists a set of all ordinals).
Two different things:
(1) There is no set of all ordinals.
(2) We can quantify over all ordinals in the sense of forming formulas
of the forrm (where 'F' is any formula):
Ax(x is an ordinal -> F(x))
This is no different from ANY predicate that doesn't form a set. There
is no set of all finite sets, but we can speak of "all finite sets";
there is no set of all nonempty sets, but we can speak of "all
nonempty sets". For that matter, there is no set of all sets; be we
can speak of "all sets". Each of those in the sense, respectively, of
"Ax(x if finite -> [whatever])", "Ax(x is nonempty -> [whatever]",
"Ax(x is a set -> [whatever]" (and that is just "Ax [whatever]". Etc.
> Thus you cannot
> state (i.e., write as a formula) that a given proposition is true for
> all ordinals.
Sure you can.
Ax(x is an ordinal -> F(x))
That says, "For all ordinals x, we have F(x)".
> So I do not understand exactly how transfinite induction
> can be actually stated in Z (ZF, ZFC...). It seems that it is very
> different that the case of simple induction over integers.
It is stated as a theorem schema. Here are at least three ways of
stating transfinite induction as a schema. And each is a theorem
schema of Z set theory:
1.
If F is a formula, then
F(0) &
Ak(k is a successor ordinal -> F(k)) &
Ak(k is a limit ordinal -> F(k))
->
Ak(k is an ordinal -> F(k))
2.
If F is a formula, then
Ak((k is an ordinal & Am(m<k -> F(m))) -> Fk)
->
Ak(k is an ordinal -> F(k))
3
If F is a formula, then
F(0) &
Ak((k is an ordinal & F(k)) -> F(k+1)) &
Ak((k is a limit ordinal & Am(m<k -> F(m))) -> F(k))
->
Ak(k is an ordinal -> F(k))
So, transfinite induction is stated as various theorem schemata. In
that sense, yes, it is stated and proven in the meta-theory, but not
because of any problem expressing "for all ordinals", but rather
because we are expressing "for all formulas". However, for any
PARTICULAR formula, transfinite induction regarding that formula is
provable in Z itself.
MoeBlee
MoeBlee
> On Wed, 6 Aug 2008 10:10:19 -0700 (PDT), MoeBlee <jazzm...@hotmail.com>
Thanks, Chris.
MoeBlee
MoeBlee
> Chris Menzel <cmen...@remove-this.tamu.edu> writes:
> > I'm not certain whether this use of Replacement is essential for the
> > theorem, but I don't see any obvious way to avoid it.
>
> In case of questions like this it is instructive to recall the natural
> model of Zermelo set theory is V_omega+omega, and that all (von
> Neumann) ordinals in the model are below omega+omega.
Thanks, Aatu.
MoeBlee
Chris Menzel
<aatu.kos...@uta.fi> said:
> Chris Menzel <cme...@remove-this.tamu.edu> writes:
>
>> I'm not certain whether this use of Replacement is essential for the
>> theorem, but I don't see any obvious way to avoid it.
>
> In case of questions like this it is instructive to recall the natural
> model of Zermelo set theory is V_omega+omega, and that all (von
> Neumann) ordinals in the model are below omega+omega.
Doh! I shoulda thought of that... :-)
Chris Menzel
> On Aug 6, 2:44 pm, ju...@diegidio.name wrote:
>
>> Your idea of math is quite restricted, and overall inadequate.
>> Deduction as the queen of logical reasoning is part of the
>> monodimensionality of our epoch. From there, it is easy to give
>> preminence to calculation vs. reasoning, technicalities vs.
>> comprehension. It's in fact a specific educational model.
>
> After all your boasts, you couldn't prove that there is a set that
> maps onto its power set. So now you're reduced to foaming about the
> evils of deductive logic itself. Nicely done.
Anybody notice that julio showed up shortly after JJ disappared? :-)
Baudouin Le Charlier
> Baudouin Le Charlier <baudouin.lecharl...@uclouvain.be> writes:
>
> > Notice that my motivation is to get a better understanding of
> > ordinals and transfinite induction "in the real world" although I do
> > not particularly believe that ZF (or ZFC) is the real world of
> > mathematics.
>
> What does it mean for a formal theory to be "the real world of
> mathematics"? Perhaps the above is just a curious way of expressing
> disbelief in the usual principles of set theory, that you do not
> believe that every set has a power-set, that every set of non-empty
> sets has a choice function, and so on?
Sorry, by saying "ZF or ZFC is not the real world of mathematics" I
mean that
(a) formal terms are not *the* "real mathematical objects" and
formulas in ZF or ZFC are not *the* meaningful mathematical
statements;
(b) formal systems such as ZF or ZFC are not a completely
satisfactory axiomatization for all mathematics.
I am taking the position that abstract mathematical objects such as
numbers and sets exist in some objective sense and that the goal of
mathematics is to 'discover' them 'as they are'. I think that systems
such as ZF(C) are designed to avoid reasoning mistakes but they
provide incomplete information about the whole mathematical universe.
It is nevertheless amazing that we can deduce so many useful theorem
from such systems. But also at a high price I think.
>
> --
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
Baudouin Le Charlier
I understand that there are two kinds of sets (in the intuitive or
naive or real sense) in ZF:
(a) those that are definable by a formula F<x> and
(b) those that are definable by a formula F<x> such that one can prove
(exists y: x in y <--> F<x>)
Thus the set of all ordinals can be defined by such a formula F but
(exists y: x in y <--> F<x>) is not provable.
Moreover the existence of ordinals as formalized by the scheme you
explained is less certain and their 'real nature' is somewhat unclear:
one can prove the existence of some of them but one cannot see clearly
'where they stop' (sorry).
Another conclusion that I draw is that transfinite induction cannot be
proved in systems such as Z, ZF, ZFC. It can only be used as a
metatheoretic procedure. In other words there is no provable formula
which can be interpreted as a formal statement of the transfinite
induction principle.This is a good argument to dismiss the claim that
formal systems for set theory allow one to express all valid
mathematical reasoning since many usual reasoning method are justified
only on metamathematical grounds. At the limit, we can perhaps
conclude that all reasoning techniques must be accepted as obvious
(until we have 'a problem' with it), i.e. either obvious or wrong.
Hence mathematics can only be practiced but cannot be a priori
founded.
PS. Well I realize that the syntax, axioms and inference rules of such
formal systems can be encoded as sets. Thus encoding of metatheorems
and metarules can be formally provable. But I really think it is an
hugly vicious circle.
Baudouin
Balthasar
<baudouin....@uclouvain.be> wrote:
>
> I understand that there are two kinds of sets (in the intuitive or
> naive or real sense) in ZF:
>
Not so. In ZF(C) there's just ONE kind of set.
In class theories like NBG and/or MK there are two sorts of "sets" (or
rather /classes/): /sets/ and so called /proper classes/ (classes that
are not member of any class).
BUT there's a _formal trick_ to use a class notation even in ZFC which
allows to treat these symbols as if they were classes (in the sense of
NBG and/or MK).
In this case, one might write, say,
a e [x : F<x>]
if
F<a>.
(Note that "[x : F<x>]" does not denote a certain object -set or class-
here. The notation is -as mentioned- just a formal trick. I guess Quine
called those pseudo-objects "virtual classes".]
Moreover we could extend this notation by writing
[x : F<x>] = [x : G<x>]
if
Ax(F<x> <-> G<x>).
etc.
>
>(a) those that are definable by a formula F<x>
>
Well, no (not in ZF(C)). But in, say MK, whis would hold: For any
formula F<x> there's a class y such that Ax(x e y <-> set(x) & F<x>).
We usually write "{x : F<x>}" for this y. Hence in MK we have for any
formula F<x>:
a e {x : F<x>} <-> set(a) & F<a>.
In ZF(C) we would have (with the formal trick mentioned above)
a e [x : F<x>] <-> F<a>.
But, for example, we would not be allowed to derive
Ex(x = [x : F<x>])
from
[x : F<x>] = [x : F<x>].
With other words, "[x : F<x>]" does not denote a certain set, i.e. is
not a term.
>
> and (b) those that are definable by a formula F<x> such that one can
> prove (exists y: x in y <--> F<x>)
>
Right.
>
> Thus the set of all ordinals can be defined by such a formula F
>
No. In NBG/MK we can define the _class_ of all ordinals, and then it
turns out that this class is a _proper class_, i.e. _not a set_.
And in ZF(C) there's simply no such set. But, right, we might use our
formal trick, and work with
(*) [x : x is an ordinal].
I guess that refers to "the class of all ordinals defined by <is an
ordinal>" you had in mind here. Note though that the symbol (*) does not
have a "meaning in isolation". Especially it does not refer to a set.
>
> but (exists y: x in y <-> F<x>) is not provable.
>
At least not in ZF(C).
>
> Moreover the existence of ordinals as formalized by the scheme you
> explained ...
>
Nonsense.
>
> Another conclusion that I draw is that transfinite induction cannot be
> proved in systems such as Z, ZF, ZFC.
>
Draw what you want. It CAN BE proved and it IS proved in ZF(C), see
MoeBlee's post.
>
> It can only be used as a metatheoretic procedure. In other words there
> is no provable formula which can be interpreted as a formal statement
> of the transfinite induction principle.
>
First sentence: nonsense. Second sentence: false.
>
> This is a good argument to dismiss the claim that formal systems for
> set theory allow one to express all valid mathematical reasoning since
> many usual reasoning method are justified only on metamathematical
> grounds.
>
No. I don't think that THIS is a good argument for this claim (since
your "argument" is not sound). Moreover, axiomatic set theory is done in
a _logical_ framework which allows for the "logical reasoning" in the
context of set theory. Maybe you meant the claim that "all valid
mathematics can be reduced to set theory" - whatever that may mean. The
latter certainly might be an exaggeration.
>
> At the limit, we can perhaps conclude that all reasoning techniques
> must be accepted as obvious (until we have 'a problem' with it), i.e.
> either obvious or wrong. Hence mathematics can only be practiced but
> cannot be a priori founded.
>
This may be the case, or not. Carnap once mentioned that we could not
convince a man who is 'deductively blind' of the validity of MP. (You
certainly _may_ have a point here.)
>
> PS. Well I realize that the syntax, axioms and inference rules of such
> formal systems can be encoded as sets. Thus encoding of metatheorems
> and metarules can be formally provable. But I really think it is an
> hugly vicious circle.
>
Actually, this has no relation to your original question, a correct
answer was given to you by MoeBlee.
Balthasar
<baudouin....@uclouvain.be> wrote:
>>
>> What does it mean for a formal theory to be "the real world of
>> mathematics"? Perhaps the above is just a curious way of expressing
>> disbelief in the usual principles of set theory, that you do not
>> believe that every set has a power-set, that every set of non-empty
>> sets has a choice function, and so on?
>>
> Sorry, by saying "ZF or ZFC is not the real world of mathematics"
> I mean that
> (a) formal terms are not *the* "real mathematical objects" and
> formulas in ZF or ZFC are not *the* meaningful mathematical
> statements;
> (b) formal systems such as ZF or ZFC are not a completely
> satisfactory axiomatization for all mathematics.
>
One might argue that a Formalist might deny (a). And that for him the
"mathematical objects" actually are the _formulas_. Clearly a, say, set
theoretical Platonist would reject this position. :-)
(b) on the other hand, will be accepted as true by almost all
mathematicians, I guess. Though some certainly might claim that
"ZF or ZFC are satisfactory for most mathematical purposes".
(That's the reason why those systems are so widely used in mathematics.)
>
> I am taking the position that abstract mathematical objects such as
> numbers and sets exist in some objective sense and that the goal of
> mathematics is to 'discover' them 'as they are'.
>
Oh, a Platonist (realist). :-)
>
> I think that systems such as ZF(C) are designed to avoid reasoning
> mistakes but they provide incomplete information about the whole
> mathematical universe.
>
It was proven by Gödel that this is indeed (necessarily) the case. (Even
if Platonism is not right); i.e. those systems are (in a formal sense)
incomplete (which in turn may be interpreted in the way you suggest).
Balthasar
>>
>> I am taking the position that abstract mathematical objects such as
>> numbers and sets exist in some objective sense and that the goal of
>> mathematics is to 'discover' them 'as they are'.
>>
> Oh, a Platonist (realist). :-)
>
Btw, I don't share your views (since I'm a fictionalist). But I don't
see anything basically wrong with them.
Though I just don't "understand" how you can believe in the existence of
something you don't have the least "evidence" of. (I mean it's easy to
claim that "numbers and sets exist in some objective sense"; but HOW
would you know? How do you know that they are not just "made up" by us?)
MoeBlee
<baudouin.lecharl...@uclouvain.be> wrote:
> I understand that there are two kinds of sets (in the intuitive or
> naive or real sense) in ZF:
> (a) those that are definable by a formula F<x> and
> (b) those that are definable by a formula F<x> such that one can prove
> (exists y: x in y <--> F<x>)
Actually, those are two different senses of definability ITSELF.
There is one kind of definability: Given a structure and a particular
object per that structure, there is a formula in the language, as
intepreted by that structure, such that that formula is satisfied by
the structure and any assigment for the variables iff the free
variable in the formula is assigned to said object. That is, the
formula defines the object per the structure. (The case for more than
one free variable, thus picking out a tuple in the universe of the
structure, is similar; also for n-place functions on the universe.)
Another kind of definability (sometimes called 'representability' or
'capturing') is like the above except it involves what a theory can
PROVE. (I'll give a more precise sense of that if you like; but I'd
rather check my notes first so that I state it correctly.)
Another kind of definability: A theory proves AyE!xP(x) so that an
operation symbol (possibly a 0-place operation symbol) can be defined
per that theory. (Similar for predicate symbols.)
> Thus the set of all ordinals can be defined by such a formula F but
> (exists y: x in y <--> F<x>) is not provable.
Okay.
> Moreover the existence of ordinals as formalized by the scheme you
> explained
No, the schemata I mentioned don't formalize the EXISTENCE of
ordinals. Rather, each schema defines a set of theorems of Z set
theory.
> is less certain and their 'real nature' is somewhat unclear:
> one can prove the existence of some of them but one cannot see clearly
> 'where they stop' (sorry).
They don't "stop". And that has no bearing on the plain SYNTACTICAL
fact that each instance of the schemata is a theorem of Z set theory.
> Another conclusion that I draw is that transfinite induction cannot be
> proved in systems such as Z, ZF, ZFC.
Why do you keep saying this? What can be proved is a SYNTACTICAL
matter, and we DO prove the induction schemata. And every instance of
an induction schema is a theorem of Z set theory.
> It can only be used as a
> metatheoretic procedure.
No, any INSTANCE of a schema is a theorem of Z set theory.
> In other words there is no provable formula
> which can be interpreted as a formal statement of the transfinite
> induction principle.
Every INSTANCE of a schema is a provable formula.
> This is a good argument to dismiss the claim that
> formal systems for set theory allow one to express all valid
> mathematical reasoning
That one may regard ZFC is a presumed standard doesn't entail that one
doesn't also recognize that there are other forms of validity not
confined to first order logic, and that some mathematics may be
formulated in that regard.
> since many usual reasoning method are justified
> only on metamathematical grounds. At the limit, we can perhaps
> conclude that all reasoning techniques must be accepted as obvious
> (until we have 'a problem' with it), i.e. either obvious or wrong.
> Hence mathematics can only be practiced but cannot be a priori
> founded.
Given that that might be a reasonable view, it doesn't affect that we
prove transfinite induction for Z set theory.
> PS. Well I realize that the syntax, axioms and inference rules of such
> formal systems can be encoded as sets. Thus encoding of metatheorems
> and metarules can be formally provable. But I really think it is an
> hugly vicious circle.
It can be seen as circular. But I don't see that it is VICIOUS. Also,
my view of it is as forever escalating to meta-meta-meta...rather than
as circling back. Then the "problem" is inherent in ANY system. IF we
KEEP asking to formalize or means of formalization, no matter WHAT the
system or subject matter of that system, either we'll come back in a
circle or we'll keep going with formalization of formalization of
formalization...So I don't see this as a basis of criticism. You can't
fault set theory for what is unavoidable for ANY theory.
Anyway, please, whatever your philosophical views, at least recognize
that transfinite induction schemata are provable schemata in a meta-
theory for Z set theory and that each INSTANCE of a schema is provable
in Z set theory itself, and moreover, that there is no set of ordinals
is not a barrier to proving transfinite induction.
MoeBlee
Balthasar
wrote:
>
> On Aug 7, 1:21 am, Baudouin Le Charlier
> <baudouin.lecharl...@uclouvain.be> wrote:
>>
>> There is a point that I am unable to understand. With such a
>> definition of ordinals, you cannot speak of all ordinals (i.e.,
>> you cannot prove that there exists a set of all ordinals).
>>
Hmmm, right, there is no such set (i.e. a set of all ordinals) in ZF(C).
But we still can "speak" of all ordinals. (By quantifying over them.) In
the same way we can easily speak about all sets in ZFC - though there is
no universal set (a set containing all sets as elements) in ZFC:
Ax(...x...)
"For all sets: ..."
>
> Two different things:
>
> (1) There is no set of all ordinals.
>
> (2) We can quantify over all ordinals in the sense of forming formulas
> of the form (where 'F' is any formula):
>
> Ax(x is an ordinal -> F(x))
>
Right.
>
> This is no different from ANY predicate that doesn't form a set. There
> is no set of all finite sets, but we can speak of "all finite sets";
> there is no set of all nonempty sets, but we can speak of "all
> nonempty sets". For that matter, there is no set of all sets; but we
> can speak of "all sets". Each of those in the sense, respectively, of
> "Ax(x if finite -> [whatever])", "Ax(x is nonempty -> [whatever]",
> "Ax(x is a set -> [whatever]" (and that is just "Ax [whatever]". Etc.
>
Right.
Actually, some use a certain "class notation" in the context of ZFC to
deal with this predicates AS IF they would "define" sets:
a e [x : phi(x)] <-> phi(a).
This just formalizes what sometimes is done in a non-formal way.
Consider, for example, the following statement by Chris Menzel: "(I'm
implicitly using class talk in this proof by referring to f as an object
before I know it's a set, but that is of course eliminable in terms of
more kosher talk about formulas.)" - stated referring to a ZF-context.
>>
>> Thus you cannot state (i.e., write as a formula) that a given
>> proposition is true for all ordinals.
>>
> Sure you can.
>
> Ax(x is an ordinal -> F(x))
>
> That says, "For all ordinals x, we have F(x)".
>
Right. (Though one might argue that we do not state that F(x) is /true/
for all ordinals, this way. Some might prefer to translate this with:
/holds/ for all ordinals, etc.)
Baudouin Le Charlier
> On Fri, 8 Aug 2008 01:38:59 -0700 (PDT), Baudouin Le Charlier
>
Thank you for your comments. I am afraid that most of our
'disagreements' (it doubt this is correct english) is due to my
incorrect use of the english language. Sorry.
Baudouin
Baudouin Le Charlier
> On Fri, 08 Aug 2008 19:08:46 +0200, Balthasar <nomail@invalid> wrote:
>
> >> I am taking the position that abstract mathematical objects such as
> >> numbers and sets exist in some objective sense and that the goal of
> >> mathematics is to 'discover' them 'as they are'.
>
> > Oh, a Platonist (realist). :-)
>
> Btw, I don't share your views (since I'm a fictionalist). But I don't
> see anything basically wrong with them.
>
> Though I just don't "understand" how you can believe in the existence of
> something you don't have the least "evidence" of. (I mean it's easy to
> claim that "numbers and sets exist in some objective sense"; but HOW
> would you know? How do you know that they are not just "made up" by us?)
>
Do you think that it is really possible for me to answer your question
within a few lines ? I am not a professional philosopher thus I am
afraid that my explanations would be judged too naive. But, for
instance, I am sure that Goedel would not have imagined his proof of
the incompleteness theorem if he was not a Platonist or realist in the
strongest sense. In fact nobody would have (I believe). I find it so
nice that the most naive view of mathematics (realism) is the most
powerful for the 'mathematician at work'.
Baudouin
Baudouin Le Charlier
Sorry, my fault again. I was referring to your *definition* of
ordinals not to the scheme of transfinite induction. My point was that
the *definition* of ordinals you mention (which is standard I guess)
does not give clear insight on what ordinals really are. Thus there
is an hard work to extract the 'substance' from the definition. A
naive 'definition' of ordinals mimicking the naive process of
transfinite induction is more enlighting but also it does not allow us
to understand easily where 'the process stops'. Notice that saying
that it does not stop is no more enlighting since one can say the same
thing for the sequence of natural numbers.
>
> > is less certain and their 'real nature' is somewhat unclear:
> > one can prove the existence of some of them but one cannot see clearly
> > 'where they stop' (sorry).
>
> They don't "stop". And that has no bearing on the plain SYNTACTICAL
> fact that each instance of the schemata is a theorem of Z set theory.
>
> > Another conclusion that I draw is that transfinite induction cannot be
> > proved in systems such as Z, ZF, ZFC.
>
> Why do you keep saying this? What can be proved is a SYNTACTICAL
> matter, and we DO prove the induction schemata. And every instance of
> an induction schema is a theorem of Z set theory.
The induction schemata is true (correct) in the sence that there is a
proof of any instance of it in the formal system. But this fact is
proved at the metalevel. Thus it is no proved in the formal system.
There is no formula of set theory which 'says' that transfinite
induction is a correct reasoning principle.
>
> > It can only be used as a
> > metatheoretic procedure.
>
> No, any INSTANCE of a schema is a theorem of Z set theory.
My fault, again. I was meaning exactly that.
>
> > In other words there is no provable formula
> > which can be interpreted as a formal statement of the transfinite
> > induction principle.
>
> Every INSTANCE of a schema is a provable formula.
This does not contradict what I am saying.
>
> > This is a good argument to dismiss the claim that
> > formal systems for set theory allow one to express all valid
> > mathematical reasoning
>
> That one may regard ZFC is a presumed standard doesn't entail that one
> doesn't also recognize that there are other forms of validity not
> confined to first order logic, and that some mathematics may be
> formulated in that regard.
>
> > since many usual reasoning method are justified
> > only on metamathematical grounds. At the limit, we can perhaps
> > conclude that all reasoning techniques must be accepted as obvious
> > (until we have 'a problem' with it), i.e. either obvious or wrong.
> > Hence mathematics can only be practiced but cannot be a priori
> > founded.
>
> Given that that might be a reasonable view, it doesn't affect that we
> prove transfinite induction for Z set theory.
You prove it at the metalevel or you prove an encoding of it at the
object level.
>
> > PS. Well I realize that the syntax, axioms and inference rules of such
> > formal systems can be encoded as sets. Thus encoding of metatheorems
> > and metarules can be formally provable. But I really think it is an
> > hugly vicious circle.
>
> It can be seen as circular. But I don't see that it is VICIOUS. Also,
> my view of it is as forever escalating to meta-meta-meta...rather than
> as circling back. Then the "problem" is inherent in ANY system.
agreed.
IF we
> KEEP asking to formalize or means of formalization, no matter WHAT the
> system or subject matter of that system, either we'll come back in a
> circle or we'll keep going with formalization of formalization of
> formalization...So I don't see this as a basis of criticism. You can't
> fault set theory for what is unavoidable for ANY theory.
My position is that we should not heavily rely on formal systems for
doing mathematics. I am interested in studying formal set theory
mainly to separate problems that are inherently difficult from
problems that are difficult only because they formalised within set
theory. I guess that many 'research problems' are of the later
category.
>
> Anyway, please, whatever your philosophical views, at least recognize
> that transfinite induction schemata are provable schemata in a meta-
> theory for Z set theory and that each INSTANCE of a schema is provable
> in Z set theory itself
okay.
, and moreover, that there is no set of ordinals
> is not a barrier to proving transfinite induction.
I still 'have a problem' with transfinite induction since I cannot
see exactly what ordinals are. I am pleased with transfinite induction
limited to some clearly defined 'initial segment' of the class of
ordinals but I am skeptical about the general principle. In fact I
think that I accept transfinite induction as far as it can easily be
reduced to induction over the natural numbers but no further.
Thanks for the discussion,
Baudouin
Balthasar
<baudouin....@uclouvain.be> wrote:
>>>>
>>>> I am taking the position that abstract mathematical objects such as
>>>> numbers and sets exist in some objective sense and that the goal of
>>>> mathematics is to 'discover' them 'as they are'.
>>>>
>>> Oh, a Platonist (realist). :-)
>>>
Another one:
"I believe that mathematical reality lies outside us, and that our
function is to discover or observe it, and that the theorems we prove,
and which we describe grandiloquently as our "creations" are simply our
notes of our observations."
(G.H. Hardy, A Mathematician's Apology, 1940)
>>
>> Btw, I don't share your views (since I'm a fictionalist). But I don't
>> see anything basically wrong with them.
>>
>> Though I just don't "understand" how you can believe in the existence of
>> something you don't have the least "evidence" of. (I mean it's easy to
>> claim that "numbers and sets exist in some objective sense"; but HOW
>> would you know? How do you know that they are not just "made up" by us?)
>>
> Do you think that it is really possible for me to answer your question
> within a few lines ?
>
Not really. :-)
>
> I am not a professional philosopher thus I am afraid that my explanations
> would be judged too naive.
>
No problem. As I mentioned already: Platonism/Realism is a respected
position - though, of course, it may be questioned. (There ARE some
"problems" with it.)
>
> But, for instance, I am sure that Goedel would not have imagined his
> proof of the incompleteness theorem if he was not a Platonist or
> realist in the strongest sense.
>
You may be right. At least that was HIS OWN view.
>
> In fact nobody would have (I believe). I find it so nice that the
> most naive view of mathematics (realism) is the most powerful for
> the 'mathematician at work'.
>
Again a position shared by Gödel. (You aren't a rebirth of Gödel, BTW?)
"Even recognizing the fruitfulness of my objectivism for my work,
people might choose not to adopt the objectivistic position but merely
do their work a s i f the position were true--provided they are able to
produce such an attitude. But then they only take this as-if point of
view toward this position after it has been shown to be fruitful.
Moreover, it is doubtful whether one can pretend so well as to yield the
desired effect of getting good scientific results.
Abraham Robinson is a representative of an as-if position, according to
which it is fruitful to behave as if there were mathematical objects,
and in this way you achieve success by a false picture. This requires a
special art of pretending well. But such pretending can never reach the
same degree of imagination as one who believes objectivism to be true.
The success in the application of a belief in the existence of something
is the usual and most effective way of proving existence."
[Kurt Gödel---quoted in: Wang, Hao (1996). /A logical journey: From
Gödel to philosophy/. Cambridge, MA: The MIT Press.]
Here's a "modern" position:
»On foundations we believe in the reality of mathematics,
but of course when philosophers attack us with their
paradoxes we rush to hide behind formalism and say
"Mathematics is just a combination of meaningless symbols,"
and then we bring out Chapters 1 and 2 on set theory.
Finally we are left in peace to go back to our mathematics
and do it as we have always done, with the feeling each
mathematician has that he is working with something real.
This sensation is probably an illusion, but is very convenient.
That is Bourbaki's attitude toward foundations.«
(J. Dieudonné)
Baudouin Le Charlier
> On Sat, 9 Aug 2008 01:12:30 -0700 (PDT), Baudouin Le Charlier
>
What should I add to your comments ? Beautiful citations! I like them.
I feel less lonely now.
Baudouin
MoeBlee
<baudouin.lecharl...@uclouvain.be> wrote:
> I was referring to your *definition* of
> ordinals not to the scheme of transfinite induction. My point was that
> the *definition* of ordinals you mention (which is standard I guess)
> does not give clear insight on what ordinals really are.
I don't know what is unclear about the definition. Ultimately, all the
definitions resolve back to the primitives, which are unclear in the
sense that they are not themselves defined. But every defined term is
precisely clear RELATIVE to whatever clarity of notion we have of the
primitives.
> Thus there
> is an hard work to extract the 'substance' from the definition.
The definition is entirely syntactical. As to substance (as I
understand that word in such a context), that is given with and
interpretation of the language.
> A
> naive 'definition' of ordinals mimicking the naive process of
> transfinite induction is more enlighting but also it does not allow us
> to understand easily where 'the process stops'. Notice that saying
> that it does not stop is no more enlighting since one can say the same
> thing for the sequence of natural numbers.
So? We DO illustrate the difference between ordinals in general and
natural numbers in particular.
> > > is less certain and their 'real nature' is somewhat unclear:
> > > one can prove the existence of some of them but one cannot see clearly
> > > 'where they stop' (sorry).
>
> > They don't "stop". And that has no bearing on the plain SYNTACTICAL
> > fact that each instance of the schemata is a theorem of Z set theory.
>
> > > Another conclusion that I draw is that transfinite induction cannot be
> > > proved in systems such as Z, ZF, ZFC.
>
> > Why do you keep saying this? What can be proved is a SYNTACTICAL
> > matter, and we DO prove the induction schemata. And every instance of
> > an induction schema is a theorem of Z set theory.
>
> The induction schemata is true (correct) in the sence that there is a
> proof of any instance of it in the formal system. But this fact is
> proved at the metalevel. Thus it is no proved in the formal system.
Yes, it is a meta-theorem (and the meta-theory may itself be a formal
theory) However, any instance is a ttheorem of the object theory
itself.
> There is no formula of set theory which 'says' that transfinite
> induction is a correct reasoning principle.
No, but transfinite induction is a formal theorem of a formal meta-
theory.
Anyway, in this regard, transfinite induction is like many another
meta-theorem, including even the indiscerniblity of identicals. For
first order, it is in the meta-theory that we prove that if x=y then
any property of x is a property of y and vice versa. If you're going
to fret about transfinite induction being a meta-theorem, then you
might as well fret about indiscernibility of identicals.
> My position is that we should not heavily rely on formal systems for
> doing mathematics.
One may prefer to rely heavily or not to rely heavily on formal
systems. But I don't see that the fact that transfinite induction is a
meta-theorem suggests in itself that's any harm in using formal
systems.
> I am interested in studying formal set theory
> mainly to separate problems that are inherently difficult from
> problems that are difficult only because they formalised within set
> theory. I guess that many 'research problems' are of the later
> category.
People have all kinds of different interests. I don't see how the
formal nature of transfinite induction suggests anything about that.
> I still 'have a problem' with transfinite induction since I cannot
> see exactly what ordinals are.
You can see what ordinals are as well as you can see about any other
defined predicate of set theory.
> I am pleased with transfinite induction
> limited to some clearly defined 'initial segment' of the class of
> ordinals but I am skeptical about the general principle.
You're skeptical because the schemata are proven in the meta-theory?
Then you might as well be skeptical that x=y entails x and y have the
all the same properties, which is only provable as a meta-theorem.
> In fact I
> think that I accept transfinite induction as far as it can easily be
> reduced to induction over the natural numbers but no further.
Your'e free not to accept whatever you don't want to accept. But
you've not given a reason that holds up.
MoeBlee
Baudouin Le Charlier
> On Aug 9, 1:53 am, Baudouin Le Charlier
>
> <baudouin.lecharl...@uclouvain.be> wrote:
> > I was referring to your *definition* of
> > ordinals not to the scheme of transfinite induction. My point was that
> > the *definition* of ordinals you mention (which is standard I guess)
> > does not give clear insight on what ordinals really are.
>
> I don't know what is unclear about the definition.
The definition is clear but its consequences are not, for an (my)
human brain.
Ultimately, all the
> definitions resolve back to the primitives, which are unclear in the
> sense that they are not themselves defined. But every defined term is
> precisely clear RELATIVE to whatever clarity of notion we have of the
> primitives.
>
> > Thus there
> > is an hard work to extract the 'substance' from the definition.
>
> The definition is entirely syntactical. As to substance (as I
> understand that word in such a context), that is given with and
> interpretation of the language.
In the case of formal set theory, there are more than one
interpretation of the language and there are more than one model.
>
> > A
> > naive 'definition' of ordinals mimicking the naive process of
> > transfinite induction is more enlighting but also it does not allow us
> > to understand easily where 'the process stops'. Notice that saying
> > that it does not stop is no more enlighting since one can say the same
> > thing for the sequence of natural numbers.
>
> So? We DO illustrate the difference between ordinals in general and
> natural numbers in particular.
Sorry, I do not understand the above sentence.
This is true only for analyzing formals systems. A formal system can
be strangely defined or its definition can contain a bug. So such a
property must be proved to (partly) ensure that a formal system agrees
with the intuition. But at the intuitive level, indiscernibility is a
tautology since obviously 'anything is equal to itself'. To the
contrary transfinite induction is not a tautology at the intuitive
level. It is not even clear that it has any meaning.
>
> > My position is that we should not heavily rely on formal systems for
> > doing mathematics.
>
> One may prefer to rely heavily or not to rely heavily on formal
> systems. But I don't see that the fact that transfinite induction is a
> meta-theorem suggests in itself that's any harm in using formal
> systems.
To do what ?
>
> > I am interested in studying formal set theory
> > mainly to separate problems that are inherently difficult from
> > problems that are difficult only because they formalised within set
> > theory. I guess that many 'research problems' are of the later
> > category.
>
> People have all kinds of different interests. I don't see how the
> formal nature of transfinite induction suggests anything about that.
If transfinite induction has any value, it is because it may help to
prove facts about 'the real world of mathematics'. (Only my personal
opinion, of course)
>
> > I still 'have a problem' with transfinite induction since I cannot
> > see exactly what ordinals are.
>
> You can see what ordinals are as well as you can see about any other
> defined predicate of set theory.
Why ?
>
> > I am pleased with transfinite induction
> > limited to some clearly defined 'initial segment' of the class of
> > ordinals but I am skeptical about the general principle.
>
> You're skeptical because the schemata are proven in the meta-theory?
> Then you might as well be skeptical that x=y entails x and y have the
> all the same properties, which is only provable as a meta-theorem.
I am not skeptical about the formal schemata nor (a priori) about its
proof (although I should read and understand it). I am skeptical about
the fact that the schemata has a precise intuitive meaning.
Baudouin
MoeBlee
<baudouin.lecharl...@uclouvain.be> wrote:
> On 11 août, 21:21, MoeBlee <jazzm...@hotmail.com> wrote:
>
> > On Aug 9, 1:53 am, Baudouin Le Charlier
>
> > <baudouin.lecharl...@uclouvain.be> wrote:
> > > I was referring to your *definition* of
> > > ordinals not to the scheme of transfinite induction. My point was that
> > > the *definition* of ordinals you mention (which is standard I guess)
> > > does not give clear insight on what ordinals really are.
>
> > I don't know what is unclear about the definition.
>
> The definition is clear but its consequences are not, for an (my)
> human brain.
The set of consequences is not computable. However, given a proof of a
particular consequence, you don't have a problem understanding the
proof (assuming it's sufficiently detailed or explained), do you?
> > The definition is entirely syntactical. As to substance (as I
> > understand that word in such a context), that is given with and
> > interpretation of the language.
>
> In the case of formal set theory, there are more than one
> interpretation of the language and there are more than one model.
That's true of ANY consistent theory. And true of many theories also
that not all models are isomorphic. And I don't see why this should be
a problem for the definition of 'is an ordinal' anymore than for the
defintion of any other predicate.
> > > A
> > > naive 'definition' of ordinals mimicking the naive process of
> > > transfinite induction is more enlighting but also it does not allow us
> > > to understand easily where 'the process stops'. Notice that saying
> > > that it does not stop is no more enlighting since one can say the same
> > > thing for the sequence of natural numbers.
>
> > So? We DO illustrate the difference between ordinals in general and
> > natural numbers in particular.
>
> Sorry, I do not understand the above sentence.
You said that saying about ordinals, "it doesn't stop" is not helpful,
since we also say that about naturals. So, if I understand correctly
what you meant, it is that "it doesn't stop" is not enough to
distinguish ordinals in general from natural numbers in particular. So
I answered that we have other ways of making that distinction.
There are no bugs for systems that satisfy such theorems as unique
readability.
> So such a
> property must be proved to (partly) ensure that a formal system agrees
> with the intuition.
Then that's an additonal requirement you have.
> But at the intuitive level, indiscernibility is a
> tautology since obviously 'anything is equal to itself'.
Actually, "anythig is equal to itself" is its own axiom of identity
theory. We can't prove the indiscernibility of identicals just from
"anything is equal to itself", nor vice versa.
> To the
> contrary transfinite induction is not a tautology at the intuitive
> level. It is not even clear that it has any meaning.
As to having meaning or not, we're back full circle. But I'll take
your point that indiscernibility of identicals is ordinarily taken as
a logical truth. But then I'd just move on to some other example - one
of a theorem schema but not of a logical truth. And then I don't know
why you wouldn't object to that example but do object to a theorem
schema about ordinals. For example, from the axiom schema of
separation and the axiom of extensionality, we get the theorem schema:
AzE!xAy(yex <-> (yez & P))
where P is any formula in which x does not occur free.
Why object to transfinite induction but not to the above?
> > > My position is that we should not heavily rely on formal systems for
> > > doing mathematics.
>
> > One may prefer to rely heavily or not to rely heavily on formal
> > systems. But I don't see that the fact that transfinite induction is a
> > meta-theorem suggests in itself that's any harm in using formal
> > systems.
>
> To do what ?
To prove theorems.
> > > I am interested in studying formal set theory
> > > mainly to separate problems that are inherently difficult from
> > > problems that are difficult only because they formalised within set
> > > theory. I guess that many 'research problems' are of the later
> > > category.
>
> > People have all kinds of different interests. I don't see how the
> > formal nature of transfinite induction suggests anything about that.
>
> If transfinite induction has any value, it is because it may help to
> prove facts about 'the real world of mathematics'. (Only my personal
> opinion, of course)
Then that's a separate matter. The question of value is separate from
the mere question as to why one would object to some theorem schemata
but not others.
> > > I still 'have a problem' with transfinite induction since I cannot
> > > see exactly what ordinals are.
>
> > You can see what ordinals are as well as you can see about any other
> > defined predicate of set theory.
>
> Why ?
Why not?
What is different about the definition of 'is an ordinal' from the
definitions of all other kinds of predicates that makes the definition
of 'is an ordinal' especially obscure to you?
> > > I am pleased with transfinite induction
> > > limited to some clearly defined 'initial segment' of the class of
> > > ordinals but I am skeptical about the general principle.
>
> > You're skeptical because the schemata are proven in the meta-theory?
> > Then you might as well be skeptical that x=y entails x and y have the
> > all the same properties, which is only provable as a meta-theorem.
>
> I am not skeptical about the formal schemata nor (a priori) about its
> proof (although I should read and understand it). I am skeptical about
> the fact that the schemata has a precise intuitive meaning.
Well, that seems to me to be a pretty different position from the one
you started with. Anyway, don't you think there's something oxymoronic
about "precise intuitive meaning"? And, still, what is especially
intuitively imprecise about the predicate 'is an ordinal' as compared
to many another mathematical predicate?
An ordinal is just a set that is epsilon transitive and well ordered
by epsilon.
Is the notion of a set being epsilon transitive especially
intutitively imprecise to you? Is the notion of a set being well
ordered by epsilon especially intuitively imprecise about you?
Or, what is the very FIRST step in the trail of definitions from the
primitives that you find especially intuitively imprecise?
MoeBlee