In a course on theoretical computer science we have to prove if sets are endless. I have two problems with the exercise:

  • I don't understand exactly, what an endless set is (I find it very hard to understand, maybe because of the "endless")
  • I don't know, how I can prove that the given sets are endless

The definition given is this:

A set $X$ is called endless set, if there is a endless family of sets $\{X_n\}_{n=0}^{\infty}$ with $... \in X_3 \in X_2 \in X_1 \in X_0 \in X$.

Can someone explain in simple words what an endless set is?

  • $\begingroup$ This notion of endlessness essentially means that (if endless sets exist) the element-of relation is not well-founded, i.e. we must be working in a version of set theory which does not satisfy the axiom of regularity. Which axioms are you using? $\endgroup$ – Klaus Draeger Jun 29 '15 at 12:26
  • $\begingroup$ I removed the second question, since we only want one question per post. $\endgroup$ – Raphael Jun 29 '15 at 12:40
  • $\begingroup$ @Raphael: These were closely related questions about the same concept - are we really that strict about this rule? Is this a recent development? $\endgroup$ – Klaus Draeger Jun 29 '15 at 12:58
  • 1
    $\begingroup$ @KlausDraeger Depends. The way I see it, these were not strictly related; one is an understanding question (which we like) and the other a problem dump (which we don't like). Therefore, I chose to remove the part we don't like; it is also probably obsolete once the OP understands the definition (since the exercise is very easy). Note that I adapted the answer, leaving the examples there. The only problem wrong with this question now is that it's a pure mathematics question, and hence offtopic here. $\endgroup$ – Raphael Jun 29 '15 at 14:27
  • 1
    $\begingroup$ @KlausDraeger Regarding your first comment, I think it's unlikely that the OP is familiar with well-foundedness or the axiom of regularity. If they had this kind of penetration of the material, they'd probably not have to ask this question. $\endgroup$ – Raphael Jun 29 '15 at 14:29

Defining endless sets, you probably assume that you don't have the Axiom of regularity.

A set is endless when it doesn't contain only simple elements, it has to contain an other set among his elements, and this other set has again to contain an other set and this third set has to contain an other set, etc..

For example, a set verifying $M = \{M\}$ is endless because it contains an other set ($M$) which contains an other set (still $M$) which contains an other set ($M$), etc.. You can take $X=X_0= X_1= ... = M$ as infinite family.

A counter example is $M = \{42\}$; $M$ doesn't contain any set. $M= \{42, \{12\}\}$ is also a counter example because $M$ contains a set ($\{12\}$) but this set doesn't contain any set.

  • $\begingroup$ I've never heard about the axiom of regularity before, but I think you are right, we not use it for this exercise. But thanks a lot, I think I get it now. $\endgroup$ – mgluesenkamp Jun 29 '15 at 15:35

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.