Thread: Help with understanding the infinity axiom in ZF

Originally Posted by bryangoodrich

No doubt the von Neumann construction is the typical approach to constructing the natural numbers as a least inductive successor set, but recognize how you previously stated it was unique

No, I did not say that there is only one way to construct the natural numbers; I did not say that the von Neumann construction is the only way to construct the natural numbers nor that the von Neumann construction is the only way to construct a Peano system. Rather, I said that there is a unique inductive successor set. Obviously, that is to be taken in the context that we are given some specific defintion of 'successor inductive'. And in this context, I used 'successor inductive' to correspond to the xu{x} method given in the axiom of infinity in its ordinary formulation and as formulated in the first post of this thread.

GIVEN the definitions:

y is successor inductive <-> (0 in y & Ax(x in y -> xu{x} in y))

y is a least successor inductive set <->
y is successor inductive & Ax(x is successor inductive -> y subset of x)

then there is

a unique least successor inductive set.

And it would be seen that that definition of 'successor inductive' would be at play here since it corresponds exactly to the axiom of infinity as is ordinary and as stated in the first post in this thread.

If it was not clear by context to you that I meant some specific definition of 'successor inductive' then fine, I made it explicit after you mentioned it. I thought that, since this is standard textbook stuff, and since I'm in context of the axiom of infinity as in the first post, which is the ordinary formulation, such a context would have been understood.

If I had said, "there is a unique Peano system" or "there is a unique way to construct a system of natural numbers" or "there is a unique such system and no others are isomorphic with it", then, yes, I would have been quite in error. But what I said is that there is unique successor inductive set, and when I use a mathematical term like 'successor inductive' I mean it as having some specific definition.

P.S. As to the article 'a', my use is correct.

There is a unique least successor inductive set.

Of course, there is not a unique Peano system.

Nor do I claim that one can't give a different definition of 'successor inductive' that provides a different set from the von Neumann naturals but still provides for a Peano system. For that matter, one can take ANY denumerable set and make a Peano system out of it.

Originally Posted by MoeBlee

Successor inductive. In this context, "leastness" refers to the subset relation. There is a unique least successor inductive set in the sense that there is a unique set w such that w is successor inductive and for all x, if x is successor inductive then w is a subset of x.

That set is not successor inductive. Recall that X is successor inductive if and only if 0 is in X and for all y, if y is in X then yu{y} is in X.

Of course, we could define 'successor' or 'successor inductive' in a different way, indeed so that the Zermelo natural numbers you just mentioned suit such a definition. But in context, we refer to the more ordinary definitions I'm using.

i see the distinction you draw between "inductive" and "successor inductive" (meaning a very specific function X--->XU{X}). as you have stated it, you are correct (i had to think about this for quite some time), obviously there are other set injections that might serve as a "successor function" (such as X-->{X}). the thing is, we really want to regard these in some way "as the same". the "usual" defintion of the natural numbers borders on the contradictory: the natural numbers are the unique set possessing all the properties of the natural numbers (i am being deliberately vague here, so as to avoid a lengthy discussion of what those properties actually ARE). in fact, i see this as a fundamental flaw in set theory itself: we want to characterize a set by the properties its elements have. of course, we can't just go ahead and say that will do, or we run into various antimonies (such as the Russell set). so we restrict comprehension, by agreeing that if we have some other (previously defined) set, we can describe a subset by listing the properties this subset will have. of course, this pre-supposes we can find a big enough set to be sure the set we wish to describe is actually a subset of our "big set". making THAT precise, gets a bit away from the basic axioms of ZF.

The axiom schema of separation:

For all P and x, if P is a formula and x is a variable not free in P, then all closures of the following are axioms:

ExAy(y in x <-> (y in z & P))

So you see that the only technical matter about variables is that x is not free in the defining formula P. That is hardly "convoluted". Indeed it's straightforward and common sense. It's common sense that you wouldn't define a set, calling it 'x' with a condition that itself mentions x. Indeed convolultion (and contradiction) would result by allowing x to be free in P.

As to what predicates are allowable. This is rigorous and straightforward. Any formula P in which x does not occur free.

