🚀 go-pugleaf

In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>Randall Holmes - a question.  You say that it is a *theorem* of ZF that
>
>   "for any set x, for some ordinal a, x E V(a)" .
>
>[where V(a) is defined by  V(0) = {}
>                           V(a+1) = P{V{a}}
>                           V(L) = U{a < L}[V(a)] (L a limit ordinal). ]
>
>Is this really true ? Surely not. The collection of V's is a model for ZF, yes.
>But the above isn't a theorem, is it? 
>I expect it *is* a theorem of ZF+AxFndtn.

I'm sure that's what Randall meant.  You can't rank sets without FA.
If you weaken FA to AFA you have counterexamples to the above like
Omega = {Omega}, to which the above definition cannot assign any
ordinal in a way that satisfies these equations.  (Consider the least
ordinal a for which Omega E V{a}.  Clearly a is not 0.  Since Omega has
only one element a cannot be a limit ordinal.  So a is a successor
ordinal, call it b+1.  But then Omega is a subset of V{b}, whence
Omega's only element, Omega, is an element of V{b} and hence of rank
less than a, contradiction.)

Conversely, once you have FA you can prove the above theorem by
assigning a rank to each set by the following informally described
procedure.  To rank set x, assign ranks to its elements.  This
recursive procedure is well-defined because there are no infinite
descending membership chains.  Now take the rank of x to be the least
ordinal strictly greater than the rank of any element of x.  This rank
will be 0 when x is empty, a successor ordinal when x contains an
element of rank maximal among its siblings, and otherwise a limit
ordinal.

This informal procedure can be made rigorous as follows.  The form of
FA that I find most useful for these purposes is the Axiom Schema of
Restriction, namely one axiom for every ZF formula phi(x) with one free
variable x.  The axiom says that either phi holds of no set, or there
exists a set y for which phi holds of y but of none of its members.

So now take phi(x) to be "for every ordinal a, x is not in V(a)".  If
phi holds of no set we are done.  Otherwise by restriction there is a
set y for which phi(y) holds but for all members z of y, phi(z) is
false.  If y is empty this contradicts the first equation defining V.
If y is nonempty then all its members have ranks.  If there is a
maximum rank b of those members then y is a subset of V(b), hence an
element of V(b+1) by the second equation.  If there is no maximum rank
then let b be the union of these ranks, necessarily a limit ordinal.
Then y is an element of V(b) by the third equation, and we are done.
(And hence of course phi holds of no sets.)
-- 
Vaughan Pratt				There's no truth in logic, son.

In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:

BT:
>>>A = { 1 , { 2 , { 3 , { 4 , {.....}}}}} . Such a set seems very well defined

VP:
>>If you are comfortable with A, you should not mind
>>B = { 1 , { 1 , { 1 , { 1 , {.....}}}}} .

BT:
>Yes, I *do* mind B, for the very reason you suggest; that it is a member of
>itself. There is, I agree, not a lot of difference, on the face of it, between
>B and A.  I'm not *devoted* to A. It *does* have a slightly fishy look. 
>Even a hereditarily fishy look.  :)    That's why I put out my request.
>Let me repeat it...
>
>REQUEST: Can B above, be obtained from A above, by ZF methods.
>~~~~~~~  I don't think Replacement can achieve it, but I'm open to correction.
>Any ideas, anyone ?

Bill, Vaughan, -- look at the proof I sent you.  Better yet, here it
is.  This is some material from my set theory notes, which should work
as is in amslatex:

\begin{document}

\theoremstyle{plain}

