User:IssaRice/Computability and logic/Some important distinctions and equivalences in introductory mathematical logic: Difference between revisions
No edit summary |
No edit summary |
||
| Line 63: | Line 63: | ||
* When I think of "algorithm" or "program", I imagine it being a string rather than a natural number (it seems most concrete to me to imagine a Python program). This distinction turns out to not be important, since we can just think of strings as integers. | * When I think of "algorithm" or "program", I imagine it being a string rather than a natural number (it seems most concrete to me to imagine a Python program). This distinction turns out to not be important, since we can just think of strings as integers. | ||
* When I think of "index" I think of natural numbers. I also imagine there being some sequence of indices, whereas with "algorithm" or "program" I can think of them in isolation. | * When I think of "index" I think of natural numbers. I also imagine there being some sequence of indices, whereas with "algorithm" or "program" I can think of them in isolation. | ||
==theory vs axioms== | |||
I think "theory" and "axioms" can often be used interchangeably in logic. For instance, to say that a theory proves a sentence is the same as saying the axioms prove the sentence, since everything in the theory comes from the axioms. | |||
Synecdoche problem: in mathematics more generally, when referring to a structured space (such as a group) it is conventional to use the same name for both the space itself as well as the set of objects living in that space. I think a similar thing happens with the word "theory" in logic. Some books say a theory is just a set of sentences -- any set of sentences. Other books require that this set be closed under deductions. Yet other books single out the starting set of sentences (as non-logical axioms) and then call the set of sentences that can be proved from it the theorems; the "theory" is then the overall name applied to the whole structure. | |||
In practice this distinction doesn't seem to matter much. | |||
==notes== | ==notes== | ||
| Line 69: | Line 77: | ||
* structure vs interpretation vs model: synecdoche problem | * structure vs interpretation vs model: synecdoche problem | ||
* interpretation: there's interpretation in the "structure" sense and also interpretation in the sense of embedding one theory inside another theory (e.g. doing arithmetic with sets) | * interpretation: there's interpretation in the "structure" sense and also interpretation in the sense of embedding one theory inside another theory (e.g. doing arithmetic with sets) | ||
* language vs logic vs formal system vs system | * language vs logic vs formal system vs system | ||
* proves logically vs proves in a particular theory: each theory adds some non-logical axioms that allows it to prove things that aren't logically valid | * proves logically vs proves in a particular theory: each theory adds some non-logical axioms that allows it to prove things that aren't logically valid | ||