---

Step * of Lemma general-pigeon-hole

∀[n,m,k:ℕ]. ∀[f:ℕn ⟶ ℕm].
  n ≤ (k * m) supposing ∀L:ℕn List. (no_repeats(ℕn;L) ⇒ (∃i:ℕm. (∀x∈L.f[x] = i ∈ ℕm)) ⇒ (||L|| ≤ k))
BY
{ (((Auto THEN InstLemma `finite-partition` [⌜n⌝;⌜m⌝;⌜f⌝]) THENA Auto)
   THEN ExRepD
   THEN Assert ⌜Σ(||p j|| | j < m) ≤ (k * m)⌝⋅
   THEN Auto
   THEN BLemma `sum_bound`
   THEN Auto) }

1
1. n : ℕ
2. m : ℕ
3. k : ℕ
4. f : ℕn ⟶ ℕm
5. ∀L:ℕn List. (no_repeats(ℕn;L) ⇒ (∃i:ℕm. (∀x∈L.f[x] = i ∈ ℕm)) ⇒ (||L|| ≤ k))
6. p : ℕm ⟶ (ℕ List)
7. Σ(||p j|| | j < m) = n ∈ ℤ
8. ∀j:ℕm. ∀x,y:ℕ||p j||.  p j[x] > p j[y] supposing x < y
9. ∀j:ℕm. ∀x:ℕ||p j||.  (p j[x] < n c∧ ((f p j[x]) = j ∈ ℤ))
10. j : ℕm
⊢ ||p j|| ≤ k

---

Latex:

---

Latex:
\mforall{}[n,m,k:\mBbbN{}].  \mforall{}[f:\mBbbN{}n  {}\mrightarrow{}  \mBbbN{}m].
    n  \mleq{}  (k  *  m)  supposing  \mforall{}L:\mBbbN{}n  List.  (no\_repeats(\mBbbN{}n;L)  {}\mRightarrow{}  (\mexists{}i:\mBbbN{}m.  (\mforall{}x\mmember{}L.f[x]  =  i))  {}\mRightarrow{}  (||L||  \mleq{}  k))


By

---

Latex:
(((Auto  THEN  InstLemma  `finite-partition`  [\mkleeneopen{}n\mkleeneclose{};\mkleeneopen{}m\mkleeneclose{};\mkleeneopen{}f\mkleeneclose{}])  THENA  Auto)
  THEN  ExRepD
  THEN  Assert  \mkleeneopen{}\mSigma{}(||p  j||  |  j  <  m)  \mleq{}  (k  *  m)\mkleeneclose{}\mcdot{}
  THEN  Auto
  THEN  BLemma  `sum\_bound`
  THEN  Auto)

---

Home Index