The paradox of the complete catalogue of all catalogues

Kyriakos

Creator
Joined
Oct 15, 2003
Messages
78,218
Location
The Dream
This is a variation on Russel's (an actually good English philosopher, which is almost a paradox by itself :) ) quite acute comment on the set theory used by Cantor, and (to not sound more pompous than absolutely needed) it states that

"if a set exists for all sets that are not part of themselves (elaboration on that in a bit) then that set can neither be part of itself or not part of itself".

A brief elaboration on that follows:

In Cantor's set theory the sets are either of type X, ie include elements which do not also have the set itself as part of them, or of type Y, ie include elements as well as the actual set including them.
You may ask what a set including its own self can be. A rather direct example i read is of a set that includes all squares which can be formed in a plane. Those squares (unless limited by the definition) are infinite, cause a plane can have countless squares of whatever perimeter. Such a set is not including its own self there, though, cause the set of those squares is obviously something else and not another square on that plane.
By contrast if we name a set as "the set of everything that is not a square on that plane", then the set does indeed also include its own self, for as an object it is not a square on that plane. But so is any other arbitrary thing, eg a human, or a flower, or any triangle on that plane, or any triangle not on that plane, or any square not on that plane, and so on.

Russel noted that it is ambiguous and incomplete to have a notion of a set that collects anything being left out of all other sets in a theory, and thus the theory of sets would not be true to its own system of definition of sets.

In essence the question is one of the vast difference between something "being" something, and something "not being" something, cause in the former case something can be seen as a type or nearing such a type, whereas in the latter case there is (crucially, non trivially) no larger degree of difference in non-being X regardless if you are Y, Z or any infinite variation in between.

What follows is a more descriptive analogous formation of Russel's paradox, titled as the paradox of the complete catalogue of catalogues. Useful to note it was worded in 1908, so a couple of decades prior to Borges' famous short story about a library with infinite volumes of books. :)


Paradox of the complete catalogue of catalogues said:
Suppose that every public library has to compile a catalogue of all its books. Since the catalogue is itself one of the library's books, some librarians include it in the catalogue for completeness; while others leave it out as it being one of the library's books is self-evident.

Now imagine that all these catalogues are sent to the national library. Some of them include themselves in their listings, others do not. The national librarian compiles two master catalogues—one of all the catalogues that list themselves, and one of all those that don't.

The question is: should these catalogues list themselves? The 'Catalogue of all catalogues that list themselves' is no problem. If the librarian doesn't include it in its own listing, it is still a true catalog of those catalogues that do include themselves. If he does include it, it remains a true catalogue of those that list themselves.

However, just as the librarian cannot go wrong with the first master catalogue, he is doomed to fail with the second. When it comes to the 'Catalogue of all catalogues that don't list themselves', the librarian cannot include it in its own listing, because then it would include itself. But in that case, it should belong to the other catalogue, that of catalogues that do include themselves. However, if the librarian leaves it out, the catalogue is incomplete. Either way, it can never be a true catalogue of catalogues that do not list themselves.

*

You can comment on the issues presented here, either on set theory or language and the hugely crucial difference between being and non-being, which was a central issue in Eleatic philosophy too, with Parmenides having as one of his main axioms that "Being exists, and non-being is nothing at all", hence protecting himself from the cutting edges of a similar paradox in his view of Oneness. Likewise in set theory without restrictive (non purely logic following) axioms we cannot have the totality of sets. :)
 
When a mathematical system is complex enough to reference itself these sorts of things occur. Douglas Hofstadter calls these systems "[wiki]Strange loops[/wiki]". He thinks human self-concept, an important component of consciousness is a similar system and can have similar self reference issues.

Similar issues in mathematics:
[wiki]Godel incompleteness[/wiki]
[wiki]Halting problem[/wiki]
 
When a mathematical system is complex enough to reference itself these sorts of things occur. Douglas Hofstadter calls these systems "[wiki]Strange loops[/wiki]". He thinks human self-concept, an important component of consciousness is a similar system and can have similar self reference issues.

Similar issues in mathematics:
[wiki]Godel incompleteness[/wiki]
[wiki]Halting problem[/wiki]

Nice, i also am of the view that this issue mirrors (and isn't that just to be expected?) our own consciousness set-up insofar as distinct logic in our consciousness goes. But this is not meaning that inherently we cannot improve upon such a system, although it would seem to mean two other things:

a) any improvement again will include more parts but not a totality
b) the more parts included will still have a limit to non defined parts, thus the new system is merely 'more complete' in relation to a previous variation of it, and not to a totality.

It is also at core an issue not just of smaller parts beyond what we deem as distinct logic, not being expressed in any bounded system, but also of the very crucial terms of "being" and "not being". Cause while "being" can be expressed as containing stuff which are either of a type or approximating such a type (in whatever way we want), "not being" is not merely containing stuff that can be linked to each other in any finite manner.

Goes without saying that this is in essence not some 19th or 20th century issue, but merely another facet of the eternal Parmenido-Protagoro-Anaxagoric debates :smug: ;)
 
Dear Lord, I'm getting flashbacks from University.

"So you build a turing machine that takes as inpt a turing machine. Then you feed the turing machine into itself. As a result of this, we can prove that it's not possible - "

*head explodes*
 
I'm not sure what you're getting at with being versus non-being. Can you provide an example?

Yes i can:

If i ask you to create a bounded set of all chalks you have in your room, you can always do so, regardless if you have no chalk (empty set) or any number of them, cause you cannot have infinite chalks in your room. This is a set formed by things which are BEING something, in this case chalk.
If i ask you, by contrast, to create a bounded set of all THINGS in your room which are NOT chalk, then you will have more issues there, cause all things not being chalk include all things in your room other than chalk, but also all things which are there in less distinct way. Ie you would already be hard pressed to create this bounded group listing stuff in all their formations up to known particles. And if the particles break into more you cannot even know are there theoretically then your set is incomplete due to issues inherent with the set not being bounded regardless of what you do.

But i still just asked you to create sets of things tied to being or not being the same thing (chalk). The latter evidently is not finitely resulting from any dynamic formations/types that construct the former ;)

*

@Warpus: :) Btw, i find it very interesting that Parmenides also argued that his Oneness (Singularity of ALL) would be "infinitely divisible to account for all there is, but still bounded by something other". Maybe a spherical god in perpetual free fall in a dark void :p

tumblr_m9pi7uC3G51r5r7hwo1_500.gif
 
"So you build a turing machine that takes as inpt a turing machine. Then you feed the turing machine into itself. As a result of this, we can prove that it's not possible - "

You write a program that takes as an input a text file. Choose the text file to be the source code.

That's the same in layman's terms. :)

Spoiler :
You're writing an IDE for java-development. It has features such as syntax check etc. You also want to make it the best IDE ever written, so you want it to tell the user if he's programming an endless loop. So you write a method
Code:
/* This tells whether the textFile is a source code 
    java program that will stop some time. */
public static boolean halts(File textFile){
...}

Then a prankster uses your method to write this:
Code:
public static main(String[] args){
if (halts(new File("prank.java"))) {
   while (true){
     System.out.println("Warpus rules!");
     }
}
He saves the source as "prank.java", compiles and runs.
 
You write a program that takes as an input a text file. Choose the text file to be the source code.

That's the same in layman's terms. :)

The implications in terms of the halting problem and other issues are a bit mind-bending though, and that's not easily put into layman's terms. I think I stopped understanding it with clarity the moment I walked out of that exam room.
 
Back
Top Bottom