mathlib3 documentation

data.nat.pairing

Naturals pairing function #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

This file defines a pairing function for the naturals as follows:

 0  1  4  9 16
 2  3  5 10 17
 6  7  8 11 18
12 13 14 15 19
20 21 22 23 24

It has the advantage of being monotone in both directions and sending ⟦0, n^2 - 1⟧ to ⟦0, n - 1⟧².

def nat.mkpair (a b : ) :

Pairing function for the natural numbers.

Equations
def nat.unpair (n : ) :

Unpairing function for the natural numbers.

Equations
@[simp]
theorem nat.mkpair_unpair' {n a b : } (H : nat.unpair n = (a, b)) :
@[simp]
theorem nat.unpair_mkpair (a b : ) :
nat.unpair (nat.mkpair a b) = (a, b)

An equivalence between ℕ × ℕ and .

Equations
@[simp]
theorem nat.mkpair_eq_mkpair {a b c d : } :
nat.mkpair a b = nat.mkpair c d a = c b = d
theorem nat.unpair_lt {n : } (n1 : 1 n) :
@[simp]
theorem nat.unpair_zero  :
theorem nat.unpair_left_le (n : ) :
theorem nat.left_le_mkpair (a b : ) :
theorem nat.right_le_mkpair (a b : ) :
theorem nat.unpair_right_le (n : ) :
theorem nat.mkpair_lt_mkpair_left {a₁ a₂ : } (b : ) (h : a₁ < a₂) :
nat.mkpair a₁ b < nat.mkpair a₂ b
theorem nat.mkpair_lt_mkpair_right (a : ) {b₁ b₂ : } (h : b₁ < b₂) :
nat.mkpair a b₁ < nat.mkpair a b₂
theorem nat.add_le_mkpair (m n : ) :
m + n nat.mkpair m n
theorem supr_unpair {α : Type u_1} [complete_lattice α] (f : α) :
( (n : ), f (nat.unpair n).fst (nat.unpair n).snd) = (i j : ), f i j
theorem infi_unpair {α : Type u_1} [complete_lattice α] (f : α) :
( (n : ), f (nat.unpair n).fst (nat.unpair n).snd) = (i j : ), f i j
theorem set.Union_unpair_prod {α : Type u_1} {β : Type u_2} {s : set α} {t : set β} :
( (n : ), s (nat.unpair n).fst ×ˢ t (nat.unpair n).snd) = ( (n : ), s n) ×ˢ (n : ), t n
theorem set.Union_unpair {α : Type u_1} (f : set α) :
( (n : ), f (nat.unpair n).fst (nat.unpair n).snd) = (i j : ), f i j
theorem set.Inter_unpair {α : Type u_1} (f : set α) :
( (n : ), f (nat.unpair n).fst (nat.unpair n).snd) = (i j : ), f i j