[manooooh]

Hola

Pues es muy fácil. Basta tener en cuenta que \( p\rightarrow (q\rightarrow p) \). Si sabes demostrar \( p \) (que sí que sabes), sólo tienes que añadir: por lo tanto, \( q\rightarrow p \).

No entiendo cómo deduces esas cosas. ¿Podrías explicarte un poco más, por favor?

A mí me parece objetivo que la prueba en cuestión supone tácitamente que todo árbol con \( h+1 \) vértices puede obtenerse añadiendo un vértice y una arista a uno de \( h \) vértices, y que eso chirría al leerlo. Es como si quieres probar que todo número racional \( r \) cumple una propiedad \( P(r) \) y en lugar de eso tomas una función \( f: \mathbb N\longrightarrow \mathbb Q \) y demuestras que, para todo \( n\in \mathbb N \) se cumple \( P(f(n)) \). Eso sólo vale si \( f \) es suprayectiva, pero resulta muy raro que quieras probar algo sobre números racionales y que en su lugar partas de un número natural sin más explicaciones al que luego le aplicas \( f \), siempre sin mencionar siquiera que \( f \) es suprayectiva, por obvio que esto pudiera ser.

No entiendo la crítica. Yo simplemente sostengo esto:

Y aunque en la tesis haya un árbol con \( h \) vértices, no cambia en nada. Si uno demuestra \( p\to q \) partiendo de \( p \), hace cálculos y llega a \( q \), es igualmente válido tomar una parte de \( q \) (si es una igualdad, la izquierda; si es un condicional, la hipótesis), y usar \( p \) para llegar a la otra parte de \( q \). Son dos caminos distintos y prueban lo mismo pero ninguno es más "natural" que otro, creo yo.

Hay tantos ejemplos de pruebas "alienígenas" tan naturales como las de empezar por la hipótesis que me da pereza buscar uno...

A diferencia de ustedes, para demostrar \( C\subseteq A\cup B\to(C-B)\subseteq A \) voy a empezar por el primer miembro de la tesis y no por el antecedente de la implicación, ¡¡no me tilden de alienígena que uso tanta naturalidad como ustedes!!:

\( \forall x\colon x\in C-B\to x\in C\land x\notin B\to x\in A\cup B\land x\notin B\to(x\in A\lor x\in B)\land x\notin B \)
\( \to(x\in A\land x\notin B)\lor(x\in B\land x\notin B)\to(x\in A\land x\notin B)\lor x\in\emptyset\to x\in A\land x\notin B\to x\in A \)

Saludos

[Carlos Ivorra]

No entiendo cómo deduces esas cosas. ¿Podrías explicarte un poco más, por favor?

1) \( p\rightarrow (q\rightarrow p) \) es una tautología (si construyes su tabla de verdad verás que siempre es verdadera). Por lo tanto, es un teorema.

2) Si has demostrado \( p \), entonces, sólo tienes que añadir a la demostración la tautología anterior y luego concluir \( q\rightarrow p \) por modus ponens.

Aquí \( q\rightarrow p \) es la implicación que le pedías demostrar a Luis.

No entiendo la crítica. Yo simplemente sostengo esto:

Y aunque en la tesis haya un árbol con \( h \) vértices, no cambia en nada. Si uno demuestra \( p\to q \) partiendo de \( p \), hace cálculos y llega a \( q \), es igualmente válido tomar una parte de \( q \) (si es una igualdad, la izquierda; si es un condicional, la hipótesis), y usar \( p \) para llegar a la otra parte de \( q \). Son dos caminos distintos y prueban lo mismo pero ninguno es más "natural" que otro, creo yo.

Eso es cierto, pero no es lo que hace tu profesor. Tiene la hipótesis:

Si un árbol \( T \) tiene \( h \) vértices \( \rightarrow \) \( T \) tiene \( h-1 \) aristas.

Y quiere demostrar que

Si un árbol \( T \) tiene \( h+1 \) vértices \( \rightarrow \) \( T \) tiene \( h \) aristas.

Si hiciera caso a lo que has dicho tú, tendría que empezar con un árbol con \( h+1 \) vértices, para probar que tiene \( h \) aristas, pero en lugar de hacer eso, parte de un árbol con \( h \) vértices (lo cual no es la hipótesis del condicional que quiere probar, es decir, no hace lo que tú dices que es natural hacer), se construye otro con \( h+1 \) vértices, prueba que tiene \( h \) aristas y concluye que ha probado algo para todos los árboles con \( h+1 \) vértices, lo cual es cierto gracias a algo que no dice, y es que todos los árboles con \( h+1 \) vértices pueden construirse como él ha construido el suyo.

