A finite set with a fixed-point-free involution has even cardinality
Lax712553.Involution · concepts/Lax712553/Involution.lean · lax-712553
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let be a finite set and a map with and for every , and which sends into itself. Then the elements of come in pairs , so has an even number of elements. This is the elementary counting principle behind parity arguments of the kind "the number of representations is even because negating one coordinate is a fixed-point-free involution".
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Mathlib.Data.Finset.Card |
| 2 | import Mathlib.Algebra.Group.Even |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: A finite set with a fixed-point-free involution has even cardinality |
| 7 | type: theorem |
| 8 | --- |
| 9 | Let `S` be a finite set and `f` a map with `f (f x) = x` and `f x ≠ x` for every |
| 10 | `x ∈ S`, and which sends `S` into itself. Then the elements of `S` come in pairs |
| 11 | `{x, f x}`, so `S` has an even number of elements. This is the elementary counting |
| 12 | principle behind parity arguments of the kind "the number of representations is |
| 13 | even because negating one coordinate is a fixed-point-free involution". |
| 14 | -/ |
| 15 | |
| 16 | namespace Lax712553.Involution |
| 17 | |
| 18 | /-- A finite set carrying a fixed-point-free involution has even cardinality. -/ |
| 19 | axiom even_card_of_fixedPointFree_involution {α : Type*} [DecidableEq α] |
| 20 | (S : Finset α) (f : α → α) (hmaps : ∀ x ∈ S, f x ∈ S) (hinv : ∀ x ∈ S, f (f x) = x) |
| 21 | (hfree : ∀ x ∈ S, f x ≠ x) : Even S.card |
| 22 | |
| 23 | end Lax712553.Involution |
| 24 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments