The axiom of foundation and hereditarily finite sets

151 Views Asked by At

I've been trying to understand the axiom of foundation, and I came up with this question, I hope it's correctly formulated.

Let $R_{i} = \left \{ i \right \}$ and $S = \left \{ R_{i} \right \}_{i\in [a,m_{0}]}$. Let $m_{n+1}=\frac{a+m_{n}}{2}$ so $m_{n+1}$ is the midpoint between $a$ and $m_{n}$ and define sets $C_{ni}$ recursively as:

$C_{1i} = \left \{ R_{i}, R_{i+m_{1}} \right \}$ for $i\in [a,m_{1}]$, and

$C_{(n+1)i} = \left \{ C_{ni}, C_{n(i+m_{n})} \right \}$ for $i\in [a,m_{n}]$

Now let $L_{a}=\left \{ C_{na}:n\in \mathbb{N} \right \}$ and define an ordering on $L$ as $C_{xa}\leq C_{ya}$ if $x\leq y$ in $\mathbb{N}$. Now define:

$C_{\omega a}= \sup_{n \in \omega } L$

Is $C_{\omega a}$ a set? I think it's not due to the axiom of foundation, but I'm not sure, hence the question.

Another question I have is: If we define an operator $\square$ recursively as:

$\square C_{1i}= \left \{ R_{i} \cup R_{i+m_{1}}\right \}$ for $i\in [a,m_{1}]$, and

$\square C_{(n+1)i}= \left \{ \square C_{ni} \cup \square C_{n(i+m_{n})}\right \}$ for $i\in [a,m_{n}]$

If $C_{\omega a}$ is a set, then does $\square C_{\omega a}=S$?

And if $C_{\omega a}$ isn't a set, does that mean that there are no hereditarily finite set s.t. the bottom of a $\in$ chain ends with all the elements of an interval of real numbers? And would this be a result of the axiom of foundation?

1

There are 1 best solutions below

2
On

If I'm understanding your construction correctly, $C_{\omega a}$ is certainly a set. The usage of $\sup$ here is strange - I assume you just mean "union". Otherwise, $C_{\omega a}$ doesn't exist at all - there is no upper bound in $L$ of $L$.

But assuming you mean $\sup$ in the same sense as is used for ordinals - so that $\sup L$ is really the union of all of the members of $L$ - then it's still a set. It's just a set of various $C_{ni}$. Note that the "towers" in it are arbitrarily tall - there are chains of $C$'s contained in other $C$'s of greater and greater lengths - but there are no downwards infinite regressions. The Axiom of Foundation prohibits a situation like having $\cdots \in C_{ni_2} \in C_{ni_1} \in C_{ni_0}$, not the other way around. And no member of $C_{\omega a}$ begins such a chain.