Ver o código fonte de «Proba por contradición»


En [[lóxica]],a '''proba por contradición''' é unha forma de [[Proba matemática|proba]] que establece a [[verdade]] ou a [[Validez (lóxica)|validez]] dunha [[proposición (lóxica)|proposición]], demostrando que asumir a proposición como falsa leva a unha [[contradición]]. Aínda que se usa con bastante liberdade nas demostracións matemáticas, non todas [[Filosofía das matemáticas|as escolas de pensamento matemático]] aceptan este tipo de [[Proba non construtiva|probas non construtivas]] como universalmente válidas.<ref>Bishop, Errett 1967. ''Foundations of Constructive Analysis'', New York: Academic Press. {{ISBN|4-87187-714-0}}</ref>

De forma máis ampla, a proba por contradición é calquera forma de argumento que establece un enunciado chegando a unha contradición, aínda que o suposto inicial non sexa a negación do enunciado que se quere demostrar. Neste sentido xeral, a proba por contradición tamén se coñece como '''proba indirecta''' ou '''''redución ao absurdo'''''.<ref>{{Cita web|url=https://www.britannica.com/topic/reductio-ad-absurdum|title=Reductio ad absurdum {{!}} logic|website=Encyclopedia Britannica|language=en|access-date=2019-10-25}}</ref>

Unha demostración matemática que emprega a proba por contradición normalmente procede do seguinte xeito:

# A proposición a demostrar é ''P''.
# Supoñemos que ''P'' é falso, é dicir, asumimos ''¬P''.
# Demostramos logo que ''¬P'' implica falsidade. Isto normalmente conséguese derivando dúas afirmacións mutuamente contraditorias, ''Q'' e ''¬Q'', e apelando ao [[principio da non contradición]].
# Dado que asumir que ''P'' é falsa leva a unha contradición, conclúese que ''P'' é verdadeira.

== Formalización ==
O principio pódese expresar formalmente como a [[fórmula proposicional]] ''¬¬P ⇒ P'', equivalentemente ''(¬P ⇒ ⊥) ⇒ P'', que se pode ler como: "Se asumir ''que P'' é falsa implica falsidade, entón ''P'' é verdadeira".

Na [[dedución natural]] o principio toma a forma da [[regra de inferencia]] seguinte

: <math>\cfrac{\vdash \lnot \lnot P}{\vdash P}</math>

que podemos ler como: "Se demostramos <math>\lnot\lnot P</math>, daquela podemos concluír <math>P</math>".

No [[cálculo de secuentes]] o principio exprésase pola secuencia

: <math>\Gamma, \lnot\lnot P \vdash P, \Delta</math>

que podemos ler como: “As hipóteses <math>\Gamma</math> ''e'' <math>\lnot\lnot P</math> implican a conclusión <math>P</math> ''ou'' <math>\Delta</math>."

== Xustificación ==
Na [[lóxica proposicional]] o principio pódese xustificar escribindo a [[táboa de verdade]] da proposición ''¬¬P ⇒ P'', que demostra que é unha [[Tautoloxía (lóxica)|tautoloxía]]:
{| class="wikitable" style="margin:1em auto; text-align:center;"
! style="width:80px" |''p''
! style="width:80px" | {{Math|''¬p''}}
! style="width:80px" | {{Math|''¬¬p''}}
! style="width:80px" | {{Math|''¬¬p ⇒ p''}}
|-
! style="background:papayawhip" | T
! F
! T
! T
|-
! style="background:papayawhip" | F
! T
! F
! T
|}
Outra forma de xustificar o principio é derivalo ao [[principio do terceiro excluído]], isto é, asumimos ''¬¬P'' e procuramos demostrar ''P''. Pola lei do terceiro excluído ''P'' cúmprese ou non se cumpre:

# se ''P'' se cumpre, logo ''P'' cúmprese.
# se ''¬P'' se cumpre, daquela demostramos falsidade aplicando ao [[Principio de non contradición|principio da non contradición]] a ''¬P'' e ''¬¬P'', o que nos permite concluír ''P''.

En calquera caso, establecemos ''P'' . Resulta que, pola contra, a proba por contradición pódese utilizar para derivar a lei do medio excluído.

No cálculo de secuentes a proba por contradición derívase das regras de inferencia para a negación:

: <math>\cfrac{\cfrac{\cfrac{\ }{\Gamma, P \vdash P, \Delta} \; (I)}{\Gamma, \vdash \lnot P, P, \Delta} \; ({\lnot}R)}{\Gamma, \lnot\lnot P \vdash P, \Delta} \; ({\lnot}L)</math>

== Relación con outras técnicas de proba ==

=== Refutación por contradición ===
Sería similar mais usada para probar unha negación en vez dunha afirmación

# A proposición a demostrar é ''¬P''.
# Supoñemos ''P.''
# Demostramos a falsidade de ''P''.
# Por tanto temos ''¬P'' .

Comparamos coa proba por contradición xa comentada enriba:

# A proposición a demostrar é ''P''.
# Supoñemos ''¬P''.
# Demostramos a falsidade de ''¬P''.
# Por tanto temos ''P.''

=== Principio do terceiro excluído ===
A proba por contradición equivale ao [[principio do terceiro excluído]] formulada por primeira vez por [[Aristóteles]].

A é verdadeiro ou é falso, non hai unha terceira posibilidade: '''A v ¬A'''

=== Principìo da non contradición ===
O [[Principio de non contradición|principio da non contradición]] foi declarado por primeira vez como un principio metafísico por [[Aristóteles]]. 

A non pode ser A e non-A ao mesmo teempo: '''¬(A ∧ ¬A)'''

== Exemplos de probas por contradición ==

=== Elementos de Euclides ===
Unha aparición temperá da proba por contradición pódese atopar nos [[Elementos de Euclides]], Libro 1, Proposición 6:<ref>{{cita web | url=https://mathcs.clarku.edu/~djoyce/elements/bookI/propI6.html | title=Euclid's Elements, Book 6, Proposition 1 | access-date=2 October 2022}}</ref>

: Se nun triángulo dous ángulos son iguais, entón os lados opostos aos ángulos iguais tamén son iguais.

A demostración procede asumindo que os lados opostos non son iguais, e deriva unha contradición.

=== Teorema dos ceros de Hilbert ===

: Se <math>f_1,\ldots,f_k</math> son [[Polinomio|polinomios]] con {{Mvar|n}} indeterminados con coeficientes [[Número complexo|complexos]], que non teñen [[Raíz dunha función|ceros]] comúns, daquela existen polinomios <math>g_1,\ldots, g_k</math> tal que <math>f_1g_1+\ldots +f_kg_k=1.</math>

Hilbert demostrou a afirmación supoñendo que non existen tales polinomios <math>g_1, \ldots, g_k</math> e derivou unha contradición.<ref>{{Cita libro|last=Hilbert |first=David |author-link=David Hilbert |date=1893 |title=Ueber die vollen Invariantensysteme |journal=[[Mathematische Annalen]] |volume=42 |issue=3 |pages=313–373 |doi=10.1007/BF01444162 | url=https://resolver.sub.uni-goettingen.de/purl?PPN235181684_0042}}</ref>

=== Infinidade de primos ===
O [[teorema de Euclides]] afirma que hai infinitos números primos. No tratado [[Elementos de Euclides]] o teorema aparece no Libro IX, Proposición 20:<ref>{{cita web | url=https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html | title=Euclid's Elements, Book 9, Proposition 20 | access-date=2 October 2022}}</ref>

: Os números primos son máis que calquera multitude asignada de números primos.Considere calquera lista finita de números primos ''p''<sub>1</sub> , ''p''<sub>2</sub>, ... , ''p<sub>n</sub>''. Imos mostrar que existe polo menos un número primo adicional que non figura nesta lista. Sexa ''P'' o produto de todos os números primos da lista: ''P'' = ''p''<sub>1</sub>''p''<sub>2</sub> ... ''p<sub>n</sub>''. Sexa ''q'' = ''P'' + 1. Entón ''q'' pode ser primo ou non:

* Se ''q'' é primo, é un primo máis que non está na lista.
* Se ''q'' non é primo, entón algún [[Número primo|factor primo]] ''p'' divide ''q''. Se este factor ''p'' estivese na nosa lista, entón dividiría ''P'' (xa que ''P'' é o produto de todos os números da lista); pero ''p'' tamén divide ''a P'' + 1 = ''q'', como acabamos de dicir. Se ''p'' divide ''a P'' e tamén ''a q,'' entón ''p'' tamén debe dividir a diferenza  dos dous números, que é (''P'' + 1) − ''P'' = 1. Como ningún número primo divide a 1, ''p'' non pode estar na lista. Isto significa que hai polo menos un número primo máis que non é dos da lista.

== Exemplos de refutacións por contradición ==

=== Irracionalidade da raíz cadrada de 2 ===
A proba clásica de que a raíz cadrada de 2 é irracional é unha refutación por contradición.<ref>{{cita web|url=http://www.math.utah.edu/~pa/math/q1.html|title=Why is the square root of 2 irrational?|last=Alfeld|first=Peter|date=16 August 1996|work=Understanding Mathematics, a study guide|publisher=Department of Mathematics, University of Utah|access-date=6 February 2013|data-arquivo=31 de decembro de 2023|url-arquivo=https://web.archive.org/web/20231231064504/https://www.math.utah.edu/~pa/math/q1.html|url-morta=yes}}</ref> Debemos probar a negación ''¬ ∃ a, b ∈ <math>\mathbb{N}</math>'' ''tal que'' ''a/b = {{Sqrt|2}}'' supoñendo que existen números naturais ''a'' e ''b'' cuxa razón é a raíz cadrada de dous, e deriva unha contradición.

=== Proba por descenso infinito ===
A [[proba por descenso infinito]] é un método de demostración polo que se mostra que un obxecto máis pequeno coa propiedade desexada non existe:

* Supoña que hai un obxecto máis pequeno coa propiedade desexada.
* Demostrar que existe un obxecto aínda máis pequeno coa propiedade desexada, derivando así unha contradición.

== Notas ==
{{reflist|30em}} 
{{Reflist|group=groupname}}
== Véxase tamén ==
{{Commonscat}} 
=== Bibliografía ===
* {{cita libro|last1=Franklin|first1=James|author-link1=James Franklin (philosopher)|last2=Daoud|first2=Albert|title=Proof in Mathematics: An Introduction|year=2011|publisher=Kew|location=chapter 6|isbn=978-0-646-54509-7|url=http://www.maths.unsw.edu.au/~jim/proofs.html}}
=== Outros artigos ===
*[[Principio do terceiro excluído]]
*[[Principio da non contradiction]]
*[[Proba do descenso infinito]]
*[[Modus tollens]]

=== Ligazóns externas ===

* [http://zimmer.csufresno.edu/~larryc/proofs/proofs.contradict.html Proof by Contradiction] from Larry W. Cusick's [http://zimmer.csufresno.edu/~larryc/proofs/proofs.html How To Write Proofs]
* [http://www.iep.utm.edu/reductio/ Reductio ad Absurdum] Internet Encyclopedia of Philosophy; ISSN 2161-0002


{{control de autoridades}}
[[Categoría:Lóxica]]
[[Categoría:Lóxica matemática]]
[[Categoría:Wikipedia:Páxinas con traducións non revisadas]]