L.replace – Calculemus

Límite de sucesiones no decrecientes

PorJosé A. Alonso 6 septiembre 20213 septiembre 2021

En Lean, una sucesión u₀, u₁, u₂, … se puede representar mediante una función (u : ℕ → ℝ) de forma que u(n) es uₙ.

En Lean, se define que a es el límite de la sucesión u, por

   def limite (u: ℕ → ℝ) (a: ℝ) :=
     ∀ ε > 0, ∃ N, ∀ n ≥ N, |u n - a| < ε
<pre lang="text">
donde se usa la notación |x| para el valor absoluto de x
<pre lang="text">
   notation `|`x`|` := abs x

def limite (u: ℕ → ℝ) (a: ℝ) :=

∀ ε > 0, ∃ N, ∀ n ≥ N, |u n - a| < ε

donde se usa la notación |x| para el valor absoluto de x

notation `|`x`|` := abs x

y que la sucesión u es no decreciente por

   def no_decreciente (u : ℕ → ℝ) :=
     ∀ n m, n ≤ m → u n ≤ u m

1 2	def no_decreciente (u : ℕ → ℝ) := ∀ n m, n ≤ m → u n ≤ u m

Demostrar que si u es una sucesión no decreciente y su límite es a, entonces u(n) ≤ a para todo n.

Para ello, completar la siguiente teoría de Lean:

import data.real.basic
import tactic

variable {u : ℕ → ℝ}
variable (a : ℝ)

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=
  ∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def no_decreciente (u : ℕ → ℝ) :=
  ∀ n m, n ≤ m → u n ≤ u m