Hay tantos ejemplos de pruebas "alienígenas" tan naturales como las de empezar por la hipótesis que me da pereza buscar uno...

A diferencia de ustedes, para demostrar \( C\subseteq A\cup B\to(C-B)\subseteq A \) voy a empezar por el primer miembro de la tesis y no por el antecedente de la implicación, ¡¡no me tilden de alienígena que uso tanta naturalidad como ustedes!!:

\( \forall x\colon x\in C-B\to x\in C\land x\notin B\to x\in A\cup B\land x\notin B\to(x\in A\lor x\in B)\land x\notin B \)
\( \to(x\in A\land x\notin B)\lor(x\in B\land x\notin B)\to(x\in A\land x\notin B)\lor x\in\emptyset\to x\in A\land x\notin B\to x\in A \)

Es que ese ejemplo es completamente natural, al contrario que lo que hace tu profesor.

[Richard R Richard]

No se si se me pasa algo muy jugoso matemáticamente,  pero a mi ojo de buen cubero veo que

De la definición de árbol, se desprende que este debe ser conexo, (no tenemos  vértices sueltos, ni dos arboles no conexos, ni ningún ciclo, siempre es completo y no tiene doble arista entre dos vertices) , de lo que se desprende también que un conjunto con único vértice no es un árbol.



Luego un árbol de 2 vértices y 1 arista no puede venir de un árbol de menor cantidad de vértices, lo que no cumpliría la hipótesis del profesor, porque no provendría de un árbol de  menor cantidad de vértices.




Pero sí podemos afirmar que de todo árbol de h vértices se puede obtener uno de h+1 vértices, simplemente  agregando un vértice uniéndolo por obligación para hacerlo conexo mediante una arista. De ese modo siempre se cumple que v=h+1.

[Carlos Ivorra]

De la definición de árbol, se desprende que este debe ser conexo, (no tenemos  vértices sueltos, ni dos arboles no conexos, ni ningún ciclo, siempre es completo y no tiene doble arista entre dos vertices) , de lo que se desprende también que un conjunto con único vértice no es un árbol.

Yo sí consideraría que un conjunto con 1 vértice y 0 aristas es un árbol (y diría que es lo habitual), pero en cualquier caso es cuestión de gustos y, si no lo consideramos como tal, entonces la inducción empieza en \( h=2 \). De todos modos, en la demostración del profesor, éste empieza considerando un árbol de 1 vértice y 0 aristas, luego está claro que sigue el mismo criterio que yo.

Luego un árbol de 2 vértices y 1 arista no puede venir de un árbol de menor cantidad de vértices, lo que no cumpliría la hipótesis del profesor, porque no provendría de un árbol de  menor cantidad de vértices.

Pero es que, como digo, él sí que admite árboles con 1 vértice y 0 aristas, y me parece razonable.

[Luis Fuentes]

Hola

Pero sí podemos afirmar que de todo árbol de h vértices se puede obtener uno de h+1 vértices, simplemente  agregando un vértice uniéndolo por obligación para hacerlo conexo mediante una arista. De ese modo siempre se cumple que v=h+1.

Si, eso es cierto; pero lo que necesita la demostración del profesor para funcionar es lo contrario: que todo árbol de \( h+1 \) vértices pueda obtenerse agregando un vértice a uno de \( h \) vértices. ¡También se cumple, pero hay que mencionarlo y justificarlo!.

Saludos.

[Richard R Richard]

Claro, claro, yo apuntaba a que si la definición no permitiese arboles de \( v=1 \), entonces el de \( v=2 \) no podía provenir de un árbol "conexo"(porque lo consideraba excluyente, y fui a leer por ahí y me dejo el vocablo), y entonces así fallaba la demostración.


Saludos.


Pd por otro lado es posible obtener un arbol \( h+1 \) de otro modo que no sea exclusivamente de agregar un vértice y una arista a uno de \(  h \),


