How is it that naïve sets can be used in logic consistently before ZFC?

[ontologic]

I've been following the first few chapters of Yuri Manin's "A Course in Mathematical Logic for Mathematicians," and as an undergraduate who has only had basic logic and naïve set theory, the way he explained a few of the topics rubbed me the wrong way - specifically, the definitions of the ordinals, and the definition of an interpretation of a language (in model theory).

First of all, in constructing the ordinals, we had to allow for infinite sets, and Manin uses naïve sets in doing so; from what I've read, it seems that in order to allow for infinite sets, we would need an axiomatic set theory such as ZFC or Neumann-Bernays-Goedel to avoid paradoxes; but ordinals are used in the rank of the von Neumann Universe, which is used to interpret either of those two systems. How is it that we can do this without compromising our system?

Secondly, the notion of an interpretation involves a mapping from a language L to a set M; but from all accounts I've read, M is again allowed to be infinite. How can we know how to safely (i.e. axiomatically) handle infinite sets without an axiomatic system?

I suspect the important possibilities I may be overlooking are that (a) we're ultimately using finite sets at the core to construct these things and (b) this all ties into computability quite elegantly somehow; but I'd like some clarification on this either way. Specifically, I'd REALLY appreciate a short rundown of how logic is justified - an "epistemological timeline," if you will, where logical assumptions are noted down one after another in their order of precedence, like "languages exist and we use finite sets to characterize them; languages lead to axiomatic set theory after assuming sets exist and obey certain axioms," etc., or perhaps "Turing machines exist; define the class of computable functions, then define set theory, and so on."


Thanks. This has been bugging me for weeks.

 

[yossell]

Hi ontologic,

welcome to the forums.

(a)
I'm not sure what you have in mind by `naive sets'. `Naive set theory' is often used to refer to a set-theory that turned out to be inconsistent - one that essentially said that there was a set for every property, thus entailing things like Russell's paradox. It would certainly be problematic if anyone was still using *this* theory to prove anything.

However, parts of your post suggest that `naive' just means something like `intuitive' - that things are being proved about sets before a specific axiom system has been examined and introduced. If so, it's less clear that this is a problem. Even when doing logic, we rarely properly use axiom systems to prove things or show things - try writing out any moderately complex proof fully in first order logic and you'll see what I mean.

Moreover, just having an axiomatisation is no guarantee against inconsistency - if we're worried about deriving contradictions, the possession of an axiomatisation does not, in itself, rule out that contradictions can be derived - though they can reassure us.

