1
$\begingroup$

A set $A$ is expressible if there exists a first order logic formula with a single free variable $\alpha(x)$ such that $V_{I,v_{x=t}}(\alpha(x))=1 \iff t \in A$, that is, $A$ contains the values I should assign to the single free variable to make $\alpha(x)$ true.

Does the expressibility of a set $A$ imply the expressibility of the singleton sets $\{a\}, a\in A$ ?

E: Let $v:VAR \to U_I$ be a valuation (with $U_I$ being the universe of discourse of the interpretation $I$).

Then $v_{x=t}$ denotes the valuation that sastisfies: $v_{x=t}(x)=t, v_{x=t}(y)=v(y), \forall y\neq x$.

If $\alpha(x)$ is a formula with a single variable $x$, then after assigning some value to $x$, the truth value of $\alpha$ under the interpretation $I$ is independent of the valuation chosen.

$\endgroup$
6
  • $\begingroup$ What first-order language are you working in - the usual language of first-order set theory? It is not clear whether your notion of "expressible" is different from the standard notion of "definable": it would help if you explained your notation $V_{I,v_{x=t}}(\alpha(x))=1$. $\endgroup$ – Rob Arthan Oct 11 '15 at 20:33
  • $\begingroup$ I'm sorry Rob, I'm translating from my spanish notes and these terms seem to use very different words, could you tell me what the usual notion of "definable" is? $\endgroup$ – YoTengoUnLCD Oct 11 '15 at 20:45
  • $\begingroup$ Let ${\cal M} = (U, \ldots)$ be astructure for a first-order language (with universe $U$), A subset $A \subset U$ is definable iff there is a formula $\phi(x) \in \cal L$, such that for every $a \in U$, $a \in A$ iff ${\cal M} \models \phi(a)$ (where $\phi(a)$ means the result of interpreting $\phi$ with $x$ interpreted as $a$). $\endgroup$ – Rob Arthan Oct 11 '15 at 20:52
  • $\begingroup$ Yes! That's what I meant to say. Thanks a lot, Rob. $\endgroup$ – YoTengoUnLCD Oct 11 '15 at 20:54
  • $\begingroup$ So now we need to know what theory or class of models you are working in. E.g., in the theory of a linear order in the language with signature $(U, <)$ the only definable sets are the empty set and $U$ and so no singleton sets are definable if $U$ has more than one element. $\endgroup$ – Rob Arthan Oct 11 '15 at 20:59
2
$\begingroup$

From the comments, you are interested in examples like the first-order theory of the additive group of real numbers. In $(\Bbb{R}, +)$, you can define the set $A = \Bbb{R}$, using the formula $\phi(x) \equiv x= x$, but the only singleton subset of $A$ that you can define is $\{0\}$ (because a definable subset has to be invariant under the automorphism that sends $x$ to $-x$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.