example
  (h : limite u a)
  (h' : no_decreciente u)
  : ∀ n, u n ≤ a :=
sorry

import data.real.basic

import tactic

variable {u : ℕ → ℝ}

variable (a : ℝ)

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=

∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def no_decreciente (u : ℕ → ℝ) :=

∀ n m, n ≤ m → u n ≤ u m

example

(h : limite u a)

(h' : no_decreciente u)

: ∀ n, u n ≤ a :=

sorry

[expand title=»Soluciones con Lean»]

import data.real.basic
import tactic

variable {u : ℕ → ℝ}
variable (a : ℝ)

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=
  ∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def no_decreciente (u : ℕ → ℝ) :=
  ∀ n m, n ≤ m → u n ≤ u m

-- 1ª demostración
example
  (h : limite u a)
  (h' : no_decreciente u)
  : ∀ n, u n ≤ a :=
begin
  intro n,
  by_contradiction H,
  push_neg at H,
  replace H : u n - a > 0 := sub_pos.mpr H,
  cases h (u n - a) H with m hm,
  let k := max n m,
  specialize hm k (le_max_right _ _),
  specialize h' n k (le_max_left _ _),
  replace hm : |u k - a| < u k - a, by
    calc |u k - a| < u n - a : hm
               ... ≤ u k - a : sub_le_sub_right h' a,
  rw ← not_le at hm,
  apply hm,
  exact le_abs_self (u k - a),
end

-- 2ª demostración
example
  (h : limite u a)
  (h' : no_decreciente u)
  : ∀ n, u n ≤ a :=
begin
  intro n,
  by_contradiction H,
  push_neg at H,
  cases h (u n - a) (by linarith) with m hm,
  specialize hm (max n m) (le_max_right _ _),
  specialize h' n (max n m) (le_max_left _ _),
  rw abs_lt at hm,
  linarith,
end

import data.real.basic

import tactic

variable {u : ℕ → ℝ}

variable (a : ℝ)

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=

∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def no_decreciente (u : ℕ → ℝ) :=

∀ n m, n ≤ m → u n ≤ u m

-- 1ª demostración

example

(h : limite u a)

(h' : no_decreciente u)

: ∀ n, u n ≤ a :=

begin

intro n,

by_contradiction H,

push_neg at H,

replace H : u n - a > 0 := sub_pos.mpr H,

cases h (u n - a) H with m hm,

let k := max n m,

specialize hm k (le_max_right _ _),

specialize h' n k (le_max_left _ _),

replace hm : |u k - a| < u k - a, by

calc |u k - a| < u n - a : hm

... ≤ u k - a : sub_le_sub_right h' a,

rw ← not_le at hm,

apply hm,

exact le_abs_self (u k - a),

end

-- 2ª demostración

example

(h : limite u a)

(h' : no_decreciente u)

: ∀ n, u n ≤ a :=

begin

intro n,

by_contradiction H,

push_neg at H,

cases h (u n - a) (by linarith) with m hm,

specialize hm (max n m) (le_max_right _ _),

specialize h' n (max n m) (le_max_left _ _),

rw abs_lt at hm,

linarith,

end

Se puede interactuar con la prueba anterior en esta sesión con Lean.

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="lean"> y otra con </pre>
[/expand]

[expand title=»Soluciones con Isabelle/HOL»]

theory Limite_de_sucesiones_no_decrecientes
imports Main HOL.Real
begin

definition limite :: "(nat ⇒ real) ⇒ real ⇒ bool"
  where "limite u a ⟷ (∀ε>0. ∃N. ∀k≥N. ¦u k - a¦ < ε)"

definition no_decreciente :: "(nat ⇒ real) ⇒ bool"
  where "no_decreciente u ⟷ (∀ n m. n ≤ m ⟶ u n ≤ u m)"

(* 1ª demostración *)
lemma
  assumes "limite u a"
          "no_decreciente u"
  shows   "∀ n. u n ≤ a"
proof (rule allI)
  fix n
  show "u n ≤ a"
  proof (rule ccontr)
    assume "¬ u n ≤ a"
    then have "a < u n"
      by (rule not_le_imp_less)
    then have H : "u n - a > 0"
      by (simp only: diff_gt_0_iff_gt)
    then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"
      using assms(1) limite_def by blast
    let ?k = "max n m"
    have "n ≤ ?k"
      by (simp only: assms(2) no_decreciente_def)
    then have "u n ≤ u ?k"
      using assms(2) no_decreciente_def by blast
    have "¦u ?k - a¦ < u n - a"
      by (simp only: hm)
    also have "… ≤ u ?k - a"
      using ‹u n ≤ u ?k› by (rule diff_right_mono)
    finally have "¦u ?k - a¦ < u ?k - a"
      by this
    then have "¬ u ?k - a ≤ ¦u ?k - a¦"
      by (simp only: not_le_imp_less)
    moreover have "u ?k - a ≤ ¦u ?k - a¦"
      by (rule abs_ge_self)
    ultimately show False
      by (rule notE)
  qed
qed

(* 2ª demostración *)
lemma
  assumes "limite u a"
          "no_decreciente u"
  shows   "∀ n. u n ≤ a"
proof (rule allI)
  fix n
  show "u n ≤ a"
  proof (rule ccontr)
    assume "¬ u n ≤ a"
    then have H : "u n - a > 0"
      by simp
    then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"
      using assms(1) limite_def by blast
    let ?k = "max n m"
    have "¦u ?k - a¦ < u n - a"
      using hm by simp
    moreover have "u n ≤ u ?k"
      using assms(2) no_decreciente_def by simp
    ultimately have "¦u ?k - a¦ < u ?k - a"
      by simp
    then show False
      by simp
  qed
qed

(* 3ª demostración *)
lemma
  assumes "limite u a"
          "no_decreciente u"
  shows   "∀ n. u n ≤ a"
proof
  fix n
  show "u n ≤ a"
  proof (rule ccontr)
    assume "¬ u n ≤ a"
    then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"
      using assms(1) limite_def by fastforce
    let ?k = "max n m"
    have "¦u ?k - a¦ < u n - a"
      using hm by simp
    moreover have "u n ≤ u ?k"
      using assms(2) no_decreciente_def by simp
    ultimately show False
      by simp
  qed
qed

end

theory Limite_de_sucesiones_no_decrecientes

imports Main HOL.Real

begin

definition limite :: "(nat ⇒ real) ⇒ real ⇒ bool"

where "limite u a ⟷ (∀ε>0. ∃N. ∀k≥N. ¦u k - a¦ < ε)"

definition no_decreciente :: "(nat ⇒ real) ⇒ bool"

where "no_decreciente u ⟷ (∀ n m. n ≤ m ⟶ u n ≤ u m)"

(* 1ª demostración *)

lemma

assumes "limite u a"

"no_decreciente u"

shows "∀ n. u n ≤ a"

proof (rule allI)

fix n

show "u n ≤ a"

proof (rule ccontr)

assume "¬ u n ≤ a"

then have "a < u n"

by (rule not_le_imp_less)

then have H : "u n - a > 0"

by (simp only: diff_gt_0_iff_gt)

then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"

using assms(1) limite_def by blast

let ?k = "max n m"

have "n ≤ ?k"

by (simp only: assms(2) no_decreciente_def)

then have "u n ≤ u ?k"

using assms(2) no_decreciente_def by blast

have "¦u ?k - a¦ < u n - a"

by (simp only: hm)

also have "… ≤ u ?k - a"

using ‹u n ≤ u ?k› by (rule diff_right_mono)

finally have "¦u ?k - a¦ < u ?k - a"

by this

then have "¬ u ?k - a ≤ ¦u ?k - a¦"

by (simp only: not_le_imp_less)

moreover have "u ?k - a ≤ ¦u ?k - a¦"

by (rule abs_ge_self)

ultimately show False

by (rule notE)

qed

(* 2ª demostración *)

lemma

assumes "limite u a"

"no_decreciente u"

shows "∀ n. u n ≤ a"

proof (rule allI)

fix n

show "u n ≤ a"

proof (rule ccontr)

assume "¬ u n ≤ a"

then have H : "u n - a > 0"

by simp

then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"

using assms(1) limite_def by blast

let ?k = "max n m"

have "¦u ?k - a¦ < u n - a"

using hm by simp

moreover have "u n ≤ u ?k"

using assms(2) no_decreciente_def by simp

ultimately have "¦u ?k - a¦ < u ?k - a"

by simp

then show False

by simp

qed

(* 3ª demostración *)

lemma

assumes "limite u a"

"no_decreciente u"

shows "∀ n. u n ≤ a"

proof

fix n

show "u n ≤ a"

proof (rule ccontr)

assume "¬ u n ≤ a"

then obtain m where hm : "∀p≥m. ¦u p - a¦ < u n - a"

using assms(1) limite_def by fastforce

let ?k = "max n m"

have "¦u ?k - a¦ < u n - a"

using hm by simp

moreover have "u n ≤ u ?k"

using assms(2) no_decreciente_def by simp

ultimately show False

by simp

qed

end

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="isar"> y otra con </pre>
[/expand]

Las sucesiones divergentes positivas no tienen límites finitos

PorJosé A. Alonso 5 septiembre 20211 septiembre 2021

En Lean, una sucesión u₀, u₁, u₂, … se puede representar mediante una función (u : ℕ → ℝ) de forma que u(n) es uₙ.

Se define que a es el límite de la sucesión u, por

   def limite (u: ℕ → ℝ) (a: ℝ) :=
     ∀ ε > 0, ∃ N, ∀ n ≥ N, |u n - a| < ε

1 2	def limite (u: ℕ → ℝ) (a: ℝ) := ∀ ε > 0, ∃ N, ∀ n ≥ N, \|u n - a\| < ε

donde se usa la notación |x| para el valor absoluto de x

   notation `|`x`|` := abs x

1	notation `\|`x`\|` := abs x

La sucesión u diverge positivamente cuando, para cada número real A, se puede encontrar un número natural m tal que, para n > m , se tenga u(n) > A. En Lean se puede definir por

   def diverge_positivamente (u : ℕ → ℝ) :=
     ∀ A, ∃ m, ∀ n ≥ m, u n > A

1 2	def diverge_positivamente (u : ℕ → ℝ) := ∀ A, ∃ m, ∀ n ≥ m, u n > A

Demostrar que si u diverge positivamente, entonces ningún número real es límite de u.

Para ello, completar la siguiente teoría de Lean:

import data.real.basic
import tactic

variable  {u : ℕ → ℝ}

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=
  ∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def diverge_positivamente (u : ℕ → ℝ) :=
  ∀ A, ∃ m, ∀ n ≥ m, u n > A

example
  (h : diverge_positivamente u)
  : ¬(∃ a, limite u a) :=
sorry

import data.real.basic

import tactic

variable {u : ℕ → ℝ}

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=

∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def diverge_positivamente (u : ℕ → ℝ) :=

∀ A, ∃ m, ∀ n ≥ m, u n > A

example

(h : diverge_positivamente u)

: ¬(∃ a, limite u a) :=

sorry

[expand title=»Soluciones con Lean»]

import data.real.basic
import tactic

variable  {u : ℕ → ℝ}

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=
  ∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def diverge_positivamente (u : ℕ → ℝ) :=
  ∀ A, ∃ m, ∀ n ≥ m, u n > A

-- 1ª demostración
example
  (h : diverge_positivamente u)
  : ¬(∃ a, limite u a) :=
begin
  push_neg,
  intros a ha,
  cases ha 1 zero_lt_one with m1 hm1,
  cases h (a+1) with m2 hm2,
  let m := max m1 m2,
  specialize hm1 m (le_max_left _ _),
  specialize hm2 m (le_max_right _ _),
  replace hm1 : u m - a < 1 := lt_of_abs_lt hm1,
  replace hm2 : 1 < u m - a := lt_sub_iff_add_lt'.mpr hm2,
  apply lt_irrefl (u m),
  calc u m < a + 1 : sub_lt_iff_lt_add'.mp hm1
       ... < u m   : lt_sub_iff_add_lt'.mp hm2,
end

-- 2ª demostración
example
  (h : diverge_positivamente u)
  : ¬(∃ a, limite u a) :=
begin
  push_neg,
  intros a ha,
  cases ha 1 (by linarith) with m1 hm1,
  cases h (a+1) with m2 hm2,
  let m := max m1 m2,
  replace hm1 : |u m - a| < 1 := by finish,
  replace hm1 : u m - a < 1   := lt_of_abs_lt hm1,
  replace hm2 : u m > a + 1   := by finish,
  replace hm2 : 1 < u m - a   := lt_sub_iff_add_lt'.mpr hm2,
  apply lt_irrefl (u m),
  calc u m < a + 1 : by linarith
       ... < u m   : by linarith
end

-- 3ª demostración
example
  (h : diverge_positivamente u)
  : ¬(∃ a, limite u a) :=
begin
  push_neg,
  intros a ha,
  cases ha 1 (by linarith) with m1 hm1,
  cases h (a+1) with m2 hm2,
  let m := max m1 m2,
  specialize hm1 m (le_max_left _ _),
  specialize hm2 m (le_max_right _ _),
  rw abs_lt at hm1,
  linarith,
end

import data.real.basic

import tactic

variable {u : ℕ → ℝ}

notation `|`x`|` := abs x

def limite (u : ℕ → ℝ) (a : ℝ) :=

∀ ε > 0, ∃ m, ∀ n ≥ m, |u n - a| < ε

def diverge_positivamente (u : ℕ → ℝ) :=

∀ A, ∃ m, ∀ n ≥ m, u n > A

-- 1ª demostración

example

(h : diverge_positivamente u)

: ¬(∃ a, limite u a) :=

begin

push_neg,

intros a ha,

cases ha 1 zero_lt_one with m1 hm1,

cases h (a+1) with m2 hm2,

let m := max m1 m2,

specialize hm1 m (le_max_left _ _),

specialize hm2 m (le_max_right _ _),

replace hm1 : u m - a < 1 := lt_of_abs_lt hm1,

replace hm2 : 1 < u m - a := lt_sub_iff_add_lt'.mpr hm2,

apply lt_irrefl (u m),

calc u m < a + 1 : sub_lt_iff_lt_add'.mp hm1

... < u m : lt_sub_iff_add_lt'.mp hm2,

end

-- 2ª demostración

example

(h : diverge_positivamente u)

: ¬(∃ a, limite u a) :=

begin

push_neg,

intros a ha,

cases ha 1 (by linarith) with m1 hm1,

cases h (a+1) with m2 hm2,

let m := max m1 m2,

replace hm1 : |u m - a| < 1 := by finish,

replace hm1 : u m - a < 1 := lt_of_abs_lt hm1,

replace hm2 : u m > a + 1 := by finish,

replace hm2 : 1 < u m - a := lt_sub_iff_add_lt'.mpr hm2,

apply lt_irrefl (u m),

calc u m < a + 1 : by linarith

... < u m : by linarith

end

-- 3ª demostración

example

(h : diverge_positivamente u)

: ¬(∃ a, limite u a) :=

begin

push_neg,

intros a ha,

cases ha 1 (by linarith) with m1 hm1,

cases h (a+1) with m2 hm2,

let m := max m1 m2,

specialize hm1 m (le_max_left _ _),

specialize hm2 m (le_max_right _ _),

rw abs_lt at hm1,

linarith,

end

Se puede interactuar con la prueba anterior en esta sesión con Lean.

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="lean"> y otra con </pre>
[/expand]

[expand title=»Soluciones con Isabelle/HOL»]

theory Las_sucesiones_divergentes_positivas_no_tienen_limites_finitos
imports Main HOL.Real
begin

definition limite :: "(nat ⇒ real) ⇒ real ⇒ bool"
  where "limite u a ⟷ (∀ε>0. ∃N. ∀k≥N. ¦u k - a¦ < ε)"

definition diverge_positivamente :: "(nat ⇒ real) ⇒ bool"
  where "diverge_positivamente u ⟷ (∀A. ∃m. ∀n≥m. u n > A)"

(* 1ª demostración *)
lemma
  assumes "diverge_positivamente u"
  shows   "∄a. limite u a"
proof (rule notI)
  assume "∃a. limite u a"
  then obtain a where "limite u a" try
    by auto
  then obtain m1 where hm1 : "∀n≥m1. ¦u n - a¦ < 1"
    using limite_def by fastforce
  obtain m2 where hm2 : "∀n≥m2. u n > a + 1"
    using assms diverge_positivamente_def by blast
  let ?m = "max m1 m2"
  have "u ?m < u ?m" using hm1 hm2
  proof -
    have "?m ≥ m1"
      by (rule max.cobounded1)
    have "?m ≥ m2"
      by (rule max.cobounded2)
    have "u ?m - a < 1"
      using hm1 ‹?m ≥ m1› by fastforce
    moreover have "u ?m > a + 1"
      using hm2 ‹?m ≥ m2› by simp
    ultimately show "u ?m < u ?m"
      by simp
  qed
  then show False
    by auto
qed

(* 2ª demostración *)
lemma
  assumes "diverge_positivamente u"
  shows   "∄a. limite u a"
proof (rule notI)
  assume "∃a. limite u a"
  then obtain a where "limite u a" try
    by auto
  then obtain m1 where hm1 : "∀n≥m1. ¦u n - a¦ < 1"
    using limite_def by fastforce
  obtain m2 where hm2 : "∀n≥m2. u n > a + 1"
    using assms diverge_positivamente_def by blast
  let ?m = "max m1 m2"
  have "1 < 1"
  proof -
    have "1 < u ?m - a"
      using hm2
      by (metis add.commute less_diff_eq max.cobounded2)
    also have "… < 1"
      using hm1
      by (metis abs_less_iff max_def order_refl)
    finally show "1 < 1" .
  qed
  then show False
    by auto
qed

end

theory Las_sucesiones_divergentes_positivas_no_tienen_limites_finitos

imports Main HOL.Real

begin

definition limite :: "(nat ⇒ real) ⇒ real ⇒ bool"

where "limite u a ⟷ (∀ε>0. ∃N. ∀k≥N. ¦u k - a¦ < ε)"

definition diverge_positivamente :: "(nat ⇒ real) ⇒ bool"

where "diverge_positivamente u ⟷ (∀A. ∃m. ∀n≥m. u n > A)"

(* 1ª demostración *)

lemma

assumes "diverge_positivamente u"

shows "∄a. limite u a"

proof (rule notI)

assume "∃a. limite u a"

then obtain a where "limite u a" try

by auto

then obtain m1 where hm1 : "∀n≥m1. ¦u n - a¦ < 1"

using limite_def by fastforce

obtain m2 where hm2 : "∀n≥m2. u n > a + 1"

using assms diverge_positivamente_def by blast

let ?m = "max m1 m2"

have "u ?m < u ?m" using hm1 hm2

proof -

have "?m ≥ m1"

by (rule max.cobounded1)

have "?m ≥ m2"

by (rule max.cobounded2)

have "u ?m - a < 1"

using hm1 ‹?m ≥ m1› by fastforce

moreover have "u ?m > a + 1"

using hm2 ‹?m ≥ m2› by simp

ultimately show "u ?m < u ?m"

by simp

qed

then show False

by auto

qed

(* 2ª demostración *)

lemma

assumes "diverge_positivamente u"

shows "∄a. limite u a"

proof (rule notI)

assume "∃a. limite u a"

then obtain a where "limite u a" try

by auto

then obtain m1 where hm1 : "∀n≥m1. ¦u n - a¦ < 1"

using limite_def by fastforce

obtain m2 where hm2 : "∀n≥m2. u n > a + 1"

using assms diverge_positivamente_def by blast

let ?m = "max m1 m2"

have "1 < 1"

proof -

have "1 < u ?m - a"

using hm2

by (metis add.commute less_diff_eq max.cobounded2)

also have "… < 1"

using hm1

by (metis abs_less_iff max_def order_refl)

finally show "1 < 1" .

qed

then show False

by auto

qed

end

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="isar"> y otra con </pre>
[/expand]

Las particiones definen relaciones reflexivas

PorJosé A. Alonso 25 agosto 202119 agosto 2021

Cada familia de conjuntos P define una relación de forma que dos elementos están relacionados si algún conjunto de P contiene a ambos elementos. Se puede definir en Lean por

   def relacion (P : set (set X)) (x y : X) :=
     ∃ A ∈ P, x ∈ A ∧ y ∈ A

1 2	def relacion (P : set (set X)) (x y : X) := ∃ A ∈ P, x ∈ A ∧ y ∈ A

Una familia de subconjuntos de X es una partición de X si cada elemento de X pertenece a un único conjunto de P y todos los elementos de P son no vacíos. Se puede definir en Lean por

   def particion (P : set (set X)) : Prop :=
     (∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

1 2	def particion (P : set (set X)) : Prop := (∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

Demostrar que si P es una partición de X, entonces la relación definida por P es reflexiva.

Para ello, completar la siguiente teoría de Lean:

import tactic

variable {X : Type}
variable (P : set (set X))

def relacion (P : set (set X)) (x y : X) :=
  ∃ A ∈ P, x ∈ A ∧ y ∈ A

def particion (P : set (set X)) : Prop :=
  (∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

example
  (h : particion P)
  : reflexive (relacion P) :=
sorry

import tactic

variable {X : Type}

variable (P : set (set X))

def relacion (P : set (set X)) (x y : X) :=

∃ A ∈ P, x ∈ A ∧ y ∈ A

def particion (P : set (set X)) : Prop :=

(∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

example

(h : particion P)

: reflexive (relacion P) :=

sorry

[expand title=»Soluciones con Lean»]

import tactic

variable {X : Type}
variable (P : set (set X))

def relacion (P : set (set X)) (x y : X) :=
  ∃ A ∈ P, x ∈ A ∧ y ∈ A

def particion (P : set (set X)) : Prop :=
  (∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

-- 1ª demostración
example
  (h : particion P)
  : reflexive (relacion P) :=
begin
  unfold reflexive,
  intro x,
  unfold relacion,
  unfold particion at h,
  replace h : ∃ A ∈ P, x ∈ A ∧ ∀ B ∈ P, x ∈ B → A = B := h.1 x,
  rcases h with ⟨A, hAP, hxA, -⟩,
  use A,
  repeat { split },
  { exact hAP, },
  { exact hxA, },
  { exact hxA, },
end

-- 2ª demostración
example
  (h : particion P)
  : reflexive (relacion P) :=
begin
  intro x,
  replace h : ∃ A ∈ P, x ∈ A ∧ ∀ B ∈ P, x ∈ B → A = B := h.1 x,
  rcases h with ⟨A, hAP, hxA, -⟩,
  use A,
  repeat { split } ; assumption,
end

-- 3ª demostración
example
  (h : particion P)
  : reflexive (relacion P) :=
begin
  intro x,
  rcases (h.1 x) with ⟨A, hAP, hxA, -⟩,
  use A,
  repeat { split } ; assumption,
end

-- 4ª demostración
example
  (h : particion P)
  : reflexive (relacion P) :=
begin
  intro x,
  rcases (h.1 x) with ⟨A, hAP, hxA, -⟩,
  use [A, ⟨hAP, hxA, hxA⟩],
end

import tactic

variable {X : Type}

variable (P : set (set X))

def relacion (P : set (set X)) (x y : X) :=

∃ A ∈ P, x ∈ A ∧ y ∈ A

def particion (P : set (set X)) : Prop :=

(∀ x, (∃ B ∈ P, x ∈ B ∧ ∀ C ∈ P, x ∈ C → B = C)) ∧ ∅ ∉ P

-- 1ª demostración

example

(h : particion P)

: reflexive (relacion P) :=

begin

unfold reflexive,

intro x,

unfold relacion,

unfold particion at h,

replace h : ∃ A ∈ P, x ∈ A ∧ ∀ B ∈ P, x ∈ B → A = B := h.1 x,

rcases h with ⟨A, hAP, hxA, -⟩,

use A,

repeat { split },

{ exact hAP, },

{ exact hxA, },

end

-- 2ª demostración

example

(h : particion P)

: reflexive (relacion P) :=

begin

intro x,

replace h : ∃ A ∈ P, x ∈ A ∧ ∀ B ∈ P, x ∈ B → A = B := h.1 x,

rcases h with ⟨A, hAP, hxA, -⟩,

use A,

repeat { split } ; assumption,

end

-- 3ª demostración

example

(h : particion P)

: reflexive (relacion P) :=

begin

intro x,

rcases (h.1 x) with ⟨A, hAP, hxA, -⟩,

use A,

repeat { split } ; assumption,

end

-- 4ª demostración

example

(h : particion P)

: reflexive (relacion P) :=

begin

intro x,

rcases (h.1 x) with ⟨A, hAP, hxA, -⟩,

use [A, ⟨hAP, hxA, hxA⟩],

end

Se puede interactuar con la prueba anterior en esta sesión con Lean.

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="lean"> y otra con </pre>
[/expand]

[expand title=»Soluciones con Isabelle/HOL»]

theory Las_particiones_definen_relaciones_reflexivas
imports Main
begin

definition relacion :: "('a set) set ⇒ 'a ⇒ 'a ⇒ bool" where
  "relacion P x y ⟷ (∃A∈P. x ∈ A ∧ y ∈ A)"

definition particion :: "('a set) set ⇒ bool" where
  "particion P ⟷ (∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))) ∧ {} ∉ P"

ru(* 1ª demostración *)
lemma
  assumes "particion P"
  shows   "reflp (relacion P)"
proof (rule reflpI)
  fix x
  have "(∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))) ∧ {} ∉ P"
    using assms by (unfold particion_def)
  then have "∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))"
    by (rule conjunct1)
  then have "∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C)"
    by (rule allE)
  then obtain B where "B ∈ P ∧ (x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))"
    by (rule someI2_bex)
  then obtain B where "(B ∈ P ∧ x ∈ B) ∧ (∀C∈P. x ∈ C ⟶ B = C)"
    by (simp only: conj_assoc)
  then have "B ∈ P ∧ x ∈ B"
    by (rule conjunct1)
  then have "x ∈ B"
    by (rule conjunct2)
  then have "x ∈ B ∧ x ∈ B"
    using ‹x ∈ B› by (rule conjI)
  moreover have "B ∈ P"
    using ‹B ∈ P ∧ x ∈ B› by (rule conjunct1)
  ultimately have "∃B∈P. x ∈ B ∧ x ∈ B"
    by (rule bexI)
  then show "relacion P x x"
    by (unfold relacion_def)
qed

(* 2ª demostración *)
lemma
  assumes "particion P"
  shows   "reflp (relacion P)"
proof (rule reflpI)
  fix x
  obtain A where "A ∈ P ∧ x ∈ A"
    using assms particion_def
    by metis
  then show "relacion P x x"
    using relacion_def
    by metis
qed

(* 3ª demostración *)
lemma
  assumes "particion P"
  shows   "reflp (relacion P)"
  using assms particion_def relacion_def
  by (metis reflp_def)

end

theory Las_particiones_definen_relaciones_reflexivas

imports Main

begin

definition relacion :: "('a set) set ⇒ 'a ⇒ 'a ⇒ bool" where

"relacion P x y ⟷ (∃A∈P. x ∈ A ∧ y ∈ A)"

definition particion :: "('a set) set ⇒ bool" where

"particion P ⟷ (∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))) ∧ {} ∉ P"

ru(* 1ª demostración *)

lemma

assumes "particion P"

shows "reflp (relacion P)"

proof (rule reflpI)

fix x

have "(∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))) ∧ {} ∉ P"

using assms by (unfold particion_def)

then have "∀x. (∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))"

by (rule conjunct1)

then have "∃B∈P. x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C)"

by (rule allE)

then obtain B where "B ∈ P ∧ (x ∈ B ∧ (∀C∈P. x ∈ C ⟶ B = C))"

by (rule someI2_bex)

then obtain B where "(B ∈ P ∧ x ∈ B) ∧ (∀C∈P. x ∈ C ⟶ B = C)"

by (simp only: conj_assoc)

then have "B ∈ P ∧ x ∈ B"

by (rule conjunct1)

then have "x ∈ B"

by (rule conjunct2)

then have "x ∈ B ∧ x ∈ B"

using ‹x ∈ B› by (rule conjI)

moreover have "B ∈ P"

using ‹B ∈ P ∧ x ∈ B› by (rule conjunct1)

ultimately have "∃B∈P. x ∈ B ∧ x ∈ B"

by (rule bexI)

then show "relacion P x x"

by (unfold relacion_def)

qed

(* 2ª demostración *)

lemma

assumes "particion P"

shows "reflp (relacion P)"

proof (rule reflpI)

fix x

obtain A where "A ∈ P ∧ x ∈ A"

using assms particion_def

by metis

then show "relacion P x x"

using relacion_def

by metis

qed

(* 3ª demostración *)

lemma

assumes "particion P"

shows "reflp (relacion P)"

using assms particion_def relacion_def

by (metis reflp_def)

end

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="isar"> y otra con </pre>
[/expand]

Las clases de equivalencia de elementos no relacionados son disjuntas

PorJosé A. Alonso 23 agosto 202121 agosto 2021

Demostrar que las clases de equivalencia de elementos no relacionados son disjuntas.

Para ello, completar la siguiente teoría de Lean:

import tactic

variable  {X : Type}
variables {x y: X}
variable  {R : X → X → Prop}

def clase (R : X → X → Prop) (x : X) :=
  {y : X | R x y}

example
  (h : equivalence R)
  (hxy : ¬ R x y)
  : clase R x ∩ clase R y = ∅ :=
sorry

import tactic

variable {X : Type}

variables {x y: X}

variable {R : X → X → Prop}

def clase (R : X → X → Prop) (x : X) :=

{y : X | R x y}

example

(h : equivalence R)

(hxy : ¬ R x y)

: clase R x ∩ clase R y = ∅ :=

sorry

[expand title=»Soluciones con Lean»]

import tactic

variable  {X : Type}
variables {x y: X}
variable  {R : X → X → Prop}

def clase (R : X → X → Prop) (x : X) :=
  {y : X | R x y}

-- 1ª demostración
example
  (h : equivalence R)
  (hxy : ¬ R x y)
  : clase R x ∩ clase R y = ∅ :=
begin
  rcases h with ⟨hr, hs, ht⟩,
  by_contradiction h1,
  apply hxy,
  have h2 : ∃ z, z ∈ clase R x ∩ clase R y,
    { contrapose h1,
      intro h1a,
      apply h1a,
      push_neg at h1,
      exact set.eq_empty_iff_forall_not_mem.mpr h1, },
  rcases h2 with ⟨z, hxz, hyz⟩,
  replace hxz : R x z := hxz,
  replace hyz : R y z := hyz,
  have hzy : R z y := hs hyz,
  exact ht hxz hzy,
end

-- 2ª demostración
example
  (h : equivalence R)
  (hxy : ¬ R x y)
  : clase R x ∩ clase R y = ∅ :=
begin
  rcases h with ⟨hr, hs, ht⟩,
  by_contradiction h1,
  have h2 : ∃ z, z ∈ clase R x ∩ clase R y,
    { by finish [set.eq_empty_iff_forall_not_mem]},
  apply hxy,
  rcases h2 with ⟨z, hxz, hyz⟩,
  exact ht hxz (hs hyz),
end

import tactic

variable {X : Type}

variables {x y: X}

variable {R : X → X → Prop}

def clase (R : X → X → Prop) (x : X) :=

{y : X | R x y}

-- 1ª demostración

example

(h : equivalence R)

(hxy : ¬ R x y)

: clase R x ∩ clase R y = ∅ :=

begin

rcases h with ⟨hr, hs, ht⟩,

by_contradiction h1,

apply hxy,

have h2 : ∃ z, z ∈ clase R x ∩ clase R y,

{ contrapose h1,

intro h1a,

apply h1a,

push_neg at h1,

exact set.eq_empty_iff_forall_not_mem.mpr h1, },

rcases h2 with ⟨z, hxz, hyz⟩,

replace hxz : R x z := hxz,

replace hyz : R y z := hyz,

have hzy : R z y := hs hyz,

exact ht hxz hzy,

end

-- 2ª demostración

example

(h : equivalence R)

(hxy : ¬ R x y)

: clase R x ∩ clase R y = ∅ :=

begin

rcases h with ⟨hr, hs, ht⟩,

by_contradiction h1,

have h2 : ∃ z, z ∈ clase R x ∩ clase R y,

{ by finish [set.eq_empty_iff_forall_not_mem]},

apply hxy,

rcases h2 with ⟨z, hxz, hyz⟩,

exact ht hxz (hs hyz),

end

Se puede interactuar con la prueba anterior en esta sesión con Lean.

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="lean"> y otra con </pre>
[/expand]

[expand title=»Soluciones con Isabelle/HOL»]

theory Las_clases_de_equivalencia_de_elementos_no_relacionados_son_disjuntas
imports Main
begin

definition clase :: "('a ⇒ 'a ⇒ bool) ⇒ 'a ⇒ 'a set"
  where "clase R x = {y. R x y}"

(* 1ª demostración *)
lemma
  assumes "equivp R"
          "¬(R x y)"
  shows "clase R x ∩ clase R y = {}"
proof -
  have "∀z. z ∈ clase R x ⟶ z ∉ clase R y"
  proof (intro allI impI)
    fix z
    assume "z ∈ clase R x"
    then have "R x z"
      using clase_def by (metis CollectD)
    show "z ∉ clase R y"
    proof (rule notI)
      assume "z ∈ clase R y"
      then have "R y z"
        using clase_def by (metis CollectD)
      then have "R z y"
        using assms(1) by (simp only: equivp_symp)
      with ‹R x z› have "R x y"
        using assms(1) by (simp only: equivp_transp)
      with ‹¬R x y› show False
        by (rule notE)
    qed
  qed
  then show "clase R x ∩ clase R y = {}"
    by (simp only: disjoint_iff)
qed

(* 2ª demostración *)
lemma
  assumes "equivp R"
          "¬(R x y)"
  shows "clase R x ∩ clase R y = {}"
proof -
  have "∀z. z ∈ clase R x ⟶ z ∉ clase R y"
  proof (intro allI impI)
    fix z
    assume "z ∈ clase R x"
    then have "R x z"
      using clase_def by fastforce
    show "z ∉ clase R y"
    proof (rule notI)
      assume "z ∈ clase R y"
      then have "R y z"
        using clase_def by fastforce
      then have "R z y"
        using assms(1) by (simp only: equivp_symp)
      with ‹R x z› have "R x y"
        using assms(1) by (simp only: equivp_transp)
      with ‹¬R x y› show False
        by simp
    qed
  qed
  then show "clase R x ∩ clase R y = {}"
    by (simp only: disjoint_iff)
qed

(* 3ª demostración *)
lemma
  assumes "equivp R"
          "¬(R x y)"
  shows "clase R x ∩ clase R y = {}"
  using assms
  by (metis clase_def
            CollectD
            equivp_symp
            equivp_transp
            disjoint_iff)

(* 4ª demostración *)
lemma
  assumes "equivp R"
          "¬(R x y)"
  shows "clase R x ∩ clase R y = {}"
  using assms
  by (metis equivp_def
            clase_def
            CollectD
            disjoint_iff_not_equal)

end

theory Las_clases_de_equivalencia_de_elementos_no_relacionados_son_disjuntas

imports Main

begin

definition clase :: "('a ⇒ 'a ⇒ bool) ⇒ 'a ⇒ 'a set"

where "clase R x = {y. R x y}"

(* 1ª demostración *)

lemma

assumes "equivp R"

"¬(R x y)"

shows "clase R x ∩ clase R y = {}"

proof -

have "∀z. z ∈ clase R x ⟶ z ∉ clase R y"

proof (intro allI impI)

fix z

assume "z ∈ clase R x"

then have "R x z"

using clase_def by (metis CollectD)

show "z ∉ clase R y"

proof (rule notI)

assume "z ∈ clase R y"

then have "R y z"

using clase_def by (metis CollectD)

then have "R z y"

using assms(1) by (simp only: equivp_symp)

with ‹R x z› have "R x y"

using assms(1) by (simp only: equivp_transp)

with ‹¬R x y› show False

by (rule notE)

qed

then show "clase R x ∩ clase R y = {}"

by (simp only: disjoint_iff)

qed

(* 2ª demostración *)

lemma

assumes "equivp R"

"¬(R x y)"

shows "clase R x ∩ clase R y = {}"

proof -

have "∀z. z ∈ clase R x ⟶ z ∉ clase R y"

proof (intro allI impI)

fix z

assume "z ∈ clase R x"

then have "R x z"

using clase_def by fastforce

show "z ∉ clase R y"

proof (rule notI)

assume "z ∈ clase R y"

then have "R y z"

using clase_def by fastforce

then have "R z y"

using assms(1) by (simp only: equivp_symp)

with ‹R x z› have "R x y"

using assms(1) by (simp only: equivp_transp)

with ‹¬R x y› show False

by simp

qed

then show "clase R x ∩ clase R y = {}"

by (simp only: disjoint_iff)

qed

(* 3ª demostración *)

lemma

assumes "equivp R"

"¬(R x y)"

shows "clase R x ∩ clase R y = {}"

using assms

by (metis clase_def

CollectD

equivp_symp

equivp_transp

disjoint_iff)

(* 4ª demostración *)

lemma

assumes "equivp R"

"¬(R x y)"

shows "clase R x ∩ clase R y = {}"

using assms

by (metis equivp_def

clase_def

CollectD

disjoint_iff_not_equal)

end

En los comentarios se pueden escribir otras soluciones, escribiendo el código entre una línea con <pre lang="isar"> y otra con </pre>
[/expand]