morphisms-of-computational-structures
morphisms-of-computational-structures copied to clipboard
prathyvsh
Mathematical theories of abstractions
What is abstraction?
There are three ways to see this: 1/ Creating equivalences (quotienting / equivalence classes) 2/ Focussing on what is important and ignoring the unimportant 3/ Creating a multiply realizable object from concrete instances.
When formalizing, all these interpretations need to be facets of the unifying model.
Here are some mathematical works that try to formalize this.
I think this idea is very close to equational theories, quotienting, and the act of creating equivalence classes. This is the act of ignoring certain sets of distinctions in the domain of discourse while retaining certain others. This idea of pushing out and pulling back on the differences and sameness allows for studying various aspects of objects under consideration.
Think of grouping a set of cars by their colors. This will give a set of entries say {car1, car3}, {car2, car4} as the equivalence classes. When abstracting, you can think of quotienting in this manner with the appropriate composition creating a route from the composition to the realization in one of the element in this quotient set.
I add some papers that make this notion precise or is a close approach.
Understanding Understanding Mathematics: https://onlinelibrary.wiley.com/doi/pdf/10.1207/s15516709cog0204_3 The Structure of Mathematical Knowledge: http://dspace.mit.edu/bitstream/handle/1721.1/6928/AITR-472.pdf?sequence=2
by Edwina Michiner
The Mathematical Abstraction Theory,The Fundamentals forKnowledge Representation andSelf-Evolving Autonomous Problem Solving Systems: https://arxiv.org/ftp/arxiv/papers/1408/1408.1377.pdf
by Seppo Illari Tirri
Facets and Levels of Mathematical Abstraction: https://journals.openedition.org/philosophiascientiae/914?lang=en
On the foundation of abstract algebra (series): https://www.jstor.org/stable/1968580 by Øyster Ore.
Quotient Dynamics: The Logic of Abstraction — https://staff.fnwi.uva.nl/n.bezhanishvili/Papers/LORI-BBIO.pdf
Symbol Grounding via Chaining of Morphisms: https://arxiv.org/pdf/1703.04368.pdf
Graph quotients: A Topological Approach to Graphs / Typical bullshit paper: https://pdfs.semanticscholar.org/92bb/ca7a5acc547af46fb9d4dd0ad96bd7037e81.pdf?_ga=2.191826730.102404440.1603725460-1284050325.1602911161
Theorem proving with abstraction: https://www.sciencedirect.com/science/article/abs/pii/0004370281900151
A Semantic Theory of Abstractions: https://homes.cs.washington.edu/~alon/files/ijcai95.ps or https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.5416&rep=rep1&type=pdf
A Semantics for Abstraction: https://www.researchgate.net/publication/30530587_A_semantics_for_abstraction
Abstraction: A General Framework for Learning: https://www.semanticscholar.org/paper/Abstraction%3A-a-general-framework-for-learning-Giordana-Saitta/3d063b9b68007ad5bb7c44bba9abae152bea2c97
A Model of Abstraction in Visual Perception: https://www.tandfonline.com/doi/abs/10.1080/088395101317018591
Preserving consistency across abstract mappings: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.324.390&rep=rep1&type=pdf
Abstraction and Phase Transition: https://www.researchgate.net/publication/2519284_Abstraction_and_Phase_Transitions/link/00463517f9ee9f364c000000/download
A grounded theory of abstraction for artificial intelligence: https://www.jstor.org/stable/3558222?seq=1
Collusions and Quotients: Generalizing Equivalence Relations and Definitions by Abstraction: https://hal.archives-ouvertes.fr/hal-02369662/document
It might be interesting to explore this question from the angle of computation. There are some interesting related work as quotient types are typically used to ground the idea of abstraction.
Here are two papers: 1/ Abstraction and Computation by Venanzio Capretta: http://www-sop.inria.fr/lemme/Venanzio.Capretta/publications/thesis.pdf 2/ Computational Abstraction by Raymond Turner: https://mdpi-res.com/d_attachment/entropy/entropy-23-00213/article_deploy/entropy-23-00213-v2.pdf
I also have to explore logical relations and parametricity as it emerged in the work of John Reynolds as it provides a different kind of traction than sets/types.
Original paper: https://people.mpi-sws.org/~dreyer/tor/papers/reynolds.pdf Quotient Relations and data abstraction by Adam EppenDahl: http://www.cs.ioc.ee/~tarmo/fmmf02/eppendahl.html
An Introduction to Logical Relations: https://arxiv.org/abs/1907.11133 Logical Relations as Types by John Sterling: https://www.jonmsterling.com/pdfs/lrat.pdf Logical Relations and Parametricity - A Reynolds Programme for Category Theory and Programming Languages: http://www.cs.bham.ac.uk/~udr/papers/logical-relations-and-parametricity.pdf
This StackOverflow answer is interesting as it mentions connections between logical relations to Kan extensions by Abramsky in Vijay’s answer and to data abstraction and encapsulation by Uday Reddy: https://cstheory.stackexchange.com/questions/5427/what-are-the-differences-between-logical-relations-and-simulations/10431
From an information theoretic viewpoint, there is this paper “Towards a Mathematical Theory of Abstraction” by Beren Millidge: https://arxiv.org/pdf/2106.01826.pdf
I have to check what other works are there in Information Theory that addresses this question.