Proper Class Equivalences
Adam Burley
I ask this because on page 30 of Godel's 1940 paper (in which he defines NBG) he defines cardinality with the property that every proper class has cardinality equal to the class of all ordinals, which is itself a proper class. This would seem to imply that all proper classes are equivalent, since for sets, a set is equivalent to its cardinality by definition.
I am defining equivalence (or equivalence in size) as there being a twice-unary relation between the two classes. Or as Godel puts it, for classes X and Y, they are equivalent if there exists a Z such that:
1) Z is a relation (i.e. Z is a subset of V^2)
2) Z is twice-unary (i.e. Z is unary (single-valued) and so is its inverse)
3) The domain of Z is X
4) The domain of Z's inverse is Y.
I have read people saying (on the Internet) that you cannot have a relation between proper classes. However this is clearly nonsense - identity on the universe is a valid relation; it just is itself a proper class. I think they are getting confused with "you cannot have a relation between collections of proper classes", because obviously you cannot have a "collection of proper classes" in NBG.
Rupert
Adam Burley wrote:
> In NBG, are all proper classes equivalent?
>
Assuming the axiom of global choice, this is the case.
Adam Burley
> Adam Burley wrote:
> > In NBG, are all proper classes equivalent?
> >
>
> Assuming the axiom of global choice, this is the
> case.
>
Okay, but can we prove it?
The axiom of choice which Godel provides for NBG is that there exists a unary relation A such that for all non-empty sets x, there exists a y in x such that (x,y) is in A.
Or as Godel says, "This is a very strong form of the axiom of choice, since it provides for the simultaneous choice, by a single relation, of an element from each set of the universe under consideration." ("The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory", Kurt Gödel, 1940, p6).
Aatu Koskensilta
> In NBG, are all proper classes equivalent?
That depends on the exact formulation of NBG used. In von Neumann's
original axiomatization the following limitation of size principle is
adopted
A is a set <--> |A| is not |V|
which clearly implies all proper classes are equipollent, and as a
consequence there is a well-ordering of the universe.
In other formulations of NBG it is undecidable whether all proper
classes are equivalent or not. The reason for this discrepancy is that
it makes no difference to provability of sentences that only contain set
variables.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta
>>Adam Burley wrote:
>>
>>>In NBG, are all proper classes equivalent?
>>
>>Assuming the axiom of global choice, this is the
>>case.
>
> Okay, but can we prove it?
By the global axiom of choice every class is equipollent to an initial
segment of ordinals. But all proper initial segments of ordinals are
sets, and thus a proper class must be equipollent to the only improper
initial segment, the whole class of ordinals itself.
Adam Burley
> >>Adam Burley wrote:
> >>
> >>>In NBG, are all proper classes equivalent?
> >>
> >>Assuming the axiom of global choice, this is the
> >>case.
> >
> > Okay, but can we prove it?
>
> By the global axiom of choice every class is
> equipollent to an initial
> segment of ordinals. But all proper initial segments
> of ordinals are
> sets, and thus a proper class must be equipollent to
> the only improper
> initial segment, the whole class of ordinals itself.
I am not entirely sure what is meant by an initial segment of ordinals. I presume that you mean "a class Z of ordinal numbers, such that if X is in Z and Y is in X then Y is in Z". In other words, the segment is of the form {X:X < Y} for some ordinal number Y. Therefore, it is exactly equal to Y, and so is an ordinal number itself.
If this is the case, then why does global choice imply that any class is equipollent to an initial segment? The formulation of the axiom of global choice does not say anything about ordinals.
Aatu Koskensilta
> If this is the case, then why does global choice imply that any class is equipollent to an initial segment? The formulation of the axiom of global choice does not say anything about ordinals.
You can just apply transfinite recursion.
Adam Burley
> > If this is the case, then why does global choice
> imply that any class is equipollent to an initial
> segment? The formulation of the axiom of global
> choice does not say anything about ordinals.
>
> You can just apply transfinite recursion.
Can you explain this to me?
The only time I have ever heard of recursion is in the context of the fact that if A is a class such that it contains the empty set and the successor of every one of its members, then it has the set of all finite ordinals as a subclass (I think this is called the "principle of induction", but I have also heard it called "recursion").
Dave Seaman
I think he meant "transfinite induction" not "transfinite recursion."
Wikipedia has an explanation of the difference between transfinite induction
and ordinary induction. Basically, transfinite induction applies to all
ordinals, not just the finite ones.
--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>
Aatu Koskensilta
>> You can just apply transfinite recursion.
>
> Can you explain this to me?
I had in mind the following argument: given a class A construct a
bijection f: A --> On by repeatedly selecting elements from A.
More explicitly, the situation is as follows. Given global choice there
is a well-ordering of the universe such that every initial segment is a
set. It then follows that the universe is equipollent to On, and since
for every class A |A| >= |On|, we have that |A| = |On|.
Rupert
The difference between recursion and induction is with induction you
prove something, with recursion you are defining something. The
principle of transfinte recursion says if you have a function g, whose
domain is the set of functions whose domain is an ordinal, then there
is a function f with domain On, such that f(alpha)=g(the restriction of
f to alpha) for all alpha. So it says you can define a function on the
ordinals provided you specify each value in terms of previous values.
That's why it's called "definition by recursion".
Herman Rubin
Adam Burley <ajbu...@googlemail.com> wrote:
>> Adam Burley wrote:
>> > If this is the case, then why does global choice
>> imply that any class is equipollent to an initial
>> segment? The formulation of the axiom of global
>> choice does not say anything about ordinals.
Global choice implies any proper class of ordinals is
isomorphic to the class of all ordinals.
If V=L, all proper classes are equipollent. However,
there are models with different forms of AC for classes,
and in these, not all classes are equipollent, even with
AC for sets.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558