%{\theorembodyfont{\normalshape} \newtheorem{problem}{Problem}[section]}
{\theorembodyfont{\normalshape} \newtheorem{problem}{Problem}}
%{\theorembodyfont{\normalshape} \newtheorem{theorem}{Theorem}[section]}
{\theorembodyfont{\normalshape} \newtheorem{theorem}{Theorem}}
{\theorembodyfont{\normalshape} \newtheor% sqdots.sty
% Author: R. A. Riemenschneider (rar@ads.com)

\newdimen\sqdotdim
\sqdotdim=.35ex         % Adjust this number to change the size of the dots
% Adjust this number to change the size of the dots

\def\sqdot{{}\mathop{
   \vrule width\sqdotdim height\sqdotdim depth0ex}{}}

\def\sqdots{\sqdot\llap{\raise3\sqdotdim\hbox{$\sqdot$}}}

em{lemma}[theorem]{Lemma}}
{\newtheorem{axiom}{Axiom}}
{\theorembodyfont{\normalshape} \newtheorem{remark}{Remark}}
%{\theorembodyfont{\normalshape} \newtheorem{defn}{Definition}[section]}
{\theorembodyfont{\normalshape} \newtheorem{defn}{Definition}}
%{\theorembodyfont{\normalshape} \newtheorem{prop}{Proposition}[section]}
{\theorembodyfont{\normalshape} \newtheorem{prop}{Proposition}}
{\theorembodyfont{\normalshape} \newtheorem{cor}[theorem]{Corollary}}
\newenvironment{proof}{\noindent \rm {\sc Proof:\\}}{\quad $\blacksquare$}
%\newenvironment{proof}{\noindent \rm {\sc Proof:\\}}{$\Box$ \vspace{2 ex}}
%\newenvironment{defn}{\noindent \rm {\sc Definition:\\}}{$\Box$ \vspace{2 ex}}



\def\bexists{\boldsymbol{\exists}}
\def\boldexists{\boldsymbol{\exists}}
\def\varexists#1#2{\operatornamewithlimits{(\boldsymbol\exists \hbox{$#1$})}_{#\
2}}

\def\bsupset{\boldsymbol{\supset}}
\def\boldsupset{\boldsymbol{\supset}}
\def\varsupset#1{\operatornamewithlimits{\boldsymbol\supset}_{#1}}

\def\bequiv{\boldsymbol{\equiv}}
\def\boldequiv{\boldsymbol{\equiv}}
\def\varequiv#1{\operatornamewithlimits{\boldsymbol\equiv}_{#1}}


\begin{axiom}
\label{foundation}
% Fraenkel \& Bar-Hillel, p.88
Foundation.
If $x$ is non-empty, then it contains a member which is disjoint from $x$,
i.e.~a member $y$ with no members common to $x$ and $y$:
$$\varexists{u}{}(u \in x) \varsupset{x} \varexists{y}{y \in x}
\varforall{z}{z \in x} \sqdot z \not\in y.$$
\end{axiom}

\begin{remark}
\label{inmin}
As a consequence of the Axiom~\ref{foundation}, we will obtain that if
there is some element $x$ which fulfils $\cal{P}(x)$ then there is an
$\in$-minimal element $u$ which fulfils $\cal{P}(x)$, i.e., $u$ fulfils
$\cal{P}(x)$ but none of its members fulfils $\cal{P}(x)$.  In symbols,
$$\varforall{z_1}{} \ldots \varforall{z_n}{} \sqdot \varexists{x}{} \phi(x)
\boldsupset \varexists{x}{} \sqdot \phi(x) \sqdot (y \in x \boldequiv_y \neg
\phi(y)).$$
This axiom is our second example (after the Axiom~\ref{comprehension}
(Comprehension)) of a principle that stipulates that all sets have certain
properties; all the other axioms can be interpreted as weakened instances
of the comprehension scheme embodied in Proposition~\ref{comprehension}.
\end{remark}

\begin{problem}
\label{hw1}
% homework #1
Show that there are no finite $\in$-cycles.

