# Regular sets in set theory

I have come across the following definition in different books on set theory:

A set $x$ is regular iff $(\forall y)(x\in y\implies(\exists w\in y)(w\cap y=\emptyset))$.

I don't grasp this concept. What does it intuitively mean for $x$ to be regular? Considering $y=\{x \}$ it tells me $x\not\in x$ but does it provide any information beyond that?

Also is this related to regular languages in computer science?

A set is regular iff it is the language of a regular expression (alternatively: deterministic finite automaton).

-
It has nothing to do with the definition of regular languages. The term regular is unfortunately overloaded and has many different meanings in mathematics. – J.-E. Pin Feb 21 at 11:42
Intuitively it means that there is no infinite sequence $x_0,x_1,x_2,\dots$ such that $x_0=x$ and $x_{n+1}\in x_n$ for every $n$. – bof Feb 21 at 11:45
And it has nothing to do with regular language, regular polygon, regular topological space, etc. – bof Feb 21 at 11:47
It feel like an awkward name. More standard would have been to call these sets well-founded. – Andrés Caicedo Feb 21 at 13:25
@AndrésCaicedo: I suspect one consideration here is to avoid confusion with sets that are well-founded when seen from the metalevel. – Henning Makholm Feb 21 at 13:27

The term regular comes from the axiom of regularity, which is also known as the axiom of foundations.

The statement means that $\in$ is well-founded with regards to regular sets, which means that we can do induction on the $\in$ relation over all the set.

Intuitively it means that $x\notin x$, since $x\cap\{x\}=\varnothing$ (it has to be, since $x$ is the unique element of $\{x\}$); and that there is no $z$ such that $x\in z\in x$ again, using $\{x,z\}$ to show that. And so on.

There is no real connection to the term regular expression, since we don't require that a set has a definition, or that it can be verified or determined in some way. There is a small connection, though, that having a deterministic verification process can be thought as having some nice well-founded construction.

But this seems contrived, and most likely the term "regular" came from the same place it comes elsewhere in mathematics. These are just the objects that we investigate "regularly".

-
Just to make sure, the axiom of regularity basically says that all sets are regular, right? So in ZF there are no irregular sets? – akkarin Feb 21 at 13:23
@akkarin Right. – Andrés Caicedo Feb 21 at 13:26

No, this has nothing to do with regular languages (and likewise nothing to do with regular cardinals).

As for intuition, I find it much easier to think about what it would mean for a set not to be regular:

A set $x$ is non-regular if there is an $y$ which contains $x$ as an element, such that for every $w\in y$ there is a $z\in w$ that is also in $y$.

This means, in particular, that we can take $w$ to be $x$, and find a chain of elements $$x \ni w_1 \ni w_2 \ni w_3 \ni \cdots$$ where at each step $w_i$ can be chosen to be in $y$, which allows us to continue the chain indefinitely.

So if a set $x$ is not regular, there is a way to construct an infinitely descending $\in$-chain starting from $x$. (This can be carried out inside the set theory itself if we have the Axiom of Choice, and at the metalevel if we have choice there).

Conversely, if $x$ is regular, then there cannot be any infinite chain $$x \ni x_1 \ni x_2 \ni x_3 \ni \cdots$$ -- or at least such a chain cannot be known inside set theory in the form of a function defined on $\omega$ that maps each $i$ to $x_i$ -- because the range of that function would work as an $y$ that certifies $x$ as non-regular.

It is still possible that an element of a model of set theory can be regular, yet there is an infinite chain that we can see at the metalevel, that is, looking at the model from outside. (This will be the case for any model of set theory that contains non-standard integers, for example). But in that case the chain cannot be encoded in toto as an object within the model.

-