3 ms·

relations are also defined in terms of sets: As a sets of pairs, e.g. an element of a set like {x ,{x,y}} is just the pair (x,y), a set of such pairs IS a relat

by bsedlm 4y ago

relations are also defined in terms of sets: As a sets of pairs, e.g. an element of a set like {x ,{x,y}} is just the pair (x,y), a set of such pairs IS a relation. moreover, in terms of sets functions are a relation with some restrictions: - That they are binary relations - The "functional-requirement" (as I call it) refers to the difference between a relation and a function. for every x, f(x) = (only one thing); e.g. a relation can have pairs (x,a) and (x,b) but no function can do this. As far as I've understood, this gets really "fun" when characteristic-functions enter the scene... With these boolean-valued functions it's possible to define a set.

layer8 4y ago
I’m aware of all that, but it doesn’t really answer my question. If functions can be used as a fundamental concept not based on sets (maybe similar to arrows in category theory), what prevents generalizing that approach to relations? While relations lose the guarantee of single-valuedness, they gain the guarantee of being invertible (or in the case of n-ary relations, arguably a further generalization, permutable).
- housecarpenter 4y ago
  Since all three notions are closely interrelated, it's fairly trivial to take any one you choose as "fundamental" and define the others in terms of it: - Sets as fundamental: define ordered pairs via Kuratowski's definition, define relations as sets of ordered pairs, define functions as relations not containing any two ordered pairs with the same first projection but different second projections - Relations as fundamental: define sets as unary relations, define functions as relations the same way as before - Functions as fundamental: define sets as functions where the codomain is some fixed singleton (characteristic functions are more appropriate for subsets of a set, rather than sets on their own), define relations as functions whose codomains are power sets Because of this sort of thing, I don't think any notion of "fundamental" that's purely based on interdefinability really makes much sense. I personally have a sense that some definitions are "constructive" and others are "destructive" (my use of "constructive" here is in no way related to "constructive" as in "constructive logic", it's just based on the English meaning of "construct"). Of the definitions I gave above, I perceive the definitions of functions and relations from sets, of functions from relations, and relations from functions as "constructive", while the definitions of sets from functions and from relations are "destructive". Since I can't think of any "constructive" definition of sets from functions or relations, while I can think of "constructive" definitions in the opposite direction, I would say sets are more fundamental than functions and relations. Whereas since both relations and functions can be "constructively" inter-defined, I'd say they're both on the same level. Admittedly, I have no idea how to define "constructive".
  - layer8 4y ago
    Right, I’m actually not convinced that it’s possible to have functions (or relations) as fundamentals without presupposing a concept of sets (domains/codomains) in the first place. But assuming that it is possible (as the GP believes), my feeling is that relations would be more general, maybe similar to how graphs are a more general concept than directed graphs. Representing relations as functions to power sets feels rather complex to me compared with functions being a special type of relation, which is why I would find the latter more natural. And thus I was wondering whether the GP maybe has a good reason to go with functions rather than relations.
    - throwaway17_17 4y ago
      The ‘common’ strategy of going with functions first are mostly due to Type Theoretic Foundations research. The most usual presentation presents the function type as foundational and inherent for the development. There has been some research pushing towards Function types being a specialization of Relations as types, where relations become the foundational elements. But I think the biggest point of contention in your comment is finding sets (i.e. Domains/Codomains) to be required to define functions. Most of this discussion is inspired (either implicitly or explicitly) by the type theoretic foundations. There is a fundamental difference between sets and types, but they are both used to describe the ‘inputs’ and ‘outputs’ of a function in general discussion. However, type theoretical foundations takes types to be the foundation of mathematics, so sets are then defined in terms of types and do not act as the ‘inputs’ and ‘outputs’ for functions.
      - layer8 4y ago
        Thanks. Can you recommend where I can read up on the precise formal definition of ‘type’ in that sense, and how sets are then defined in terms of types? So far I only have seen (too) informal discussions on that.
        throwaway17_17 4y ago
        I think the first recommendation would be the SEP (Stanford Encyclopedia of Philosophy) article on Type Theory written by Couquand [1]. It is a broad but well founded walk through the basis of type theory and it’s usage as a foundation for both logic and mathematics. It also contains a section discussing Univalent Foundations, which is the foremost area for type theoretic foundations at present. The papers listed in the reference section contain most of the fundamental research results of note. I do think Aczel’s “The type theoretic interpretation of constructive set theory” (1978) and Bell’s “Types, Sets and Categories” (2012), which are both cited are good papers. 1 —- https://plato.stanford.edu/entries/type-theory/ https://plato.stanford.edu/entries/type-theory/
- bsedlm 4y ago
  having thought about this some more, I guess that no, the more fundamental notion should be sets. may I recommend this links to read up on the precise formal definition of ‘type’ https://plato.stanford.edu/entries/type-theory/ https://plato.stanford.edu/entries/type-theory/ Simple Type Theory https://plato.stanford.edu/entries/type-theory-church/ https://plato.stanford.edu/entries/type-theory-church/

by bsedlm 4y ago

layer8 4y ago

I’m aware of all that, but it doesn’t really answer my question. If functions can be used as a fundamental concept not based on sets (maybe similar to arrows in category theory), what prevents generalizing that approach to relations? While relations lose the guarantee of single-valuedness, they gain the guarantee of being invertible (or in the case of n-ary relations, arguably a further generalization, permutable).

housecarpenter 4y ago
Since all three notions are closely interrelated, it's fairly trivial to take any one you choose as "fundamental" and define the others in terms of it: - Sets as fundamental: define ordered pairs via Kuratowski's definition, define relations as sets of ordered pairs, define functions as relations not containing any two ordered pairs with the same first projection but different second projections - Relations as fundamental: define sets as unary relations, define functions as relations the same way as before - Functions as fundamental: define sets as functions where the codomain is some fixed singleton (characteristic functions are more appropriate for subsets of a set, rather than sets on their own), define relations as functions whose codomains are power sets Because of this sort of thing, I don't think any notion of "fundamental" that's purely based on interdefinability really makes much sense. I personally have a sense that some definitions are "constructive" and others are "destructive" (my use of "constructive" here is in no way related to "constructive" as in "constructive logic", it's just based on the English meaning of "construct"). Of the definitions I gave above, I perceive the definitions of functions and relations from sets, of functions from relations, and relations from functions as "constructive", while the definitions of sets from functions and from relations are "destructive". Since I can't think of any "constructive" definition of sets from functions or relations, while I can think of "constructive" definitions in the opposite direction, I would say sets are more fundamental than functions and relations. Whereas since both relations and functions can be "constructively" inter-defined, I'd say they're both on the same level. Admittedly, I have no idea how to define "constructive".
- layer8 4y ago
  Right, I’m actually not convinced that it’s possible to have functions (or relations) as fundamentals without presupposing a concept of sets (domains/codomains) in the first place. But assuming that it is possible (as the GP believes), my feeling is that relations would be more general, maybe similar to how graphs are a more general concept than directed graphs. Representing relations as functions to power sets feels rather complex to me compared with functions being a special type of relation, which is why I would find the latter more natural. And thus I was wondering whether the GP maybe has a good reason to go with functions rather than relations.
  - throwaway17_17 4y ago
    The ‘common’ strategy of going with functions first are mostly due to Type Theoretic Foundations research. The most usual presentation presents the function type as foundational and inherent for the development. There has been some research pushing towards Function types being a specialization of Relations as types, where relations become the foundational elements. But I think the biggest point of contention in your comment is finding sets (i.e. Domains/Codomains) to be required to define functions. Most of this discussion is inspired (either implicitly or explicitly) by the type theoretic foundations. There is a fundamental difference between sets and types, but they are both used to describe the ‘inputs’ and ‘outputs’ of a function in general discussion. However, type theoretical foundations takes types to be the foundation of mathematics, so sets are then defined in terms of types and do not act as the ‘inputs’ and ‘outputs’ for functions.
    - layer8 4y ago
      Thanks. Can you recommend where I can read up on the precise formal definition of ‘type’ in that sense, and how sets are then defined in terms of types? So far I only have seen (too) informal discussions on that.
      - throwaway17_17 4y ago
        I think the first recommendation would be the SEP (Stanford Encyclopedia of Philosophy) article on Type Theory written by Couquand [1]. It is a broad but well founded walk through the basis of type theory and it’s usage as a foundation for both logic and mathematics. It also contains a section discussing Univalent Foundations, which is the foremost area for type theoretic foundations at present. The papers listed in the reference section contain most of the fundamental research results of note. I do think Aczel’s “The type theoretic interpretation of constructive set theory” (1978) and Bell’s “Types, Sets and Categories” (2012), which are both cited are good papers. 1 —- https://plato.stanford.edu/entries/type-theory/ https://plato.stanford.edu/entries/type-theory/
bsedlm 4y ago
having thought about this some more, I guess that no, the more fundamental notion should be sets. may I recommend this links to read up on the precise formal definition of ‘type’ https://plato.stanford.edu/entries/type-theory/ https://plato.stanford.edu/entries/type-theory/ Simple Type Theory https://plato.stanford.edu/entries/type-theory-church/ https://plato.stanford.edu/entries/type-theory-church/