ejemplo si \( h+1 =x+y \) dpnde \( x \) e \( y \) son el numero de vértices de dos arboles cualesquiera los puedes unir por cualquier par de vértices y obtener un arbol de \( h+1 \) vértices, sin provenir necesariamente de uno de \( h \) vértices.

[manooooh]

Hola

1) \( p\rightarrow (q\rightarrow p) \) es una tautología (si construyes su tabla de verdad verás que siempre es verdadera). Por lo tanto, es un teorema.

2) Si has demostrado \( p \), entonces, sólo tienes que añadir a la demostración la tautología anterior y luego concluir \( q\rightarrow p \) por modus ponens.

Aquí \( q\rightarrow p \) es la implicación que le pedías demostrar a Luis.

Ya lo veo. Mm, no sé si era lo que yo pedía demostrar, porque un ejercicio de grafos se traslada a uno de lógica, aunque tu razonamiento es perfectamente válido.

La pregunta sigue siendo la misma: ¿se puede parchear uno de los problemas del profesor (el otro es cómo está redactado) simplemente agregando lo rojo?:

Es decir reconozco que la prueba está incompleta; pero si se agregara algo como "y como se sabe que 1) y 2) se cumplen en todo árbol" quedando:

Paso Base (...)

Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \). Esto es así pues al agregar una arista entre dos vértices de un árbol, deja de árbol y todas las aristas de un árbol son puentes.

¿Con lo agregado en rojo ahora queda completa la prueba?

Con esto quiero saber si realmente hace falta mencionar una prueba de que todo árbol de \( h+1 \) vértices se puede construir añadiendo un vértice a uno de \( h \) vértices, porque las 2 propiedades que mencioné ya se pueden tomar como verdaderas. Entonces lo que Luis demuestra ya está demostrado previamente. Pero claro, si lo que agrego no es lo mismo (equivalente) de lo que Luis demuestra es porque lo que pretendo agregar no justifica dicha prueba.

Por decir un ejemplo, podríamos decir que el Modus Tollens (que dice \( p\to q \) y \( \neg q \) por tanto \( \neg p \)) se puede demostrar de una manera sofisticada y correcta. Pero la realidad es que si uno toma de base el Modus Ponens (lo que yo digo de las 2 propiedades en mi mensaje #25) no hace falta usar la prueba sofisticada pues simplemente por equivalencia del condicional \( \neg q\to\neg p \), y se concluye de inmediato.

Eso es cierto, pero no es lo que hace tu profesor. Tiene la hipótesis:

Si un árbol \( T \) tiene \( h \) vértices \( \rightarrow \) \( T \) tiene \( h-1 \) aristas.

Y quiere demostrar que

Si un árbol \( T \) tiene \( h+1 \) vértices \( \rightarrow \) \( T \) tiene \( h \) aristas.

Si hiciera caso a lo que has dicho tú, tendría que empezar con un árbol con \( h+1 \) vértices, para probar que tiene \( h \) aristas, pero en lugar de hacer eso, parte de un árbol con \( h \) vértices (lo cual no es la hipótesis del condicional que quiere probar, es decir, no hace lo que tú dices que es natural hacer), se construye otro con \( h+1 \) vértices, prueba que tiene \( h \) aristas y concluye que ha probado algo para todos los árboles con \( h+1 \) vértices, lo cual es cierto gracias a algo que no dice, y es que todos los árboles con \( h+1 \) vértices pueden construirse como él ha construido el suyo.

Comprendo.

Saludos

[Carlos Ivorra]

La pregunta sigue siendo la misma: ¿se puede parchear uno de los problemas del profesor (el otro es cómo está redactado) simplemente agregando lo rojo?:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).

A cualquiera de esos árboles, le agregamos un nuevo vértice \( v_{h+1} \) para formar un nuevo árbol \( T_{h+1} \) es decir: \( V_{h+1}=V_u\cup\{v_{h+1}\} \). Esto es así pues al agregar una arista entre dos vértices de un árbol, deja de árbol y todas las aristas de un árbol son puentes.

¿Con lo agregado en rojo ahora queda completa la prueba?

Sigue estando implícito que puede partir de un árbol con \( h \) vértices y extenderlo a uno con \( h+1 \) vértices porque todo árbol con \( h+1 \) vértices puede obtenerse de ese modo.

Creo que confundes lo importante del asunto. A ver si así lo ves mejor:

Lo que hay que probar (partiendo de la hipótesis de inducción):

