6 ms·

A foundation for mathematics is any formalism sufficient to prove the results typically taken as axioms in practical mathematics. For example, in ZFC you can d

A foundation for mathematics is any formalism sufficient to prove the results typically taken as axioms in practical mathematics. For example, in ZFC you can define numbers as sets in many different ways and prove that 1+1=2 for each of them - other foundations include higher order logic, topos theory, other set theories, etc.

wubrr 3y ago
Is it also possible to define set theory in terms of arithmetic?
- wisnesky 3y ago
  Yes, at least with a strong enough arithmetic (such as Peano's), but that is usually more complicated; for example, you might have to create a Godel numbering or some other "deep embedding" to represent each set as a number. There's also so-called "reverse mathematics", which tries to determine the weakest axiom system capable of establishing a particular result.
  - wubrr 3y ago
    Interesting, thanks!
- Kranar 3y ago
  You can certainly define some set theories using arithmetic but arithmetic as formalized by first-order Peano arithmetic can not define a set theory powerful enough to prove results about uncountable sets, such as large cardinal axioms or even properties of real numbers.
  - wubrr 3y ago
    Any links/examples of why this isn't possible? My thinking is - if all existing set theory and set theoretic proofs are expressed in finite set-theoretic statements/expressions - can't we 'encode' these expressions within the system of arithmetic?
    - Kranar 3y ago
      Do I have links off the top of my head that directly address this, no unfortunately I do not. I do have links to different pieces that you can use to understand this, however. First is the notion of the consistency strength of a formal system which basically is the ability of one formal system to prove the consistency of another formal system [1]. ZFC is strictly stronger than PA in the sense in that ZFC can prove the consistency of PA [2]. From this, however, it follows that PA can not prove the consistency of ZFC. If PA could prove the consistency of ZFC then ZFC would be able to prove the consistency of itself, which we know from Godel's incompleteness theorem would mean that ZFC is inconsistent [3]. So this gives one concrete proof that ZFC can produce that PA can not produce, namely the consistency of PA itself. [1] https://en.wikipedia.org/wiki/Equiconsistency#Consistency_strength https://en.wikipedia.org/wiki/Equiconsistency#Consistency_st... [2] https://mathoverflow.net/questions/66121/is-pa-consistent-do-we-know-it https://mathoverflow.net/questions/66121/is-pa-consistent-do... [3] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Second_incompleteness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
nitwit005 3y ago
You're getting at the problem with saying "foundation". If you can reach the same conclusions from a large number of starting points, there isn't any special set of ideas on which everything rests.
- epgui 3y ago
  Why does the foundation need to be unique? It seems intuitive to me that they must not be unique.

wubrr 3y ago

Is it also possible to define set theory in terms of arithmetic?

wisnesky 3y ago
Yes, at least with a strong enough arithmetic (such as Peano's), but that is usually more complicated; for example, you might have to create a Godel numbering or some other "deep embedding" to represent each set as a number. There's also so-called "reverse mathematics", which tries to determine the weakest axiom system capable of establishing a particular result.
- wubrr 3y ago
  Interesting, thanks!
Kranar 3y ago
You can certainly define some set theories using arithmetic but arithmetic as formalized by first-order Peano arithmetic can not define a set theory powerful enough to prove results about uncountable sets, such as large cardinal axioms or even properties of real numbers.
- wubrr 3y ago
  Any links/examples of why this isn't possible? My thinking is - if all existing set theory and set theoretic proofs are expressed in finite set-theoretic statements/expressions - can't we 'encode' these expressions within the system of arithmetic?
  - Kranar 3y ago
    Do I have links off the top of my head that directly address this, no unfortunately I do not. I do have links to different pieces that you can use to understand this, however. First is the notion of the consistency strength of a formal system which basically is the ability of one formal system to prove the consistency of another formal system [1]. ZFC is strictly stronger than PA in the sense in that ZFC can prove the consistency of PA [2]. From this, however, it follows that PA can not prove the consistency of ZFC. If PA could prove the consistency of ZFC then ZFC would be able to prove the consistency of itself, which we know from Godel's incompleteness theorem would mean that ZFC is inconsistent [3]. So this gives one concrete proof that ZFC can produce that PA can not produce, namely the consistency of PA itself. [1] https://en.wikipedia.org/wiki/Equiconsistency#Consistency_strength https://en.wikipedia.org/wiki/Equiconsistency#Consistency_st... [2] https://mathoverflow.net/questions/66121/is-pa-consistent-do-we-know-it https://mathoverflow.net/questions/66121/is-pa-consistent-do... [3] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Second_incompleteness_theorem https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

nitwit005 3y ago

You're getting at the problem with saying "foundation". If you can reach the same conclusions from a large number of starting points, there isn't any special set of ideas on which everything rests.

epgui 3y ago
Why does the foundation need to be unique? It seems intuitive to me that they must not be unique.