[geómetracat]

Los axiomas son una cosa más básica, están fijados de antemano. Por ejemplo, los axiomas de PA que enlacé en un mensaje anterior, o los de ZFC, que sirven de marco para cualquier razonamiento matemático. No es algo que se pueda añadir o quitar a la ligera.

Si en un artículo se prueba (razonadamente) que el algoritmo de Collatz es equivalente a otro, eso es una demostración a partir de los axiomas usuales (ZFC, pongamos), y no añadir un axioma nuevo.

[martiniano]

Hola.

Intentaré explicarte un poco el asunto lo mejor que pueda, aunque esto da básicamente para un primer curso de lógica. Si nunca has visto nada de lógica matemática, es necesario explicar bastantes cosas, así que el mensaje será largo, pero lo voy a intentar. Necesariamente voy a ser un tanto vago e impreciso al explicar algunos conceptos y me voy a dejar casi todos los detalles, para no escribir aquí un libro, pero espero que se entienda algo, y si no se entiende, vuelve a insistir.

Antes que nada, muchísimas gracias por tan vasta introducción al mundo de la lógica. Me va a servir para adquirir conceptos, aunque sea de forma superficial, que me resultan muy interesantes.

En lógica formal siempre hay dos vertientes: la sintáctica y la semántica. La parte sintáctica trata de lo que llamamos "demostraciones formales". Aquí se ven las fórmulas como conjuntos de símbolos. Un sistema axiomático es un conjunto de axiomas (fórmulas que quieres considerar como "verdaderas", aunque en la parte sintáctica aún no hay noción de verdad) y reglas de inferencia, que te dicen cómo obtener nuevas fórmulas a partir de otras. Por ejemplo una regla de inferencia típica es el modus ponens: a partir de \[ \varphi \to \psi \] y de \[ \varphi \] puedes obtener \[ \psi \]. Entonces, en un sistema axiomático fijado, se define una demostración de una fórmula \[ \varphi \] como una sucesión de fórmulas \[ \psi_1, \psi_2, \dots, \psi_n=\varphi \] que acaba en \[ \varphi \], donde cada fórmula es o bien un axioma, o se sigue de las anteriores usando una regla de inferencia. (En realidad hay muchas maneras de definir "demostración", bastante distintas pero todas equivalentes. Esta es una de las más sencillas de entender, así que quédate con esta).

Normalmente, siempre se trabaja con un sistema axiomático de "base" que permite deducir todas las fórmulas que uno intuitivamente querría que sean demostrables, que se siguen por motivos puramente lógicos (para entendernos, tautologías, pero en lógica de primer orden), cosas como \[ \forall x (x=x) \] o como \[ (\varphi \to \psi)\wedge \varphi \to \psi \] para cualquier par de fórmulas \[ \varphi, \psi \], etc. A los axiomas de este sistema axiomático de base se les conoce como "axiomas lógicos". Si una fórmula \[ \varphi \] se puede demostrar en este sistema base (a partir de axiomas lógicos y reglas de inferencia) se denota así: \[ \vdash \varphi \].

