-
Notifications
You must be signed in to change notification settings - Fork 265
/
Synonym.lean
178 lines (126 loc) · 4.99 KB
/
Synonym.lean
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
/-
Copyright (c) 2020 Johan Commelin, Damiano Testa. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Johan Commelin, Damiano Testa, Yaël Dillies
-/
import Mathlib.Logic.Equiv.Defs
import Mathlib.Logic.Nontrivial.Defs
import Mathlib.Order.Basic
/-!
# Type synonyms
This file provides two type synonyms for order theory:
* `OrderDual α`: Type synonym of `α` to equip it with the dual order (`a ≤ b` becomes `b ≤ a`).
* `Lex α`: Type synonym of `α` to equip it with its lexicographic order. The precise meaning depends
on the type we take the lex of. Examples include `Prod`, `Sigma`, `List`, `Finset`.
## Notation
`αᵒᵈ` is notation for `OrderDual α`.
The general rule for notation of `Lex` types is to append `ₗ` to the usual notation.
## Implementation notes
One should not abuse definitional equality between `α` and `αᵒᵈ`/`Lex α`. Instead, explicit
coercions should be inserted:
* `OrderDual`: `OrderDual.toDual : α → αᵒᵈ` and `OrderDual.ofDual : αᵒᵈ → α`
* `Lex`: `toLex : α → Lex α` and `ofLex : Lex α → α`.
## See also
This file is similar to `Algebra.Group.TypeTags`.
-/
variable {α β γ : Type*}
/-! ### Order dual -/
namespace OrderDual
instance [h : Nontrivial α] : Nontrivial αᵒᵈ :=
h
/-- `toDual` is the identity function to the `OrderDual` of a linear order. -/
def toDual : α ≃ αᵒᵈ :=
Equiv.refl _
/-- `ofDual` is the identity function from the `OrderDual` of a linear order. -/
def ofDual : αᵒᵈ ≃ α :=
Equiv.refl _
@[simp]
theorem toDual_symm_eq : (@toDual α).symm = ofDual := rfl
@[simp]
theorem ofDual_symm_eq : (@ofDual α).symm = toDual := rfl
@[simp]
theorem toDual_ofDual (a : αᵒᵈ) : toDual (ofDual a) = a :=
rfl
@[simp]
theorem ofDual_toDual (a : α) : ofDual (toDual a) = a :=
rfl
-- Porting note:
-- removed @[simp] since this already follows by `simp only [EmbeddingLike.apply_eq_iff_eq]`
theorem toDual_inj {a b : α} : toDual a = toDual b ↔ a = b :=
Iff.rfl
-- Porting note:
-- removed @[simp] since this already follows by `simp only [EmbeddingLike.apply_eq_iff_eq]`
theorem ofDual_inj {a b : αᵒᵈ} : ofDual a = ofDual b ↔ a = b :=
Iff.rfl
@[simp]
theorem toDual_le_toDual [LE α] {a b : α} : toDual a ≤ toDual b ↔ b ≤ a :=
Iff.rfl
@[simp]
theorem toDual_lt_toDual [LT α] {a b : α} : toDual a < toDual b ↔ b < a :=
Iff.rfl
@[simp]
theorem ofDual_le_ofDual [LE α] {a b : αᵒᵈ} : ofDual a ≤ ofDual b ↔ b ≤ a :=
Iff.rfl
@[simp]
theorem ofDual_lt_ofDual [LT α] {a b : αᵒᵈ} : ofDual a < ofDual b ↔ b < a :=
Iff.rfl
theorem le_toDual [LE α] {a : αᵒᵈ} {b : α} : a ≤ toDual b ↔ b ≤ ofDual a :=
Iff.rfl
theorem lt_toDual [LT α] {a : αᵒᵈ} {b : α} : a < toDual b ↔ b < ofDual a :=
Iff.rfl
theorem toDual_le [LE α] {a : α} {b : αᵒᵈ} : toDual a ≤ b ↔ ofDual b ≤ a :=
Iff.rfl
theorem toDual_lt [LT α] {a : α} {b : αᵒᵈ} : toDual a < b ↔ ofDual b < a :=
Iff.rfl
/-- Recursor for `αᵒᵈ`. -/
@[elab_as_elim]
protected def rec {C : αᵒᵈ → Sort*} (h₂ : ∀ a : α, C (toDual a)) : ∀ a : αᵒᵈ, C a :=
h₂
@[simp]
protected theorem «forall» {p : αᵒᵈ → Prop} : (∀ a, p a) ↔ ∀ a, p (toDual a) :=
Iff.rfl
@[simp]
protected theorem «exists» {p : αᵒᵈ → Prop} : (∃ a, p a) ↔ ∃ a, p (toDual a) :=
Iff.rfl
alias ⟨_, _root_.LE.le.dual⟩ := toDual_le_toDual
alias ⟨_, _root_.LT.lt.dual⟩ := toDual_lt_toDual
alias ⟨_, _root_.LE.le.ofDual⟩ := ofDual_le_ofDual
alias ⟨_, _root_.LT.lt.ofDual⟩ := ofDual_lt_ofDual
end OrderDual
/-! ### Lexicographic order -/
/-- A type synonym to equip a type with its lexicographic order. -/
def Lex (α : Type*) :=
α
/-- `toLex` is the identity function to the `Lex` of a type. -/
@[match_pattern]
def toLex : α ≃ Lex α :=
Equiv.refl _
/-- `ofLex` is the identity function from the `Lex` of a type. -/
@[match_pattern]
def ofLex : Lex α ≃ α :=
Equiv.refl _
@[simp]
theorem toLex_symm_eq : (@toLex α).symm = ofLex :=
rfl
@[simp]
theorem ofLex_symm_eq : (@ofLex α).symm = toLex :=
rfl
@[simp]
theorem toLex_ofLex (a : Lex α) : toLex (ofLex a) = a :=
rfl
@[simp]
theorem ofLex_toLex (a : α) : ofLex (toLex a) = a :=
rfl
-- Porting note:
-- removed @[simp] since this already follows by `simp only [EmbeddingLike.apply_eq_iff_eq]`
theorem toLex_inj {a b : α} : toLex a = toLex b ↔ a = b :=
Iff.rfl
-- Porting note:
-- removed @[simp] since this already follows by `simp only [EmbeddingLike.apply_eq_iff_eq]`
theorem ofLex_inj {a b : Lex α} : ofLex a = ofLex b ↔ a = b :=
Iff.rfl
/-- A recursor for `Lex`. Use as `induction x`. -/
@[elab_as_elim, induction_eliminator, cases_eliminator]
protected def Lex.rec {β : Lex α → Sort*} (h : ∀ a, β (toLex a)) : ∀ a, β a := fun a => h (ofLex a)
@[simp] lemma Lex.forall {p : Lex α → Prop} : (∀ a, p a) ↔ ∀ a, p (toLex a) := Iff.rfl
@[simp] lemma Lex.exists {p : Lex α → Prop} : (∃ a, p a) ↔ ∃ a, p (toLex a) := Iff.rfl