The axiom schema of separation expresses a straightforward notion: Given a set z, we can form the set x that is a subset of z and x has as members all and only those objects that are in z and that have property P. That is even common everyday reasoning. Given the set of all umbrellas we can also form the set of all umbrellas that are red. That is given the set z of all umbrellas, we have the set x that is a subset of z and such that the members of x are all and only those objects in z that are red.

can we actually, just from the ZF axioms, show that the set of umbrellas exists? or, even more basically, can we establish that {umbrella} (one umbrella) forms a set? how does one define "conceptual objects" (the abstract idea of a single umbrella) in a certain well-defined manner? naively, of course, i am perfectly willing to talk about "a set of umbrellas". but when it comes to formalizing how to talk logically about umbrellas, it gets trouble-some. does a partially destroyed umbrella count? what defines "umbrella-ness?" if, at some point, we are reduced to defining logic in purely linguistic terms, how can we ever say that logical reasoning applies to the "real world" we wish it to? i again humbly submit that there are well-formed logical predicates that are "meaningless" in natural language. when it comes to questions of foundation, we are faced with an (i believe) unavoidable dilemma: undefinition, or circularity.

Yes, as does any formal first order theory. What formal first order theory that axiomatizes mathematics for the sciences would one point to as being less complicated than ZC set theories?

Of course, one doesn't have to concern oneself with formal theories for mathematics, but if one is interested in a formal axiomatization, then I don't see that ZFC is espeically convoluted or complicated.

and how does one define a first-order logic in a set-free way (after all, it is rather unfair to use sets to define a first-order logic, and then use first-order logic to define sets)? this is what i mean by "it begs the question" of which predicates are allowable.

But the machinery is not JUST to be able to say "1 is a natural number".

of course not, i was being facetious. the idea is to generate all of the usual sets of mathematics we are accustomed to dealing with: N, Z, Q, R, C, various function sets involving the previous, etc. my point being, expressing even the simplest statements, like: one thing and one thing make two things (something self-evident to a small child), have a very dense expression in terms of ZF.

Just to be clear, I'm not an "adherent" of ZFC. I find that it has certain virtues and also that one may have certain philosophical objections to it. I enjoy studying it, but I don't take it as some theory that I must "adhere" to.

i see it as a stop-gap measure until we get something better. i think topoi are a step in the right direction. i think math should take a cue from natural language, and focus more on verbs as the pivotal elements, rather than nouns, that is to say: who cares what things ARE, what do they DO? it's quite evident to me you enjoy ZF set theory as an object of study. i'm not saying you're some sort of zealot, lol.

MoeBlee, I'm not really disagreeing with you on that point. As Deveno pointed out, "successor" can be defined differently. The context that is important is, as you pointed out, which definition of inductive set we are using. I understand the context from the original post, but I was merely emphasizing that the von Neumann ordinals is just one approach as Deveno provided an alternative. Of course, once we fix the definition, then by the axiom of extension the natural numbers just is the inductive set with the minimality property we seek, and they are uniquely defined. The axiom of infinity defines an inductive set, and just is the inductive set common to all inductive sets. This is, of course, what you stated initially.

Originally Posted by Deveno

we really want to regard these in some way "as the same"

That is done as we define the notion of a Peano system and show that any two Peano systems are isomorphic.

Originally Posted by Deveno

the "usual" defintion of the natural numbers borders on the contradictory

I don't know what it means for something to "border" on contradiction; a theory is inconsistent or it's not. Also, definitions (properly formed) do not introduce contradiction.

Originally Posted by Deveno

the natural numbers are the unique set possessing all the properties of the natural numbers (i am being deliberately vague here, so as to avoid a lengthy discussion of what those properties actually ARE).

Any X is the unique thing having the properities of X. That's true. But, just to be clear, it's not a definition, since it's true but circular.

Originally Posted by Deveno

i see this as a fundamental flaw in set theory itself: we want to characterize a set by the properties its elements have. of course, we can't just go ahead and say that will do, or we run into various antimonies (such as the Russell set). so we restrict comprehension, by agreeing that if we have some other (previously defined) set, we can describe a subset by listing the properties this subset will have. of course, this pre-supposes we can find a big enough set to be sure the set we wish to describe is actually a subset of our "big set". making THAT precise, gets a bit away from the basic axioms of ZF.