Ahora bien, a nosotros nos interesa hablar de cosas que no son puramente lógicas, como números naturales, conjuntos, grupos, etc. Entonces lo que hacemos es suplementar primero el lenguaje con el que podemos construir fórmulas con nuevos símbolos (por ejemplo, \[ \in \] para la teoría de conjuntos, \[ 0, S, +, \cdot \] para la aritmética, \[ \cdot, e \] para los grupos), y después suplementamos el sistema axiomático de base con axiomas que son fórmulas que van a describir cómo son esos objetos, es decir, fórmulas que intuitivamente queremos que sean verdaderas para esos objetos.
Voy a usar como ejemplo la teoría de grupos. Aquí añadimos los símbolos \[ \cdot \] y \[ e \] (que van a ser la multiplicación del grupo y el elemento neutro) y los axiomas:
\[ A. \forall x \forall y \forall z (x\cdot y)\cdot z = x \cdot (y \cdot z) \]
\[ E. \forall x (e\cdot x=e \wedge x \cdot e = x) \]
\[ I. \forall x \exists y (x \cdot y = e \wedge y \cdot y = e)  \]
Intuitivamente, \[ A \] es la asociatividad, \[ E \] el hecho de que \[ e \] es el elemento neutro, e \[ I \] el hecho de que todo elemento tiene inverso. A partir de esto y de los axiomas y reglas de inferencia del sistema de base, podemos demostrar formalmente teoremas de la teoría de grupos, como \[ \forall u (\forall x (u \cdot x=x \wedge x \cdot u=x) \to u=e) \] (unicidad del elemento neutro), etc.
Si \[ \Gamma \] es un conjunto de fórmulas, escribimos \[ \Gamma \vdash \varphi \] para denotar que la fórmula \[ \varphi \] se puede demostrar tomando el sistema base y además las fórmulas de \[ \Gamma \] como axiomas adicionales. Así, si llamamos al conjunto de los tres axiomas de arriba \[ TG \], tenemos que \[ TG \vdash \forall u (\forall x (u \cdot x=x \wedge x \cdot u=x) \to u=e)  \].
Igualmente hay axiomas que pretenden describir cómo funcionan los conjuntos (el más famoso es \[ ZFC \]), o cómo funcionan los naturales (el más famoso es la aritmética de Peano, \[ PA \], del que puedes ver los axiomas aquí).

Vale. Con PA querías decir aritmética de Peano (qué espeso estuve  ), con TG teoría de grupos, etc.

Creo que hasta aquí lo estoy pillando bien. 

Lo que es importante es observar que esto es todo puramente formal y mecánico, es decir, no hacemos ningún caso a qué significan los símbolos, y una vez tenemos nuestros axiomas y reglas de inferencia podemos poner un ordenador a hacer demostraciones.

Ahora pasamos a la parte semántica de la lógica. Aquí lo que pretendemos es entrar en el significado de las fórmulas, ya no verlas como meras cadenas de símbolos, sino como enunciados que expresan algo sobre unos objetos. Para ello se define la noción de modelo. Un modelo (a secas) es un conjunto junto con una interpretación de los símbolos no lógicos (los que hemos añadido antes, como \[ \in \] en teoría de conjuntos, o \[ \cdot, e \] en grupos). Por ejemplo, en el caso del lenguaje de teoría de grupos un modelo podría ser un conjunto \[ M \] junto con una operación binaria \[ \cdot^M:M \times M \to M \] y un elemento \[ e^M \in M \]. Ponemos un superíndice \[ M \] para distinguir la interpretación del símbolo en el modelo del símbolo en sí. Es decir, \[ \cdot \] es un simple símbolo, mientras que \[ \cdot^M \] es una función.
Ahora, fijado un modelo podemos interpretar una fórmula como un enunciado que está diciendo cosas sobre el modelo, que puede ser verdadera o falsa. Por ejemplo, considera el grupo \[ \Bbb Z/2 \] como modelo, es decir, el conjunto \[ \Bbb Z/2 = \{0, 1\} \] junto con la operación usual definida por \[ 0 \cdot^{\Bbb Z/2} 0 = 1 \cdot^{\Bbb Z/2} 1 = 0 \] y \( 1 \cdot^{\Bbb Z/2} 0 = 0 \cdot^{\Bbb Z/2} 1 = 1 \) y el neutro \[ e^{\Bbb Z/2} = 0 \].
En este modelo podemos decir que la fórmula \[ \forall x\forall y(x\cdot y = y \cdot x) \] es verdadera, pero \[ \exists x (x \cdot x) \neq e \] es falsa. Hay una definición precisa de cúando una fórmula es verdadera en un modelo, que se da recursivamente, pero no la voy a poner porque es larga y no creo que aporte mucho. Confío en que sabes interpretar las fórmulas (y si no es así, dilo).

