我一直在尝试通过 YouTube 上的“数学的光明面”系列视频学习朴素集合论。到目前为止,我已经能够理解后继映射和否0否0\mathbb{N}_{0}。我现在已经知道他对加法的定义。他的定义如下:
加法是一张地图 否0×否0→否0加法是一张地图 否0×否0→否0\text{Addition is a map } \mathbb{N}_{0} \times \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}
(米,n )↦米+ n(米,n)↦米+n(m,n) \mapsto m + n
他还给出了以下内容:
米+ 0 : =米米+0:=米m+0:=m
m + s (n ):= s (m + n )米+s(n):=s(米+n)m + s(n) := s(m+n)
我能够理解他是如何得出这些结论的,因为他在视频中很好地解释了这些结论。然而,在我看来,这似乎是循环论证。你如何用+++符号,这不是违背定义的目的吗?
在进一步研究的过程中,我找到了以下文章:。然而,作为一个完全的初学者,上面的答案对我来说没有多大意义,我想知道是否有人不使用加法来定义加法+++(或者这是否可能)?
\endgroup
3
最佳答案
3
这个定义中看似循环,其实是假象。可以证明存在一个独特的函数F:N × N → NF:否×否→否f:\mathbb N\times\mathbb N\to \mathbb N使得
\begin{align}
f(m,0) &= m \, , \tag{1}\label{1}\\
f(m,s(n)) &= s(f(m,n)) \, , \tag{2}\label{2}
\end{align}
对全部m , n∈N米,n∈否m,n\in\mathbb N。一旦我们确定了这一事实,定义+++作为这个独特的功能。这与定义埃X埃Xe^x作为初值问题的解是′= y,是(0 )= 1是′=是,是(0)=1y’=y,\, y(0)=1,前提是我们知道 (a) 这样的解存在,并且 (b) 它是唯一的。
那么我们如何证明FFf? 由于所讨论的定理非常基础,因此答案对您使用的基础系统很敏感。如果您在集合论环境中工作,那么您通常会诉诸以下内容。
递归定理。如果AAa是集合的一个元素XXX, 和G:X→十G:X→Xg:X\to X是一个函数,那么存在一个唯一的函数u : N → X你:否→Xu:\mathbb N\to X使得u (0 )=一你(0)=Au(0)=a和u (s (n ))= g(u (n ))你(s(n))=G(你(n))u(s(n)) =g(u(n))对全部n∈Nn∈否n\in\mathbb N。
递归定理的证明可以在 Halmos 的书《朴素集合论》(第 12 节,第 48 页)以及其他一些关于数理逻辑和集合论的书籍中找到。证明中涉及的几乎所有工作都用于实际构建函数你你u;唯一性断言只是一种常规归纳。
一旦我们掌握了递归定理,我们就可以按如下方式进行。对于每个m∈N米∈否m\in\mathbb N,我们让s米:N → Ns米:否→否s_m:\mathbb N\to\mathbb N是满足的唯一函数s米(0 )=米s米(0)=米s_m(0)=m和s米(s (n ))= s (s米(n ))s米(s(n))=s(s米(n))s_m(s(n))=s(s_m(n))对全部n∈Nn∈否n\in\mathbb N。然后,我们定义F:N × N → NF:否×否→否f:\mathbb N\times\mathbb N\to\mathbb N经过F(米,n )=s米(名词)F(米,n)=s米(n)f(m,n)=s_m(n)。 很清楚FFf满足(1)\eqref{1}和(2)\eqref{2},并归纳nnn表明最多有一个函数具有此属性。因此,我们的定义+++是连贯的。
\endgroup
|
这+++符号是“中缀”函数定义
+ :否0×否0→否0+:否0×否0→否0+: \mathbb{N}_0 \times \mathbb{N}_0 \to \mathbb{N}_0。与普通函数唯一的区别是,对于m , n∈否0米,n∈否0m,n \in \mathbb{N}_0而不是写作+ (米,n )+(米,n)+(m,n)我们写分子+数米+nm + n(中缀表示法)。请注意,您可以使用除+++例如只需调用它添加A德德\mathrm{ADD}。此外,您不需要使用中缀表示法。
这个定义本质上是递归的。设米∈否0米∈否0m \in \mathbb{N}_0假设我们想计算米+秒( 0 )米+s(0)m + s (0).然后根据定义
m + s(0) =s( m+ 0) = s (m).
以同样的方式(使用上面的公式得出第二个等式):
m+ s(s(0)) = s (m + s(0) ) = s( s(m))
不难理解,我们可以计算分子+数米+nm+n这样对于任何∈否0n∈否0n \in \mathbb{N}_0简单地表达为nnn继任者000.因此递归定义的函数+++定义明确。
\endgroup
3
-
1\begingroup
我明白,但是有没有办法把这个写成逻辑语句?换句话说,你会怎么说nnn第一位继任者000带有逻辑陈述?
\endgroup
–
-
\begingroup
@SpyridonManolidis 检查和
\endgroup
– -
\begingroup
@SpyridonManolidis 尤其是上面链接问题中的
\endgroup
–
|
我们可以用类似于定义的方式定义它否0否0\mathbb{N}_0—作为具有某些属性的最小集合。设
\begin{align}
\varphi(u) &= (\forall x \in \mathbb{N}_0) (x, 0, x) \in u\\
&\quad \wedge (\forall xyz \in \mathbb{N}_0)((x, y, z) \in u \to (x, s(y), s(z)) \in u),
\end{align}
然后让δ(是) = φ ( y) ∧∀z( φ () → y⊆z)δ(是)=φ(是)∧∀是(φ(是)→是⊆是)\delta(y) = \varphi(y) \wedge \forall z (\varphi(z) \to y \subseteq z)。然后我们可以使用集合论的公理来证明∃ ! yδ(是)∃!是δ(是)\exists! y \, \delta(y),这证明了定义符号+++经过是= + ↔ δ(是)是=+↔δ(是)y = {+} \leftrightarrow \delta(y)。然后我们采用简写,x + y= zX+是=是x + y = z意思是(x , y, z) ∈ +(X,是,是)∈+(x, y, z) \in {+}。
用文字来说,上述定义是+++是自然数有序三元组的最小集合,满足(x ,0 ,x )∈ +(X,0,X)∈+(x, 0, x) \in {+}对于每个自然数XXx,并且每当(x , y, z) ∈ +(X,是,是)∈+(x, y, z) \in {+}, 我们还有(x ,s (y) , s ( z) ) ∈ +(X,s(是),s(是))∈+(x, s(y), s(z)) \in {+}。
使用简写符号,口头描述更加清晰。在这种情况下,+++是自然数有序三元组的最小集合,满足x + 0 = xX+0=Xx + 0 = x对于每个自然数XXx,并且每当x + y= zX+是=是x + y = z, 我们还有x + s ( y) = s ( z)X+s(是)=s(是)x + s(y) = s(z)。
\endgroup
|
它是完成的。一旦你知道了什么分子+数米+nm+n意味着你可以定义什么m + ( n + 1 )米+(n+1)m+(n+1)方法。
\endgroup
–
你可以通过递归方程来思考这个定义(涉及+++在右边)被证明是合理的,或者说是语法糖,是“真正的”定义+++,用类型论的语言来说,就像+ = λm 。录制否(米,λ x . s x ) +=λ米。录制否(米,λX。s X)+ = \lambda m. \text{rec}_\mathbb{N}(m, \lambda x. s\ x)换句话说,递归定义就是这些方程的解。
\endgroup
–
“你怎么能用 + 符号来定义加法呢?这不是违背定义的目的吗?”好问题!但这不是循环的。加号只是一个用来表示抽象函数的符号。如果我们调用该函数:F:否0→否0F:否0→否0f:\mathbb N_0\to \mathbb N_0通过F(米,0 )=米F(米,0)=米f(m,0)=m和F(m ,s (n ))= s (f(男),n )F(米,s(n))=s(F(米),n)f(m,s(n))= s(f(m),n)这+++只不过是我们定义的符号“a + bA+ba + b“意味着简单地F(a ,b )F(A,b)f(a,b)。这是一种直观有用的符号,就像我们在学习函数之前学习二元运算一样,尽管二元运算只是函数的一种类型。
\endgroup
–
|