2
$\begingroup$

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.

  • 0
    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$.2011-04-14

1 Answers 1

3

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$.

  • 0
    @Apostolos: I see now. Sorry for being a bit dense. I was thrown off by @Andres' comment "Apostolos is saying that $X=\emptyset$ is such a witness." -- I understand now that that's not what you were saying.2011-04-14