Eliminationstheorie

09.11.2015, 12:39	mariem	Auf diesen Beitrag antworten »
Eliminationstheorie Hallo, sei $\begin{eqnarray} L \end{eqnarray}$ ein Differentialoperator. Sei $\begin{eqnarray} L=\{+, ' , 0, 1, T, C\} \end{eqnarray}$ die Sprache wobei $\begin{eqnarray} ' : \frac{d}{dz} \end{eqnarray}$ , $\begin{eqnarray} T(x) \Leftrightarrow x \notin \mathbb{C} \end{eqnarray}$ (also ncht konstant) , $\begin{eqnarray} C(x) \Leftrightarrow x \in \mathbb{C} \end{eqnarray}$ (also konstant) $\begin{eqnarray} x, f, g \in \mathbb{C}[z, e^{\lambda z } \mid \lambda \in \mathbb{C}]. \end{eqnarray}$ (In diesen Ring haben die Differentialgleichungen immer eine Lösung.) Wir haben die folgende Formel $\begin{eqnarray} \exists x \phi (x , \overline{y}) \end{eqnarray}$ wobei $\begin{eqnarray} \phi: \displaystyle{\bigwedge_{j=1}^n \phi_j} \end{eqnarray}$ mit $\begin{eqnarray} \phi_j : \left\{\begin{matrix}<br /> Lx=f \\ <br /> Lx \neq g<br /> \end{matrix}\right.\} \end{eqnarray}$ Ich will eine äquivalente quantorenfreien Formel finden. Ein Beipspiel der obigen Formel ist folgendes: $\begin{eqnarray} \begin{pmatrix}<br /> x'+x=f\\ <br /> x''+x'=g<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> x'+x=f\\ <br /> f'=g<br /> \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix}<br /> x'+x=f\\ <br /> x''+2x'=g<br /> \end{pmatrix} \overset{\text{gaußsche Eliminationsverfahren}}{\underset{\text{Linearitaet der Ableitung}}{\Leftrightarrow}} \begin{pmatrix}<br /> x'+x=f\\ <br /> f'=g<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> x=f-g+f'\\ <br /> x'=g-f'<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> x=f-g+f'\\ <br /> f-g'+f''=g-f'<br /> \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix}<br /> x'+x=f\\ <br /> x''+2x' \neq g<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> x'+x=f\\ <br /> x'\neq g-f<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> x'+x=f\\ <br /> x \neq g-2f<br /> \end{pmatrix} \Leftrightarrow \begin{pmatrix}<br /> \begin{pmatrix}<br /> (g-2f)'+(g-2f) \neq f\\ <br /> x'+x=f<br /> \end{pmatrix}\\ <br /> \begin{pmatrix}<br /> (g-2f)'+(g-2f)=f\\ <br /> x'+x=f\\ <br /> \text{kern}(x'+x) \neq \{0\}<br /> \end{pmatrix}<br /> \end{pmatrix} \overset{\text{In diesen Ring gilt immer kern}(x'+x) = \{0\}}{\Leftrightarrow } \begin{pmatrix}<br /> (g-2f)'+(g-2f) \neq f\\ <br /> x'+x=f<br /> \end{pmatrix} \end{eqnarray}$ Also um die Quantorenelimination zu zeigen habe ich folgendes gemacht: Wenn die Formel in der Form $\begin{eqnarray} \exists x \phi (x , \overline{y}) \end{eqnarray}$ wobei $\begin{eqnarray} \phi: \displaystyle{\bigwedge_{j=1}^n L_j x=f_j } \end{eqnarray}$ wollen wir zeigen dass man in der Form $\begin{eqnarray} \exists x \phi (x , \overline{y}) \end{eqnarray}$ wobei $\begin{eqnarray} \phi: \displaystyle{Lx=f \land \psi} \end{eqnarray}$ wobei $\begin{eqnarray} \psi \end{eqnarray}$ kein $\begin{eqnarray} x \end{eqnarray}$ , sondern nur $\begin{eqnarray} f \end{eqnarray}$ und $\begin{eqnarray} g \end{eqnarray}$ enthält. Um das zu tun benutzt man Induktion für $\begin{eqnarray} n \end{eqnarray}$ , für die Anzahl der der Gleichingen, oder? Ich habe das folgenderweise gemacht: Induktionsanfang: Für $\begin{eqnarray} n=1 \end{eqnarray}$ haben wir eine Gleichung, also ist es in der gewünschte Form. Induktionsbehauptung: Wir behaupten dass es für $\begin{eqnarray} n=k \end{eqnarray}$ gilt, also wenn $\begin{eqnarray} \phi \ \ k \end{eqnarray}$ enthält, dann können wir das in der Form $\begin{eqnarray} Lx=f \land \psi \ \ \text{ wobei } \psi \text{ kein } x \text{ enthält} \end{eqnarray}$ reduzieren. Induktionsschritt: Wir wollen zeigen dass es für $\begin{eqnarray} n=k+1 \end{eqnarray}$ gilt, also wenn wir $\begin{eqnarray} k+1 \end{eqnarray}$ Gleichungen haben können wir dieses System in der Form $\begin{eqnarray} Lx=f \land \psi \ \ \text{ wobei } \psi \text{ kein } x \text{ enthält} \end{eqnarray}$ reduzieren. Von der Induktionsbehauptung wissen wir dass wir die ersten $\begin{eqnarray} k \end{eqnarray}$ Gleichungen in der obigen Form reduzieren können. Also haben wir zwei Gleichungen die das $\begin{eqnarray} x \end{eqnarray}$ und desses Ableitungen enthalten. Wenn in diesen zwei Gleichungen eine gemeinsame Ableitung von $\begin{eqnarray} x \end{eqnarray}$ ist löst man für diese Ableitung in der einen Gleichung und setzt diese in der anderen Gleichung ein. Wenn in diesen zwei Gleichungen keine gemeinsame Ableitung von $\begin{eqnarray} x \end{eqnarray}$ ist, leitet man die eine Gleichung sooft ab bis wir eine bekommen. Also bekommen wir die gewünschte Form. Ist das so richtig? Danach muss ich das gleiche machen für den Fall $\begin{eqnarray} \exists x \phi (x , \overline{y}) \end{eqnarray}$ wobei $\begin{eqnarray} \phi: \displaystyle{\bigwedge_{j=1}^n L_j x\neq g_j } \end{eqnarray}$ , und dann können wir die Form $\begin{eqnarray} \phi: \displaystyle{\bigwedge_{j=1}^n \phi_j} \end{eqnarray}$ mit $\begin{eqnarray} \phi_j : \left\{\begin{matrix}<br /> Lx=f \\ <br /> Lx \neq g<br /> \end{matrix}\right. \end{eqnarray}$ in den oben ernannten zwei Fällen reduzieren. Ist das richtig?

1

Verwandte Themen