1. ## Set Theory Question: Contradiction and the Empty Set

while

B ={x
∈A|x∌A} does not lead to a contradiction, but yields the empty set.

Why?

2. ## Re: Set Theory Question: Contradiction and the Empty Set

The short answer is: not everything is allowed to be a set.

In other words, it is possible to make a definition of a collection of things that do not form a set. So it is not sufficient to say: let $X$ be the set of all things with property $P$, for such a collection may, for various reasons, not BE a set.

In particular, the collection of all sets that do not contain themselves as a member, is not a set (if it were, there is a thorny problem deciding if such a set is a member of itself).

To get around this difficulty, "comprehension" (defining a set by a defining property) is "restricted" to elements that are already in a well-defined set. If such a property is self-contradictory, then no elements will satisfy it, and the set is empty.

In words, we should always say: let $X$ be the set of all elements IN $A$, with property $P$. So first we need the "superset" $A$.

Even this is not entirely satisfactory, consider this example:

Let $X = \{x \in \Bbb N: x = p+q,\ \text{where }p,q\text{ are primes and }2|x\}$

No one knows what this set is, although most people suspect it is the entire set of even natural numbers greater than 2.

3. ## Re: Set Theory Question: Contradiction and the Empty Set

Originally Posted by Deveno
The short answer is: not everything is allowed to be a set.

if it were, there is a thorny problem deciding if such a set is a member of itself
Well, if we define a set by the following:

B ={x∈A|x∌A}

What about the thorny problem of defining whether A belongs to itself?

If one x in the above equation is A, in other words, ∃x[x = A]

A∈A^A∌A

If A belongs to itself, it won't belong to itself anymore, which will result in it belonging to itself again, and then it goes.

Again, we shall fall in contradiction...

4. ## Re: Set Theory Question: Contradiction and the Empty Set

The set B you give in your example is empty. Letting x = A doesn't trigger the contradiction because A is NOT an element of A.

There is an important distinction drawn in set theory between the two sets: A and {A}. A is only an element of the second set.

If a set (say S, for example) could be an element of itself, say S = {S,a} = {{S,a},a} = {{{S,a},a},a} = .....

we would get an "infinite descent" of nested sets, without ever reaching the bottom. Such a set is said to be not-well-founded, and such "sets" are prohibited in Zermelo-Fraenkel set theory.

Alternate set theories DO exist, where such sets are allowed, but...these are not the set theories mathematicians USUALLY mean, when they talk about sets.

My suggestion is that you defer studying those "alternate" set theories, until after you know "the usual kind" much better.

5. ## Re: Set Theory Question: Contradiction and the Empty Set

Originally Posted by Deveno
Letting x = A doesn't trigger the contradiction because A is NOT an element of A.

Why not?
__________________________________________________ __________________________________________________ __________________________________________________ ___________

In Cantor's Axiom Schema of Comprehension:

For every property P(x), there exists a set Y which comprises all elements, here denoted by "x", which follow P(x):

∀P∃Y[Y={x|P(x)}]

We then can formulate the property P(x) of all sets, here denoted by X, which are not members of themselves:

∃x[x = X] (Some elements x are sets X)

∃P(X)[P(X)=X∌X]

Among all sets (labeled as X), there exists the aforementioned set Y:

∃X[X=Y]

We then can formulate the following