\begin{proof}
Assume there exists a cycle of length $n$, that is, $x_1 \in x_2 \in
\ldots \in x_n \in x_1$.  Let $y = \{ x_1, x_2, \ldots, x_n \}$, which
exists by iterated application of the Pairing and Union Axioms.  Consider
an arbitrary $x_i\in y$, $1\leq i\leq n$; then, if $i > 1$, we have that
$x_{i-1} \in x_i \cap y$; otherwise, if $i=1$, we have that $x_n\in x_i
\cap y$.  Hence the condition of Axiom~\ref{foundation} (Foundation) is
violated.

Alternatively, $y$ fails to satisfy the condition of Remark~\ref{inmin},
since there is no $\in$-minimal set which satisfies the property $(\lambda
x)\sqdot x \in y$.
\end{proof}
\end{problem}

\end{document}

Now, showing that 

A = { 1 , { 2 , { 3 , { 4 , {.....}}}}}

is *not* a set in a well-founded theory is left as an exercise for the
reader.  However, if your theory has no equivalent of the axiom of
foundation (a.k.a. regularity), then, given a suitable comprehension
schema guaranteeing the existence of A, you can obtain

B = { 1 , { 1 , { 1 , { 1 , {.....}}}}}

by Replacement with transfinite recursion.  I think.  Look at Aczel to
make sure.

BT:
>Randall Holmes - a question.  You say that it is a *theorem* of ZF that
>
>   "for any set x, for some ordinal a, x E V(a)" .
>
>[where V(a) is defined by  V(0) = {}
>                           V(a+1) = P{V{a}}
>                           V(L) = U{a < L}[V(a)] (L a limit ordinal). ]
>
>Is this really true ? Surely not. The collection of V's is a model for ZF, yes.
>But the above isn't a theorem, is it? 
>I expect it *is* a theorem of ZF+AxFndtn.
>
>Can you confirm this point please; and give a reference, if you still say
>it's a theorem of ZF only?

"ZF only" is conventionally taken to include Foundation.

Here is some more stuff:

\begin{defn}
\label{R}
\label{wellfounded}
% F&B, p.93-4, Jech, p.21, Levy, p.68
We define the function $R$ on all ordinals by transfinite recursion as
follows:
\begin{itemize}
\item[\I] $R(0) = \emptyset$,
\item[\II] $\varforall{\alpha}{}\sqdot R(S(\alpha)) = \f{P}(R(\alpha))$,
\item[\III] $\varforall{\lambda}{\Lim{\lambda}}\sqdot R(\lambda) =
\bigcup_{\beta < \alpha} R(\beta)$.
\end{itemize}
A set $x$ is said to be {\it well-founded} if it is a member (or a subset)
of $R(\alpha)$ for some ordinal $\alpha$.  The rank $\rho(x)$, or $\rank
(x)$, of a well-founded set $x$ is the least ordinal $\beta$ such that $x
\subseteq R(\beta)$: $$\rho (x) \Df (\mu \beta) \sqdot \Ord (\beta) \sqdot x
\subseteq R(\beta).$$
\end{defn}

(You may have to make some obvious adjustments to compile this.)

Being that an equivalent form of the Axiom of Foundation is that all
sets are well-founded, under these definitions each set has a rank.

>------------------------------------------------------------------------------
>            Bill Taylor              wft@math.canterbury.ac.nz
>------------------------------------------------------------------------------
>                   I think, therefore I am; (I think).
>------------------------------------------------------------------------------

cordially,
mikhail zeleny@husc.harvard.edu
" -- I shall speak bluntly, because life is short."

In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz 
(Bill Taylor) writes:

   >A = { 1 , { 2 , { 3 , { 4 , {.....}}}}}
   >B = { 1 , { 1 , { 1 , { 1 , {.....}}}}}
   >Can B above, be obtained from A above, by ZF methods.

  The question is vague in several respects, but the most likely
answer is no. A, to put this into formal ZF terms, is, let us say, the
range of a function f defined on the natural numbers, where
f(n)={n,f(n+1)} for all n.  Assuming the existence of such a function
in ZF (without foundation) does not in any obvious way (and hence not
at all, by the argument from experience) imply the existence of a set
x such that x={1,x}.  In particular, Replacement by itself is no help
since to get x using replacement, we need to define a function h by
h(n)=G(f(n)), where G({a,b})={1,G(b)}, and there is no way of defining
G in ZF (without foundation) so that this is provable. In other words:
Replacement allows us to make infinite "substitutions" in sets, but to
make infinite substitutions in non-well-founded sets we need a
corresponding non-well-founded recursion principle.

  Of course, even if this is correct it doesn't follow that accepting
A and rejecting B makes any sense. Or in other words: it doesn't help
explain what mathematical objects, if any, you have in mind.

In article <TORKEL.92Nov5103134@isis.sics.se> torkel@sics.se (Torkel Franzen)
 writes:

   >the range of a function f defined on the natural numbers, where
   >f(n)={n,f(n+1)} for all n.

  Not the range, of course, but f(1).

In article <1992Nov5.044052.12870@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>>Randall Holmes - a question.  You say that it is a *theorem* of ZF that
>>
>>   "for any set x, for some ordinal a, x E V(a)" .
>>
>>[where V(a) is defined by  V(0) = {}
>>                           V(a+1) = P{V{a}}
>>                           V(L) = U{a < L}[V(a)] (L a limit ordinal). ]
>>
>>Is this really true ? Surely not. The collection of V's is a model for ZF, yes.
>>But the above isn't a theorem, is it? 
>>I expect it *is* a theorem of ZF+AxFndtn.
>
>I'm sure that's what Randall meant.

I meant exactly what I said.  Foundation is an axiom of ZF.  The
system without Foundation is called ZF-.

  You can't rank sets without FA.

