11–20 of 425 posts
The fascinating thing is that now these transistors are helping make new math proofs beyond human comprehension.... how does that come out of addition?
Does anyone have an intuition for why Presburger arithmetic is decidable, but once you introduce x, it is not? If + can be rewritten as repeated succ, (which is decidable) and x can be rewritten as repeated +, then it seems logical that x should be decidable, but as any undergraduate CS student knows, Peano arithmetic is undecidable. What is so special about x exactly?
* addition: the cardinality of the disjoint union of two sets
* multiplication: the cardinality of the direct product of two sets
* exponentiation: a^b is the cardinality of the set of maps from B to A where B is a set of cardinality b and A is a set of cardinality a
My favourite way of thinking about these operations comes from category theory: * addition: the cardinality of the disjoint union of two sets * multiplication: the cardinality of the direct product of two sets * exponentiation: a^b is the cardinality of the set of maps from B to A where B is a set of cardinality b and A is a set of cardinality a
The teacher mentions juggling units when adding and multiplying, but is 2 cm × 3 cm the same thing as 2 × 3?
I just found this interesting article. If you are interested, it is a review of the following "conversation of articles" (which are reachable from the OP but I guess it's useful enough to list): - https://www.maa.org/external_archive/devlin/devlin_09_07.html - https://www.maa.org/external_archive/devlin/devlin_06_08.html - https://denisegaskins.com/2008/07/01/if-it-aint-repeated-addition/ - (the link I posted that cr…
My favourite way of thinking about these operations comes from category theory: * addition: the cardinality of the disjoint union of two sets * multiplication: the cardinality of the direct product of two sets * exponentiation: a^b is the cardinality of the set of maps from B to A where B is a set of cardinality b and A is a set of cardinality a
This is just set theory, not category theory.
https://mathoverflow.net/questions/360578/category-theory-an...
Does anyone have an intuition for why Presburger arithmetic is decidable, but once you introduce x, it is not? If + can be rewritten as repeated succ, (which is decidable) and x can be rewritten as repeated +, then it seems logical that x should be decidable, but as any undergraduate CS student knows, Peano arithmetic is undecidable. What is so special about x exactly?
The fundamental theorem of arithmetic says for any non-zero natural number x there is a unique finite sequence of integers a_i such that x = 2^a_0 . 3^a_1 . 5^a_3 ... p_n^a_n and that given x the sequence a_i is computable (similarly given a_i you can easily construct their x).
This basically gives you a (bijective) mapping between integers and tuples of integers x (a_0, a_1, ... a_n) which lets you build up more complicated structures and eventually construct the sentence you need for an incompleteness theorem (if you're as smart as Gödel).
Does anyone have an intuition for why Presburger arithmetic is decidable, but once you introduce x, it is not? If + can be rewritten as repeated succ, (which is decidable) and x can be rewritten as repeated +, then it seems logical that x should be decidable, but as any undergraduate CS student knows, Peano arithmetic is undecidable. What is so special about x exactly?
We went to very different universities it seems. Neither Peano arithmetic nor decidability were ever mentioned