∃Y[[Y={X|X∌X}]

As ∃X[X=Y], a question arises: does Y belong to itself?

Y∈Y ↔ Y∌Y

__________________________________________________ __________________________________________________ __________________________________________________ ___________

As Cantor's Axiom Schema of Comprehension was proved false, it was formulated the Axiom Schema of Separation, which postulates the following:

∀P∃Y[Y={x∈A|P(x)}]

As in the Axiom Schema of Comprehension, in the Axiom Schema of Separation, x can be any element which follows the property P(x)

If in the Axiom Schema of Comprehension it was possible to formulate a property P such as:

∃P(X)[P(X)=X∌X]

Y={X|X∌X}

∃X[X=Y]

Y∈Y ↔ Y∌Y

Why can't we have the following:?

∃P(X)[P(X)=X∌A]

Y={X∈A|X∌A}

∃X[X=A]

A∈A ↔ A∌A

6. ## Re: Set Theory Question: Contradiction and the Empty Set

Because P(X), the predicate, is LIMITED IN SCOPE to a given set, A. Now this means that in order to "apply" comprehension, we need some well-defined sets we can create to apply it TO. In order to be able to produce such sets, various other axioms:

Pairing
Replacement
Union
Power-set
Infinity

are postulated to give us enough "basic sets" to restrict via predicates. We therefore cannot speak of "the set of even", but rather of "the set of even integers" or "the set of even natural numbers".

The axiom of regularity is then used to "initialize" set theory (much like 1 "initializes" the natural numbers): it says we have to "start somewhere", we cannot define a set by an endless self-reference:

I am the part of me that says I am the part of me that says I am the part of me that says....

********************

It is perfectly fine to define the predicate: P(x) = x is not in A.

If we define Y = {x in A: P(x)}, then Y consists of all x in A for which P(x) is true. Which is exactly none of them, since if x is in A, then P(x) is false.

This DOES NOT MEAN the set A is "paradoxical", or even that Y is, it means that Y is EMPTY (any elements it DID have would be paradoxical).

For example, we might define a set S as "the set of all integers that are not integers". This set, too, is empty.

***********************

You can't make Russell's paradox "go through" in Zermelo-Fraenkel set theory. There is no set of all sets. There are only subsets of other sets we can make using the methods outlined above.

Of course, since we might want something to apply equally well to ALL sets, we may wish to talk about "all sets at once". There are some different ways this is done:

1. Posit a Grothendieck universe (equivalently: a sufficiently inaccessible cardinal)
2. Posit collections of a larger type (such as a von Neumann class)
3. Posit "large categories" (or more specifically, topoi in which such large categories exist)
4. Abandon the axiom of regularity, and employ a not-well-founded set theory, such as Quine's New Foundations

It's really no use arguing with me about this, I did not fabricate set theory, and I'm not even one of its biggest fans. None of what I'm telling you, though, is ground-breaking news, it has been examined rather thoroughly for nearly a century now.

************************

You asked: why is A not an element of A? There is an axiom, called the axiom of pairing, which says:

Given any set A, and any set B, there exists a set whose elements are A and B. In the special case when A = B, this gives the set {A,A} = {A} (repeated elements are discarded in sets, unlike in "multi-sets").

There is another axiom, the axiom of regularity, which says:

Every non-empty set X contains an element disjoint from X (that is, there is x in X with $x \cap X = \emptyset$).

Applying this to the set {A}, whose only element is A, we obtain, $A\cap\{A\} = \emptyset$.

Since $A \in \{A\}$, we cannot have $A \in A$, or else the intersection would be non-empty.

In effect, these axioms were "designed" to prevent $A \in\{A\}$.

In my opinion, the machinery of Zermelo-Fraenkel set theory is "clunky" and awkward to deal with. But there is a good reason for this: just because we can "phrase" an idea, it does not mean this idea is USEFUL, the classic example is:

"This sentence is a lie".

I can SAY that, but can I MEAN it? Does it impart any information at all?

7. ## Re: Set Theory Question: Contradiction and the Empty Set

Here's what I have in mind

∀P∃Y∃A[Y={x∈A|P(x)}] → ∀P∃A[x∈A^P(x)] (The Axiom Schema of Separation)

∃P[P(x)=x∉A]

P(x)[P(x) = x∉A] ⇔ x∈A (false)

∴¬∀P∃A[x∈A^P(x)] (true)

¬∀P∃A[x∈A^P(x)] → ¬∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation)

Which yields the very same reasoning as Russell's Paradox does:

∀P∃Y[Y={x|P(x)}] (The Axiom Schema of Comprehension)⇔ ∀P∃Y[x∈Y^P(x)]

∃P[P(x)=x∉Y]

P(x)[P(x) = x∉Y] ⇔ x∈Y (false, the very same contradiction born by the former derivation)

∴¬∀P∃Y[x∈Y^P(x)] (true)

¬∀P∃Y[x∈Y^P(x)] ⇔ ¬∀P∃Y[Y={x|P(x)}] (The Axiom Schema of Comprehension)

Also, the Axiom Schema of Separation seems to be false due to the following

∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation) ⇔∀P∃Y∃A[x∈A^x∈Y^P(x)]

