2
$\begingroup$

I did the following two related exercises in Just/Weese on page 114:

18: Show that if $z$ is a finite set and $y \subset z$ then there exists a formula $\varphi(x)$ of $L_S$ such that $y = \{x \in z: \varphi (x) \}$.

19: Let $Y$ be the collection of all $y \subset \omega$ for which there exists a formula $\varphi (x)$ without parameters such that $y = \{x \in \omega : \varphi (x) \}$. Show that $Y$ is countable.

One problem I have is that the first one is rated "difficult" and the second one is rated "extra difficult" but both of my answers are not only very simple but it also only took me a minute to come up with each so both are probably wrong and I am missing something. Here they are:


18: Let $y$ be the set $y = \{y_1 , \dots , y_n \} \subset z$. Let $\varphi(x) = (x = y_1) \lor \dots (x=y_n)$. Then $y = \{ x \in \omega : \varphi (x) \}$.


19: Let $F_n$ be the set of all formulas $\varphi$ in $L_S$ such that $\varphi$ consists of $n$ characters. Since there are only finitely many symbols in $L_S$, logical and non-logical combined, $F_n$ is finite. Then $F = \bigcup_{n \in \mathbb N} F_n$, the set in which each element corresponds to a definable $y \subset \omega$, is a countable union of finite sets and hence countable.

Could you point out what I am missing? Thanks for your help!

  • 0
    What are $y_1,y_2,\dots$? All we are given is a set $A$ that satisfies the formal condition of finiteness.2012-11-25
  • 0
    @AndréNicolas I thought if it's finite I can enumerate it.2012-11-25
  • 1
    We are looking for a formula in the language of say ZF. The expression in the post was at most an outline of how one might construct such a formula, with all the hard detail missing.2012-11-25
  • 1
    18 is deeper than it looks -- if it is true at all, it depends on the Axiom of Foundation/Regularity, which is not something you see every day. (Without Foundation, $z$ could be a set of two different Quine atoms, and those cannot be distinguished by any formula). This suggests that there's probably an induction on the rank of the sets hidden somewhere.2012-11-26
  • 1
    By the way, notice that what you're asked to prove in 18 _doesn't_ assume that $z\subseteq \omega$.2012-11-26

2 Answers 2

1

The problem with your solution to 19 is the the correspondence between $F_n$ and $y$ is not itself definable by a formula within the system (there's a diagonalization argument showing this). Therefore you have no guarantee that this correspondence is a set, which means that you cannot be sure that a bijection between the countably many formulas and the describable subsets exists as a set.

(In fact it is not even clear to me a priori that $Y$ is necessarily a set).

  • 0
    Is it necessary to make this collection internally definable?2012-11-25
  • 0
    @AsafKaragila: The _correspondence_ must be internally definable if one just wants to wave his hand and construct a function (as a set) from it. I'm not sure it is essential to make the _collection_ internally definable, but it sure needs to be a set if it is to be countable.2012-11-25
  • 0
    I'm even more confused now. I'll return later and try to decipher my initial thoughts on this.2012-11-25
  • 0
    Dear Henning, thank you for your answer. What about 18? Is there anything to say?2012-11-25
  • 2
    @Matt: As regards 18 I agree with Asaf(s now deleted answer) that "$(x=y_1)$" is not necessarily a formula. For example, suppose $z$ is a set of 100 well-orderings for $\mathbb R$. Then $y_1$ well-orders $\mathbb R$, and as we know it is not easy to write a formula that expressed that $x$ is exactly _that_ well-ordering of $\mathbb R$.2012-11-25
  • 1
    My feeling is that 18 would be easier to attack in the equivalent form "if $x\ne y$ then there is a formula $\phi$ such that $\phi(x)$ and $\neg\phi(y)$". But the details elude me.2012-11-25
  • 2
    To complement what Henning is saying, [this MO answer](http://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numbe/44129#44129) elaborates on the issues of defining definability.2012-11-26
0

In your solution to (19), $F_{n}$ the set of all formulas $\varphi$ in $L_{S}$ such that $\varphi$ consists of $n$ characters is not finite, because the set of all atomic formulas $P=\lbrace p_{1},p_{2}, \ldots \rbrace $ usually is not finite.

  • 1
    There are really just two atomic formulas in one free variable. $x=x$ and $x\in x$.2012-11-26
  • 0
    So I did not get the question correctly. You say that it means we have no variable except x. THANKS ASAF KARAGILA2012-11-26
  • 0
    Oh, you did make a good point, and Matt did ignore that which is a mistake. But not an actual mistake, as we only want formulas with one free variable.2012-11-26
  • 0
    The solution to (18) seems to be true.2012-11-26
  • 0
    @AsafKaragila Please do not invent stories of your own that people not mentioned in the story cannot distinguish from reality. I did not ignore anything.2012-11-26
  • 0
    @Matt: Then how come your proposed solution to 19 says all formulas of length $n$ rather than all formula with $x$ as the only free variable? I am sure you were aware of this, you didn't write it though.2012-11-26
  • 0
    @AsafKaragila Oh, I see. I thought you were saying that I was ignoring this answer.2012-11-26