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!

  • 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).

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

  • 0
    @AsafKaragila Oh, I see. I thought you were saying that I was ignoring this answer.2012-11-26