Definability of structures

56 Views Asked by At

Good evening, I would like to know if my proof to a problem is correct. Below are the definitions and properties that I have used, followed by the problem in concern and my proof. Thank you.

Let $\varphi$ be a $\text{wff}$ (well-formed formula) of our language , $\frak{A}$ be a structure for the language, $s:V \to |\frak{A}|$ be a function from the set $V$ of all variables into the universe $|\frak{A}|$ of $\frak{A}.$ Informal meaning of $ \vDash_{\frak{A}} \varphi(s)$ is $\vDash_{\frak{A}} \varphi(s)$ if and only if the translation of $\varphi$ determined by $\frak{A},$ where the variable $x$ is translated as $s(x)$ wherever it occurs free, is true.

It follows that $\vDash_{\frak{A}} \forall x \varphi[s]$ iff for every $d \in |\frak{A}|,$ we have $\vDash_{\frak{A}} \varphi[s(x|d)],$ where $s(x|d)$ is the function exactly like $s$ except that at variable $x,$ it assumes $d.$

Suppose $\varphi$ is a formula such that all variables occurring free on $\varphi$ are included among $v_1,...,v_k.$ Then for elements $a_1,...,a_k$ of $|\frak{A}|, $$\ \vDash \varphi\|a_1,...,a_k\|$ means $\frak{A}$ satisfies $\varphi$ with some (and hence with any) functions $s:V \to |\frak{A}|$ for which $s(v_i)=a_i, 1\leq i \leq k.$


Let $\frak{R}=$ $(\mathbb{R};0,1,+, \cdot),$ where the language(with equality) has constant symbols $\bf{0}$ and $\bf{1}$ and two place function symbols $+$ and ${\bf{\cdot}} .$

If $a\geq 0,$ then $\vDash_{\frak{A}} \exists v_2 \ v_1 =v_2 \cdot v_2 \|a\|$

My Proof(Is it correct?): Let $s:V \to |\frak{R}|$ such that $s(v_1)=a.$

$\vDash_{\frak{R}} \exists v_2 \ v_1 =v_2 \cdot v_2 [s] $

$\Leftrightarrow $ for some $d \in |\frak{R}|, \vDash_{\frak{R}}$ $ v_1=v_2 \cdot v_2[s(v_2|d)].$

Indeed, if we let $d= \sqrt{a},$ then $ \vDash_{\frak{R}}$ $ v_1=v_2 \cdot v_2[s(v_2|d)] $ $\Leftrightarrow (\overline s(v_1), \overline s(v_2 \cdot v_2))=(a,\sqrt{a}\cdot\sqrt{a}) \in \ =^{{\frak{R}}}$

1

There are 1 best solutions below

0
On

Yes, this is correct.


Incidentally, this is a case where we can make things simpler by using a more natural language:

  • We want to show that, if $a\ge 0$, then $\mathfrak{R}\models\exists x(x\cdot x=a)$.

  • Given such an $a$, take $b=\sqrt{a}$.

  • Then $\mathfrak{R}\models b\cdot b=a$.

  • So $\mathfrak{R}\models\exists x(x\cdot x=a)$.

This obviously doesn't match the precise language you're using, but it's easy to translate it into that language; in particular, it may be much easier coming up with the proof if you first think about it in (something like) the language above.

The important simplification here is the incorporation of elements into formulas. This can be made precise: to every $\Sigma$-structure $\mathfrak{A}$, there is an associated larger language $\Sigma_\mathfrak{A}$ and an expansion $\hat{\mathfrak{A}}$ of $\mathfrak{A}$ which is a $\Sigma_\mathfrak{A}$-structure:

  • $\Sigma_\mathfrak{A}$ is the language gotten by adding to $\Sigma$ a set of new constant symbols $\{\underline{a}: a\in \mathfrak{A}\}$.

  • $\hat{\mathfrak{A}}$ is the expansion of $\mathfrak{A}$ to $\Sigma_\mathfrak{A}$ gotten by interpreting $\underline{a}$ as $a$, for each $a\in\mathfrak{A}$.

Then an expression like "$\exists x(x\cdot x=a)$" is shorthand for "$\exists x(x\cdot x=\underline{a})$," which is a genuine sentence in the language of $\Sigma_\mathfrak{A}$. Reasoning in this expanded language simplifies many proofs substantially.