Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Rank (exercise in Kunen)

5 views
Skip to first unread message

Norman Megill

unread,
Sep 15, 2006, 7:29:59 AM9/15/06
to
Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.

U=big union, P=power set, u=union, X=cross product,
y^x (where y is a superscript) = mappings from y to x

I have worked out the following:

rank(Ux) = sup(rank(y) s.t. y \in x)
rank(P(x)) = rank(x)+1
rank({x}) = rank(x)+1
rank(xuy) = rank(x) u rank(y)
rank({x,y}) = (rank(x) u rank(y))+1
rank(<x,y>) = (rank(x) u rank(y))+2

but am having trouble with rank(xXy) and rank(y^x).

Thanks for any help.
--
Norm Megill http://public.xdi.org/=nm
(Use this link to contact me; the "From" address is bogus.)

Achim Blumensath

unread,
Sep 15, 2006, 7:41:55 AM9/15/06
to
Hello,

Norman Megill wrote:
> Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
> Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.
>
> U=big union, P=power set, u=union, X=cross product,
> y^x (where y is a superscript) = mappings from y to x
>
> I have worked out the following:
>
> rank(Ux) = sup(rank(y) s.t. y \in x)

This supremum can be expressed in terms of rank(x).

> rank(P(x)) = rank(x)+1
> rank({x}) = rank(x)+1
> rank(xuy) = rank(x) u rank(y)
> rank({x,y}) = (rank(x) u rank(y))+1
> rank(<x,y>) = (rank(x) u rank(y))+2
>
> but am having trouble with rank(xXy) and rank(y^x).

To compute rank(x X y) you can use your result for rank(<a,b>).
Similarly, rank(y^x) can be computed using rank(a X b).

Achim
--
________________________________________________________________________
| \_____/ |
Achim Blumensath \O/ \___/\ |
TU Darmstadt =o= \ /\ \|
www.mathematik.tu-darmstadt.de/~blumensath /"\ o----|
____________________________________________________________________\___|

William Elliot

unread,
Sep 16, 2006, 12:25:11 AM9/16/06
to
On Fri, 15 Sep 2006, Norman Megill wrote:

> Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
> Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.
>
> U=big union, P=power set, u=union, X=cross product,
> y^x (where y is a superscript) = mappings from y to x
>
> I have worked out the following:
>
> rank(Ux) = sup(rank(y) s.t. y \in x)
> rank(P(x)) = rank(x)+1
> rank({x}) = rank(x)+1
> rank(xuy) = rank(x) u rank(y)

You make gibberish.

