wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> questions about set theory
        
(Message started by: BenVitale on Mar 15^th, 2008, 2:45pm)

Title: questions about set theory
Post by BenVitale on Mar 15^th, 2008, 2:45pm

It seems that there are combinations that are not sets.

A counting argument shows there are collections of integers that are not sets. If a set is implied by the ZFC axioms, a finite chaine of inference forces that set to exist. Such a chain can be encoded as a finite sequence of numbers, and there are countably many such sequences. Therefore the number of sets implied by our axioms is countable.
However, there are uncountably many collections of integers. Most of these are never described mathematically, i.e. never gathered together into sets.

Yes I know, all ordinals are sets, and there are uncountably many ordinals.

This sounds like a contradiction. Could anyone explain it ?

Title: Re: questions about set theory
Post by Obob on Mar 15^th, 2008, 7:07pm

Before I write this I must say that my set theory is a little bit rusty, so there may be errors in what follows. I think at least the general idea is correct, though.

I think what the issue here is that you are confusing the ZFC axioms for set theory and what a model of the ZFC axioms is. A model of the ZFC axioms is some collection of objects that satisfy the ZFC axioms. A priori sets don't exist "because of the ZFC axioms." Rather, one gives a model for the ZFC axioms where one can do set theory. Then the objects in the model, which we think of as being sets, don't have to exist as a consequence of the axioms. They merely have to satisfy the axioms.

One consequence is that things like ordinals are not automatically sets: an ordinal only becomes a set once we fix a model of ZFC where the ordinal is one of the sets in that model. We cannot, for instance, fix a model where all the ordinals are simultaneously sets: there are just too many ordinals.

It is of course true that all collections of integers are sets, provided we take the colloquial definition of "set."

Title: Re: questions about set theory
Post by Icarus on Mar 16^th, 2008, 11:31am

To expand a little on what Obob said:

In ZFC, any collection of integers is a set, because the integers themselves form a set. What you have demonstrated is not that the sets of integers are countable, but rather that the sets we can explicitly identify are countable. For the remaining sets we cannot ever express an exact definition. But even unnamed, they still exist, as the theory demands this.

We see a similar (indeed, related) situation in writing down real numbers. It is impossible to actually write out an infinite expression. Therefore, the only real numbers we can explicitly write down are those that can be expressed in a finite number of symbols. This obviously includes all rationals, and it isn't hard to see that it includes all algebraics. It even includes some transcendentals, such as e or http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif, for which we have introduced other symbolisms. But no matter how many such symbolisms we introduce, we can never express more than a countable number of them, which means that almost all real numbers can never be explicitly expressed. But this does not mean that the real numbers are countable, as Cantor showed.

The fact that only countably many sets of positive integers can be explicitly expressed, while uncountably many such sets exist, is key to Godel's incompleteness theorem.

Title: Re: questions about set theory
Post by Eigenray on Mar 16^th, 2008, 12:52pm

In ZFC, we have the powerset http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/scrp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif). So any subset of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif is a set. But this is a tautology!

By the axiom of comprehension, the integers satisfying any given definable property also form a set. But if a "subset" is undefinable, how do we know it actually exists?

Assuming ZFC is consistent, there exists a countable model of ZFC. Within this model, we can prove http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/scrp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif) is uncountable. But that just means that the model doesn't contain any bijection between http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/scrp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif), even though we can find one outside the model. That is, from outside the model, we can see that the version of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/scrp.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif) in the model is countable, but a person 'inside the model' couldn't.

Note that, from outside the model, we know there are uncountably many subsets of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif. We also know, from outside the model, that the model is countable. Therefore, from outside the model, we know that the model must be missing some subsets of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif. But the model doesn't know this! Within the model, every axiom of ZFC is satisfied. So any subset of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbn.gif whose existence is implied by the axioms does exist in the model.

For a simpler example: within any model of ZFC, the universe is always 'too big' to be a set. But from a point of view outside the model, the domain of a model is always a set.

Title: Re: questions about set theory
Post by Obob on Mar 16^th, 2008, 1:00pm

Well said, Icarus and Eigenray. The last point in Eigenray's post really hits home at one of the strangest (and most necessary!) points of set theory.

Title: Re: questions about set theory
Post by BenVitale on Mar 17^th, 2008, 12:34am

Thank you , guys. It's clear now.

Cantor's discovery (set of real numbers being uncountable) raised a question that hasn't been fully answered even today: Is there a "medium" size of infinity—bigger than the natural numbers but smaller than the real numbers? The supposition that nothing is in between the two in size is called the "continuum hypothesis," after the continuum of numbers.
I've heard of a different approach, entirely different from Cantor's, proving that the real numbers aren't countable. It is the method of Matthew H. Baker of the Georgia Institute of Technology in Atlanta.

Is anyone familiar with it?

Title: Re: questions about set theory
Post by Eigenray on Mar 17^th, 2008, 1:09am

