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