Creo que sí. Básicamente la primera dice que la operación que aparece es conmutativa, lo cual es verdadero en \[ \mathbb{Z/2} \] pero no tiene por qué serlo en otros grupos. Y la segunda que hay elementos que no son inversos de sí mismos, lo cual es falso en \[ \mathbb{Z/2} \] pero puede ser verdadero en otros grupos.

Si una fórmula \[ \varphi \] es verdadera en un modelo \[ M \], lo denotamos por \[ M \models \varphi \]. Así por ejemplo, hemos visto que \[ \Bbb Z/2 \models \forall x\forall y(x\cdot y = y \cdot x) \].
Dado un conjunto de fórmulas \[ \Gamma \], decimos que un modelo \[ M \] es un modelo de \[ \Gamma \] si todas las fórmulas de \[ \Gamma \] son verdaderas en \[ M \]. Así, por ejemplo \[ \Bbb Z/2 \] es un modelo de \[ TG \]. Un modelo de \[ PA \] sería cualquier modelo en que los axiomas de \[ PA \] sean verdaderos, etc.
Y finalmente, denotamos por \[ \Gamma \models \varphi \] el hecho de que para todo modelo \[ M \] de \[ \Gamma \] se tiene \[ M \models \varphi \]. Así, por ejemplo, tenemos que \[ TG \models \forall u (\forall x (u \cdot x=x \wedge x \cdot u=x) \to u=e) \] (todo modelo que cumple los axiomas de grupo cumple también que el neutro es único), pero \[ TG \not \models \forall x \forall y (x \cdot y = y \cdot x) \], porque hay grupos que no son conmutativos.

Fíjate que hemos definido dos relaciones: \[ \Gamma \vdash \varphi \] y \[ \Gamma \models \varphi \], la primera sintáctica, usando procedimientos mecánicos, y la segunda semántica, atendiendo a qué significan las fórmulas una vez interpretadas en un modelo.

Me cuesta ver la diferencia entre ambas relaciones, la verdad. Concretamente se me escapa un poco el significado de la frase en rojo. Pero no sé hasta qué punto es grave. He leído los siguientes párrafos y creo haberlos entendido bien.

El resultado básico más importante en lógica matemática es el teorema de completitud de Gödel (no confundir con los teoremas de incompletitud): ambas relaciones coinciden. Esto se suele partir en dos partes. La primera es que si \[ \Gamma \vdash \varphi \] entonces \[ \Gamma \models \varphi \]. A esto se le llama también teorema de corrección, y está claro que si no tuviéramos esta propiedad ya podríamos tirar las demostraciones formales a la basura porque nos permitirían concluir cosas falsas (en algún modelo) a partir de cosas verdaderas. La parte más interesante es la otra, la que se llama teorema de completitud propiamente dicho: si \[ \Gamma \models \varphi \] entonces \[ \Gamma \vdash \varphi \]. Esto quiere decir que si una fórmula \[ \varphi \] es verdadera en todos los modelos de \[ \Gamma \] entonces es demostrable en el sistema axiomático. O usando el contrarrecíproco, si una fórmula no se puede demostrar a partir de \[ \Gamma \], es porque esta fórmula es falsa en al menos un modelo de \[ \Gamma \].

Equipados con esto podemos entender mejor el fenómeno de la incompletitud. Se dice que una fórmula \[ \varphi \] es independiente de un sistema axiomático (\[ TG \], por ejemplo) si se tiene que \[ TG \not\vdash \varphi \] y \[ TG \not\vdash \neg \varphi \]. Es decir, es independiente del sistema axiomático si éste no es capaz de demostrarla ni refutarla. Por el teorema de completitud, tenemos una equivalencia de esto en la parte semántica: una fórmula es independiente de un sistema axiomático si hay modelos de los axiomas donde es verdadera y otros modelos donde es falsa. Ahora podemos probar que \[ TG \] es incompleto y dar un ejemplo de fórmula independiente de \[ TG \]: \[ \forall x \forall y (x\cdot y = y \cdot x) \]. Como hay grupos (= modelos de \[ TG \]) que son conmutativos y otros que no, esa fórmula no se puede demostrar ni refutar a partir de \[ TG \].

