Um modelo diferente dos números naturais

Nosso objetivo aqui é provar que, se não assumirmos que, no contexto da teoria dos números naturais s(\mathbb{N}) = \mathbb{N}^* ou a tricotomia da ordem, ou pelo menos que a\neq s(a) então é impossível provar que o Princípio da Boa Ordem (PBO) \Rightarrow Princípio da Indução Finita.

Seja L uma linguagem de primeira ordem, com um símbolo de constante (0), uma função unária (sucessor), duas funções binárias (soma e produto) e um símbolo de relação binária (menor). Seja T o seguinte conjunto de fórmulas:

  1. \forall x(s(x)\neq 0)
  2. \forall x \forall y ( s(x) = s(y) \Rightarrow x=y)
  3. \forall x (x+0 = x)
  4. \forall x \forall y(x + s(y) = s(x+y))
  5. \forall x (x.0 = 0)
  6. \forall x \forall y (x.s(y) = xy + x)
  7. \forall x\forall y ((x<y)\Leftrightarrow(\exists k (x+s(k) = y))

Além disso, para toda fórmula \phi(x), T contém:

\forall x(\phi(x) \rightarrow \exists z \forall y(\phi(y) \rightarrow ((z<y)\land \phi(z)))

Que é o PBO para conjuntos definíveis.

Considere agora \mathcal{M} = \mathbb{N}\cup\{a\} onde a\notin\mathbb{N}

Onde a tabela de soma e multiplicação dos naturais permanece a mesma que a usual e além disso \mathcal{M} satisfaz

T1) \forall x(a+x = x+a=a)

T2) \forall x(a.x=x.a)

T3) \forall x(((x=0)\land (a.x=0))\lor (a.x=a))

T4) a.a = a

T5) s(a)=a

Veja que \mathcal{M} \vDash T e ainda:

T6) \forall x(x<a) pois x+s(a)=x+a=a e basta tomar k=a em P6 para conclusão.

{\mathcal{M}} satisfaz PBO: se \phi(x) for uma sentença e \mathcal{M} \vDash \phi(a), se existir algum n \in \mathbb{N} tal que \mathcal{M} \vDash \phi(n), então o conjunto S =\{n \in \mathbb{N}| \phi(n)\} obedece o PBO já que é um subconjunto dos números naturais. Assim existe um menor natural m que satisfaz \forall n(m<n). Por T6, m é o menor elemento.

Se não existir nenhum n tal que \mathcal{M} \vDash \phi(n) então a é o menor (e único) elemento.

Vamos mostrar que {\mathcal{M}} não satisfaz a PIF:

Seja \phi (x)=x\neq s(x), então claramente \mathcal{M} \vDash \phi(0) e \mathcal{M} \vDash \forall x(\phi(x) \rightarrow \phi(s(x))),  (pela fórmula 2) e  \mathcal{M} \not\vDash \phi(a). Assim \mathcal{M} não satisfaz a PIF.