Consider the structure $(\mathbb{R},+,*,0,1,<)$. We adjoin to it a subset $S$ of $\mathbb{R}$. Is it possible to give a single formula $F$ in the expanded language such that $F$ is true precisely when $S$ is an infinite subset of the reals? I know it is certainly possible by replacing $\mathbb{R}$ with $\mathbb{N}$ or by $\mathbb{Z}$. We can just say that $S$ has no upper bound, in the case of $\mathbb{N}$, or that $S$ has either no upper bound or no lower bound, in the case of $\mathbb{Z}$.

  • $\begingroup$ To clarify, you're adding a unary predicate symbol to the language? $\endgroup$ – Reveillark Jun 1 at 22:20

Yes. $S$ is infinite if and only if either $S$ is unbounded or $S$ contains pairs of elements arbitrarily close together: $\forall {\epsilon>0}\,\exists x\in S\,\exists y\in S(0< (x-y)^2<\epsilon)$.

| cite | improve this answer | |
  • 1
    $\begingroup$ You should make clear that your formula only corresponds to the second half of your written condition. $\endgroup$ – Stig Hemmer Jun 2 at 8:35
  • $\begingroup$ @StigHemmer Thanks, but imo it's already pretty clear. $\endgroup$ – David C. Ullrich Jun 2 at 14:38

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.