∃P[P(x)=x∉Y]

P(x)[P(x)= x∉Y] ⇔ x∈Y (false, again, the same contradiction)

∴¬∀P∃Y∃A[x∈A^x∈Y^P(x)] (true)

¬∀P∃Y∃A[x∈A^x∈Y^P(x)] ⇔¬∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation)

Originally Posted by Deveno

If we define Y = {x in A: P(x)}, then Y consists of all x in A for which P(x) is true. Which is exactly none of them, since if x is in A, then P(x) is false.

This DOES NOT MEAN the set A is "paradoxical", or even that Y is, it means that Y is EMPTY (any elements it DID have would be paradoxical).
As aforederived, the reason which make the Russell set paradoxical in the Axiom Schema of Comprehension seems to be the same that make the set A empty. Such being the case, I cannot understand why the Russell set is paradoxical if the set A in Zermelo-Fraenkel is not.

Again, thank you very much for the help, Deveno.

8. ## Re: Set Theory Question: Contradiction and the Empty Set

If you really insist on this, I must advise you to not pursue a career in mathematics, unless you are immune to the ridicule of others. You will find it hard to get other people to take you seriously. I know this sounds harsh, but mathematicians can be a savage bunch with little patience for those who don't see things the way they do.

Originally Posted by Schiavo
Here's what I have in mind

∀P∃Y∃A[Y={x∈A|P(x)}] → ∀P∃A[x∈A^P(x)] (The Axiom Schema of Separation)
I don't agree with this. It's a subtle point: the first statement defines Y, the second defines A. You can't so easily dispense with the restriction that A is defined a priori, to conclude we can then use unrestricted comprehension to define ANY A.

∃P[P(x)=x∉A]
Again, I'm not sure what your intended meaning is, here. If you are just stating that THIS P is one possible predicate, then sure.

P(x)[P(x) = x∉A] ⇔ x∈A (false)
Using P(x) as x∉A is somewhat of a smoke-screen, here. For any statement Q, it is certainly true that (Q ⇔ ¬Q) is a false statement.

∴¬∀P∃A[x∈A^P(x)] (true)
Ok, but what does this really say? You can't use ∀P to quantify over ALL predicates on one hand, and intend P(x) to be the SPECIFIC predicate x∉A on the other. What you have written says that for SOME predicate P, there is some set A that doesn't have the property defined by P. If you wish to say P(x) = x∉A, you need to drop the ∀P.

¬∀P∃A[x∈A^P(x)] → ¬∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation)

Which yields the very same reasoning as Russell's Paradox does:
Again, the problem with this, is that you dropped Y almost immediately, and went straight to A. Can't do that. A is given BEFORE we can define Y, and we can only talk about Y. You want to use the predicate that defines Y (and in this case the predicate is self-defeating, so defines nothing) to define A. I want to emphasize this:

Predicates (properties) do not define sets. They only define subsets of OTHER sets. If you could prove that the Russell set WAS a bona-fide set, then your argument would work, and yield the same paradox as Russell's paradox. But to prove that, you'd need to find some set that Russell's set was a subset OF, first.

∀P∃Y[Y={x|P(x)}] (The Axiom Schema of Comprehension)⇔ ∀P∃Y[x∈Y^P(x)]

∃P[P(x)=x∉Y]

P(x)[P(x) = x∉Y] ⇔ x∈Y (false, the very same contradiction born by the former derivation)

∴¬∀P∃Y[x∈Y^P(x)] (true)

¬∀P∃Y[x∈Y^P(x)] ⇔ ¬∀P∃Y[Y={x|P(x)}] (The Axiom Schema of Comprehension)

Also, the Axiom Schema of Separation seems to be false due to the following

∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation) ⇔∀P∃Y∃A[x∈A^x∈Y^P(x)]

∃P[P(x)=x∉Y]

P(x)[P(x)= x∉Y] ⇔ x∈Y (false, again, the same contradiction)

∴¬∀P∃Y∃A[x∈A^x∈Y^P(x)] (true)

¬∀P∃Y∃A[x∈A^x∈Y^P(x)] ⇔¬∀P∃Y∃A[Y={x∈A|P(x)}] (The Axiom Schema of Separation)
The axioms of set theory are neither true, nor false. We assume they are true. We don't know. IF they are true, we can derive other things we believe to be true FROM them. It is possible to assume DIFFERENT axioms are true. There are many variants of set theory, and some of them contradict each other.