Todo árbol con \( h+1 \) vértices tiene \( h \) aristas.

Lo que prueba tu profesor:

Todo árbol con \( h+1 \) vértices obtenido añadiendo un vértice y una arista a otro de \( h \) vértices tiene \( h \) aristas.

La cuestión no es justificar que a todo árbol con \( h \) vértices se le puede añadir un vértice y una arista para formar un nuevo árbol con \( h+1 \) vértices, que es lo que parece que quieras justificar con la frase que has puesto en rojo. Lo que hay que justificar es que:

Todo árbol con \( h+1 \) vértices

es lo mismo que

Todo árbol con \( h+1 \) vértices obtenido añadiendo un vértice y una arista a otro de \( h \) vértices

Aunque es mucho más sencillo y natural no justificar nada de esto y partir desde un principio de un árbol con \( h+1 \) vértices como está mandado.

[manooooh]

Hola

Tengo 2 consultas:

1) Considerando la prueba completa de Luis:

Prueba

Para que no queden dudas mi prueba completa sería:

Teorema: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Demostración por inducción en el número de vértices:

Caso base \( n=2 \). Es inmediato que un árbol \( T_2 \) de dos vértices tiene \( 1 \) arista que los conecta. Por tanto \( |V(T_2)|=2=1+1=|A(T_2)|+1 \).

Paso inductivo:

Hipótesis: Todo árbol \( T_n \) con \( |V(T_n)|=n \) (de \( n \) vértices) cumple \( |V(T_n)|=|A(T_n)|+1 \).

Tesis: Todo árbol \( T_{n+1} \) con \( V(T_{n+1})=n+1 \) (de \( n+1 \) vértices) cumple \( |V(T_{n+1})|=|A(T_{n+1})|+1 \).

Sea \( T_{n+1} \) un árbol de \( n+1 \) vértices.

1) Por ser \( T_{n+1} \) un árbol tiene un vértice de grado uno.

Prueba:

Sea \( v_1\to v_2\to \ldots\to v_k) \) un camino maximal (no se puede añadir más vértices). Si \( v_1 \) no tiene grado \( 1 \), tiene otra arista distinta de la que lo une con \( v_2 \). Pero por ser un camino maximal \( v_1 \) no puede ser unido a otro vértice distinto de los \( k \) vértices que forman el camino  por tanto estaría unido a alguno de los vértices \( v_3,\ldots,v_k \) y tendríamos un ciclo. Pero un árbol no tiene ciclos.

[cerrar]

2) Si al \( T_{n+1} \) le quitamos su vértice de grado uno y su única arista adyacente queda un árbol \( T_n \) con un vértice menos y una arista menos, es decir,

\( |V(T_n)|=|V(T_{n+1})|-1,\qquad |A(T_n)|=|A(T_{n+1)}|-1 \)

Prueba:

Que el nuevo grafo tiene un vértice menos y una arista menos es obvio por construcción. Nos queda ver que es árbol.

Está claro que si el grafo original \( T_{n+1} \) no tenía ciclos al quitar un vértice de grado \( 1 \) y su arista, sigue sin haber ciclos. Lo único que hay que probar es que \( T_{n+1}-\{v\} \) sigue siendo conexo. Pero dados dos vértices de \( u,w\in T_{n+1}-\{v\} \) sabemos que se pueden conectar por un camino en \( T_{n+1} \). Como \( grado(v)=1 \) ese camino no puede contener a \( v \) (ya que en un camino salvo los vértices inical y final todos los demás tienen al menos grado dos). Por tanto ese camino está en \( T_{n+1}-\{v\} \).

[cerrar]

3) Por hipótesis de inducción el árbol \( T_n \) con \( |V(T_n)|=|V(T_{n+1})|-1=n+1-1=n \) cumple:

\( |V(T_n)|=|A(T_n)|+1 \)

Pero entonces:

\( |V(T_{n+1})|=|V(T_n)|+1=|A(T_n)|+1+1=|A(T_{n+1})|+1 \)

que es justo lo que queríamos probar.

[cerrar]

¿Sigue siendo válida si definimos grafo agregando la posibilidad de que existen aristas paralelas (dados dos vértices pueden haber más de una arista entre ellos) y agregando la posibilidad de bucles (aristas de un vértice a sí mismo)? ¿O deja de ser válida con esta definición de grafo? Necesito amoldar la prueba para este tipo de grafos pues es cómo se enseña en mi universidad desde siempre.

