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 pueden definirse mediante una fórmula de aritmética de Peano de primer orden . Los conjuntos aritméticos se clasifican según 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 declarar 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 la gráfica de es un conjunto aritmético. ${\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle f}$

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

Definicion formal

Un conjunto X de números naturales es aritmético o definible aritméticamente 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 sólo si φ( n ) se cumple en el modelo estándar. de aritmética. De manera similar, una relación k -aria es aritmética si existe una fórmula que sea válida 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 B como parámetro del conjunto.

Ejemplos

• El conjunto de todos los números primos es aritmético.
• Todo conjunto recursivamente enumerable es aritmético.
• Cada 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 (números de Gödel del) conjunto de fórmulas verdaderas de la aritmética de primer orden no es aritméticamente definible.

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 aritméticamente definible. Por lo tanto, no existe una fórmula aritmética φ( n , m ) que sea verdadera si y sólo si m es miembro del n- ésimo predicado aritmético.

De hecho, tal 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 los números aritméticos reales es contable , denso y de orden isomorfo al conjunto de los números racionales.

Conjuntos implícitamente aritméticos

Cada conjunto aritmético tiene una fórmula aritmética que dice si determinados números están en el conjunto. Una noción alternativa de definibilidad permite una fórmula que no dice 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 aritméticamente definible si se puede definir con una fórmula aritmética que pueda utilizar 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 membresía de conjunto tal que Y es el conjunto único 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á implícitamente definido 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.

Ver también

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

Otras lecturas

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