Looking at it (available [link=http://www.math.gatech.edu/~mbaker/papers.html]here[/link]), it looks like a special case of the following (taken from Munkres's Topology):

Theorem 27.7: Let X be a nonempty compact Hausdorff space. If X has no isolated points, then X is uncountable.

Let {x₁,...} http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif X be a countable subset. Build a nested sequence of nonempty open sets V₀ = X http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supset.gif V₁ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supset.gif V₂ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supset.gif ...., with the property that x_n is not in the closure of V_n, as follows. Since x_n is not an isolated point, pick y http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif V_n-1, y http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif x_n. By Hausdorfficity, we can find a neighborhood V_n of y disjoint from a neighborhood of x_n.

Now by compactness http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif cl(V_n) must contain a point of X, distinct from any of the x_n.

The relationship is this: Bob chooses b_n such that V_n = (a_n, b_n) doesn't contain s_n, and furthermore, its closure doesn't contain s_n-1. These are nested intervals, and the intersection of the closure contains lim a_n, which can't be any of the s_n.

However, the shortest proof I know is this: if [0,1] were countable, it would have Lebesgue measure 0.

Title: Re: questions about set theory
Post by BenVitale on Mar 17^th, 2008, 1:11am

I've just realized that set theorists are pursuing game theory approaches. They have been pursuing game theory approaches for decades. The axiom in question is the Axiom of Determinacy. I'm not familiar with it, though. I won't be able to discuss it.

Title: Re: questions about set theory
Post by BenVitale on Mar 17^th, 2008, 4:27pm

Baker started by considering a little mathematical game. Let's say that Alice and Bob decide on some subset of the real numbers between 0 and 1. Alice starts by picking any number she likes between 0 and 1, and Bob follows by choosing a number that is bigger than Alice's but still less than 1. Then they take turns picking new numbers that are always between the last two numbers chosen.

If we call Alice's numbers A1, A2, A3, etc., and Bob's B1, B2, B3, etc., we can draw a picture that would look something like this:

|----------|-----|---|---|----|---|---|-------|-----|

0.........A1....A2..A3..A4..B4...B3..B2......B1.....1

Notice that Alice and Bob's picks get closer and closer to each other over time. An important theorem in calculus says that if they were to keep picking numbers this way forever, Alice's numbers would get closer and closer to just one single number, which will be bigger than all the An's and smaller than all the Bn's.

So that brings us to the point of the game. Remember at the beginning that Alice and Bob agreed on some subset of the interval. If the number Alice converges toward is in that subset, Alice wins, and if it's outside, then Bob wins.

Baker found a strategy that Bob can use to win anytime the subset is countable. Bob can make a list of all the numbers in the subset: S1, S2, S3, etc. Bob has to make sure that Alice's numbers can't converge toward any number on that list.

For his first pick, he looks at S1. If S1 is smaller than A1, he doesn't have to worry about Alice's numbers converging toward it, because he knows Alice's numbers have to converge toward something bigger than any of them. So he just picks any number he feels like that is allowed.

If S1 is bigger than A1, he can just pick S1! After all, he also knows Alice's numbers can only converge toward something smaller than all of his numbers. By making each of his choices this way, he can make sure that Alice's numbers can't converge toward any point in the subset.

But then Baker noticed something else. If the subset that Alice and Bob agreed on at the beginning was the entire interval from 0 to 1, Bob obviously couldn't win. But if the subset were countable, Bob could win. So that implies that the whole interval can't be countable.

Baker says his proof doesn't show anything Cantor didn't, but that it's a nice example of how two areas of mathematics that don't seem to have much to do with one another—in this case, game theory and set theory—are in fact tightly linked. Hard problems in mathematics are often solved by bringing together fields of math that seem only distantly related.

Indeed, set theorists are pursuing game theory approaches. "People take some of these games seriously because they can give non-trivial insights into the nature of real numbers," Baker says. "They may be able to shed light on things like the continuum hypothesis."

However, didn't Cohen show that that the continuum hypothesis is independent of the other axioms of Zermelo-Frankel set theory?

Thus, it can be taken as another axiom of set theory or omitted, and the resulting systems will be equally consistent. In this sense, it is like the parallel postulate of geometry.

Moreover, didn't Cohen's results raise the question of whether an axiom should be added to the Zermelo-Frankel axioms to decide the question?

Title: Re: questions about set theory
Post by BenVitale on May 7^th, 2008, 12:05pm

I plan on working through some more model theory, i.e., Hodges shorter model theory and some more recursive functions, i.e., the second half of Roger's theory of rec. functions and effective computability. For the most part, I think I can handle this.
I need a more rigorous knowledge of set theory past naive set theory and the basic ZFC/cardinalities formalization.
I believe I know the equivalent of Halmos' 'Naive Set theory'
I have Jech's third edition, I have only looked at the 71' version, but don't have the 2003 version which is a total rewrite.
I'm not looking for popular reconstructions of set theory, like Potter's set theory or something as slow as "The Joy of Sets". Any recommendations?