# Is there a simple paradox like Russell's paradox that arises if we assume

... that for a given property P, there is a set of all and only the unordered pairs {x,y} such that x satisfies P and y doesn't satisfy P?

Clearly, to avoid Russell's paradox, we would refrain from assuming that we can select a constant c and have a set of all x such that {x,c} is an element of the set whose existence is posited above. We have no need to make such an assumption, since if we want to consider such values x, then we can simply introduce a notation that abbreviates the assertion that {x,c} is an element of the set.

It's not immediately obvious how one would obtain a paradox. For example, consider the following property: {x,empty set} not an element of x.

It seems that from our comprehension schema, we would be able to deduce that there exists a set m such that,

If {x,empty set} isn't an element of x and {y,empty set} is an element of y then {x,y} is an element of m.

This train of thought doesn't suggest an obvious contradiction that we can arrive at. However, maybe I'm failing to see something that is obvious to others.

• Once you formed such a set S, you will be able, by the axiom of union, to form a set S' whose elements are elements of elements of S, and then, by specification, a set S'' whose elements are elements of S' that do not satisfy P. When P(x) = (x ∈ x) that will be the Russel's set. Commented Aug 10 at 3:39
• It's worth pointing out that if you only assume your axiom, and nothing else whatsoever, then you actually do have a model where ∅ is the only set that exists. For any property P, you have ∅ = {{x,y} : P(x) & ¬P(y)}\$, which works since all x,y have x=∅=y and thus P(x) ⇔ P(y). If you at least assume that {∅} exists, however, then the answer given by user21820 shows how your axiom leads to a Russel-like contradiction. Commented Aug 10 at 17:58
• Not sure what you mean here by "avoid Russell's Paradox." RP arose from an early attempt to formalize set theory by G. Frege. Using his axioms, it was possible to both prove and disprove that there exists a set r such that, for all x (x in r <=> ~(x in x)), i.e. his axioms were found to be inconsistent. As far as we know, modern set theories manage to avoid RP. It is no longer an issue in mathematics. Commented Aug 18 at 2:49

Simple:

``````Let ∅ = { {x,y} : ⊥∧¬⊥ }.
Let c = {∅,∅}.
Let Q(x) ≡ x≠∅∧{x,∅}∉x.  [A]
Q(c).
¬Q(∅).
Let S = { {x,y} : Q(x)∧¬Q(y) }.  [B]
{c,∅}∈S.
S≠∅.
If {S,∅}∈S:
Q(S)∧¬Q(∅) ∨ Q(∅)∧¬Q(S).  [by B]
Q(S).  [since ¬Q(∅)]
{S,∅}∉S.  [by A]
⊥.
{S,∅}∉S.
Q(S).  [by A]
{S,∅}∈S.  [by B]
⊥.
``````
• +1 for "simple" and then going full-not-simple-mode XD Commented Aug 11 at 2:00
• It's really as simple as we can get, since every line is essentially necessary due to the structure of the problem. In particular, due to the unordered pair, we need to exclude Q(∅) if we want to get a contradiction from {S,∅}∈S. So we modify Q. And because of that we need to prove S≠∅, so we need to find a member, hence we try the most obvious. This proof assumes that we can construct any unordered pair, and Jade Vanadium noted that if we have no other existence axiom then we cannot exclude the trivial model where ∅ is the only object. The rest is the same as for the Russell paradox. Commented Aug 11 at 4:32
• I am sure it is simple, once you understand all the symbols and be adept in maths ;) It is concise and aimed/tailored to the solution for sure. Thanks for your explanation! It gives a glimpse of the underlying ideas. Commented Aug 11 at 15:34
• @Antares: Of course, of course. One ought to be sufficiently familiar with logic before even dabbling in foundation of mathematics, not to say philosophy of mathematics. =) Commented Aug 12 at 13:00

User21820 gives an excellent answer, showing that we derive a contradiction so long as we assume {∅} exists. I think that's sufficient to answer your question, and you should accept it if you agree. I felt inclined to give a more in-depth answer, though, since the existence of {∅} is technically not a necessary consequence of your axiom. As I pointed out in a comment, we actually have a trivial model of your axiom provided we assume ∅ is the only set that exists. I'm going to prove that this is the only possible model of your theory. As demonstrated by user21820, we have ∅={{x,y} : ⊥∧¬⊥}, so at least ∅ must exist. In pursuit of contradiction, suppose there exists a nonempty set c....

Given any set n, define S(n)={{x,y} : x=n ∧ y≠n}, and notice that necessarily S(n)≠∅ regardless of n. Indeed, if n=∅ then {n,c}∈S, and otherwise {n,∅}∈S, so in any case we have S(n)≠∅. This also verifies that {a,b}∈S(a) so long as a≠b, hence the unordered pair {a,b} exists so long as a≠b. We also observe that ∅∉S(n), which works since all p∈S(n) obey n∈p and thus p≠∅. Using these facts, we infer the existence of at least three distinct objects: ∅, and S(∅), and finally {∅,S(∅)}.

Since there are at least three distinct objects, we can prove the S function is injective. Indeed, suppose we have S(n)=S(m), then we can find an object k such that both n≠k and m≠k. Since n≠k then {n,k}∈S(n)=S(m) and thus {n,k}∈S(m), and since m≠k then necessarily n=m.

Now, for a proposition P, define the notation [P]={{x,y} : Q(x) & ¬Q(y)}, where Q(x) means ∃z, P(z) & x=S(z). Notice that necessarily ¬Q(∅), and thus we have {S(x),∅}∈[P] if and only if P(x) holds. Finally, we derive our contradiction by letting R=[{S(x),∅}∉x], and asking whether or not {S(R),∅}∈R. By definition of R, we have {S(R),∅}∈R if and only if R satisfies the proposition {S(x),∅}∉x in place of x, and this is an outright contradiction.

The higher-level logic here is actually pretty interesting, and it's how I came up with this proof. All Russel-like paradoxes are ultimately just a variation on Cantor's diagonal argument, which proves |U|<|2^U| for any set U. Some structures are inherently larger (read: more complex) than others, in that they resist compression beyond a certain point. This holds for infinite structures just as well as it does for finite structures.

Let U denote the class of all objects in your domain of discourse, and let 2^U denote the hyperclass which contains all the subclasses of U. Your axiom induces a function from 2^U to U, given by F(C)={{x,y} : x∈C ∧ y∉C}. This function is nearly injective: If we have F(A)=F(B), then either A=B or else A=U\B. If we require that A and B agree on the membership of at least one object, such as requiring that both ∅∉A and ∅∉B, then having F(A)=F(B) simply implies A=B. Because of this, your axiom gives us an injection witnessing 2^|U-1|≤|U|. This is already pretty close to impossible.

What I did was show that |U|≤|U-1|, by constructing a function (namely S) which was injective but not surjective. Incidentally, the function S is literally just S(n)=F({n}), which is injective due to the near injectivity of F (and the fact that 3≤|U|), and fails to be surjective since we never have S(n)=∅. This induces an injection 2^|U| ≤ 2^|U-1|, which composes with F to give an injection 2^|U|≤|U|, which was exactly my [P] notation. From there, I simply deployed Cantor's theorem to derive a contradiction.

• +1 for taking the time paraphrasing what the "simple" answer by user21820 means and also going more in-depth even, with your proof by contradiction (would be eligible for +2) :D Commented Aug 11 at 2:03