Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 119 lines (92 sloc) 3.465 kB
ca887d4 Move everything everywhere
Guillaume Brunerie authored
1 {-# OPTIONS --without-K #-}
2
3 open import Base
4
5 module Integers where
6
7 succ :
8 succ O = pos O
9 succ (pos n) = pos (S n)
10 succ (neg O) = O
11 succ (neg (S n)) = neg n
12
13 pred :
14 pred O = neg O
15 pred (pos O) = O
16 pred (pos (S n)) = pos n
17 pred (neg n) = neg (S n)
18
19 abstract
20 succ-pred : (t : ℤ) succ (pred t) ≡ t
21 succ-pred O = refl O
22 succ-pred (pos O) = refl (pos O)
23 succ-pred (pos (S y)) = refl (pos (S y))
24 succ-pred (neg y) = refl (neg y)
25
26 pred-succ : (t : ℤ) pred (succ t) ≡ t
27 pred-succ O = refl O
28 pred-succ (pos y) = refl (pos y)
29 pred-succ (neg O) = refl (neg O)
30 pred-succ (neg (S y)) = refl (neg (S y))
31
32 succ-is-equiv : is-equiv succ
33 succ-is-equiv = iso-is-eq succ pred succ-pred pred-succ
34
35 succ-equiv : ℤ ≃ ℤ
36 succ-equiv = (succ , succ-is-equiv)
37
38 -- Equality on ℕ and ℤ is decidable and both are sets
39
40 private
41 ℕ-get-S :
42 ℕ-get-S 0 = 42
43 ℕ-get-S (S n) = n
44
45 S-injective : (n m : ℕ) (p : S n ≡ S m) n ≡ m
46 S-injective n m p = map ℕ-get-S p
47
48 ℕ-Sn≢O-type : Set
49 ℕ-Sn≢O-type O =
50 ℕ-Sn≢O-type (S n) = unit
51
52 ℕ-Sn≢O : (n : ℕ) (S n ≢ O)
53 ℕ-Sn≢O n p = transport ℕ-Sn≢O-type p tt
54
55 ℕ-dec-eq : dec-eq ℕ
56 ℕ-dec-eq O O = inl (refl O)
57 ℕ-dec-eq O (S n) = inr (λ p ℕ-Sn≢O n (! p))
58 ℕ-dec-eq (S n) O = inr (ℕ-Sn≢O n)
59 ℕ-dec-eq (S n) (S m) with ℕ-dec-eq n m
60 ℕ-dec-eq (S n) (S m) | inl p = inl (map S p)
61 ℕ-dec-eq (S n) (S m) | inr p⊥ = inr (λ p p⊥ (S-injective n m p))
62
63 ℕ-is-set : is-set ℕ
64 ℕ-is-set = dec-eq-is-set ℕ ℕ-dec-eq
65
66 private
67 ℤ-get-pos :
68 ℤ-get-pos O = 0
69 ℤ-get-pos (pos n) = n
70 ℤ-get-pos (neg n) = 0
71
72 pos-injective : (n m : ℕ) (p : pos n ≡ pos m) n ≡ m
73 pos-injective n m p = map ℤ-get-pos p
74
75 ℤ-get-neg :
76 ℤ-get-neg O = 0
77 ℤ-get-neg (pos n) = 0
78 ℤ-get-neg (neg n) = n
79
80 neg-injective : (n m : ℕ) (p : neg n ≡ neg m) n ≡ m
81 neg-injective n m p = map ℤ-get-neg p
82
83 ℤ-neg≢O≢pos-type : Set
84 ℤ-neg≢O≢pos-type O = unit
85 ℤ-neg≢O≢pos-type (pos n) =
86 ℤ-neg≢O≢pos-type (neg n) =
87
88 ℤ-O≢pos : (n : ℕ) (O ≡ pos n ⊥)
89 ℤ-O≢pos n p = transport ℤ-neg≢O≢pos-type p tt
90
91 ℤ-O≢neg : (n : ℕ) (O ≡ neg n ⊥)
92 ℤ-O≢neg n p = transport ℤ-neg≢O≢pos-type p tt
93
94 ℤ-neg≢pos-type : Set
95 ℤ-neg≢pos-type O = unit
96 ℤ-neg≢pos-type (pos n) =
97 ℤ-neg≢pos-type (neg n) = unit
98
99 ℤ-neg≢pos : (n m : ℕ) (neg n ≡ pos m ⊥)
100 ℤ-neg≢pos n m p = transport ℤ-neg≢pos-type p tt
101
102 ℤ-dec-eq : dec-eq ℤ
103 ℤ-dec-eq O O = inl (refl O)
104 ℤ-dec-eq O (pos n) = inr (ℤ-O≢pos n)
105 ℤ-dec-eq O (neg n) = inr (ℤ-O≢neg n)
106 ℤ-dec-eq (pos n) O = inr (λ p ℤ-O≢pos n (! p))
107 ℤ-dec-eq (pos n) (pos m) with ℕ-dec-eq n m
108 ℤ-dec-eq (pos n) (pos m) | inl p = inl (map pos p)
109 ℤ-dec-eq (pos n) (pos m) | inr p⊥ = inr (λ p p⊥ (pos-injective n m p))
110 ℤ-dec-eq (pos n) (neg m) = inr (λ p ℤ-neg≢pos m n (! p))
111 ℤ-dec-eq (neg n) O = inr (λ p ℤ-O≢neg n (! p))
112 ℤ-dec-eq (neg n) (pos m) = inr (ℤ-neg≢pos n m)
113 ℤ-dec-eq (neg n) (neg m) with ℕ-dec-eq n m
114 ℤ-dec-eq (neg n) (neg m) | inl p = inl (map neg p)
115 ℤ-dec-eq (neg n) (neg m) | inr p⊥ = inr (λ p p⊥ (neg-injective n m p))
116
117 ℤ-is-set : is-set ℤ
118 ℤ-is-set = dec-eq-is-set ℤ ℤ-dec-eq
Something went wrong with that request. Please try again.