If you look at the actual applications of the axioms, from theorem to theorem, you won't find any "getting away from the basic axioms" that you imagine.

Originally Posted by Deveno

can we actually, just from the ZF axioms, show that the set of umbrellas exists? or, even more basically, can we establish that {umbrella} (one umbrella) forms a set?

ZF doesn't have a predicate "is an umbrella". That's aside the point here. I used umbrellas merely for concrete example of everyday reasoning.

Originally Posted by Deveno

how does one define "conceptual objects"

Mathematics has a method of definitions. First is to prove in the theory E!xP (for some formula P), then define some constant c by Ax(x=c <-> P). Then c is the unique x such that P.

Originally Posted by Deveno

(does a partially destroyed umbrella count? what defines "umbrella-ness?"

Those kinds of questions are not addressed by set theory. Rather, those are matters in the study of outdoor weather gear.

Originally Posted by Deveno

(if, at some point, we are reduced to defining logic in purely linguistic terms, how can we ever say that logical reasoning applies to the "real world" we wish it to? i again humbly submit that there are well-formed logical predicates that are "meaningless" in natural language.

Those are philosophical questions that you may wish to entertain yourself with, but they hardly vitiate (or make "borderline contradictory") the simple mathematical content I've presented.

Originally Posted by Deveno

when it comes to questions of foundation, we are faced with an (i believe) unavoidable dilemma: undefinition, or circularity.

Whatever the merits of your belief, it does not prevent us from forming mathematical definitions.

Originally Posted by Deveno

and how does one define a first-order logic in a set-free way (after all, it is rather unfair to use sets to define a first-order logic, and then use first-order logic to define sets)? this is what i mean by "it begs the question" of which predicates are allowable.

Yes, we recognize that we use some of the same notions in our meta discussion about our formal theory that are themselves formalized in the formal theory. Aside from the notion of sets, we use such notions as modus ponens reasoning, identity, etc. to formalize modus ponens reasoning, identity theory, etc. I don't know how one would propose to escape the use of certain basic notions such as those. In any case though, your criticism in that regard is across the board as to formal theories; the matter of definining a least successor inductive set then is merely one out of EVERY mathematical definition you could have such objections to.

Originally Posted by Deveno

expressing even the simplest statements, like: one thing and one thing make two things (something self-evident to a small child), have a very dense expression in terms of ZF.

Yes, and that's typical of axiomatic development. We define such things as natural numbers, addition on natural numbers, etc. because logically we don't NEED to take them as primitive. That's part of the point of what we're doing when we work from axioms.

Originally Posted by Deveno

i see it as a stop-gap measure until we get something better.

That's fine. Except that we might find that some systems are better in certain aspects and other systems better in other aspects.

Originally Posted by Deveno

i think topoi are a step in the right direction.

I would be very suprised if it turns out that using topoi in whatever manner you have in mind avoids the kind of philosophical difficulties you mentioned above.

Originally Posted by Deveno

i think math should take a cue from natural language, and focus more on verbs as the pivotal elements, rather than nouns, that is to say: who cares what things ARE, what do they DO?

You're welcome to point out whatever theory or developments along those lines that you endorse.

Originally Posted by bryangoodrich

once we fix the definition, then by the axiom of extension[ality] the natural numbers just is the inductive set with the minimality property we seek, and they are uniquely defined. The axiom of infinity defines an inductive set, and just is the inductive set common to all inductive sets.

I would state it this way: Given the definition of 'successor inductive' I used, the axiom of infinity is that there exists a set that is successor inductive. Then an instance of the separation schema gives us the existence of a successor inductive set that is a subset of all successor inductive sets. Then the axiom of extensionality gives us that there is a unique set that is succesor inductive and a subset of all successor inductive sets. Then we define w (read 'omega') as that unique such set.

i want to point out (and obviously i'm doing it wrong), that depending on how the axiom of infinity is formulated, we get differing notions of what a minimal inductive set IS (in terms of the actual elements). as long as you call that set ω, and make no claim to it actually "being" the natural numbers, that's defensible. in fact, even referring to a set as "successor inductive" is misleading: if what ones actually means by "successor inductive" is that it can serve as a model for the Peano axioms.

there is a tendency to view the "succession" function X--> X U {X} as the most "natural" one, and to go even further with identifying this with the set of natural numbers. this, i believe, is a mistake. for example, the wikipedia article Axiom of infinity - Wikipedia, the free encyclopedia says:

"The infinite set I is a superset of the natural numbers. To show that the natural numbers themselves constitute a set, the axiom schema of specification can be applied to remove unwanted elements, leaving the set N of all natural numbers. This set is unique by the axiom of extensionality."

this is just wrong. what is left is "a" set which can be identified with the natural numbers. and yet many respected authors/texts/websites will make the mistake of saying ω is N. to go a bit further, i was dead serious when talking about umbrellas. people use "sets" of everyday objects to illustrate the basics of set theory, such as:

{Bob, Alice, Ted} ∩ {Bob, Barry} = {Bob}. if we don't have a predicate "is an umbrella", than using umbrellas to illustrate set theory isn't very kosher, is it? in fact, proving the existence of anything BUT certain sets guaranteed by the ZF axioms is problemmatic. for example, take the free semigroup on one letter (let's use A. it's a fine letter). we cannot prove (or disprove, for that matter) from the ZF axioms that {A} is a set. even more worrisome, we cannot show that there is a set consisting of any "string", although it seems to me, that we would like very much to be able to consider these "strings" as sets, so that we can use what we know about relations on sets to manipulate them. it is somewhat of a victory that we CAN define (a version of) the natural numbers flowing just from the axioms (as one can prove that the trivial group with trivial operation is a group just from the axioms), but it is also dismaying that ZF isn't "big enough" for what we want it for.

you're probably right....any system powerful enough to express enough mathematics as to be considered a "base" is likely to have a "hole" in it....something mysterious, a kind of we-don't-really-know-what-it-is-ness. i wish i was clever enough to think of a way around this dilemma. i wll point out that the consistency of ZF is, to my knowledge, an open question. we hope it's consistent, so far, so good....

i hope you can recognize, that there is a certain problem in the very concept of "definition". mathematicians, in particular, seem to feel very satisfied with they come up with a "suitable" definition (this goes back to Euclid at least, who presented his "postulates" as self-evident). one of the main insights of the 20th century, is the realization that you can't talk about a theory wholly inside the theory (except for some theories of limited scope), and at some point you have to "step outside the theory", either in the form of a "meta-theory" or in some non-mathematical way (such as appealing to common experience).

but, we go rather far afield (a field, it's a math joke, get it?), waaay past the concerns the original poster had. and i am rather poor at sharpening my point, which is this: i think the "content" of the ZF axioms is rather deep, and our discussion of the "interpretation" of it here is somewhat superficial (relating it to non-mathematical ideas about induction and a "hereditary property"). there are subtleties here, buried in the terseness of the first-order logical statement of the axiom. the original poster couldn't "relate", but to you it's "straight-forward". why do you suppose that might be?

Originally Posted by Deveno

i want to point out (and obviously i'm doing it wrong), that depending on how the axiom of infinity is formulated, we get differing notions of what a minimal inductive set IS (in terms of the actual elements). as long as you call that set ω, and make no claim to it actually "being" the natural numbers, that's defensible.

For my own part, I don't opine as to what the natural numbers are in terms of "actual being" aside from a given formal definition in a formal theory such as Z set theory. I have various notions about such things, but I don't assert that any particular notion along those lines must be taken as definitive or preeminent

Originally Posted by Deveno

in fact, even referring to a set as "successor inductive" is misleading: if what ones actually means by "successor inductive" is that it can serve as a model for the Peano axioms.

Yes, that would be using a different definition from the one I was using.

Originally Posted by Deveno

there is a tendency to view the "succession" function X--> X U {X} as the most "natural" one, and to go even further with identifying this with the set of natural numbers.

Just to be clear about my own view, I don't assert anything about such naturalness. The xu{x} method is convenient, it is the most common, and it has certain virtues. But I don't opine as to whether it is the most natural.

Originally Posted by Deveno

Wikipedia, the free encyclopedia says:

"The infinite set I is a superset of the natural numbers. To show that the natural numbers themselves constitute a set, the axiom schema of specification can be applied to remove unwanted elements, leaving the set N of all natural numbers. This set is unique by the axiom of extensionality."

this is just wrong.

No, it's not wrong, given the definitions that are in use in that context.

Originally Posted by Deveno

what is left is "a" set which can be identified with the natural numbers. and yet many respected authors/texts/websites will make the mistake of saying ω is N.

It seems to me that you're confusing two different matters. When we say that the set of natural numbers is defined as just mentioned, we are giving a particular formal definition for the purpose of working in certain theories. We are not necessarily saying that there are not other ways one could form definitions. We are stating a convention; we are not disallowing that one may have a different convention in play in another context, nor are we necessarily saying that the natural numbers "actually are" (whatever that means) such and such a formally defined set.

Originally Posted by Deveno

if we don't have a predicate "is an umbrella", than using umbrellas to illustrate set theory isn't very kosher, is it?

There's nothing in the least that would make a rabbi blush. When I mentioned umbrellas, I was just giving an informal explanation of an idea. Of course, I don't use the notion of umbrellas in actual formal proofs in set theory. But to use such common items in certain general explanations is harmless. I merely illustrated the notion of the schema of separation. There was nothing ESSENTIAL in choosing umbrellas. I could have mentioned "schumbrellas" or "crumbellas" or "x's" or "y's" or whatever. However, of course, whether Orthodox Judaism permits the use of umbrellas on the Sabbath, on that question we must defer to the Talmudic scholars...

Originally Posted by Deveno

in fact, proving the existence of anything BUT certain sets guaranteed by the ZF axioms is problemmatic.

Of course, yes, ZF only proves the existence statements that ZF proves.

Originally Posted by Deveno

for example, take the free semigroup on one letter (let's use A. it's a fine letter). we cannot prove (or disprove, for that matter) from the ZF axioms that {A} is a set.

I don't recall the details about what 'free' means regarding semigroups, but generally speaking, in ZF we can define such predicates as 'is a semigroup', etc. (and I guess we could define 'is a free semigroup'?). Then also, given any A, of course in set theory we have that there exists a unique set {A} such that members of {A} are all and only A.

Originally Posted by Deveno

even more worrisome, we cannot show that there is a set consisting of any "string", although it seems to me, that we would like very much to be able to consider these "strings" as sets, so that we can use what we know about relations on sets to manipulate them.

Strings are taken as sets commonly. We can take strings to be finite sequences, or we can take strings to be n-tuples. This is discussed in various texts in mathematical logic and in computability.

Originally Posted by Deveno

it is also dismaying that ZF isn't "big enough" for what we want it for.

Depends on what we want it for. For example, if you want full category theory, my understanding (I'm not expert on this) is that adding to ZFC the axiom that there exists a Grothendieck universe gives you category theory.

Originally Posted by Deveno

i hope you can recognize, that there is a certain problem in the very concept of "definition". mathematicians, in particular, seem to feel very satisfied with they come up with a "suitable" definition (this goes back to Euclid at least, who presented his "postulates" as self-evident). one of the main insights of the 20th century, is the realization that you can't talk about a theory wholly inside the theory (except for some theories of limited scope), and at some point you have to "step outside the theory", either in the form of a "meta-theory" or in some non-mathematical way (such as appealing to common experience).

Of course we use meta-theories. But I don't know what specific problem you find with the ordinary method of mathematical definitions.

Originally Posted by Deveno

there are subtleties here, buried in the terseness of the first-order logical statement of the axiom. the original poster couldn't "relate", but to you it's "straight-forward". why do you suppose that might be?

The original poster had a question on how to prove something. I don't know whether he was having a problem relating to anything. As to why I find the schema of separation straightforward, I think it's because I studied such basic set theory in a clear, step by step manner. I have no special talent for mathematics or set theory, but most of this basic stuff presents to me as pretty clear when I approach it calmly and systematically.