Conjunto aritmético

Concepto matemático

En lógica matemática , un conjunto aritmético (o conjunto aritmético ) es un conjunto de números naturales que se puede definir mediante una fórmula de aritmética de Peano de primer orden . Los conjuntos aritméticos se clasifican mediante la jerarquía aritmética .

La definición se puede extender a un conjunto contable arbitrario A (por ejemplo, el conjunto de n - tuplas de números enteros , el conjunto de números racionales , el conjunto de fórmulas en algún lenguaje formal , etc.) utilizando números de Gödel para representar elementos del conjunto y declarando que un subconjunto de A es aritmético si el conjunto de números de Gödel correspondientes es aritmético.

Una función se llama aritméticamente definible si su gráfica es un conjunto aritmético. ${\displaystyle f:A\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle f}$

Un número real se denomina aritmético si el conjunto de todos los números racionales menores es aritmético. Un número complejo se denomina aritmético si sus partes reales e imaginarias son ambas aritméticas.

Definición formal

Un conjunto X de números naturales es aritmético o aritméticamente definible si existe una fórmula de primer orden φ( n ) en el lenguaje de la aritmética de Peano tal que cada número n está en X si y solo si φ( n ) se cumple en el modelo estándar de la aritmética. De manera similar, una relación k -aria es aritmética si existe una fórmula tal que se cumple para todas las k -tuplas de números naturales. ${\displaystyle R(n_{1},\ldots ,n_{k})}$ ${\displaystyle \psi (n_{1},\ldots ,n_{k})}$ ${\displaystyle R(n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})}$ ${\displaystyle (n_{1},\ldots ,n_{k})}$

Una función se llama aritmética si su gráfica es una relación aritmética ( k + 1)-aria. ${\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$

Se dice que un conjunto A es aritmético en un conjunto B si A es definible mediante una fórmula aritmética que tiene a B como parámetro del conjunto.

Ejemplos

• El conjunto de todos los números primos es aritmético.
• Todo conjunto enumerable recursivamente es aritmético.
• Toda función computable es definible aritméticamente.
• El conjunto que codifica el problema de detención es aritmético.
• La constante de Chaitin Ω es un número real aritmético.
• El teorema de indefinibilidad de Tarski muestra que el conjunto de fórmulas verdaderas de la aritmética de primer orden (los números de Gödel) no son aritméticamente definibles.

Propiedades

• El complemento de un conjunto aritmético es un conjunto aritmético.
• El salto de Turing de un conjunto aritmético es un conjunto aritmético.
• La colección de conjuntos aritméticos es contable, pero la secuencia de conjuntos aritméticos no es definible aritméticamente. Por lo tanto, no existe una fórmula aritmética φ( n , m ) que sea verdadera si y solo si m es un miembro del predicado aritmético n .

De hecho, dicha fórmula describiría un problema de decisión para todos los saltos de Turing finitos y, por lo tanto, pertenece a 0 ^(ω) , que no puede formalizarse en aritmética de primer orden , ya que no pertenece a la jerarquía aritmética de primer orden .

• El conjunto de números aritméticos reales es contable , denso e isomorfo en orden al conjunto de números racionales.

Conjuntos aritméticos implícitos

Cada conjunto aritmético tiene una fórmula aritmética que indica si determinados números están en el conjunto. Una noción alternativa de definibilidad permite una fórmula que no indica si determinados números están en el conjunto, sino si el conjunto en sí satisface alguna propiedad aritmética.

Un conjunto Y de números naturales es implícitamente aritmético o implícitamente definible aritméticamente si es definible con una fórmula aritmética que puede usar Y como parámetro. Es decir, si hay una fórmula en el lenguaje de la aritmética de Peano sin variables numéricas libres y un nuevo parámetro de conjunto Z y una relación de pertenencia al conjunto tal que Y es el único conjunto Z tal que se cumple. ${\displaystyle \theta (Z)}$ ${\displaystyle \in }$ ${\displaystyle \theta (Z)}$

Todo conjunto aritmético es implícitamente aritmético; si X está definido aritméticamente por φ( n ), entonces está definido implícitamente por la fórmula

${\displaystyle \forall n[n\in Z\Leftrightarrow \phi (n)]}$.

Sin embargo, no todo conjunto implícitamente aritmético es aritmético. En particular, el conjunto de verdad de la aritmética de primer orden es implícitamente aritmético pero no aritmético.

Véase también

• Jerarquía aritmética
• Conjunto computable
• Número computable

Lectura adicional

• Hartley Rogers Jr. (1967). Teoría de funciones recursivas y computabilidad efectiva. McGraw-Hill. OCLC  527706