rank(x v y) = (max{rank(x), rank(y)}

> rank({x,y}) = (rank(x) u rank(y))+1
> rank(<x,y>) = (rank(x) u rank(y))+2
>

Make coherent your gibberish.

> but am having trouble with rank(xXy) and rank(y^x).
>

Hint. xXy = \/{ <a,b> | <a.b> in xXy }

y^x? Do you mean y intersection x or y raised to x?

William Elliot

unread,
Sep 16, 2006, 3:59:03 AM9/16/06
to

On Fri, 15 Sep 2006, William Elliot wrote:
> On Fri, 15 Sep 2006, Norman Megill wrote:
>
Correction and additions made below near end of post.

> > Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
> > Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.
> >
> > U=big union, P=power set, u=union, X=cross product,
> > y^x (where y is a superscript) = mappings from y to x
> >
> > I have worked out the following:
> >
> > rank(Ux) = sup(rank(y) s.t. y \in x)
> > rank(P(x)) = rank(x)+1
> > rank({x}) = rank(x)+1
> > rank(xuy) = rank(x) u rank(y)
>
> You make gibberish.
>

> rank(x \/ y) = max{rank(x), rank(y)}


>
> > rank({x,y}) = (rank(x) u rank(y))+1
> > rank(<x,y>) = (rank(x) u rank(y))+2
> >
> Make coherent your gibberish.
>
> > but am having trouble with rank(xXy) and rank(y^x).
> >
> Hint. xXy = \/{ <a,b> | <a.b> in xXy }

xXy = \/{ {<a,b>} | <a.b> in xXy }

> y^x? Do you mean y intersection x or y raised to x?

rank(y /\ x) = min(rank(y), rank(x))
rank(/\A) = inf{ rank(x) | x in A }

David C. Ullrich

unread,
Sep 16, 2006, 7:16:08 AM9/16/06
to

Really? How do you prove that?

>rank(/\A) = inf{ rank(x) | x in A }

Or that?

************************

David C. Ullrich

William Elliot

unread,
Sep 16, 2006, 7:41:53 AM9/16/06
to
On Sat, 16 Sep 2006, David C. Ullrich wrote:
> <ma...@hevanet.remove.com> wrote:
> >On Fri, 15 Sep 2006, William Elliot wrote:
> >> On Fri, 15 Sep 2006, Norman Megill wrote:
> >>
> >Correction and additions made below near end of post.
> >
> >> > Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
> >> > Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.
> >> >
> >> > U=big union, P=power set, u=union, X=cross product,
> >> > y^x (where y is a superscript) = mappings from y to x
> >> >
> >> > I have worked out the following:
> >> >
> >> > rank(Ux) = sup(rank(y) s.t. y \in x)
> >> > rank(P(x)) = rank(x)+1
> >> > rank({x}) = rank(x)+1
> >> > rank(xuy) = rank(x) u rank(y)
> >>
> >> rank(x \/ y) = max{rank(x), rank(y)}
> >>
> >> > rank({x,y}) = (rank(x) u rank(y))+1
> >> > rank(<x,y>) = (rank(x) u rank(y))+2
> >>
> >> > but am having trouble with rank(xXy) and rank(y^x).
> >> >
> >> Hint. xXy = \/{ <a,b> | <a.b> in xXy }
> >
> > xXy = \/{ {<a,b>} | <a.b> in xXy }
> >
> >> y^x? Do you mean y intersection x or y raised to x?
> >
> >rank(y /\ x) = min(rank(y), rank(x))
>
> Really? How do you prove that?
>
rank(N /\ 2N) = 0 ??

> >rank(/\A) = inf{ rank(x) | x in A }
>
> Or that?
>

rank(S) = sup{ rank(s) | s in S }
Let S = y /\ x or /\A.
rank(nulset) = rank(N /\ 2N) = 0.

William Elliot

unread,
Sep 16, 2006, 8:33:21 AM9/16/06
to

rank(2N+1 /\ 2N) = 0 ??

> > >rank(/\A) = inf{ rank(x) | x in A }
> >
> > Or that?
> >
> rank(S) = sup{ rank(s) | s in S }
> Let S = y /\ x or /\A.
> rank(nulset) = rank(N /\ 2N) = 0.

rank(nulset) = rank(2N+1 /\ 2N) = 0.

Norman Megill

unread,
Sep 17, 2006, 9:40:23 AM9/17/06
to
Achim Blumensath wrote:
> Norman Megill wrote:
> > Exercise 4 of Kunen _Set Theory_ p. 107 asks to compute the ranks of
> > Ux, P(x), {x}, xXy, xuy, {x,y}, <x,y>, and y^x.
> >
> > U=big union, P=power set, u=union, X=cross product,
> > y^x (where y is a superscript) = mappings from y to x
> >
> > I have worked out the following:
> >
> > rank(Ux) = sup(rank(y) s.t. y \in x)
>
> This supremum can be expressed in terms of rank(x).

Good point. I assume you mean rank(Ux)=U rank(x).

> > rank(P(x)) = rank(x)+1
> > rank({x}) = rank(x)+1
> > rank(xuy) = rank(x) u rank(y)
> > rank({x,y}) = (rank(x) u rank(y))+1
> > rank(<x,y>) = (rank(x) u rank(y))+2
> >
> > but am having trouble with rank(xXy) and rank(y^x).
>
> To compute rank(x X y) you can use your result for rank(<a,b>).

I'm not sure what you are suggesting. Of course it will involve the
ordered pair members, but unlike the simple cases above, I don't think
you can just take the sup of the ranks of the ordered pairs and add 1
(unless the cross product is finite). That only shows an upper bound.
(Also, x or y could be 0, which would complicate the final formula
somewhat.)

--
Norm Megill http://public.xdi.org/=nm
(Use this link to contact me; the "From" address is bogus.)

_____________________________________________________________|

Norman Megill

unread,
Sep 17, 2006, 9:51:00 AM9/17/06
to
William Elliot wrote:
> On Fri, 15 Sep 2006, Norman Megill wrote:
[...]

> > rank(xuy) = rank(x) u rank(y)
>
> You make gibberish.
>
> rank(x v y) = (max{rank(x), rank(y)}

The union of two ordinals is their maximum.

[...]


> y^x? Do you mean y intersection x or y raised to x?

All symbols are defined in the 2nd paragraph of my original post.
To repeat:

U=big union, P=power set, u=union, X=cross product,
y^x (where y is a superscript) = mappings from y to x

I recommend that you use these for the purpose of this thread, to
facilitate communication. And it would be helpful to define any new
ones you introduce, since I am not quite understanding your other
responses. Thanks.

David C. Ullrich

unread,
Sep 17, 2006, 10:18:58 AM9/17/06
to

Wow. And you were complaining about the OP writing
gibberish.

Not only is this not a proof that rank(y /\ x) = min(rank(y), rank(x))
it's actually a _counterexample_.

>> > >rank(/\A) = inf{ rank(x) | x in A }
>> >
>> > Or that?
>> >
>> rank(S) = sup{ rank(s) | s in S }
>> Let S = y /\ x or /\A.
>> rank(nulset) = rank(N /\ 2N) = 0.
>
>rank(nulset) = rank(2N+1 /\ 2N) = 0.


************************

David C. Ullrich

William Elliot

unread,
Sep 17, 2006, 10:48:39 PM9/17/06
to
On Sun, 17 Sep 2006, David C. Ullrich wrote:
> <ma...@hevanet.remove.com> wrote:
>
> >> > >> > but am having trouble with rank(xXy) and rank(y^x).
> >> > >> >
> >> > >> Hint. xXy = \/{ <a,b> | <a.b> in xXy }
> >> > >
> >> > > xXy = \/{ {<a,b>} | <a.b> in xXy }
> >> > >
> >> > >> y^x? Do you mean y intersection x or y raised to x?
> >> > >
> >> > >rank(y /\ x) = min(rank(y), rank(x))
> >> >
> >> > Really? How do you prove that?
> >
> >rank(2N+1 /\ 2N) = 0 ??
>
> Wow. And you were complaining about the OP writing gibberish.
>
> Not only is this not a proof that rank(y /\ x) = min(rank(y), rank(x))
> it's actually a _counterexample_.
>
Yup, exactly what the teacher asked. ;-)

William Elliot

unread,
Sep 17, 2006, 10:59:21 PM9/17/06
to
On Sun, 17 Sep 2006, Norman Megill wrote:

> William Elliot wrote:
> > On Fri, 15 Sep 2006, Norman Megill wrote:
> [...]
> > > rank(xuy) = rank(x) u rank(y)
> >
> > You make gibberish.
> >
> > rank(x v y) = (max{rank(x), rank(y)}
>
> The union of two ordinals is their maximum.
>

That's specific to ZFC set theory which isn't the only set theory.

> [...]
> > y^x? Do you mean y intersection x or y raised to x?
>
> All symbols are defined in the 2nd paragraph of my original post.
> To repeat:
>
> U=big union, P=power set, u=union, X=cross product,
> y^x (where y is a superscript) = mappings from y to x
>
> I recommend that you use these for the purpose of this thread, to
> facilitate communication. And it would be helpful to define any new
> ones you introduce, since I am not quite understanding your other
> responses. Thanks.
>

I and others use /\ and \/ for cap and cup, intersection and union
both as A \/ B and \/C, the union of A and B and the collective union
of C. Missed your definition of y^x, some use y ^ x for intersection.

Rank Y^X = sup{ rank(f) | f in Y^X }.
So what's the rank of f:X -> Y ?

David C. Ullrich

unread,
Sep 18, 2006, 7:55:21 AM9/18/06
to
On Sun, 17 Sep 2006 19:48:39 -0700, William Elliot
<ma...@hevanet.remove.com> wrote:

>On Sun, 17 Sep 2006, David C. Ullrich wrote:
>> <ma...@hevanet.remove.com> wrote:
>>
>> >> > >> > but am having trouble with rank(xXy) and rank(y^x).
>> >> > >> >
>> >> > >> Hint. xXy = \/{ <a,b> | <a.b> in xXy }
>> >> > >
>> >> > > xXy = \/{ {<a,b>} | <a.b> in xXy }
>> >> > >
>> >> > >> y^x? Do you mean y intersection x or y raised to x?
>> >> > >
>> >> > >rank(y /\ x) = min(rank(y), rank(x))
>> >> >
>> >> > Really? How do you prove that?
>> >
>> >rank(2N+1 /\ 2N) = 0 ??
>>
>> Wow. And you were complaining about the OP writing gibberish.
>>
>> Not only is this not a proof that rank(y /\ x) = min(rank(y), rank(x))
>> it's actually a _counterexample_.
>>
>Yup, exactly what the teacher asked. ;-)

No, actually it's gibberish.

>> >> > >rank(/\A) = inf{ rank(x) | x in A }
>> >> >
>> >> > Or that?
>> >> >
>> >> rank(S) = sup{ rank(s) | s in S }
>> >> Let S = y /\ x or /\A.
>> >> rank(nulset) = rank(N /\ 2N) = 0.
>> >
>> >rank(nulset) = rank(2N+1 /\ 2N) = 0.
>>


************************

David C. Ullrich

David C. Ullrich

unread,
Sep 18, 2006, 8:00:59 AM9/18/06
to

How do you prove _this_?

(Hint: X = Y = {} is a counterexample.)

>So what's the rank of f:X -> Y ?


************************

David C. Ullrich

William Elliot

unread,
Sep 18, 2006, 8:14:37 AM9/18/06
to
On Mon, 18 Sep 2006, David C. Ullrich wrote:
> <ma...@hevanet.remove.com> wrote:
> >On Sun, 17 Sep 2006, Norman Megill wrote:
> >> William Elliot wrote:
> >> > On Fri, 15 Sep 2006, Norman Megill wrote:

> >> > > rank(xuy) = rank(x) u rank(y)
> >> >

> >> > rank(x v y) = (max{rank(x), rank(y)}
> >>
> >> The union of two ordinals is their maximum.
> >>
> >That's specific to ZFC set theory which isn't the only set theory.
> >

> >> > y^x? Do you mean y intersection x or y raised to x?
> >>
> >> All symbols are defined in the 2nd paragraph of my original post.
> >> To repeat:
> >>
> >> U=big union, P=power set, u=union, X=cross product,
> >> y^x (where y is a superscript) = mappings from y to x
> >>

> >I and others use /\ and \/ for cap and cup, intersection and union
> >both as A \/ B and \/C, the union of A and B and the collective union
> >of C. Missed your definition of y^x, some use y ^ x for intersection.
> >
> >Rank Y^X = sup{ rank(f) | f in Y^X }.
>
> How do you prove _this_?
>
> (Hint: X = Y = {} is a counterexample.)
>

Hm, Y^X = {nulset}. You mean
rank A = sup{ rank(a) | a in A }

is wrong? Ok, let's tinker with it.
rank A = sup{ rank(a) + 1 | a in A }

Norman Megill

unread,
Sep 18, 2006, 3:31:42 PM9/18/06
to
William Elliot wrote:

> rank A = sup{ rank(a) + 1 | a in A }

This is just the definition of rank. The problem asks to compute
rank(xXy) and rank(x^y) in terms of rank(x) and rank(y).

Specifically, for the first problem it is easy to show

rank(x) u rank(y) <= rank(xXy) <= (rank(x) u rank(y))+2

when x and y are not empty, since x u y = UU(xXy) and
xXy subset PP(x u y) (where P = power set). I would like to know
how to tighten these bounds, assuming they can be.

David C. Ullrich

unread,
Sep 19, 2006, 6:21:09 AM9/19/06
to

Or let's not. Why not only answer questions that
we actually know the answer to?

Or at least, when our answer is just a wild guess,
why not _say_ it's just a guess?

> rank A = sup{ rank(a) + 1 | a in A }
>
>> >So what's the rank of f:X -> Y ?
>>


************************

David C. Ullrich

Norman Megill

unread,
Sep 20, 2006, 8:25:01 AM9/20/06
to
I was able to find the rank of cross product, finally:

If xXy=0, then rank(xXy)=0.
Otherwise, if rank(x u y) is a limit ordinal, rank(xXy)=rank(x u y).
Otherwise, rank(xXy)=rank(x u y)+2.

(My proof is rather long, and I don't have time to clean it up and post
it at the moment. Maybe later if anyone other than myself is
interested.)

0 new messages