Is there a way, using set comprehension, to denote the closure of a set under a particular operation?

For example, if $\mathrm{succ}(n)$ denotes the successor operator $n \mapsto n \cup \{n\}$, then the set $\mathbb N$ of natural numbers can be described as the closure of the set $\{0\}$ under the operator $\mathrm{succ}(n)$. But how can this be written using set comprehension? Would it be something like this?

$$\mathbb N = \{0\} \cup \{\mathrm{succ}(n):n\in\mathbb N\}$$

Or would I have to define, say, \begin{align*} \mathbb N_0 &= \{0\}\\ \mathbb N_i &= \{\mathrm{succ}(n) : n\in \mathbb N_{i-1}\}\\ \mathbb N &= \bigcup_{i = 0}^\infty \mathbb N_i \end{align*}

It seems odd using a union with indices to define the natural numbers though!

  • $\begingroup$ There's an archaic notation I quite like, but it's dated enough that you'd need to explain it if you're going to use it. Given any function $f$ (really any relation), we can use $*f$ to denote its transitive-reflexive closure, that is $*f:=\{\langle x,y\rangle:\forall A(x\in A\wedge \forall z(z\in A\Rightarrow f(z)\in A)\:.\Rightarrow y\in A)\}.$ Then your $f$-closure of a set $U$ is just the image of $U$ under $*f$; hence $\mathbb{N}=*\mathrm{succ}[\{0\}]$. $\endgroup$ – Malice Vidrine Aug 30 '18 at 22:04

If you're just interested in defining $\mathbb{N}$, then the usual way to do it in ZF is via the axiom of infinity. This axiom guarantees the existence of at least one set which is inductive which means that it contains the empty set and all successors of its own elements. $\mathbb{N}$ (usually called $\omega$ in set theory) is then the intersection of all inductive sets, i.e. the smallest inductive set. (You need at least one inductive set in order for the intersection to be well-defined.)

  • $\begingroup$ To be honest, I'm interested in finding a way, using set comprehension, to express the set $\{x, f(x), f(f(x)), f(f(f(x))), \dots\}$. $\endgroup$ – Luke Collins Aug 30 '18 at 15:03
  • 1
    $\begingroup$ In that case I'd define a notation like $f^0(x)=x$ and $f^{n+1}(x)=f(f^n(x))$. You can then write $\{f^n(x) : x \in \mathbb{N}\}$. $\endgroup$ – Frunobulax Aug 30 '18 at 15:06
  • $\begingroup$ Thanks! Poor choice of example on my part perhaps, since $\mathbb N$ is defined axiomatically $\endgroup$ – Luke Collins Aug 30 '18 at 15:13

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.