¿Demostración de la factorización primaria única en la lógica de primer orden?

Question

Supongamos que tengo los símbolos $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ y funciones $Div(x,y)$ ( $x$ divide $y$ ), $Prime(x)$ verdadero si $x$ es un primo, y el dominio $\mathbb{N}$ . ¿Cómo puedo construir una fórmula que exprese el hecho de que todo número mayor que 0 tiene una factorización primaria única?

Mi pensamiento requiere la capacidad de tener elipses, para mostrar por ejemplo para un número $k$ es que $\exists a_1,\ldots,a_k$ tal que $a_1^{n_1}\cdots a_{j}^{n_j}= k$ para $j \leq k$ . Por ejemplo, $4 = 2^2$ .

Algo así, no lo sé.

¿Cómo puedo construir esa fórmula?

Answer 1

El desafío aquí es que no hay a priori en el número de factores. Así, para expresar el teorema fundamental de la aritmética en una teoría de primer orden como la aritmética de Peano, primero hay que demostrar que la teoría es capaz de expresar la idea de cuantificar sobre secuencias finitas. La maquinaria para hacer esto se entiende bien; un método comúnmente utilizado es el $\beta$ función presentado por Kurt Gödel.

La idea general es que la frase final diga "para cada $n > 1$ existe una secuencia finita $\sigma$ tal que (1) cada número que aparece en $\sigma$ es primo, y (2) $n$ es el producto de los números que aparecen en $\sigma$ ."

Answer 2

Definamos primero $\text{Prime}(n)$ para ser una expresión que es verdadera si $n$ es primo:

$$ \text{Prime}(n) \stackrel{\text{def}}{⟺} ∀x∀y\Big[ (x×y=n) ⟶ (1<p<x+y) \Big] $$

Esto funciona porque los únicos factores de par de $n$ cuya suma es mayor que $n$ es $1$ y $n$ sí mismo.

Ahora definamos $d$ divide $n$ ( $d|n$ ):

$$ d|n \stackrel{\text{def}}{⟺} ∃x \big[d×x=n\big]$$

Ahora bien, ten en cuenta que un número es $0$ , $1$ , primo, o un número compuesto (divisible por un primo):

$$ ∀x\Big[(x<0)∨\text{Prime}(x) ∨ ∃y∃z\big[(y×z=x)∧\text{Prime}(y)\big]\Big] $$

Así que ahora sabemos que todo número compuesto $x$ tiene un factor primo $y$ y otro factor $z$ . Si $z$ en un número primo, $x$ es el producto de 2 números primos.

Lo siento, no estoy del todo seguro de a dónde ir a partir de aquí, pero pensé en publicar esto de todos modos en caso de que sea útil para usted. Tal vez vuelva y lo edite más tarde.