定理

维基百科,自由的百科全书
跳转至: 导航搜索
Confusion grey.svg
提示:本条目的主题不是科學定律

定理英语Theorem)是經過受邏輯限制的證明為真的陈述。一般來說,在數學中,只有重要或有趣的陳述才叫定理。證明定理是數學的中心活動。一个定理陈述一个给定类的所有(全称)元素一种不变的关系,这些元素可以是无穷多,它们在任何时刻都无区别地成立,而没有一个例外。(例如:某些ax,某些ay,就不能算是定理)。

猜想是相信為真但未被證明的數學敘述,或者叫做命题,當它經過證明後便是定理。猜想是定理的來源,但並非唯一來源。一個從其他定理引伸出來的數學敘述可以不經過成為猜想的過程,成為定理。

如上所述,定理需要某些邏輯框架,繼而形成一套公理公理系統)。同時,一個推理的過程,容許從公理中引出新定理和其他之前發現的定理。

命題邏輯,所有已證明的敘述都稱為定理。

各種數學敘述(按重要性來排列)[编辑]

  1. 引理(又稱輔助定理補理)-某個定理的證明的一部分的敘述。它並非主要的結果。引理的證明有時還比定理長,例如舒尔引理
  2. 推论-一個從定理隨之而即時出現的敘述。若命題B可以很快、簡單地推導出命題A,命題A為命題B的推论。
  3. 命題
  4. 定理
  5. 數學原理

結構[编辑]

定理一般都有许多條件。然後有結論——一個在條件下成立的數學敘述。通常寫作「若條件,則結論」。用符號邏輯來寫就是條件→結論。而當中的證明不視為定理的成分。

逆定理[编辑]

若存在某敘述為A→B,其逆敘述就是B→A。逆敘述成立的情況是A←→B,否則通常都是倒果為因,不合常理。若果敘述是定理,其成立的逆敘述就是逆定理

  • 若某敘述和其逆敘述都為真,條件必要且充足
  • 若某敘述為真,其逆敘述為假,條件充足。
  • 若某敘述為假,其逆敘述為真,條件必要。

逻辑中的定理[编辑]

在逻辑语言中的定理,它表示一个公式集合,并且该公式集合中的每一个公式都代表着知识的一个片段,由此我们可以给定理一个更准确的表达(这里所说的定理指的是在一阶逻辑中的定理,通常来说任意一个命题集合往往不一定是定理)。
定理在逻辑中的定义
一个定理是一个含有(L-propositions)由建立于语言集合L上的命题组成的非空集合,这个定理(或这个命题集合)我们记作T,这些建立于语言集合L上的命题必须符合如下属性:
对所有在T中的命题φ(L-propositions),如果T |= φ,那么φ∈T
比如一个永真命题集合是一个定理,这个永真命题集合被包含在所有建立在语言集合L上的定理中
我们说一个定理是另外一个定理T的扩展(extension),前提是该定理包含定理T
有一个命题集合A,我们称一个集合命题集合A的定理(记作)Th (A),当Th (A)={ φ | A |= φ }
显而易见A |= Th (A),所以Th(A)是一个定理
比如我们有一个集合,记做G,G有三个基于语言L上的命题,语言L={ e,f },其中e是常数符号,f是函数符号
三个命题如下:
\forall x \forall y \forall z f(f(x,y),z)=f(x,f(y,z))
\forall x  f(x,e)=x \and f(e,x)=x
\forall x \exist y f(x,y)=e \and f(y,x)=e
那么如果有Th (G)={ φ | G |= φ },那么Th(G)是G的定理
当然如果A和B是两个命题集合且满足A⊆B,那么Th (A)⊆Th (B)
我们说一个定理T是完整的(Complete),当且仅当对于和T一样构建在同样语言集合上的所有命题φ,要么φ∈T,要么˥φ∈T
注意:这个概念不能和定理T的完备性(Completude)混淆,完备性是证明在定理T中的永真命题是递推可枚举的(recursivement enumerable),但是不能说它一定是完整的
一个定理T称作是稳健的(Consistante),当且仅当∀φ∈T,˥φ∉T
不是所有的定理T是完整的
比如Th(Φ)一个空集合{Φ}的定理是所有真命题集合,但是Th(Φ)不是完整的
假如我们有ψ= ∃x∃y x≠y对于ψ来说,它既不是永真命题,也不是永假命题,它是一个可满足式的命题,
也就是说Th(Φ)|ǂ ψ且Th(Φ)|ǂ ˥ψ
因此ψ∉Th(Φ),所以我们说Th(Φ)不是完整的
我们说对所有的解释(Interpretation)I,Th (I)是一个定理,并且Th(I)既是稳健的又是完整的

命题集合的可计算性问题(Calculabilite)[编辑]

我们可以通过可计算性(Calculabilite)这一概念来解释命题集合的满足性问题,也就是说是对于命题集合在可决定性问题上(Decidabilite)是否存在一个肯定的测试结果,还是一个否定的测试结果 我们知道当我们用任何一种计算机语言编写程序编译成功并执行中,在计算机上执行的目标代码是以二进制表示的一串0和1的组合比如01010011........... 如果转化成十进制表示的话,这个二进制组合就对应一个实数 更进一步,对于一个任一公式φ(公式是一个算法),我们通过计算机编程实现公式φ的算法,根据上面的描述,该程序必定有一个唯一的实数与之对应 也就是说φ→ n(φ)n(φ)是一个代表由公式φ所对应的实数(这个函数是单射的(Injection)) 那么我就可以简单的通过一个一一对应(Bijection)的函数g对应于某一个一阶逻辑的公式集合印射到到自然数集合中 那么我们假设公式集合中有ψ个公式,ψ是一个自然数,对于公式集合中的每一个公式,我们假设{φ0,φ1,....},它们对应的自然数n(φi)<ψ 通过这样的方式我们把逻辑和计算机可计算性问题相联系,也就是说如果要证明一阶逻辑公式的可满足性问题转化成计算机可计算性的问题加以证明,如果在计算机可决定性问题的证明中,证明它是一个可决定的问题,既它是一个肯定测试,那么对于对应的逻辑公式来说,该公式必定是可满足的

  • 定理1一个没有量词(Quantificateur)的有限命题集合Γ的可满足性问题(Satisfaisabilite)是可以决定的(Decidable)
证明:假设命题集合Γ中的每个元素由以下组成:
一个以语言集合L构建的项集合(L-Term),我们记作项集合T,根据项的组成语法规则,T肯定是有有限个数的项,并且每个项是由语言集合L中的符号有限组成。
如果T为空集(即空项集合),那么我们在SAT命题的情况下,Γ就认为是可决定的(Decidable)。
如果Γ是可满足的,假设存在一个解释(或模型)I, I |= Γ,I的解释域是D,假设存在另外一个解释域D',满足以下条件D'=I (T)={I (t)∈D|t∈T}
我们在D'上定义另一个解释(或模型)I',定义如下:

//如果……(under construction)

  • 定理2一阶逻辑命题的永真性(Validite)是可以通过一个肯定测试(Test Positif)来知道的。
    • 证明:
  • 定理3所有公理化(Axiomatisable)的定理T是可递推枚举的(Recursivement Enumerable)。
    • 证明:
  • 定理4所有公理化的完整的(Complete)定理T是可递推的。
    • 证明:
  • 定理5所有可递推枚举的定理T是公理化的。
    • 证明:

参见[编辑]