One cannot establish the truth of an axiom system, within that axiom system. At best, one can only show consistency, which comes with a certain price tag (either limitation in expressive power, or completeness). The Russell paradox shows that unrestricted comprehension is inconsistent-it leads to (for the Russell set, R):

$(R \in R) \wedge (R \not\in R)$

As aforederived, the reason which make the Russell set paradoxical in the Axiom Schema of Comprehension seems to be the same that make the set A empty. Such being the case, I cannot understand why the Russell set is paradoxical if the set A in Zermelo-Fraenkel is not.

Again, thank you very much for the help, Deveno.
The empty set IS paradoxical: that's why it's a darn good thing it has no elements-they would all be "impossible to exist".

Consider this example:

A = {integers k: k = 2t, for some integer t}, and B = the complement of A in the set of integers (odd integers).

What is $A \cap B$? Isn't it the set of integers that are SIMULTANEOUSLY odd and even? We can DESCRIBE this set with words that "appear to make sense", but it turns out that no integer "fits the bill".

I like to put it this way: the elements of the empty set are green. They're also blue. Also, none of them are green.

If we allowed "the set of all things for which P is true and P is false" to BE a set, the whole notion of "set" eats itself, and is rendered useless. Such was the unfortunate position Gottlob Frege found himself in, when Bertrand Russell pointed out the fallacy of defining sets solely by the properties they possess.

Set theory allows ONE SET S to have the property Q(x) = (P(x) and ¬P(x)), for all x in S and all P. Just that one (and there's no x's in it, anyways). If we had ANY others, the whole structure comes falling down.

The idea is: we start with sets that are "safe". We build these sets up with unions (to make bigger sets) and pairing (also to make bigger sets), and power sets (to make bigger sets, and then obtain smaller sets as elements of this bigger set), and to ensure our sets can be "as big as we like", we insist we have at least one "infinite set" (we can then make "sets with bigger infinite-ness" using power sets).

Starting with just the empty set, and it's power set: $\{\emptyset\}$, we can (using union) create any natural number (a "set version" of it, anyway), and appealing to the axiom of infinity, create a set large enough to support the Peano axioms. Since we can make sets of pairs (cartesian products), we can define relations (and functons!), and thus equivalence relations, and with these, define the integers from the natural numbers (a process called Grothendieck groupification).

Having created the integers, we can form the field of fractions, and having formed the field of fractions, we can form its Cauchy completion under the Euclidean metric. Now we have real numbers, and we can form the algebraic completion of the real numbers to get complex numbers. So all these things, at least, can be created step-by-step from "safe sets". To express what the complex number:

$\dfrac{\sqrt{2}}{2} + i\dfrac{\sqrt{2}}{2}$

is as a "basic set", is perhaps beyond my ability to do (certainly it would try my patience!), the encoding would go many layers deep.

9. ## Re: Set Theory Question: Contradiction and the Empty Set

Originally Posted by Deveno

I don't agree with this. It's a subtle point: the first statement defines Y, the second defines A. You can't so easily dispense with the restriction that A is defined a priori, to conclude we can then use unrestricted comprehension to define ANY A.
I'm somewhat of a newcomer to quantitative logic, so I might be committing elementary mistakes when expressing myself. What I meant is:

∀P∃Y∃A[Y={x∈A|P(x)}] For all P, there is an Y for which there is an A which follow the property within brackets

∀P∃A[x∈A^P(x)] For all, P, there is an A which follow the property within brackets

I believe the first to imply the second, as, if, for all P, there isn't an A which follow the property within brackets, there cannot be both an Y and an A.

Originally Posted by Deveno
∃P[P(x)=x∉A]
Again, I'm not sure what your intended meaning is, here. If you are just stating that THIS P is one possible predicate, then sure.

This is exactly what I meant. Am I misexpressing myself? Again, I'm a newcomer to the quantitative logic syntax.

Originally Posted by Deveno

