Show that if $A$ is finite, then $Def(A) = P(A)$, where $P(A)$ is the power set of $A$.

75 Views Asked by At

Definition: $b$ is definable from $a$ iff there is a formula $\phi$ with parameters in $a$ so $b = \{x \in a: \phi^a(x)\}$. $Def(a)$ is the set of all sets which are definable from $a$.

Definition: Given a set $a$ and a formula $\phi$ we define formula $\phi(a)$ to be the formula derived from $\phi$ by replacing each occurrence of "$\forall x_i$" in $\phi$ by an occurrence of "$\forall x_i \in a$".

Show that if $A$ is finite, then $Def(A) = P(A)$, where $P(A)$ is the power set of $A$.

My try: since $A$ is finite, let's say that $A = \{a_1, a_2, \ldots, a_n\}$. Let $B = \{x \in A: x \neq a_1, x \neq a_2, \ldots, x \neq a_n\}$, hence we have $\emptyset$. We could do the similar trick for any subset of $A$. Is this the right approach?

1

There are 1 best solutions below

0
On BEST ANSWER

Clearly, if $B \in \text{Def}(A)$, then $B \in \mathcal{P}(A)$ by the definition of definability.

Conversely, if $B \subseteq A$, then $B = \{ b_1,\ldots,b_k\}$ for some $k\geq 0$ ($k=0$ corresponds to $B=\emptyset$). We can then define $B$ by the formula $\phi(x) = \bigvee^{k}_{i=1} x=b_i$.