algebraeon_sets/structure/
morphism.rs

1use itertools::Itertools;
2
3use super::*;
4use std::fmt::Debug;
5use std::marker::PhantomData;
6
7pub trait Morphism<Domain: Structure, Range: Structure>: Debug + Clone {
8    fn domain(&self) -> &Domain;
9    fn range(&self) -> &Range;
10}
11
12pub trait Function<Domain: SetStructure, Range: SetStructure>: Morphism<Domain, Range> {
13    fn image(&self, x: &Domain::Set) -> Range::Set;
14}
15
16pub trait InjectiveFunction<Domain: SetStructure, Range: SetStructure>:
17    Function<Domain, Range>
18{
19    fn try_preimage(&self, x: &Range::Set) -> Option<Domain::Set>;
20}
21
22pub trait BijectiveFunction<Domain: SetStructure, Range: SetStructure>:
23    InjectiveFunction<Domain, Range>
24{
25    fn preimage(&self, x: &Range::Set) -> Domain::Set {
26        self.try_preimage(x).unwrap()
27    }
28}
29
30/// The identity morphism X -> X
31#[derive(Debug, Clone, PartialEq, Eq)]
32pub struct IdentityMorphism<X: Structure> {
33    x: X,
34}
35
36impl<X: Structure> IdentityMorphism<X> {
37    pub fn new(x: X) -> Self {
38        Self { x }
39    }
40}
41
42impl<X: Structure> Morphism<X, X> for IdentityMorphism<X> {
43    fn domain(&self) -> &X {
44        &self.x
45    }
46
47    fn range(&self) -> &X {
48        &self.x
49    }
50}
51
52impl<X: SetStructure> Function<X, X> for IdentityMorphism<X> {
53    fn image(&self, x: &X::Set) -> X::Set {
54        x.clone()
55    }
56}
57
58impl<X: SetStructure> InjectiveFunction<X, X> for IdentityMorphism<X> {
59    fn try_preimage(&self, x: &X::Set) -> Option<X::Set> {
60        Some(x.clone())
61    }
62}
63
64impl<X: SetStructure> BijectiveFunction<X, X> for IdentityMorphism<X> {}
65
66/// The composition A -> B -> C of two morphisms A -> B and B -> C
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub struct CompositionMorphism<
69    A: Structure,
70    B: Structure,
71    C: Structure,
72    AB: Morphism<A, B>,
73    BC: Morphism<B, C>,
74> {
75    a: PhantomData<A>,
76    b: PhantomData<B>,
77    c: PhantomData<C>,
78    // required to satisfy ab.range() == bc.domain()
79    a_to_b: AB,
80    b_to_c: BC,
81}
82
83impl<A: Structure, B: Structure, C: Structure, AB: Morphism<A, B>, BC: Morphism<B, C>>
84    CompositionMorphism<A, B, C, AB, BC>
85{
86    pub fn new(a_to_b: AB, b_to_c: BC) -> Self {
87        assert_eq!(a_to_b.range(), b_to_c.domain());
88        Self {
89            a: PhantomData,
90            b: PhantomData,
91            c: PhantomData,
92            a_to_b,
93            b_to_c,
94        }
95    }
96
97    pub fn a(&self) -> &A {
98        self.a_to_b.domain()
99    }
100
101    pub fn b(&self) -> &B {
102        let b = self.a_to_b.range();
103        debug_assert_eq!(b, self.b_to_c.domain());
104        b
105    }
106
107    pub fn c(&self) -> &C {
108        self.b_to_c.range()
109    }
110
111    pub fn a_to_b(&self) -> &AB {
112        &self.a_to_b
113    }
114
115    pub fn b_to_c(&self) -> &BC {
116        &self.b_to_c
117    }
118}
119
120impl<A: Structure, B: Structure, C: Structure, AB: Morphism<A, B>, BC: Morphism<B, C>>
121    Morphism<A, C> for CompositionMorphism<A, B, C, AB, BC>
122{
123    fn domain(&self) -> &A {
124        self.a()
125    }
126
127    fn range(&self) -> &C {
128        self.c()
129    }
130}
131
132impl<A: SetStructure, B: SetStructure, C: SetStructure, AB: Function<A, B>, BC: Function<B, C>>
133    Function<A, C> for CompositionMorphism<A, B, C, AB, BC>
134{
135    fn image(&self, x: &A::Set) -> C::Set {
136        self.b_to_c.image(&self.a_to_b.image(x))
137    }
138}
139
140impl<
141    A: SetStructure,
142    B: SetStructure,
143    C: SetStructure,
144    AB: InjectiveFunction<A, B>,
145    BC: InjectiveFunction<B, C>,
146> InjectiveFunction<A, C> for CompositionMorphism<A, B, C, AB, BC>
147{
148    fn try_preimage(&self, x: &C::Set) -> Option<A::Set> {
149        self.a_to_b.try_preimage(&self.b_to_c.try_preimage(x)?)
150    }
151}
152
153impl<
154    A: SetStructure,
155    B: SetStructure,
156    C: SetStructure,
157    AB: BijectiveFunction<A, B>,
158    BC: BijectiveFunction<B, C>,
159> BijectiveFunction<A, C> for CompositionMorphism<A, B, C, AB, BC>
160{
161    fn preimage(&self, x: &C::Set) -> A::Set {
162        self.a_to_b.preimage(&self.b_to_c.preimage(x))
163    }
164}
165
166pub trait MorphismsStructure<Domain: Structure, Range: Structure>: SetStructure
167where
168    Self::Set: Morphism<Domain, Range>,
169{
170}
171
172/// Represent all functions from `domain` to `range`
173#[derive(Debug, Clone, PartialEq, Eq)]
174pub struct Functions<Domain: SetStructure, Range: SetStructure> {
175    domain: Domain,
176    range: Range,
177}
178
179impl<Domain: SetStructure, Range: SetStructure> Functions<Domain, Range> {
180    pub fn new(domain: Domain, range: Range) -> Self {
181        Self { domain, range }
182    }
183}
184
185impl<Domain: SetStructure, Range: SetStructure> Structure for Functions<Domain, Range> {}
186
187impl<Domain: FiniteSetStructure, Range: EqStructure> SetStructure for Functions<Domain, Range> {
188    type Set = Vec<Range::Set>;
189
190    fn is_element(&self, x: &Self::Set) -> bool {
191        x.len() == self.domain.size() && x.iter().all(|y| self.range.is_element(y))
192    }
193}
194
195impl<Domain: FiniteSetStructure, Range: EqStructure + FiniteSetStructure> CountableSetStructure
196    for Functions<Domain, Range>
197{
198    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> {
199        (0..self.domain.size())
200            .map(|_| self.range.list_all_elements())
201            .multi_cartesian_product()
202    }
203}
204
205impl<Domain: FiniteSetStructure, Range: EqStructure + FiniteSetStructure> FiniteSetStructure
206    for Functions<Domain, Range>
207{
208}
algebraeon_sets/structure/morphism.rs

algebraeon_sets/structure/
morphism.rs
