Set Theory Questions!

sponsoredwalk

Got two questions, the first is on number systems arising out of set theory
& the second is a small one about functions, I've tried to be as clear as
possible but bear with me, the only reason I'm posting this is because I'm
so confused.

I'm trying to get my bearings on the set-theoretic construction of the
natural numbers. Just as I was confused looking at the the way the reals
could be axiomatically defined, or constructed by Cantor or Dedekind, or
thinking that Cauchy, Weierstrass etc... all had different constructions so
now am I going through that with the various explanations of the natural
numbers as originating from set theory.

The Peano axioms can be taken as the starting point, but I found out that
they could be taken as a theorem in set theory so I've been trying to do
that. It seems that one way is to look at the idea of an ordinal which is a
transitive set whose elements are also transitive. But there's also this
idea of equivalence classes that apparently lead to contradictions in ZFC,
also there's this axiom of infinity method in the wiki link I've given below.
Perhaps there's even more, or these are the same in some way I can't
see?

A problem arises for me as I've come to believe that rational numbers are
defined as a set of equivalence classes, but wikipedia says that
equivalence classes are ruled out of axiomatic set theory so what replaces
Q when dealing with ZFC? When you remove equivalence classes from the
picture what defines the rational numbers in ZFC? I'm sure whatever you
do will generalize to the reals.

I think the question could best be put as follows:

Starting from the most fundamentals, i.e. the axioms of a specific model of
set theory, what is the logical & linear progression of topics that leads to
the construction of N, then Z, then Q, then R, then C? It seems to me
that there are at least two possible methods this way, one using Von
Neumann ordinals (with an axiom of infinity?), while the other uses the ideas
of relations/equivalence classes etc... If you know anything about how to
do this & understand the distinctions between the various methods of
doing this could you just let me know, hopefully with a few analogies!

As an aside, I just read earlier that the difference between the Riemann &
Lebesgue integrals can be explained by the analogy of a shop taking in
money, the Riemann integral adds the money up as it comes in all through
the day while the Lebesgue integral seperates the coins out at the end of
the day according to a certain scheme (i.e. the idea of measure).
I'm sure there exists a nice way to picture the two (or more) schemes for
constructing the number systems! (I read this earlier & I had to mention it as it would
just be so helpful! ).

I think equivalence classes originated with Frege & Russell used them but
they run into contradictions which ZFC surmounts but Quine's set theory
removes the contradictions & allows the use of equivalence classes. I'm
sure there is more than just the use of equivalence classes that
distinguishes these two seperate constructions. Is it fair to group this
into Frege/Russell/Quine on one side & ZFC-Neumann on the other?
What about the axiom of infinity description in the wiki link below?
Also, I assume that the construction of the number systems in the
"Elementary Set Theory with a Universal Set" link below is just the
Frege-Quine idea right, I mean it's not another new one is it?

Some links might be helpful:

http://en.wikipedia.org/wiki/Ordinal_number#Definition_of_an_ordinal_as_an_equivalence_class

http://books.google.ie/books?id=FE5cluQ3CE4C&printsec=frontcover#v=onepage&q&f=false

(Page 77, notice at the top of the page they say that ∈ is a "well-founded relation".
My knowledge of Naive set theory tells me that ∈ is one of two undefinable constructs that
you're supposed to take as given (I could quote the sources of this if needed), but here they
call it a relation. Surely they don't mean relation in the subset of the cartesian product
way do they? If it is a relation why would naive set theory call it undefinable when it deals
in defining what relations are???.

http://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers

http://en.wikipedia.org/wiki/Axiom_of_Infinity
Notice here they've used something totally different (I think???) to
construct the natural numbers, the axiom of infinity. There is no
mention of ordinals in this link

http://math.boisestate.edu/~holmes/holmes/head.pdf
Holmes, Randall, 1998. Elementary Set Theory with a Universal Set
Surely not a different construction?

So, that is the current state of my thoughts on this topic, it's taken me a
quite a while to figure this meagre stuff out & to find good sources which
aren't at the graduate level to learn properly. If I hadn't read all this
conflicting stuff I'd be happy to just use the following sources as my
main material:

http://www2.latech.edu/~schroder/fund_videos.htm

link to a great, absolutely amazing looking book!

Ali Nesin Set Theory Notes

Basically if you could help me clean up my thoughts as regards the above
stuff I've written, i.e. 3 different constructions 1) ZFC, 2) Frege
Equivalence Relations, 3) Axiom of Infinity, I could move on to greener
pastures!

---

