2
$\begingroup$

I am studying set theory, and I have some difficulties in understanding how people define the notion of rank there (I hope, specialists in logic will excuse me for this).

As far as I understand, there are two equivalent ways of defining rank of a set:

  1. Krzysztof Ciesielski in his book Set Theory for the Working Mathematician defines rank by the formula $$ \text{rank}(X)=\min\{A\in\text{Ordinal numbers}: \ X\in V_{A+1}\}, $$ where $V_A$ is what is called cumulative hierarchy.

  2. J.Donald Monk in his Introduction to Set Theory defines rank by the formula $$ \text{rank}(X)=\min\{A\in\text{Ordinal numbers}: \ \forall Y\in X\quad \text{rank}(Y)< A\}. $$

There is no problem for me with the first definition, but I don't understand the second one.

J.D.Monk writes that his definition is justified by the

General recursion principle: each function $F:V\to V$ (where $V$ is the class of all sets) defines a unique function $G:V\to V$ by the formula $$ G(X)=F(G\big|_X),\qquad X\in V $$ (here $G\big|_X$ is the restriction of $G$ on $X$; I simplify a bit Monk's Theorem 13.1).

The problem for me is that I don't understand, which function $F:V\to V$ in these terms defines rank. I would think that Monk has in mind the function $$ F(H)=\min\{A\in\text{Ordinal numbers}: \ \text{Range}(H)\subseteq A\}. $$ But this function is not defined for all $H\in V$, only for those $H$ which have range in the class of all ordinals (I wrote this in one of my previous questions, here).

I suppose, there must be a standard trick, that people use here, but I don't know it. Can anybody clarify me this?

$\endgroup$
  • $\begingroup$ We have to check the hypotheses of Monk's Th.13.1... 1) $R$ must be well-founded: in the def of rank $R$ is $\in$ and it's Ok. $\endgroup$ – Mauro ALLEGRANZA Mar 6 '16 at 14:53
  • $\begingroup$ 2) The field of $\in$ is $V$ and for all $x \in V$ (i.e. in $Fld \in$), $\{ y : y \in x \}$ is a set, and also this is Ok, because not all classes in $V$ are sets, but all classes which belongs to some class are. $\endgroup$ – Mauro ALLEGRANZA Mar 6 '16 at 14:56
  • $\begingroup$ No, that is not all. Monk writes also that $F$ "is a function with the domain $\text{Fld}\ R\times V$". For $R=\in$ we can use my formulation, and in this case $F$ must be a function with the domain $V$. Which function has this domain and defines rank? $\endgroup$ – Sergei Akbarov Mar 6 '16 at 15:00
  • $\begingroup$ It seems to me that we must have: $Gx = min( \alpha, G|_{\{ y:y∈x \}} < \alpha \text { for each } y \in x)$. $\endgroup$ – Mauro ALLEGRANZA Mar 6 '16 at 15:14
  • $\begingroup$ The function $F$ is "min" and of course it depends also on $x$. $\endgroup$ – Mauro ALLEGRANZA Mar 6 '16 at 15:17
2
$\begingroup$

Just define $$F(H)=\min\{A\in\text{Ordinal numbers}: \ \text{Range}(H)\subseteq A\}$$ if $H$ is a function and every value of $H$ is an ordinal number, and $F(H)=\emptyset$ otherwise. By the general recursion principle, you then get a function $G$, and you can prove by $\in$-induction that $G(X)$ is an ordinal for all $X$ and so $G(X)$ is actually always given by the first case in the definition of $F$.

$\endgroup$
  • $\begingroup$ Eric, this is strange for me. If we define $G$ in this way, then it trivially will have range in the class of ordinal numbers. So $\text{Range}(G)\subseteq\text{Ordinal numbers}$ will not give further information. $\endgroup$ – Sergei Akbarov Mar 6 '16 at 20:00
  • 1
    $\begingroup$ If you know the range of $G$ is contained in the ordinals, then you know that for any $X$, the range of $G|_X$ is contained in the ordinals. So $G(X)=F(G|_X)$ is always defined using the first case. $\endgroup$ – Eric Wofsey Mar 6 '16 at 20:08
  • 1
    $\begingroup$ You can prove the two definitions are equal by $\in$-induction. Exactly how the proof goes depends on how $V_A$ is defined. $\endgroup$ – Eric Wofsey Mar 6 '16 at 20:14
  • 1
    $\begingroup$ That never happens because $G|_X$ always actually is an ordinal-valued function. $\endgroup$ – Eric Wofsey Mar 6 '16 at 20:37
  • 1
    $\begingroup$ I don't know of a reference off the top of my head, but it should be pretty straightforward (I wouldn't be surprised if it was an exercise in many books). If you want details, you could ask it as a new question (but be sure to include Ciesielski's definition of $V_A$ and the exact axiomatic system you're working in). $\endgroup$ – Eric Wofsey Mar 6 '16 at 21:00
0
$\begingroup$

Long comment

We have to verify the conditions of Th.13.1.

1) The relation $\in$ is well–founded. and

2) The field of $\in$ is $V$ and, for all $x \in V$ (i.e.$x \in Fld (\in)$): $\{ y : y∈x \}$ is a set.

Now we have to define the function $F$ with domain $Fld (\in) \times V$, i.e. $V \times V$ such that:

$$F(x,u) = \min(\{ \alpha \in OR : u(y) < \alpha, \text { for each }y \in x \})$$

if $u$ is a function whose range is contained in $OR$ and $y = \emptyset$ otherwise.

Then, by recursion, there is a unique function $G$ such that $Dom(G) = Fld(\in)=V$ and for all $x \in V$,

$$Gx = F(x,G|_{\{ y : y \in x \}})$$

$$ρ(x) = \min(\{ \alpha : \rho(y) < \alpha, \text { for each } y \in x \}).$$

$\endgroup$
  • $\begingroup$ Mauro, there must be a simple trick, that explains everything immediately. Or this (second) definition is a "big mistake". :) $\endgroup$ – Sergei Akbarov Mar 6 '16 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.