Also: provided the informal justification for Manin's constructions use principles that are part of or follow from ZFC, then what would be really problematic about his construction? Agreed, if at some point he has used the principle `to every property there corresponds a set', this would be unsatisfactory. But if he only used things like: `for any set S, for any property P, there is a subset of S which contains precisely the P's' - wouldn't that be ok? For that is pretty much the effect of the comprehension (separation) axiom that appears in ZFC.

(b) You seem to have a particular worry about infinite sets. What is it about infinite sets that particularly requires axiomatisation? Again, an axiomatisation alone won't prove that we're handling infinite sets safely: it depends upon the principles the axiomatisation uses. But if it depends upon the princples, Manin may have felt it was just better at first to use the principles rather than first axiomatise - and then, later, show you an axiomatisation, and show how the principles he's been using appear in the axiomatisation.

(I know you don't say this, but it's worth emphasising that that ZFC does very little to justify the existence of infinite sets; one of its axioms is the axiom of infinity, which basically just says that there's a set containing infinitely many objects. Remove it, and the remaining theory is compatible with there being only finite sets. So it's not as if the axiomatisation does much to help us explain why infinite sets exist. That they do exist is just pretty much assumed, and the assumption doesn't go away and isn't explained by anything deeper in the axiomatisation.)

I didn't understand your worry about the ordinal construction. In the formulations of ZFC that I can recall, there is no explicit mention of the ordinals. What there are, are certain axioms or principles telling you what sets exist, or don't exist. Axioms like: if a and b exist, their union exists; if a is a set, and P is a property, then the set of things that are members of a and satisfy P exist; if a is a set, then all the subsets of a form a set; an infinite set exists; there's no set containing a set containing a set...ad infinitum (Foundation). From these, and other, axioms, the ordinals can be defined. From these, it's possible to show there is a mapping from sets to ordinals which can then be called the rank of the ordinal. Does this speak to your worry?

If you have enough sets with enough structure, you can start modelling other things. And it turns out that a lot of things in mathematics and logic can be modeled in set-theory. So chains of definitions start appearing: an ordered pair <a b> is defined as {a {a b}} (this definition is not unique - there are many equivalent ones). A function is defined as a set of ordered pairs. The words of a language can be identified with arbitrarily chosen sets; sentences with certain sequences of words; proofs with certain sequences of sentences; the definitions are long, ugly and hack-like - but they can be done; proof theory and model theory can all be done using sets and properties of sets. The fact that certain languages exist can then be done by proving the existence of the relevant languages. And so on. This is the way in which things are built up in set-theory.

Of course, all of these constructions depend upon the axioms. And the axioms - the axiom of infinity, the axiom of choice - receive no further justification from within set-theory. If you want to talk about their justification, then either we turn to intuition and examples to try and convince you that the relevant axiom holds, or we shrug our shoulders and say that further justification isn't possible or relevant, that this is just the game of set-theory.

This probably won't satisfy you - there's no justification from computability theory, from finite sets, or from languages. But justifying an axiom is essentially a frustrating business - on some points of view, axioms are the bedrock.

 

[ontologic]

Yossell, I suppose what I initially wrote was not very well worded. To be honest, it was done a bit too hastily.

My apologies for the ambiguities - again, I am almost completely new to studying rigorous foundations of mathematics, and part of the issue is that I need some sort of psychological crutch for this topic. That isn't the case for, say, Hilbert spaces - they do "actually" exist, in that they are connected to quantum mechanics, say; or that they rise from considering a set of functions as a space.

I think I see where the flaw in my train of thought was. The presentation in the book had led me to believe that the notion of language was somehow more primitive than that of the sets; referencing Cohen's book on the continuum hypothesis (which is actually mostly predicate logic and set theory) clarified this issue. So I suppose the primitive undefined notions are sets, and the axioms (I guess either ZFC or NBG) are used to justify every other construction? Is the von Neumann Universe something that just happens to be constructed from set theory after a sufficient axiomatic system has been laid down? (Perhaps this is a point of contention between formalists and realists?)

Also, I understand that ZFC isn't guaranteed to be consistent, but I was under the impression that having a system that was at least thought to be fairly secure was better that just using plain old naive set theory, which is known to be inconsistent. My concern with infinite sets was that I thought the idea was to proceed in a constructive, finitist way until the idea of a language was well-defined enough to proceed to sets - but I suppose it was a silly mistake on my part; the term "well-defined" probably has no meaning unless sets were axiomatized, anyway.

I still have a few questions, though they are somewhat unrelated; first of all, why is it that analysis requires a second-order language? In what sense does it "require" a second order language? Secondly, I still don't quite understand the notion of "class" in ZFC. In von Neumann-Goedel-Bernays, they're treated formally. In Zermelo-Fraenkel, they're treated "informally," via an equivalence class determined by a formula. What exactly doe the term "equivalence class" mean here? Certainly the equivalence class can't be a set or else the equivalence class defined by the formula "x=x" will lead to a contradiction, and it surely can't be a class since that's undefined in ZFC. (Perhaps this is a moot question, since in principle we can just equivalently use formal classes in NGB.) I'm sorry if these questions seem a bit ignorant, but my intuition just does not work at all at this level - it's, erm, too "foundational" for me to think straight until I get used to it.

Thanks for responding. I really appreciate it. This is my first foray into Foundations of Math, and I suppose I'm just not used to the idea of working at the "bedrock" of mathematics.

 

[yossell]

Hi Ontologic

My apologies for the ambiguities

What you wrote was fine! I was just trying to be very careful in my responses and trying to avoid ambiguities. Misunderstandings that take seconds to clear up in face to face discussions can linger for days in the forums.

That isn't the case for, say, Hilbert spaces - they do "actually" exist, in that they are connected to quantum mechanics, say;

A lot of people get irritated with set-theory because it's so far removed from concrete applications. And that's fine - different people get different things out of set-theory. Hilbert spaces are also pretty abstract too.

Many think set-theory no longer has a point. The Russell-Frege attempt to derive mathematics from logic has failed, some of the axioms of set-theory are harder to justify, less plausible than the axioms of arithmetic - so, other than the fact that you can `do' all maths in set-theory, in what sense is it a real foundation for other mathematics?

The presentation in the book had led me to believe that the notion of language was somehow more primitive than that of the sets;

That's interesting. It's not beyond imagination that one might begin with language and a theory and the notion of a model, and then present set-theory by claiming that certain theories have a certain kind of model. Some extensions of set-theory have that flavour.

However, there's sometimes another worry people have which is that as set-theory is presented axiomatically needs language to present the axioms. It *can* seem that this somehow puts language first - until you realize that any theory requires language for its expression, but that the content of the theory needn't be about language at all.

So I suppose the primitive undefined notions are sets

