¿Es esta una representación adecuada para " $b$ es una potencia de 2" usando TNT de Gödel, Escher, Bach

Question

En el libro "Gödel, Escher, Bach" de Hofstadter se introduce el sistema de " Teoría tipográfica de los números ". Uno de los ejercicios consiste en escribir "b es una potencia de 2", y acabé obteniendo lo siguiente $<(a \cdot c)=b \supset \exists a':(SS0 \cdot a')=a \land \exists c': (SS0 \cdot c')=c>$ Mi interpretación al inglés de la frase es " $a$ y $c$ siendo factores de $b$ implica que tanto y $a$ y $c$ son pares", lo que creo que sólo es cierto para $b$ que son potencias de 2. ¿Es ésta una forma válida de escribir 'b es una potencia de 2' en el sistema, y si lo es/no lo es cómo puedo estar seguro.

Answer 1

Tu fórmula no funciona del todo como está escrita, porque cada número tiene $1$ como factor. Por ejemplo, $8$ es una potencia de $2$ , pero tenemos $1\cdot 8 = 8$ y $1$ no es uniforme.

Pero la idea básica es correcta. Se puede expresar " $b$ es una potencia de $2$ " por "cada factor de $b$ excepto en el caso de $1$ está en paz". Yo escribiría esto de la siguiente manera: $$\forall a\, ((\exists c\, a\cdot c = b) \rightarrow (a = S0 \lor \exists d\, (a = SS0\cdot d)))$$

No estoy seguro de que mi notación coincida con la de Hofstadter (por ejemplo, prefiero firmemente $\rightarrow$ a $\supset$ como símbolo de implicación), pero confío en que puedas hacer los ajustes notacionales necesarios para traducir mi fórmula en una fórmula de TNT.

---

En los comentarios, escribes "¿Cómo puedo estar seguro de que no existe un contraejemplo espeluznante?". ¡Puedes estar seguro demostrándolo!

Supongamos que $n$ es un número natural. Queremos demostrar que $n$ es una potencia de $2$ si y sólo si cada factor de $n$ es par o igual a $1$ .

Si $n$ es una potencia de $2$ entonces, por la unicidad de la factorización primaria, el único número primo que divide a $n$ es $2$ . Si $n$ tiene un factor impar $m$ con $m\neq 1$ entonces $m$ tiene un factor primo impar $p$ que también es un factor primo impar de $n$ contradicción.

Por el contrario, si cada factor de $n$ es par o igual a $1$ Entonces, como $1$ no es primo y $2$ es el único número primo par, el único número primo que aparece en la factorización primaria de $n$ es $2$ Así que $n$ es una potencia de $2$ .

Answer 2

Asegúrese de cuantificar universalmente el $a$ y $c$ . Y sí, entonces su fórmula funciona ya que entonces implica que $b$ no tiene más factores que $2$