Author |
Topic: questions about set theory (Read 890 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
questions about set theory
« on: Mar 15th, 2008, 2:45pm » |
 Quote  Modify
|
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 ?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: questions about set theory
« Reply #1 on: Mar 15th, 2008, 7:07pm » |
Quote Modify
|
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."
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: questions about set theory
« Reply #2 on: Mar 16th, 2008, 11:31am » |
Quote Modify
|
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  , 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: questions about set theory
« Reply #3 on: Mar 16th, 2008, 12:52pm » |
Quote Modify
|
In ZFC, we have the powerset  ( ). So any subset of 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 () is uncountable. But that just means that the model doesn't contain any bijection between and (), even though we can find one outside the model. That is, from outside the model, we can see that the version of () 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 . 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 . But the model doesn't know this! Within the model, every axiom of ZFC is satisfied. So any subset of 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.
|
| « Last Edit: Mar 16th, 2008, 12:54pm by Eigenray » |
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: questions about set theory
« Reply #4 on: Mar 16th, 2008, 1:00pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: questions about set theory
« Reply #5 on: Mar 17th, 2008, 12:34am » |
Quote Modify
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: questions about set theory
« Reply #6 on: Mar 17th, 2008, 1:09am » |
Quote Modify
|
Looking at it (available here), 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 {x1,...}  X be a countable subset. Build a nested sequence of nonempty open sets V0 = X  V1 V2 ...., with the property that xn is not in the closure of Vn, as follows. Since xn is not an isolated point, pick y  Vn-1, y  xn. By Hausdorfficity, we can find a neighborhood Vn of y disjoint from a neighborhood of xn.
Now by compactness  cl(Vn) must contain a point of X, distinct from any of the xn.
The relationship is this: Bob chooses bn such that Vn = (an, bn) doesn't contain sn, and furthermore, its closure doesn't contain sn-1. These are nested intervals, and the intersection of the closure contains lim an, which can't be any of the sn.
However, the shortest proof I know is this: if [0,1] were countable, it would have Lebesgue measure 0.
|
| « Last Edit: Mar 17th, 2008, 1:11am by Eigenray » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: questions about set theory
« Reply #7 on: Mar 17th, 2008, 1:11am » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: questions about set theory
« Reply #8 on: Mar 17th, 2008, 4:27pm » |
Quote Modify
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: questions about set theory
« Reply #9 on: May 7th, 2008, 12:05pm » |
Quote Modify
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print