Every quantifier free formula defines a set with finitely many connected components?

110 Views Asked by At

I was trying to prove this claim:

"Every quantifier-free formula $\psi (x, a_1, ...a_m)$, where $a_1,...,a_m \in \mathbb{R}$, defines a set with finitely many connected components."

In other words, a set that is a finite union of points and open intervals.

I'm just starting to study logic so any help would be appreciated!

1

There are 1 best solutions below

4
On

Hint: first look at the sets defined by the atomic formulas. If $\psi$ is atomic it has the form $f(x) = g(x)$ where $f$ and $g$ are polynomials in $x$ and the set defined by $\psi$ is either the whole real line or a (possibly empty) finite set of points, so what you are trying to prove is true for atomic $\psi$. Now show that if your claim holds for $\psi_1$ and $\psi_2$, then it also holds for $\lnot \psi_1$, $\psi_1 \land \psi_2$ and $\psi_1 \lor \psi_2$ (which amounts to showing that the set of all subsets of $\Bbb{R}$ comprising a finite set of points and intervals is closed under complements, unions and intersections).