Sí, sí. Esto creo que lo entiendo. Si una fórmula no se puede demostrar verdadera ni falsa a partir de los axiomas generales que definen el concepto de grupo entonces hay grupos en los que es verdadera y grupos en los que es falsa. Esto es a lo que has llamado teorema de completitud propiamente dicho. Curioso, e interesante.

Hasta aquí los preliminares sobre lógica matemática, ahora vamos a la aritmética.

Las teorías aritméticas (básicamente, puedes pensar que teoría aritmética = sistema axiomático que pretende describir a los naturales) son un tanto especiales, porque en ellas hay un "modelo estándar", que es la interpretación natural en la que uno piensa cuando le dicen "números naturales". Es decir, el conjunto \[ \Bbb N = \{0,1,2, \dots\} \] con la operación de sucesor, suma y producto habituales. Puedes comprobar fácilmente que todos los axiomas de Peano (la lista de la Wikipedia que enlacé antes) son verdaderos en este modelo. Fíjate que esto está en contraste con \[ TG \], donde no hay un "modelo estándar", no hay un grupo más especial que otros, sino que estamos interesados en todos los grupos. En cambio, cuando hacemos teorías aritméticas sí estamos interesados únicamente en el modelo estándar (al menos de entrada).
Ahora puedes decir, pues bueno, nos montamos una teoría aritmética  cuyo único modelo sea el modelo estándar y ya está: todo lo que sea demostrable a partir de esos axiomas será verdadero en los naturales, y todo lo que sea verdadero en los naturales será demostrable en esa teoría.

El problema es que las cosas no son tan sencillas. Hagas lo que hagas y pongas los axiomas que pongas se te van a colar modelos raros.

Entiendo. Por ejemplo, los números naturales cumplen los axiomas de Peano. Sin embargo, habrá muchos otros conjuntos, o modelos, que también los cumplan. Eso hace que haya sentencias que formulamos para los naturales "de toda la vida" pero que no podamos demostrar con la aritmética de Peano porque no son sentencias verdaderas en otros modelos que también cumplan los axiomas de Peano.

Esto es consecuencia de otro de los teoremas centrales de la lógica de primer orden: el teorema de compacidad. El teorema de compacidad dice que un conjunto de fórmulas (quizás infinito) \[ \Gamma \] tiene un modelo si y solo si cada subconjunto finito de \[ \Gamma \] tiene un modelo. Esto no deja de ser un reflejo del teorema de completitud de antes. La idea es que si \[ \Gamma \] no tiene ningún modelo, entonces por el teorema de completitud a partir de \[ \Gamma \] se puede demostrar una contradicción. Pero todas las demostraciones son finitas, y por tanto solo pueden usar un número finito de axiomas. Si \[ \Gamma_0 \] es el subconjunto finito que aparece en la demostración de una contradicción, entonces \[ \Gamma_0 \] es un subconjunto finito sin ningún modelo.
El teorema de compacidad al final implica que la lógica de primer orden no es muy buena captando las noción intuitiva de "infinitud", no es lo suficientemente expresiva.

Ahora puedes hacer lo siguiente. Sea \[ T \] una teoría aritmética, la que te dé la gana. Introduce un nuevo símbolo (una constante) en el lenguaje, \[ c \], que va a denotar un elemento de un modelo de \[ T \]. Fíjate que \[ \Bbb N \] es un modelo de \[ T \], por definición de teoría aritmética. Pero también lo es de \[ T \cup \{ c>0, c>1, c>2, \dots, c>N\} \] para cualquier \[ N \] natural, pues puedes tomar \[ c^{\Bbb N} = N+1 \]. Por el teorema de compacidad, tenemos que \[ T \cup \{ c > N \mid N \in \Bbb N\} \] tiene un modelo. Este es un modelo de \[ T \] en el que hay un elemento que es mayor que \[ 0 \], y mayor que \[ 1 \],... y mayor que \[ 10^{99999999} \], ... y mayor que cualquier "número natural". A esto se le llama un modelo no estándar de \[ \Bbb N \], es un modelo de \[ T \] pero no es el modelo natural, \[ \Bbb N \], que teníamos en mente al montar los axiomas.

