internlm/Lean-Github huggingface dataset:
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
⊢ surj f
Tactic:
have : inj f' := by
  intro x y eq
  let x' : Fin (n + 1) := ⟨x.val, Nat.lt_trans x.isLt (Nat.lt_succ_self n)⟩
  let y' : Fin (n + 1) := ⟨y.val, Nat.lt_trans y.isLt (Nat.lt_succ_self n)⟩
  if hx : f x' < n then
    if hy : f y' < n then
      simp [f', hx, hy] at eq
      have := h _ _ (Fin.eq_of_val_eq eq)
      simp at this
      exact Fin.eq_of_val_eq this
    else
      simp [f', hx, hy] at eq
      have := h _ _ (Fin.eq_of_val_eq eq)
      simp at this
      exact absurd (this ▸ x.isLt) (Nat.lt_irrefl _)
  else
    if hy : f y' < n then
      simp [f', hx, hy] at eq
      have := h _ _ (Fin.eq_of_val_eq eq)
      simp at this
      exact absurd (this.symm ▸ y.isLt) (Nat.lt_irrefl _)
    else
      have eqx := Fin.eq_of_not_lt hx
      have eqy := Fin.eq_of_not_lt hy
      have : f x' = f y' := by rw [eqx, eqy]
      have : x' = y' := h _ _ this
      have : x.val = y.val := by
        have : x'.val = y'.val := by rw [this]
        exact this
      exact Fin.eq_of_val_eq this
Proof state after:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
⊢ surj f
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
⊢ surj f
Tactic:
have surj : surj f' := ih _ this
Proof state after:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
⊢ Regex.Data.SparseSet.Bijection.surj f
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
⊢ Regex.Data.SparseSet.Bijection.surj f
Tactic:
intro y
Proof state after:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
y : Fin (n + 1)
⊢ ∃ x, f x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
y : Fin (n + 1)
⊢ ∃ x, f x = y
Tactic:
have : y.val ≤ n := Nat.le_of_succ_le_succ y.isLt
Proof state after:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this✝ : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
y : Fin (n + 1)
this : ↑y ≤ n
⊢ ∃ x, f x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
case succ
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → Regex.Data.SparseSet.Bijection.surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
this✝ : inj f'
surj : Regex.Data.SparseSet.Bijection.surj f'
y : Fin (n + 1)
this : ↑y ≤ n
⊢ ∃ x, f x = y
Tactic:
if isLt : y.val < n then
  let ⟨x, eq⟩ := surj ⟨y.val, isLt⟩
  simp [f'] at eq
  split at eq
  case inl =>
    simp at eq
    exact ⟨⟨x.val, Nat.lt_trans x.isLt (Nat.lt_succ_self n)⟩, Fin.eq_of_val_eq eq⟩
  case inr =>
    simp at eq
    exact ⟨n', Fin.eq_of_val_eq eq⟩
else
  have := Fin.eq_of_not_lt isLt
  simp [this]
  if isLt' : f n' < n then
    let ⟨x, eq⟩ := surj ⟨(f n').val, isLt'⟩
    simp [f'] at eq
    split at eq
    case inl =>
      simp at eq
      have := Fin.val_eq_of_eq (h _ _ (Fin.eq_of_val_eq eq))
      simp at this
      exact absurd (this ▸ x.isLt) (Nat.lt_irrefl _)
    case inr nlt =>
      have := Fin.eq_of_not_lt nlt
      exact ⟨⟨x.val, Nat.lt_trans x.isLt (Nat.lt_succ_self n)⟩, this⟩
  else
    exact ⟨n', Fin.eq_of_not_lt isLt'⟩
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
⊢ f n' < n'
Tactic:
by_contra nlt
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
⊢ False
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
⊢ False
Tactic:
have eqn : f n' = n' := Fin.eq_of_not_lt nlt
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
⊢ False
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
⊢ False
Tactic:
have : f x' = f n' := by rw [eqx, eqn]
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this : f x' = f n'
⊢ False
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this : f x' = f n'
⊢ False
Tactic:
have : x' = n' := h _ _ this
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝ : f x' = f n'
this : x' = n'
⊢ False
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝ : f x' = f n'
this : x' = n'
⊢ False
Tactic:
have : x.val = n := by
  have : x'.val = n'.val := by rw [this]
  exact this
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝¹ : f x' = f n'
this✝ : x' = n'
this : ↑x = n
⊢ False
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝¹ : f x' = f n'
this✝ : x' = n'
this : ↑x = n
⊢ False
Tactic:
exact Nat.lt_irrefl _ (this ▸ x.isLt)
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
⊢ f x' = f n'
Tactic:
rw [eqx, eqn]
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝ : f x' = f n'
this : x' = n'
⊢ ↑x = n
Tactic:
have : x'.val = n'.val := by rw [this]
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝¹ : f x' = f n'
this✝ : x' = n'
this : ↑x' = ↑n'
⊢ ↑x = n
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝¹ : f x' = f n'
this✝ : x' = n'
this : ↑x' = ↑n'
⊢ ↑x = n
Tactic:
exact this
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
x : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y : Fin (n + 1) := f x'
isLt : ¬↑y < n
eqx : f x' = n'
nlt : ¬f n' < n'
eqn : f n' = n'
this✝ : f x' = f n'
this : x' = n'
⊢ ↑x' = ↑n'
Tactic:
rw [this]
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
⊢ inj f'
Tactic:
intro x y eq
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
⊢ x = y
Tactic:
let x' : Fin (n + 1) := ⟨x.val, Nat.lt_trans x.isLt (Nat.lt_succ_self n)⟩
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
⊢ x = y
Tactic:
let y' : Fin (n + 1) := ⟨y.val, Nat.lt_trans y.isLt (Nat.lt_succ_self n)⟩
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
⊢ x = y
Tactic:
if hx : f x' < n then
  if hy : f y' < n then
    simp [f', hx, hy] at eq
    have := h _ _ (Fin.eq_of_val_eq eq)
    simp at this
    exact Fin.eq_of_val_eq this
  else
    simp [f', hx, hy] at eq
    have := h _ _ (Fin.eq_of_val_eq eq)
    simp at this
    exact absurd (this ▸ x.isLt) (Nat.lt_irrefl _)
else
  if hy : f y' < n then
    simp [f', hx, hy] at eq
    have := h _ _ (Fin.eq_of_val_eq eq)
    simp at this
    exact absurd (this.symm ▸ y.isLt) (Nat.lt_irrefl _)
  else
    have eqx := Fin.eq_of_not_lt hx
    have eqy := Fin.eq_of_not_lt hy
    have : f x' = f y' := by rw [eqx, eqy]
    have : x' = y' := h _ _ this
    have : x.val = y.val := by
      have : x'.val = y'.val := by rw [this]
      exact this
    exact Fin.eq_of_val_eq this
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
⊢ x = y
Tactic:
if hy : f y' < n then
  simp [f', hx, hy] at eq
  have := h _ _ (Fin.eq_of_val_eq eq)
  simp at this
  exact Fin.eq_of_val_eq this
else
  simp [f', hx, hy] at eq
  have := h _ _ (Fin.eq_of_val_eq eq)
  simp at this
  exact absurd (this ▸ x.isLt) (Nat.lt_irrefl _)
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
⊢ x = y
Tactic:
simp [f', hx, hy] at eq
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
⊢ x = y
Tactic:
have := h _ _ (Fin.eq_of_val_eq eq)
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
this : ⟨↑x, ⋯⟩ = ⟨↑y, ⋯⟩
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
this : ⟨↑x, ⋯⟩ = ⟨↑y, ⋯⟩
⊢ x = y
Tactic:
simp at this
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
this : ↑x = ↑y
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨↑y, ⋯⟩)
this : ↑x = ↑y
⊢ x = y
Tactic:
exact Fin.eq_of_val_eq this
Proof state after:
no goals
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
eq : f' x = f' y
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
⊢ x = y
Tactic:
simp [f', hx, hy] at eq
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
⊢ x = y
Tactic:
have := h _ _ (Fin.eq_of_val_eq eq)
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
this : ⟨↑x, ⋯⟩ = ⟨n, ⋯⟩
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
this : ⟨↑x, ⋯⟩ = ⟨n, ⋯⟩
⊢ x = y
Tactic:
simp at this
Proof state after:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
this : ↑x = n
⊢ x = y
Theorem: Regex.Data.SparseSet.Bijection.surj_of_inj
Proof state before:
n : Nat
ih : ∀ (f : Fin n → Fin n), inj f → surj f
f : Fin (n + 1) → Fin (n + 1)
h : inj f
n' : Fin (n + 1) := ⟨n, ⋯⟩
f' : Fin n → Fin n :=
  fun x =>
    let x' := ⟨↑x, ⋯⟩;
    let y := f x';
    if isLt : ↑y < n then ⟨↑y, isLt⟩
    else
      let_fun eqx := ⋯;
      let_fun isLt := ⋯;
      ⟨↑(f ⟨n, ⋯⟩), isLt⟩
x y : Fin n
x' : Fin (n + 1) := ⟨↑x, ⋯⟩
y' : Fin (n + 1) := ⟨↑y, ⋯⟩
hx : ↑(f x') < n
hy : ¬↑(f y') < n
eq : ↑(f ⟨↑x, ⋯⟩) = ↑(f ⟨n, ⋯⟩)
this : ↑x = n
⊢ x = y
Tactic:
exact absurd (this ▸ x.isLt) (Nat.lt_irrefl _)
Proof state after:
no goals