Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Every department of the University has a library and elaborates a catalog with every book in its library. Also, the University has a Central library which receives the catalog from each department.

One day, the librarian of the Central library realized that some catalogs cited themselves, and when the rector of the University noticed this mess he commanded the librarian of the Central library to add a catalog (to the Central library) with every catalog that didn't cite itself. The librarian of the Central library was fired because he couldn't comply with it. Was the librarian incompetent or the rector an insensate person?

I think that (algorithmically) the librarian was incompetent since it is "easy" to notice that one of the cites corresponds with the title of the catalog. However, the problem is set-theory oriented, but I don't get the point. I think that, if $\{b_1,b_2,..., \{b_1,b_2,...,\{b_1,...\}\}\}$ represents a "bad" catalog, it seems that we can't check if the catalog is citing itself since it can't be done in a finite number of steps.

Thanks in advance.

PD: sorry for my poor English.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Suppose that $C$ is a catalogue of all catalogues in the library that do not cite themselves. Does $C$ cite itself?

  • If $C$ does cite itself, it is not a catalogue that does not cite itself, so it should not cite itself.

  • If $C$ does not cite itself, then by definition it should: it’s one of the catalogues that don’t cite themselves.

In short, no such catalogue $C$ can exist, and the rector was demanding the impossible.

This is a slightly disguised version of Russell’s paradox of the set of all sets that do not contain themselves. The catalogues correspond to sets, and the books cited in a catalogue correspond to the elements of that set.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.