En \[ PA \] todos los modelos no estándar contienen al modelo estándar \[ \Bbb N \] como un segmento inicial. Es decir, la estructura de un modelo no estándar de \[ PA \] es que es \[ \Bbb N \] y luego por encima de los naturales "de toda la vida" hay estos naturales "no estándar" raros.

Puede haber fórmulas verdaderas en el modelo estándar pero falsas en algún modelo no estándar. Un ejemplo de esto lo da el segundo teorema de incompletitud de Gödel. Hay una fórmula que intuitivamente expresa (interpretada en el modelo estándar) que "no se puede demostrar una contradicción", y que no es demostrable. Por tanto, hay un modelo (no estándar) donde esta fórmula es falsa.
Otro ejemplo curioso de fórmula independiente de \[ PA \], pero verdadera en el modelo estándar es la que expresa el teorema de Goodstein. Este teorema es famoso porque es demostrable en ZFC pero no en PA. Puedes leer sobre ello aquí.

Síiii. Recuerdo que leí algo sobre estas sucesiones en una revista de divulgación cuando era pequeño. Ahora lo he entendido mucho mejor.

Ya para acabar: cualquier fórmula de la forma \[ \forall x \varphi(x) \] donde \[ \varphi \] solo involucra cuantificadores acotados (es decir, cosas de la forma \[ \forall x \leq n \] o \[ \exists x \leq n \]), puede ser independiente de una teoría aritmética, pero si lo es entonces es verdadera en el modelo estándar. A este tipo de fórmulas se les llama fórmulas \[ \Pi_1 \]. Un ejemplo es la del segundo teorema de incompletitud (cuya fórmula es \[ \forall x (\neg Dem(x, \ulcorner 0 \neq 1 \urcorner)) \] (en palabras sencillas, "para todo \[ x \], \[ x \] no codifica una demostración de \[ 1 \neq 0 \]"), donde aquí \[ Dem(x,y) \] es una fórmula que solo involucra cuantificadores acotados.
Este tipo de fórmulas son verdaderas en el modelo estándar si son independientes de \[ PA \] (por ejemplo) básicamente por el argumento que diste. Dado un numeral \[ \bf n \] (un numeral es un conjunto de símbolos de la forma \[ SS...S0 \], con un número finito de \[ S \]'s, donde \[ S \] es un símbolo del lenguaje que quiere decir "siguiente"), puedes demostrar o refutar \[ \varphi({\bf n}) \] porque hacerlo involucra únicamente un número finito de comprobaciones, al no contener \[ \varphi \] cuantificadores no acotados. Pero entonces, si \[ \forall x \varphi(x) \] fuera falsa en el modelo estándar, como todos los números del modelo estándar (los naturales de toda la vida) están representados por un numeral \[ \bf n \], podrías encontrar un numeral \[ \bf n \] tal que \[ \neg \varphi({\bf n}) \] es demostrable, y por tanto \[ \neg \forall x \varphi(x) \] sería demostrable.

Pero en general puede darse perfectamente el caso de que sean demostrables \[ \varphi({\bf 0}), \varphi({\bf 1}), \varphi({\bf 2}), \dots \] y en general \[ \varphi({\bf n}) \] para cualquier numeral \[ \bf{n} \], pero que sin embargo \[ \forall x \varphi(x) \] no sea demostrable, porque en algún modelo no estándar hay algún número no estándar \[ c \] tal que \[ \varphi(c) \] es falsa ahí. El problema es que los números no estándar no son representables por ninguna cadena de símbolos del lenguaje (al contrario de los números estándar, que son representados por los numerales).

En fin, al final me he puesto a escribir y me ha salido la biblia aquí.  Básicamente es un primer curso de lógica matemática condensado en uns pocos párrafos, pero espero que se entienda algo. Cualquier cosa que no se entienda o que te interese y quieras saber más, o si quieres detalles de alguna cosa, pregunta de nuevo.

Sí geómetracat. Creo que lo he entendido todo. Eres muy buen profe.  .

Muchas gracias.

Uy, no sé cómo había leído yo esto que llevo todo el hilo convencido de que se hablaba de la conjetura de Goldbach en vez de la de Collatz. Con Collatz la cosa no está tan clara, porque no está claro que sea equivalente a una fórmula \[ \Pi_1 \]. En principio, podría pasar que fuera indemostrable pero no fuera verdadera en el modelo estándar. Por ejemplo, podría pasar que existiera un número que condujera a una sucesión que nunca se repite, pero que no fuera posible demostrar en PA que nunca se repite.

Es verdad. Estaba dando por hecho que todas las órbitas estaban acotadas. No estoy muy al día en la conjetura de Collatz y no sé si se sabe algo sobre esto, pero claro, en cualquier caso no es algo trivial.

Un saludo.

[feriva]

Por ejemplo, podría pasar que existiera un número que condujera a una sucesión que nunca se repite

Pero quizá ahí podríamos establecer un criterio (creo, a lo mejor no sirve, porque de esta conjetura no he leído nada ni he pensado nada nunca sobre ella).

Por caso, con x=13 (tomo el primer ejemplo que veo en Wikipedia) da este conjunto finito de números

\( 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 \).

El conjunto tiene un máximo, \( M=40 \), y un mínimo \( m=1 \).

En un conjunto de naturales, aunque sea infinito, tiene que haber un mínimo; al menos pensando el proceso todo de “golpe”, como cardinal infinito actual, tiene que ser así.

El mínimo se puede repetir, pero tiene que aparecer por primera vez en un paso “n”; con “n” finito. Si no es 1, entonces no se cumple la conjetura, pero no deja de tener ese mínimo que surge por vez primera. Como el número de pasos es finito hasta el momento en que aparece por primera vez, también hasta ahí tiene que existir un máximo; y podemos considerar que el proceso se acaba para el “x” tomado.

Por ejemplo, imaginemos que el conjunto de x=13 pudiera ser así \( {13, 40, 20, 10, 5, 16, 8, 4, 2} \) (evidentemente no puede, porque 2/2 es 1, pero es una suposición). Si detrás no apareciera nunca ningún número menor que 2, esos números no se considerarían del conjunto a tenor de la regla que se usa; lo único que pasa es que, al no cumplirse la conjetura, el mínimo en vez de 1 es otro.

Considerado así no es importante que se repitan o no los elementos, siempre van a ser conjuntos finitos si no me equivoco. La conjetura cumpliría esto para cualquier x, \( m\cdot M=M
  \) (con “M” u otro elemento del conjunto) o no lo cumpliría, \( m\cdot M\neq M
  \).

Saludos.

[geómetracat]

Me alegro de que te haya servido de algo mi mensaje. Se me olvidó decir que si en algún momento quieres mirar todo esto en detalle, lo puedes encontrar en cualquier libro de lógica matemática (no de lógica para filósofos). Por ejemplo, en los primeros capítulos del libro de lógica de Carlos Ivorra todo esto está desarrollado con todos los detalles.

Me cuesta ver la diferencia entre ambas relaciones, la verdad. Concretamente se me escapa un poco el significado de la frase en rojo. Pero no sé hasta qué punto es grave. He leído los siguientes párrafos y creo haberlos entendido bien.

La diferencia en cómo se definen es sustancial, aunque acaben siendo la misma relación. \[ \Gamma \vdash \varphi \] requiere únicamente que seas capaz de encontrar una demostración de \[ \varphi \] a partir de \[ \Gamma \] (es decir, una sucesión finita de fórmulas que acabe en \[ \varphi \] donde cada fórmula es o bien un axioma del sistema de base, o bien una fórmula de \[ \Gamma \], o bien se sigue de fórmulas anteriores usando una regla de inferencia). Es un proceso mecánico y esencialmente finito.

En cambio, ver que \[ \Gamma \models \varphi \] a partir de la definición (que no te he dado) requiere, primero, que seas capaz de encontrar todos los modelos de \[ \Gamma \], y luego que para cada modelo de \[ \Gamma \] seas capaz de probar que satisface \[ \varphi \]. Y fíjate que esto puede llegar a ser bastante complicado: si un modelo \[ M \] es infinito y \[ \varphi \] es una fórmula con cuantificadores, por ejemplo es \[ \varphi = \forall x \psi(x) \], esto requiere comprobar que cada uno de los infinitos elementos \[ a \in M \] cumple \[ \psi(a) \].

Por seguir con el ejemplo de los grupos y la unicidad del neutro, \[ \Gamma \vdash \forall u (\forall x (u \cdot x=x \wedge x \cdot u=x) \to u=e) \] requiere dar una demostración formal de la unicidad del neutro a partir de los axiomas de grupos. Básicamente es el argumento que uno lee escrito en cualquier libro de teoría de grupos, pero desarrollado a "bajo nivel", explicitando todas las reglas lógicas que se usan, etc.
En cambio, ver que \[ \Gamma \models \forall u (\forall x (u \cdot x=x \wedge x \cdot u=x) \to u=e) \] a partir de la definición requiere, primero considerar todos los grupos, y después para cada grupo ir comprobando para cada elemento \[ g \] del grupo, que el único elemento que actúa como el neutro (\[ gx=xg=x \] para todo \[ x \] del grupo) es efectivamente el neutro del grupo.

Por ejemplo, podría pasar que existiera un número que condujera a una sucesión que nunca se repite

Pero quizá ahí podríamos establecer un criterio (creo, a lo mejor no sirve, porque de esta conjetura no he leído nada ni he pensado nada nunca sobre ella).

Por caso, con x=13 (tomo el primer ejemplo que veo en Wikipedia) da este conjunto finito de números

\( 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 \).

El conjunto tiene un máximo, \( M=40 \), y un mínimo \( m=1 \).

En un conjunto de naturales, aunque sea infinito, tiene que haber un mínimo; al menos pensando el proceso todo de “golpe”, como cardinal infinito actual, tiene que ser así.

El mínimo se puede repetir, pero tiene que aparecer por primera vez en un paso “n”; con “n” finito. Si no es 1, entonces no se cumple la conjetura, pero no deja de tener ese mínimo que surge por vez primera. Como el número de pasos es finito hasta el momento en que aparece por primera vez, también hasta ahí tiene que existir un máximo; y podemos considerar que el proceso se acaba para el “x” tomado.

Por ejemplo, imaginemos que el conjunto de x=13 pudiera ser así \( {13, 40, 20, 10, 5, 16, 8, 4, 2} \) (evidentemente no puede, porque 2/2 es 1, pero es una suposición). Si detrás no apareciera nunca ningún número menor que 2, esos números no se considerarían del conjunto a tenor de la regla que se usa; lo único que pasa es que, al no cumplirse la conjetura, el mínimo en vez de 1 es otro.

Considerado así no es importante que se repitan o no los elementos, siempre van a ser conjuntos finitos si no me equivoco. La conjetura cumpliría esto para cualquier x, \( m\cdot M=M
  \) (con “M” u otro elemento del conjunto) o no lo cumpliría, \( m\cdot M\neq M
  \).

Saludos.

Pero es que no se sabe que las órbitas de Collatz estén acotadas. En principio podría pasar algo así (me lo invento completamente):
\[ 101, 200, 55, 300, 60, 897, 500, 1056, ... \]
y que la sucesión no fuera acotada superiormente ni se repitiera nunca.
También podría pasar que después de crecer mucho la sucesión acabara yendo a \[ 1 \], pero es concebible que eso sea indemostrable (para todas las sucesiones). Esto es lo que pasa con las sucesiones de Goodstein: crecen muy rápido, van finalmente a 0, pero la aritmética de Peano no es capaz de demostrar que todas acaban en \[ 0 \].

[Granmurillo]

Ciertamente que demostrar una a una cada órbita es indemostrable pero por lo que deduzco es que si cada número impar en el algoritmo se convierte en un número par y cada número par es dividido al menos una vez entonces el límite debería ser el número par dividido entre 2, es decir la órbita no podría superar una solución que involucre este hecho. Es más, una propiedad  del algoritmo es que:

Para todo \( k ∈ I, f(4(3k+1))=f(k) \). (Porque \( 3(4k + 1) + 1 = 12k + 4 = 4(3k + 1) \).)

Lo que también llevaría a involucrar esta propiedad en la solución de la acotación de las órbitas; es decir, la división de un número par entre 4.

[feriva]

No conozco las ideas de ataque que se siguen para esto, pero se me ocurre analizarla así, si bien no llego a nada (como no la conozco mucho en general, puede que meta la pata).

Supongamos que la conjetura falla por primera vez en un número \( a+1
  \); tiene que ser impar, pues si el primer fallo fuera el número “a” par, entonces \( \dfrac{a}{2}<a
  \) y “engancha” hasta que llega a 1; puesto que todos los menores que “a” la cumplen por la hipótesis hecha.

Pero el par que sigue, \( a+2>a+1
  \) también la cumple, pues le seguiría \( \dfrac{a+2}{2}=\dfrac{a}{2}+1<a+1
  \); y el siguiente también cumple, \( \dfrac{a+4}{2}=\dfrac{a}{2}+2<a
  \)... y así hasta llegar a \( 2a
  \). Para que se cumpla la hipótesis, ninguno de estos pares, hasta 2a incluido, puede estar en la órbita.

Así, el siguiente a (a+1) que tendría que fallar en hipótesis, entonces, sería \( 3(a+1)+1=3a+4
  \), que es par. Y aquí podemos distinguir dos casos:

Si “a” fuera múltiplo de 4, tendríamos que el siguiente, al dividir entre 2, sería par también, entonces, y para que no se cumpliera, tendría que ocurrir lo que sigue:

\( \dfrac{3a+4}{2}=\dfrac{3}{2}a+2>2a
  \).

Pero esta condición no se va a cumplir, la conjetura está probada hasta números que rondan la cantidad \( 10^18 \) o más. Por tanto, para que falle la conjetura, “a” no puede ser múltiplo de 4; con lo cual \( \dfrac{3}{2}a+2
  \) sería impar.

Haciendo un cambio de variable tenemos

\( \dfrac{3}{2}a+2=3(2t+1)+2=6t+5
  \); (con \( t=\dfrac{a-2}{4}
  \)).

Los siguientes serán

\( 18t+16
  \)

\( 9t+8
  \)

Que poniendo t en función de “a” es

\( 9(\dfrac{a-2}{4})+8
  \)

Si \( a-2
  \) fuera múltiplo de 8, entonces se dividiría entre 2 y hay margen para afirmar que

\( 9(\dfrac{a-2}{8})+4<2a
  \), pero podría ser impar, siendo mayor que (a+1) y entonces no sirve para deducir nada.

Sí podemos afirmar que (a-2) no puede ser múltiplo de 16, porque entonces sí quedaría par después de dividir entre 2 y sería menor que 2a. Sin embargo, ya empieza a ser difícil sacar conclusiones.

(esto suponiendo que no me haya equivocado en algo anterior).

Saludos.

[Granmurillo]

A lo que me refería es la cantidad máxima de veces que un número impar puede ser calculado con el algoritmo hasta encontrar 1, debido a que una de las condiciones que se pide se cumpla es determinar que las órbitas se encuentren acotadas, es decir encontrar una razón por la que una órbita no pueda seguirse incrementando infinitamente aparte de la explicación heurística de la probabilidad de 3/4.

Pensaba si esta cantidad máxima sería, de alguna forma dentro de una ecuación, la misma cantidad que el número impar k, o del número par k+1, o del número par 3k+1 o debería ser la mitad de esos números pares puesto que todo número par es dividido entre 2 al menos una vez (del número impar no, porque su mitad no sería un número entero).