My second question is brief, just on the topic of a function. First a function
is the idea of y = f(x) in school. Then a function is the same thing with
domains and ranges. Then you see that a function is really a special case
of a mapping f : A --> B |defined by f : a|--> f(a). But the latest thing
I've read is that a function is really a set (A,B,F) which is also written as
((A,B),F) & I assume it's to indicate order, i.e. a Kuratowski ordered pair,
and F is really F ⊆ (A x . This is obviously a relation & it's dictated by
the rule [ ∀ (a ∈ A) ∃ (b ∈ such that (a,b) ∈ F ] ⋀ [(f(a) = b) ⇒ ((a,b) ∈ F)].
I'll admit that's not exactly clear, if it's possible to clean this up & clarify it
please let me know. For example, where has the little f come from? The
general idea here makes a lot of sense & seeing as math is always
employing set theory I wish they'd just use this notation from the
beginning in books.

So the question is, is this the final resting place for the definition of a
function? Could you clean this up for me? Could you give me some
references where this definition is explained more clearly, I can't find
anything other than a mention on wikipedia & the Ali Nesin set theory
notes in the link I've given above.

Fremen

I don't know enough set theory to answer your question well - in fact, I'd be surprised if anyone on boards does. You'll almost certainly get a better response if you copy/paste your question to this website:
http://math.stackexchange.com/

I skimmed the wikipedia article on ordinals. My interpretation isn't that you can't use equivalence classes in ZFC - rather that in ZFC, you can't define an ordinal as the equivalence class of all order-isomorphic sets.
I assume this is because the logic breaks down for much the same reason it does when you talk about the "set of all sets", which doesn't make sense.

I have no idea how one would construct Q from Z without using equivalence classes. I doubt it's possible, actually. The construction of R from Q is quite interesting. One can define an element of R as a partition of Q into two nonempty sets A and B, such that every element of A is less than every element in B.

One can also define R in terms of Cauchy sequences of elements of Q. However, this requires a metric on Q (a metric is an abstration of the notion of distance). The choice of metric d(x,y) = |x-y| is a little arbitrary. If you pick other metrics, you get different systems known as p-adic numbers.

Edit: that's a *very* nice description of Riemann vs. Lebesgue integration!

dabh

sponsoredwalk wrote: »

A problem arises for me as I've come to believe that rational numbers are
defined as a set of equivalence classes, but wikipedia says that
equivalence classes are ruled out of axiomatic set theory so what replaces
Q when dealing with ZFC? When you remove equivalence classes from the
picture what defines the rational numbers in ZFC? I'm sure whatever you
do will generalize to the reals.

I think the question could best be put as follows:
.

I haven't done more than skim portions of the original post. Just focussing in on one of the points I noticed.

And I am no expert in ZFC.

But as I understand it, ZFC does not rule out equivalence classes, as such. You simply cannot use them to arrive at sets you want by defining them as equivalence classes that are defined on some sort of 'set of all sets'. But you are allowed to put an equivalence relation on some well-defined set within the ZFC universe and construct a new set as a set of equivalence classes of elements of the set on which the equivalence relation is defined. If you could not do this then ZFC would fail as a valid abstraction of the procedures and constructions employed in normal mathematical proofs.

In short what you cannot do is the following: define relation ~ on set of all sets, where A ~ B if and only if there is a bijective function from A to B; show that ~ is an equivalence relation; define a cardinal number to be an equivalence class of sets under this equivalence relation. This is not allowed under ZFC because ZFC does not provide a 'set of all sets' on which such an equivalence relation can be defined. You could take a nice large set E that is already known to be well-defined in ZFC, and define the relation ~ on the power set of E, so that two subsets A and B of E satisfy A ~ B if and only if there is a bijective function from A to B. You could then form equivalence classes of subsets of E. This is OK, as far as it goes.

As I understand it, to use equivalence relations within ZFC it would have to be an equivalence relation on some specific set whose existence is a consequence of the ZFC axioms. You could then pass to the set of equivalence classes.

Put another way, ZFC disallows 'skyhooks' but allows 'cranes', to use terminology and a metaphor introduced by Daniel C. Dennett in another context. If you want to show that some set exists within the ZFC universe, you need to build up towards it. ZFC does not have an Axiom of Comprehension: you cannot take a property P and then pass to the set of all sets that have the given property. But you can use the Axiom of Separation as a surgeon's knife to carve sets out of other well-defined sets. And you can use axioms such as the Power Set Axiom to build up bigger, and bigger, and bigger sets out of which you can carve out the set you are after. So if you want a well-defined set whose existence is guaranteed by the ZFC axioms, you have to build up towards it - you can't just carve it out of some universal 'set of all sets', because trying to handle such a 'set of all 'sets' leads to paradoxes such as Russell's Paradox.

So, to get at rational numbers in ZFC you would first build up towards the set Z of integers, then construct from it the set Z^2 of ordered pairs of integers. Then use the Axiom of Separation to arrive at the set, call it X, of all ordered pairs of integers for which the second component is non-zero. Then maybe construct your equivalence relation as a subset of X^2. Then perhaps pass to the power set PX of X whose elements are all the subsets of X. Then perhaps use the Axiom of Separation to carve out of this power set PX the collection of all subsets of X that are equivalence classes, and you have then arrived at a set of equivalence classes of pairs of integers (with second component non-zero) which you can regard as your set Q of natural numbers. In this way you arrive at the set Q by building up towards it, constructing set after set until you arrive at the set you are interested in. This would be a construction by way of equivalence classes that is OK within ZFC.

sponsoredwalk

Yes you're absolutely right, the wikipedia explanation confused me about
that particular point. Thank you for the summary of the construction of Q
via axioms, very helpful :cool:

I'm going to do a good bit of study on Suppes & Enderton & construct the
number systems in the way both books do, compare & contrast the apparent
differences I perceive (which may just be my ignorance) & then
return to answering this question, it seems nobody understands the
distinction I'm asking about & I'd better have full knowledge of at least
one construction before I e-mail someone like Feferman or Suppes.

Incidentally,

• Hatcher, William S., 1982. The Logical Foundations of Mathematics. Pergamon. Derives the Peano axioms (called S) from several axiomatic set theories and from category theory.

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

This book looks like the exact thing I'm looking for, if anyone knows any
way to get that book cheap or on loan please let me know, the best I've
gotten to peering into this book is the following links:


http://www.rbjones.com/rbjpub/philos/bibliog/hatch82.htm
http://bahai-library.com/hatcher_foundations_mathematics

I have only browsed the essay version but I can tell that it doesn't hint
at derivations of the peano axioms from several axiomatic set theories

Fremen

I would advise against studying category theory until you've at least studied some abstract algebra (rings, groups, fields etc). In one sense, category theory is an abstraction of abstract algebra. It's not nicknamed abstract nonsense for nothing...

Fremen

This Mathoverflow link might be relevant to you, sponsoredwalk

http://mathoverflow.net/questions/5499/which-mathematicians-have-influenced-you-the-most/11379#11379

xilog

The most popular way of constructing natural numbers in set theory is using the Von Neumann ordinals.

Under this scheme, each ordinal is the set of its predecessors, so zero is the empty set, the successor of an ordinal x is the set: x union {x}.
The axiom of infinity in ZFC states that there is a set containing zero and closed under successor.
The natural numbers are then the intersection of all such sets.

The idea of using equivalence classes of equipollent (equally sized) sets as cardinal numbers is due to Frege, and cannot be used in a well-founded set theory because these equivalence classes do not exist.

There are other set theories in which this can be done which are not well-founded, Randall Holmes is one of the small band of researchers who work with such set theories, but the vast majority of set theorists work with well-founded set theories and do not use Cantor's conception of cardinal number.

However, many other equivalence classes do exist and it is normal to use equivalence classes of pairs of natural numbers in constructing the rational numbers.

The real numbers can then be obtained from the rational numbers in any of a number of ways, of which probably the most popular is the Dedekind cut, which is a particular kind of set of rationals.

The predominant notion of function in well-founded set theory is simply a set of ordered pairs, called the graph of the function, in which an ordered pair <x,y>
is the set {{x},{x,y}}.
However, for some purposes it is sometimes necessary to have a kind of function in which the domain and codomain are identified separately from the graph of the function, so that a function g:A->B may be represented by a triple <A, g, B>
in which A is the domain, B the codomain and g the graph of the function.
For yet other purposes mathematicians (or more likely logicians or computer scientists) may identify functions with rules giving the value of the function in terms of its argument.

Hatcher82 is one place to look for the story of how to construct the number systems, if you can get it.
If you are computer literate an alternative is to get an interactive proof tool capable of doing mathematics.
Many of these tools start from the core logical system and do all the definitions and proofs necessary to get you into analysis, so you can download one of the tools and see all the detailed definitions and how it does the proofs.

One place to look for such tools is:

http://www.cs.ru.nl/~freek/digimath/index.html

Unfortunately the list is now too long (he used to have a shorter league table).
I should perhaps add that its not easy to get to grips with these systems.

Roger Jones

sponsoredwalk

Thanks a lot Roger, I don't think I will use the computerized methods & will
keep on trying to get Hatcher.

xilog

Here is something slightly easier than getting to grips with a proof tool.

at: http://www.rbjones.com/rbjpub/pp/pptheories.html

There is a complete set of listings of theories which, after the manner of Principia Mathematica, take you from nothing to the theory of real numbers.
All the definitions are listed, and the theorems, but not the proofs.
This is how it is done with the tool ProofPower, which uses the language HOL,
a modern descendent of Russell's theory of types.

The people who actually do the formal derivation of mathematics these days are mostly computer scientists and the innovations in how it is done are to do with getting something usable fast.

In this case the sequence (somewhat simplified) is:

1. Start with an axiom of infinity.
2. Define the natural numbers (positive integers with zero)
3. Define the integers (positive and negative).
4. Go straight to the reals without stopping off at the rationals.

Instead of cuts in the rationals pairs consisting of an integer and a natural number
ordered as if they were representatives of the rationals, and then a cut is taken
in this ordered space to serve as a real number (that's a gross oversimplification).
This saves messing about with the equivalence relations which you need to get
rationals, which is work you don't need to do to get the reals.

There is a paper describing this method of constructing the reals here:
http://www.lemma-one.com/papers/47.pdf
(called "An irrational construction of R from Z")

Roger Jones