Ok, but what does this really say? You can't use ∀P to quantify over ALL predicates on one hand, and intend P(x) to be the SPECIFIC predicate x∉A on the other. What you have written says that for SOME predicate P, there is some set A that doesn't have the property defined by P. If you wish to say P(x) = x∉A, you need to drop the ∀P.
What I wish to say is: for some predicate P there is no set A for which x∈A. As shown before, such predicate is x∉A.

Originally Posted by Deveno
The Russell paradox shows that unrestricted comprehension is inconsistent-it leads to (for the Russell set, R):

(R∈R)∧(R∉R)
Why B ={x∈A|x∌x} doesn't lead to Russel's Paradox? Doesn't it trigger (B∈B)∧(B∉B)?

10. ## Re: Set Theory Question: Contradiction and the Empty Set

Again, no it doesn't. NO set is a member of itself. Re-read post number 6. B and {B} are ALWAYS different, in fact they have NO members in common. So if you specify a set like so:

$B = {x in A: x \in x}$, then B is empty.

Now, there are "things" (like infinite sequences) that can have "parts" (like their "tails") that are equal to the whole, but these things are not "sets".

For example, we could define the sequence:

1,0,1,0,1,0...... as:

B = 1,0,(B), where (B) means "append B".

These sorts of things ARE studied, but not under the scope of Zermelo-Fraenkel set theory.

Basically, these sorts of issues all revolve around "infinity", because in a finite universe of "objects", there are only so many sets to worry about, and each can be unambiguously tagged.

The strange thing about infinity is this: no matter how big an infinite thing you make, there is always a "bigger" one (something known as Cantor's theorem).

It becomes necessary, in this bewildering jungle of infinite things, to "layer" them appropriately. In particular, the entire collection of every set imaginable, belongs to "the next layer". That is, the collection of all sets (often denoted simply $V$) is not a set, so there is no danger of $V \in V$. In this jungle, we also have $X \not\in X$ for all sets $X$, which means that:

$\{Y: Y \not\in Y\} = V$, which is NOT a set.

There is, as such, no universal predicate defining a set: P(x) = x is a set. The way I like to think of this is: set theory is "open at the top" and "closed at the bottom".

A lot of the trouble lies with logic: when we apply logic, we often appeal to the law of the excluded middle:

Either A is true, or ¬A is true.

If A is the sentence: ¬A, we have a problem (in ordinary language: "This sentence is false"). Because of this, some schools of thought REJECT the law of the excluded middle, which means that "proofs by contradiction" are not valid. Most mathematicians regard this as "too extreme", and prefer instead to restrict the SCOPE of sentences we may apply the law of the excluded middle to. This then, means using extreme care in definitions, lest they prove to be too self-referential.

In rather broad, and somewhat inaccurate terms:

Classical logic: Yes or no. That's it. Some problems are "ill-posed" (outside the proper scope of the logic).

Non-classical logic: Definitely yes, definitely no, some things unknown (unable to prove or disprove).

A famous theorem of Kurt Godel shows that for any form of mathematics that includes basic arithmetic, this kind of problem is unavoidable, as self-reference can be encoded within it. You either need: math + meta-math+ meta-meta-math+.....

or you need to accept your "math" is just an isolated island, in the sea of knowledge.

You are free to accept whichever view you believe in.

11. ## Re: Set Theory Question: Contradiction and the Empty Set

Originally Posted by Deveno
The set B you give in your example is empty
The set B contains x∈A|x∌A so how is it empty? Define empty.

Letting x = A doesn't trigger the contradiction because A is NOT an element of A
I presume you mean A is not allowed to be an element of A under the Zermelo rules. So it is illegal to let x=A. In which case the expression needs rewriting:-

B ={x∈A|x∌A|x!=A}

That expression is false for all possible x. This entails that the expression itself is a contradiction. If it was true even for one x it would not be empty. Under no conditions is it ever empty.

It is either a contradiction or has a solution but it is never empty.

You are using the word "empty" without knowing what it means. Here is what it means: illusion.

12. ## Re: Set Theory Question: Contradiction and the Empty Set

Originally Posted by Deveno
For example, we might define a set S as "the set of all integers that are not integers". This set, too, is empty.
That expression is false for all integers and for all non integers which entails that the expression is a contradiction. The set S is a contradiction. Why would you think it is empty? If there are no true solutions then the only other alternative is all false and thus contradiction. S isn't even a set at all, just a contradiction.