I am reading Halmos's Naive Set Theory. I am really enjoying though I never read such a book. But there are some things that I am unable to grasp. Notably in the second chapter after stating the axiom of specification he presents a condition that (x does not belong to x). After that he uses this condition by say that {x belongs to A: x does not belongs x}. What I don't understand is that how can we talk about an element belonging to itself ? and what does it mean ?
Axiom of Specification
axiomsset-theory
Related Solutions
The axiom of specification is not a sentence. It's an "axiom scheme", which is to say that it is a family of sentences. This is one of the things that becomes more clear when you move to axiomatic set theory, instead of naive set theory.
For each sentence $S(x)$ that does not mention $B$, the axiom of specification includes the axiom $$ \forall A \exists B \forall x ( x \in B \Leftrightarrow x \in A \land S(x)). $$
What that axiom says, informally, is that given a set $A$ and a definition $S$ of a subset of $A$, that subset actually exists. The scheme is slightly more general than my previous formula, because the scheme allows sentences with "parameters".
The restriction that $S$ does not mention $B$ is to avoid paradoxes. Otherwise we would have as an axiom (letting $A = \{0\}$ and letting $S$ be "$x \not \in B$") $$ \exists B \forall x ( x \in B \Leftrightarrow x \in \{0\} \land x \not \in B). $$ That set is paradoxical - it contains 0 if and only if it doesn't contain $0$.
The reason that we cannot quantify over sentences is that set theory is formalized using the logical system of "first order logic". That system is not able to quantify over sentences. This isn't an arbitrary choice; the inability to quantify over sentences is a necessary result of certain logical properties of first-order logic that are desirable. There are other logics in which one can quantify over sentences, but these logics do not have nice properties (and some have argued these logics themselves include set theory).
All of this is explained, in great detail, in books on axiomatic set theory. One reasonable book is Levy's Basic set theory. The standard graduate textbook is Kunen's Set theory: an introduction to independence proofs, and it can be used to learn axiomatic set theory, but it is somewhat terse at the beginning and is better as a second book on axiomatic set theory in my opinion.
No, this sort of recursion is not allowed in first-order logic. Remember that in general a first-order formula, thought of as a query, has to "work" (= make sense and have an answer) on every element of every structure. Recursive formulas of the type in the OP run into ill-foundedness problems in general - e.g. supposing $a=\{a\}$, should we have $\Lambda(\{a\},\{a\},\{a\})$ be true or false? More relevantly, suppose $M$ is an illfounded model of $\mathsf{ZFC}$; for $a$ not in the illfounded part of $M$, how should we understand $\Lambda(a,-,-)$?
That said, in the presence of a weak fragment of $\mathsf{ZFC}$ we can make sense of your principle in a first-order way. Specifically, we first whip up a set-theoretic implementation of basic graph theory, with which we can easily talk about the result of substituting a given tree for each leaf in another tree. Note that this is totally recursion-free: basically, we talk about a particular graph on a subset of the Cartesian product of the vertex sets of two given graphs. Then we prove that we can conflate sets with certain types of trees, namely the (internally) well-founded extensional ones; this requires Replacement, since basically what we're doing is going through the transitive closure. Combining these we get a purely first-order sentence which - again, in the presence of this weak axiomatic background - expresses what you're looking for. (And in fact this sentence is outright provable in this fragment.)
Best Answer
Maybe it is simpler to approach it in terms of predicates (expressing properties of objects). See original Russell's formulation The Principles of Mathematics (1903)]:
Here we can see the basic ingredient: the Comprehension principle stating that every predicate (expressed by a formula $\varphi$ of the language of sets) identifies a unique set $S$, i.e. the set (or class) defined by the predicate "to be a predicate that cannot be predicated of itself".
Regarding "not belonging to itself", we can try with the following example.
We know the natural numbers: $0,1,2,\ldots$ and we have the set $\mathbb N$ of all naturals, such that $0,1,2 \in \mathbb N$.
We have that $\mathbb N \notin \mathbb N$: the set of all naturals is not itself a natural number.
Assume now that we can define the set of non-naturals:
we have that this set is not itself a natural, and thus: