Indeed, this is an equation and it can have 0, 1, or many solutions.

However, it is often used in a setting where some patterns of recursive equations are known to have either a unique solution, or a smallest solution. Because the proof is in the form, it is not stated explicitly each time.

Suppose that f is a mapping of subsets of a fixed domain to subsets of the domain. Assume also that f is monotone, i.e. X\subseteq Y implies f(X)\subseteq f(Y). Then the equation X = f(X) has always a least solution.

Dear all.

It seems to me that either my question is not understood or I have not explain it properly.

Every equation in my introductory message is only intended as an illustration. The question is that frequently a recursive definition is stated without proving whether of not it defines something.

Recall that a definition is recursive if it involves the defined object; therefore is of the form x = P(x); where the defined object is x. Nevertheless, if x = P(x) is regarded as an equation, usually the existence of any x satisfying it must be proved. By contrast, recursive definitions, which can be also regarded as equations, usually are stated without proving the existence of the defined object.

Usually a recursive definition is written in a form that makes it obvious that a very general theorem can be applied to prove that the equation has a unique solution. The reader who cares about such things is expected to know the theorem, or to find out.

Dear Taneli,

Your answer is smart. In any case, you say "usually". Usually or frequently do not mean always.

It is just when opening new investigation fields when the term "usually" cannot be applied; since "new" and "usualy" are not quite compatible concepts. For instance, the set of all sets is a recursive definition, and Russell noticed a contradiction in it.

Would not the contradiction (fallacy of composition, or whole is the sum of the parts) be avoided if in metamathematicially employing Cantor's Cardinality, the set of all sets (or other self-referencing or self-similar phenomena) is equated with x=set=all sets? Afterall, the first implicit definition of 'x' itself is that it is a variable, it varies or can vary or can be anything, that variation narrowed explicitly or implicitly by definition, recursive (deductively) or otherwise (inductively). I'm curious, too, if there are any examples instead of equations with absolutely NO solutions as well as PROOF of NO solutions (not just unknown solutions)? In other words, is there proof of negatives?

Dear Juan-Esteban,

Your first post was perfectly clear.

Perhaps I need to illustrate my answer with a few examples of then-new

investigation fields:

- When Peano started the study of natural numbers, the first thing he

did was to study which forms of recursive definitions always have a

unique solution (and thus can really be called a definition). Then he

used this form many times without proofs.

G. Peano, Arithmetices principia, nova methodo exposita, Bocca, Turin

(1889)

http://archive.org/stream/arithmeticespri00peangoog#page/n6/mode/2up

- When Cantor studied the ordinals, he did the same.

Cantor, G., (1897), Beitrage zur Begrundung der transfiniten

Mengenlehre. Mathematische Annalen 46.

- Most papers do not addres new investigation fields and

this theorem is clear because it is in a cited reference.

- Indeed, you can find a few papers where the needed theorem used is not

clear, that's why I used the word 'often".

Please note that the "set of all sets" is NOT a contradiction. It is

indeed part of the set theories NF, NFU, and NFI. The latter was

proved consistent by Crabbé.

What Russel proved is that "the set of all sets that do not belong to

themselves" is a contradiction. This set is not definable in the above

theories.

Quine, W.V., 1937a, “New Foundations for Mathematical Logic,” American Mathematical Monthly, 44: 70-80.

Jensen, R. B., 1969, "On the Consistency of a Slight(?) Modification of Quine's NF," Synthese 19: 250-63.

Crabbé, Marcel, 1982, On the consistency of an impredicative fragment of Quine's NF, The Journal of Symbolic Logic 47: 131-136.

Dear Pierre

You are right. The set of all sets is not a contradiction, but a concept that implies a contradiction. This is why the collection of all sets is regarded as a class. Thus, a collection is considred to be a set, provided that it can be extended. Likewise, the collection of all classes is called conglomerate.

Summarizing, the phrase the "the set of all sets" defines nothing, the proper definition is the class of all sets. Since the "set of all sets" is self-included, regarded as a definition is recursive.

Just little points:

1. to derive a contradiction from the set of all sets, you need some supplementary axioms (in ZF, the axiom that says that any subset of a set, is a set,

and therefore, we can definie the set of the sets that do (not) belong to themselves.)

2. technically, as you noted, the set of all sets is not defined recursively, but by some axiom of comprehension.

The question is old and you can find the topic in this classic book on Categorical Algebra.

http://katmat.math.uni-bremen.de/acc/acc.pdf

The expression "the set of all sets" is no longer accepted. You must say " the Class of all Sets" instead. Likewise, you must say the conglomerate of all classes" instead of the class of al classes.

@Ivan Suskov Suppose the domain is the positive integers and f(∅)=∅, and otherwise f(S) is the subset obtained when the smallest integer in S is deleted. In this case, would your "least solution" be ∅?