2) Carlos: Entiendo la crítica que haces aquí:

Eso es cierto, pero no es lo que hace tu profesor. Tiene la hipótesis:

Si un árbol \( T \) tiene \( h \) vértices \( \rightarrow \) \( T \) tiene \( h-1 \) aristas.

Y quiere demostrar que

Si un árbol \( T \) tiene \( h+1 \) vértices \( \rightarrow \) \( T \) tiene \( h \) aristas.

Si hiciera caso a lo que has dicho tú, tendría que empezar con un árbol con \( h+1 \) vértices, para probar que tiene \( h \) aristas, pero en lugar de hacer eso, parte de un árbol con \( h \) vértices (lo cual no es la hipótesis del condicional que quiere probar, es decir, no hace lo que tú dices que es natural hacer), se construye otro con \( h+1 \) vértices, prueba que tiene \( h \) aristas y concluye que ha probado algo para todos los árboles con \( h+1 \) vértices, lo cual es cierto gracias a algo que no dice, y es que todos los árboles con \( h+1 \) vértices pueden construirse como él ha construido el suyo.

Pero mira lo que veo yo en la prueba del profesor, la cito nuevamente:

(...)
Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).
(...)

Si uno quiere demostrar \( p\to q \) también es válido empezar por \( p \) y llegar a \( q \) en vez de empezar por un miembro de \( q \). En la cita es bastante obvio que empieza por la hipótesis: dice que considera un árbol de \( h \) vértices cuyas aristas son \( h-1 \). Y luego sigue. La única "crítica" que veo es que dice "Sabemos por hipótesis que (...)" pero sino, no veo nada por mejorar la redacción, ¿cómo lo ves?

Saludos

[Carlos Ivorra]

¿Sigue siendo válida si definimos grafo agregando la posibilidad de que existen aristas paralelas (dados dos vértices pueden haber más de una arista entre ellos) y agregando la posibilidad de bucles (aristas de un vértice a sí mismo)? ¿O deja de ser válida con esta definición de grafo? Necesito amoldar la prueba para este tipo de grafos pues es cómo se enseña en mi universidad desde siempre.

¿Pero cuál es entonces la definición de árbol? ¿Un grafo con dos vértices y dos aristas paralelas que los conectan es un árbol? Porque si lo consideras un árbol, entonces tiene el mismo número de vértices que de aristas, luego la afirmación es falsa.

Pero mira lo que veo yo en la prueba del profesor, la cito nuevamente:

(...)
Paso inductivo:

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \).

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

Para probarlo, consideremos cualquier árbol \( T_h \) de \( h \) vértices, o sea \( V_h=\{v_1,v_2,\dots,v_h\} \). Sabemos por hipótesis que tiene \( |A_h|=h-1 \).
(...)

Si uno quiere demostrar \( p\to q \) también es válido empezar por \( p \) y llegar a \( q \) en vez de empezar por un miembro de \( q \). En la cita es bastante obvio que empieza por la hipótesis: dice que considera un árbol de \( h \) vértices cuyas aristas son \( h-1 \). Y luego sigue. La única "crítica" que veo es que dice "Sabemos por hipótesis que (...)" pero sino, no veo nada por mejorar la redacción, ¿cómo lo ves?

En el "\( p\rightarrow q \)" del que hablas, \( p \) es

Hipótesis: En todo árbol, si \( |V|=h \) entonces \( |A|=h-1 \)

Bien, ya hemos supuesto \( p \), y queremos demostrar \( q \), que es

Tesis: En todo árbol, si \( |V|=h+1 \) entonces \( |A|=h \).

¿Y ahora qué? Una vez hemos supuesto \( p \) ¿qué hacemos para demostrar \( q \)? Tendrás que tomar un árbol con \( h+1 \) vértices para ver si tiene \( h \) aristas, ¿no?

Pero tu profesor toma un árbol con \( h \) vértices, a partir de él construye otro de \( h+1 \) vértices, y con ello demuestra que "si un árbol de \( h+1 \) vértices se ha construido a partir de otro de \( h \) vértices, entonces tiene \( h \) aristas". Ahora le falta justificar que los árboles de \( h+1 \) vértices construidos a partir de árboles de \( h \) vértices son todos los árboles de \( h+1 \) vértices.