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
    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?2011-04-14
  • 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
    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?2011-04-14
  • 0
    My 4th edition definitely has the first version (I'm staring at it right now), i.e. exactly as I have it on my question and exactly the sentence you consider in your first bullet point. This is quite strange no?2011-04-14
  • 0
    @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.2011-04-14
  • 0
    @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.2011-04-14
  • 0
    @Chuck: Well, I own an actual copy of the fifth edition (and by actual I mean made of paper) while the fourth edition I checked was a PDF version so that's probably the reason. Still I assume it's a typo in the book.2011-04-14
  • 0
    I guess my problem is more philosophical in nature, related to what exactly constitutes a proof in the metatheory. Because what prevents me from saying something like this: The validity of this sentence follows from the fact that for any model of $SOL$ the empty set will satisfy the given condition and since the emty set is a subset of any domain it will legitimately find itself in the range of the second-order quantifier. That just seems awful as a demonstration. And yet to define an $X$ explicitly also has unacceptable entanglements (e.g. the fact that it is empty because the first-order2011-04-14
  • 0
    (cont.) formula inside the set specifying the set in our metatheoretic universe is satisfied by the empty set (there are two 'empty sets' at play here, if you see what I am saying.)2011-04-14
  • 0
    @Chuck: First a slight correction. The empty set doesn't satisfy the formula for every universe. For example in the case of $R$ being empty as well we have that for every element $x$ of $X$ and every $y$ $Rxy\iff Xx$. But even if it did I don't see any problem in saying in the metatheory that the empty set is always a witness of the formula.2011-04-14
  • 0
    @Apostolos, @Andres: I'm sorry, I may be missing something essential, but I still think the first bullet point is not a valid argument. In the second bullet point, you let $R$ be any relation, then find $X$ depending on $R$ such that there is no $x$... -- that's a proof that the formula is valid. In the first bullet point, by contrast, you let $X$ be the empty set, but at the same time assume that this empty set is a specific set defined in terms of $R$. (Otherwise $R$ could just be the empty relation.) That imposes a restriction on $R$, but the formula is only valid if it's valid for all R.2011-04-14
  • 0
    @Apostolos: In your above reply to @Chuck, you speak of a "witness" for the formula. But you can't prove that a formula is valid by providing a single witness, since to be valid it has to be true in every interpretation of the language, and as you write yourself if you interpret $R$ as the empty relation then the empty set $X$ is not a witness.2011-04-14
  • 1
    @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.2011-04-14
  • 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