# Validity of a second-order formula

This is exercise 22.6 from Boolos,Jeffrey,Burgess Computability and Logic 4th ed. You are asked to prove the validity of the following sentence (with second-order logic as the underlying logic and under standard semantics): $$\exists X \neg \exists x \forall y (Rxy \leftrightarrow Xx)$$

For the life of me I cannot see how that can be true if I take a model $\mathcal{M}$ such that $R^{\mathcal{M}} = \vert \mathcal{M} \vert^2$, i.e. one in which the relation is true of any possible combination of elements.

Is there something I am missing about $R$ here? Surely I cannot then just take $X$ to be the empty set can I? I'm sure there's something obvious I am missing here, since this looks like a pretty straightforward exercise.

-
Are you sure you didn't make a typographical error when you copied it here? In my book (which is the 5th edition) it writes $\exists X\lnot\exists y\forall x(Rxy\iff Xx)$ and gives a hint calling it the principle of Russell's paradox. Your formula has a $z$ in there that isn't bound. Also for the example as you describe it why can't you take X being empty? –  Apostolos Apr 14 '11 at 14:49
Yes - made a typo obviously, sorry about that, edited. I don't know if you can, but if you can then the validity is completely trivial since an empty $X$ will always trivially satisfy the condition, regardless of your $R$. –  Chuck Apr 14 '11 at 15:11

In the fifth edition that I own it writes $\exists X\lnot\exists y\forall x(Rxy\iff Xx)$. Please note that here the $y$ and $x$ are interchanged. It may be a typo in the fourth edition copy that you own so I will answer the question for both cases since the sentence is valid anyway.
• $\exists X\lnot\exists x\forall y(Rxy\iff Xx)$: Let $\mathfrak{A}=\langle A,R^{\mathfrak{A}}\rangle$ be a model and take as $X$ the subset of the universe $X=\{a\in A : \exists b\in A\quad (a,b)\notin R^{\mathfrak{A}}\}$. $X$ being empty poses no problem at all. It's very easy to see that for this $X$ no such $x$ exists.
• $\exists X\lnot\exists y\forall x(Rxy\iff Xx)$: In this case the sentence says something more interesting. That we cannot find a relation $R$ in the universe that in a sense can define every subset of the universe using some element. Or that it's impossible to represent the powerset of the universe within the universe. As you can see this is related to Cantor's and Russell's paradox. The construction is (much like Russell's famous construction) as follows: Given the model $\mathfrak{A}=\langle A,R^{\mathfrak{A}}\rangle$ let $X=\{a\in A : (a,a)\notin R^{\mathfrak{A}}\}$. For this $X$ no $y$ exists such that for any $x$ $Rxy\iff Xx$. This is because we have $Xy\iff \lnot Ryy$ by the definition of $X$.
What do you mean by "Nothing stops us from letting $X$ be empty"? That we can choose a model such that $X$ is empty? But the question was about the validity of the sentence, so we can't just choose a model? –  joriki Apr 14 '11 at 15:58
@joriki: No, I mean that the empty set can be considered a unary predicate, i.e. a subset of the universe. I wrote it that way (and maybe I shouldn't) because Chuck was uncertain whether he can consider as $X$ the empty set, because it rendered his question fairly trivial. What I really mean by that -I guess- is "If $X$ as I defined it is empty, then this doesn't pose a problem." Thanks for pointing out that it looked weird. I will edit my post to make it more clear. –  Apostolos Apr 14 '11 at 16:45
@joriki: The model ${\mathfrak A}$ is given, and you need to provide a subset $X$ of the universe that witnesses the (second order existential) statement. Apostolos is saying that $X=\emptyset$ is such a witness. –  Andres Caicedo Apr 14 '11 at 16:47
@joriki: The empty set has nothing to do with the construction. The construction of $X$ is solely based on $R$ and defined before I mention the empty set. But because the questioner thought that if this $X$ happened to be empty then some problem may appear, I specifically noted that it doesn't matter whether $X$ is empty or not. What I wanted to do is to point out that the empty set can be considered a second order object. My construction doesn't require $X$ to be empty. –  Apostolos Apr 14 '11 at 17:49