Sección 07: Conceptos teóricos de prueba
- Page ID
- 101668
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Utilizaremos el símbolo '' para indicar que una prueba es posible. Este símbolo se llama el torniquete. A veces se le llama torniquete único, para subrayar el hecho de que este no es el símbolo de torniquete doble () que usamos para representar la vinculación semántica en el capítulo 5.
Cuando escribimos {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...} \(\mathcal{B}\), esto significa que es posible dar una prueba de\(\mathcal{B}\) con\(\mathcal{A}\) 1,\(\mathcal{A}\) 2,... como premisas. Con una sola premisa, dejamos fuera las llaves, por lo\(\mathcal{A}\) que\(\mathcal{B}\) significa que hay una prueba de\(\mathcal{B}\) con\(\mathcal{A}\) como premisa. Naturalmente, `\(\mathcal{C}\)significa que hay una prueba de\(\mathcal{C}\) que no tiene premisas.
A menudo, las pruebas lógicas se llaman derivaciones. Entonces\(\mathcal{A}\) se\(\mathcal{B}\) puede leer como '\(\mathcal{B}\)es derivable de\(\mathcal{A}\).'
Un teorema es una oración que es derivable sin premisas; es decir,\(\mathcal{T}\) es un teorema si y solo si\(\mathcal{T}\).
No es demasiado difícil demostrar que algo es un teorema— sólo hay que dar una prueba de ello. ¿Cómo podrías demostrar que algo no es un teorema? Si su negación es un teorema, entonces podrías aportar una prueba. Por ejemplo, es fácil de probar¬ (\(Pa\)&¬\(Pa\)), lo que demuestra que (\(Pa\)&¬\(Pa\)) no puede ser un teorema. Para una oración que no es ni teorema ni la negación de un teorema, sin embargo, no hay manera fácil de mostrar esto. Tendrías que demostrar no sólo que ciertas estrategias de prueba fracasan, sino que ninguna prueba es posible. Incluso si fallas en tratar de probar una oración de mil maneras diferentes, quizás la prueba sea demasiado larga y compleja para que la bajes.
Dos oraciones\(\mathcal{A}\) y\(\mathcal{B}\) son probablemente equivalentes si y solo si cada una puede derivarse de la otra; es\(\mathcal{A}\) decir,\(\mathcal{B}\)\(\mathcal{B}\) y\(\mathcal{A}\)
Es relativamente fácil demostrar que dos oraciones son probablemente equivalentes, solo requiere un par de pruebas. Demostrar que las oraciones no son probablemente equivalentes sería mucho más difícil. Sería tan difícil como demostrar que una oración no es un teorema. (De hecho, estos problemas son intercambiables. ¿Se te ocurre una oración que sería un teorema si y solo si\(\mathcal{A}\) y\(\mathcal{B}\) fueran demostrablemente equivalentes?)
El conjunto de oraciones {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...} es demostrablemente inconsistente si y solo si de ella se deriva una contradicción; es decir, para alguna oración\(\mathcal{B}\), {\(\mathcal{A}\)1,\(\mathcal{A}\) 2,...}\(\mathcal{B}\) y {\(\mathcal{A}\) 1,\(\mathcal{A}\) 2,...} ¬\(\mathcal{B}\).
Es fácil demostrar que un conjunto es demostrablemente inconsistente: Solo hay que asumir las oraciones del conjunto y demostrar una contradicción. Demostrar que un conjunto no es demostrablemente inconsistente será mucho más difícil. Requeriría algo más que aportar una prueba o dos; requeriría demostrar que las pruebas de cierto tipo son imposibles.