This is true (you can't rank sets in ZFC-).  But you _can_ rank sets
in ZFC- + AFA; you just do it differently.  See below.

>If you weaken FA to AFA you have counterexamples to the above like
>Omega = {Omega}, to which the above definition cannot assign any
>ordinal in a way that satisfies these equations.  (Consider the least
>ordinal a for which Omega E V{a}.  Clearly a is not 0.  Since Omega has
>only one element a cannot be a limit ordinal.  So a is a successor
>ordinal, call it b+1.  But then Omega is a subset of V{b}, whence
>Omega's only element, Omega, is an element of V{b} and hence of rank
>less than a, contradiction.)
>
>Conversely, once you have FA you can prove the above theorem by
>assigning a rank to each set by the following informally described
>procedure.  To rank set x, assign ranks to its elements.  This
>recursive procedure is well-defined because there are no infinite
>descending membership chains.  Now take the rank of x to be the least
>ordinal strictly greater than the rank of any element of x.  This rank
>will be 0 when x is empty, a successor ordinal when x contains an
>element of rank maximal among its siblings, and otherwise a limit
>ordinal.

Here is the informal procedure for ranking sets in AFA.  Rank 0 has
one member, the empty set.  (You need something to start the process).
Once rank a is constructed, rank a+1 consists of all sets A such that
the relation E|TC(A) (membership restricted to the transitive closure
of A) is isomorphic to a graph whose nodes are all of rank a.  The
isomorphism type of E|TC(A) determines A exactly under AFA.  Take
unions of ranks at limit ordinals.  Call rank a H(a).  It is easy to
prove that H(a) and V(a) (the well founded sets of rank a in the usual
sense) have the same cardinality and that H(a) includes V(a) (this is
only for infinite ordinals a; the finite ranks do look different).
This shows that ZFC- + AFA is _not_ significantly different from ZFC;
its universe has the same hierarchical structure, and not very many
sets are added at each level of the hierarchy.

There are ways to destroy the hierarchical structure of the universe
in fragments of ZFC, but you must jettison both Choice and Foundation,
and perhaps add some atoms, in order to do so.  AFA has the same
hierarchy bulding potential as FA, because of its "strong
extensionality" consequences.


>
>This informal procedure can be made rigorous as follows.  The form of
>FA that I find most useful for these purposes is the Axiom Schema of
>Restriction, namely one axiom for every ZF formula phi(x) with one free
>variable x.  The axiom says that either phi holds of no set, or there
>exists a set y for which phi holds of y but of none of its members.
>
>So now take phi(x) to be "for every ordinal a, x is not in V(a)".  If
>phi holds of no set we are done.  Otherwise by restriction there is a
>set y for which phi(y) holds but for all members z of y, phi(z) is
>false.  If y is empty this contradicts the first equation defining V.
>If y is nonempty then all its members have ranks.  If there is a
>maximum rank b of those members then y is a subset of V(b), hence an
>element of V(b+1) by the second equation.  If there is no maximum rank
>then let b be the union of these ranks, necessarily a limit ordinal.
>Then y is an element of V(b) by the third equation, and we are done.
>(And hence of course phi holds of no sets.)
>-- 
>Vaughan Pratt				There's no truth in logic, son.


-- 
The opinions expressed		|     --Sincerely,
above are not the "official"	|     M. Randall Holmes
opinions of any person		|     Math. Dept., Boise State Univ.
or institution.			|     holmes@opal.idbsu.edu

In article <TORKEL.92Nov5103134@isis.sics.se> torkel@sics.se (Torkel Franzen) writes:
>In article <Bx81Ho.9HL@cantua.canterbury.ac.nz> wft@math.canterbury.ac.nz 
>(Bill Taylor) writes:
>
>   >A = { 1 , { 2 , { 3 , { 4 , {.....}}}}}
>   >B = { 1 , { 1 , { 1 , { 1 , {.....}}}}}
>   >Can B above, be obtained from A above, by ZF methods.
>
>  The question is vague in several respects, but the most likely
>answer is no. A, to put this into formal ZF terms, is, let us say, the
>range of a function f defined on the natural numbers, where
>f(n)={n,f(n+1)} for all n.  Assuming the existence of such a function
>in ZF (without foundation) does not in any obvious way (and hence not
>at all, by the argument from experience) imply the existence of a set
>x such that x={1,x}.  In particular, Replacement by itself is no help
>since to get x using replacement, we need to define a function h by
>h(n)=G(f(n)), where G({a,b})={1,G(b)}, and there is no way of defining
>G in ZF (without foundation) so that this is provable. In other words:
>Replacement allows us to make infinite "substitutions" in sets, but to
>make infinite substitutions in non-well-founded sets we need a
>corresponding non-well-founded recursion principle.
>
>  Of course, even if this is correct it doesn't follow that accepting
>A and rejecting B makes any sense. Or in other words: it doesn't help
>explain what mathematical objects, if any, you have in mind.

Neither A nor B can be shown to represent a unique object in ZFC-.
You are being hypnotized by your notation.  

There _can_ be sequences of sets xi and yi such that xi = {i,x[i+1}
and yi = {1,x[i+1]}  in ZFC-.  There can be many of each!  Thus A may
ambiguously denote many objects, and B may denote many objects -- nor
need an object denoted by B be an element of itself (it may contain a
_different_ object of the form B).

Aczel's AFA has a "strong extensionality" consequence which asserts
that there can be at most one object of the form A and at most one
object of the form B, in addition to its "non-well-foundedness"
consequence which asserts that there is at least one of each.

-- 
The opinions expressed		|     --Sincerely,
above are not the "official"	|     M. Randall Holmes
opinions of any person		|     Math. Dept., Boise State Univ.
or institution.			|     holmes@opal.idbsu.edu

In article <1992Nov5.170354.29866@guinness.idbsu.edu> holmes@garnet.idbsu.edu
 (Randall Holmes) writes:

   >Neither A nor B can be shown to represent a unique object in ZFC-.

  Of course not! The question I was commenting on was whether it
is provable in ZF without foundation that if there is a function f
defined on the natural numbers satisfying f(n)={n,f(n+1)}, then there
is a set x such that x={1,x}, and my answer was that in all likelihood
this is not so.