Natural numbers with infinity #
The natural numbers and an extra top element ⊤. This implementation uses Part ℕ as an
implementation. Use ℕ∞ instead unless you care about computability.
Main definitions #
The following instances are defined:
There is no additive analogue of MonoidWithZero; if there were then PartENat could
be an AddMonoidWithTop.
-
toWithTop: the map fromPartENattoℕ∞, with theorems that it plays well with+and≤. -
withTopAddEquiv : PartENat ≃+ ℕ∞ -
withTopOrderIso : PartENat ≃o ℕ∞
Implementation details #
PartENat is defined to be Part ℕ.
+ and ≤ are defined on PartENat, but there is an issue with * because it's not
clear what 0 * ⊤ should be. mul is hence left undefined. Similarly ⊤ - ⊤ is ambiguous
so there is no - defined on PartENat.
Before the open Classical line, various proofs are made with decidability assumptions.
This can cause issues -- see for example the non-simp lemma toWithTopZero proved by rfl,
followed by @[simp] lemma toWithTopZero' whose proof uses convert.
Tags #
PartENat, ℕ∞
The computable embedding ℕ → PartENat.
This coincides with the coercion coe : ℕ → PartENat, see PartENat.some_eq_natCast.
Equations
- PartENat.some = Part.some
Instances For
Equations
- PartENat.instZeroPartENat = { zero := ↑0 }
Equations
- PartENat.instInhabitedPartENat = { default := 0 }
Equations
- PartENat.instOnePartENat = { one := ↑1 }
Equations
Equations
- PartENat.instAddCommMonoidWithOnePartENat = let src := PartENat.addCommMonoid; AddCommMonoidWithOne.mk (_ : ∀ (a b : PartENat), a + b = b + a)
Alias of Nat.cast_inj specialized to PartENat -
Equations
- PartENat.instLEPartENat = { le := fun (x y : PartENat) => ∃ (h : y.Dom → x.Dom), ∀ (hy : y.Dom), x.get (_ : x.Dom) ≤ y.get hy }
Equations
- PartENat.instTopPartENat = { top := Part.none }
Equations
- PartENat.instBotPartENat = { bot := 0 }
Equations
Alias of Nat.cast_le specialized to PartENat -
Alias of Nat.cast_lt specialized to PartENat -
Equations
- One or more equations did not get rendered due to their size.
Equations
- PartENat.boundedOrder = let src := PartENat.orderTop; let src_1 := PartENat.orderBot; BoundedOrder.mk
Equations
- One or more equations did not get rendered due to their size.
Equations
- One or more equations did not get rendered due to their size.
Equations
- PartENat.instCoeENatPartENat = { coe := PartENat.ofENat }
Equiv between PartENat and ℕ∞ (for the order isomorphism see
withTopOrderIso).
Equations
- One or more equations did not get rendered due to their size.
Instances For
to_WithTop induces an order isomorphism between PartENat and ℕ∞.
Equations
- PartENat.withTopOrderIso = let src := PartENat.withTopEquiv; { toEquiv := src, map_rel_iff' := (_ : ∀ (x x_1 : PartENat), PartENat.withTopEquiv x ≤ PartENat.withTopEquiv x_1 ↔ x ≤ x_1) }
Instances For
toWithTop induces an additive monoid isomorphism between PartENat and ℕ∞.
Equations
- PartENat.withTopAddEquiv = let src := PartENat.withTopEquiv; { toEquiv := src, map_add' := PartENat.withTopAddEquiv.proof_1 }
Instances For
Equations
- PartENat.instWellFoundedLTPartENatToLTToPreorderPartialOrder = (_ : IsWellFounded PartENat fun (x x_1 : PartENat) => x < x_1)
Equations
- PartENat.isWellOrder = (_ : IsWellOrder PartENat fun (x x_1 : PartENat) => x < x_1)
Equations
- PartENat.wellFoundedRelation = { rel := fun (x x_1 : PartENat) => x < x_1, wf := PartENat.lt_wf }
The smallest PartENat satisfying a (decidable) predicate P : ℕ → Prop
Equations
- PartENat.find P = { Dom := ∃ (n : ℕ), P n, get := Nat.find }
Instances For
Equations
- One or more equations did not get rendered due to their size.
Equations
- One or more equations did not get rendered due to their size.