also the relational `x is a member of y' is a primitive of the theory - in fact, it's often assumed that the quantifiers are restricted to the sets, the predicate for membership is the only non-logical primitive of the theory.

and the axioms (I guess either ZFC or NBG) are used to justify every other construction?

That's my understanding - certainly, to 'prove' the existence or non-existence of the relevant set.

Is the von Neumann Universe something that just happens to be constructed from set theory after a sufficient axiomatic system has been laid down? (Perhaps this is a point of contention between formalists and realists?)

I'm not quite sure what you're saying here. Given the axioms of set-theory, think of them as describing a mathematical universe: the sets; given the axioms, we see that there are such things as ordinals, well founded linearly ordered sets; given the axioms, we can define a transfinite sequence P(0), PP(0)...UP^n(0), P(UP^n0); given the axioms, we can define the rank of a set, something that associates with each set an ordinal number, which can then be thought of as the first place that set appears in the sequence defined by the earlier sequence. It turns out that every set appears in this sequence.

But once you have the axioms, the von Neumann universe is just there in the sense that: the truth of the axioms implies the existence of the universe - I don't see them as in any sense being a further construction.

However, I believe there other axiom systems for set-theory which essentially embody the idea of the von Nuemann hierarchy from the outset - more or less explicitly describe the ranking of sets via repeated use of the powerset operation - and then go on to show that the standard axioms follow. I think a book on set theory by Michael Potter takes this approach and I think it's due to Dana Scott originally.

Also, I understand that ZFC isn't guaranteed to be consistent, but I was under the impression that having a system that was at least thought to be fairly secure was better that just using plain old naive set theory, which is known to be inconsistent.

Agreed - but I was just wondering whether he really was using naive set-theory - did he really use the principle that, to every property, there exists set containing precisely those things. That would be bad. But if his use of naive set theory is just the use of certain principles involving sets that seem plausible and natural, then I have no objection. I have no objection because exactly such intuitions are used to justify or motivate the axioms.

My concern with infinite sets was that I thought the idea was to proceed in a constructive, finitist way until the idea of a language was well-defined enough to proceed to sets - but I suppose it was a silly mistake on my part; the term "well-defined" probably has no meaning unless sets were axiomatized, anyway.

No, no - this is an interesting idea - many people are unhappy with how much set-theory assumes and if we could do it for less we should.

first of all, why is it that analysis requires a second-order language? In what sense does it "require" a second order language?

Actually, this is a bit of a bone of contention, and partly depends upon how these ideas of first order and second order are understood. But it takes a bit of explaining.

Here's a rough guide, there are many caveats, but hopefully, it'll give you the idea.

Consider the set of natural numbers. By Cantor, the set of all subsets of this set is not denumerable. But now consider a first order set-theory. Look at the comprehension schema: this schema does the work of explicitly telling us which subsets of a given set exist. As a schema, and as our language contains only countably many predicates, there aren't enough instances of the comprehension axiom to say explicitly, for each of the non-denumerably many subsets of the numbers, that *that* subset exists. So there are models for first order theories which contain an infinite set, but contain only denumerably many subsets of this set. So the powerset, in such a model, is woefully lacking: it's denumerable.

In first order languages, this weakness turns out to be irredeemable. Second order languages respond effectively by treating `all the subsets of the domain' as a primitive: it really picks out ALL the subsets of the domain, definable or not. Analysis, being the study of the real line, should at least not have models that contain only denumerably many objects.

Now - whether this is really a fault of the first order LANGUAGE, or whether this is an aspect of the MODEL THEORY for first order languages, is a matter of debate. What's of interest for everyone though is that the resolution seems to be by taking the notion of ALL SUBSETS as a primitive - if so, that does begin to make set-theory a little more interesting, and relevant to other mathematics.

Secondly, I still don't quite understand the notion of "class" in ZFC.

I think this thing bothers everyone, and, if it doesn't, it should, at least a little. The problem is that, once you see Russell's paradox, you see that not every property corresponds to a set. But without that, it's hard to motivate what forms a set and what doesn't. Every system is a bit artificial in this respect. I don't think classes really exist in ZFC - either you can suppose that, we, stepping outside ZFC, can talk about the class of ordinals that ZFC can't recognise, or you take talk of a class, such as the ordinals, to be paraphrased away in terms of predicate - the predicate 'x is an ordinal' is ok, and try and say things like 'x is an ordinal then x...'

All in all, your questions seem good, so as long as it doesn't interfere with your ability to do the mathematics, I wouldn't worry too much about the fact that you have them. Certainly, as far as I know, they don't have obvious straight-forward answers that someone first meeting the course ought to just know.[/QUOTE]

Thanks for responding.

It's good to have a few people around interested in this stuff!