4 ms·
In first order logic one can only quantify over objects of the domain: in "for all x such that ..." the variable "x" represent an object. In second order logic
by yaantc 6y ago
In first order logic one can only quantify over objects of the domain: in "for all x such that ..." the variable "x" represent an object.
In second order logic, one can quantify over relations (and functions, sets...): "for all P such that ...".
The wikipaedia page [1] has more details and is quite readable. Be careful about falling into a rabbit hole ;)
[1] https://en.wikipedia.org/wiki/Second-order_logic https://en.wikipedia.org/wiki/Second-order_logic
- andi999 6y agoThanks, I will read that more. I am still confused, maybe you can tell me: for 'normal math'(what is usually taught in a formal 3 year degree), is first order logic enough (for getting all the results). What I am trying is to see where this second order logic fits in to what I use already.
- H8crilA 6y agoYou can do a lot of math (almost all of it?) without ever touching logic. It's only important when you ask yourself things like "hmm, okay, the reals are closed under taking supremum of bounded sets, isn't that too much to ask for? how do I know reals are possible?". And of course the great logicians showed us that you can find "significant problems" already in natural numbers.
- andi999 6y agoThats not what i meant. I mean certainly you are using some logic for doing math, do you agree with this? And if you agree, is the logic we use 1st or 1st and 1nd order?
- Kranar 6y agoThe overwhelming majority of math is done using informal logic, similar to using pseudocode to describe an algorithm. Almost no one proves mathematical theorems using formal logic, whether it's first order logic or otherwise.
- yaantc 6y agoNormal practice is not that formal (except for logicians ;), but would definitely be second order logic. It's common to quantify over "all functions such that..." or over set of sets for example. Second order logic is more expressive.
- andi999 6y agoThanks. I dont understand why for all elements of a set is first order and for all functions is second order - since functions (lets say R->R) are elements of the powerset of the cartesian product of RxR. So functions in math are usually part of first order logic, no?
- yaantc 6y agoAs said by @dwohnitmok it depends on the domain you consider. If you have a proposition quantifying over objects and functions operating on said objects, it's second order. But if you have a proposition considering only said functions as objects, it is first order (with a different domain: not the base objects, but functions over those objects). And again: you can ignore such subtleties for most of mathematics.
- dwohnitmok 6y agoSimply put first order logic is enough to do almost all of mathematics and is certainly enough to cover all the results of an undergraduate degree. More generally speaking the term "first order logic" is ambiguous by itself since we are not specifying our domain of discourse. For example, take the group axioms (e.g. there exists an identity element, every element has an inverse, etc.). In this context our domain of discourse is the elements of a single group. Hence while we can say things such as "there exists only one identity element," which is existential quantification over the elements of the group, we cannot say things such as "there exists a group with only one element" since that is quantification over groups themselves and disallowed by first order logic. However, if we change our domain of discourse and instead e.g. use ZFC (a first order theory) as our starting point and simply augment ZFC with the language of group theory, then both statements are expressible, since both elements of a group and a group itself are sets in ZFC. So insofar as something like ZFC is enough to do almost all of mathematics, first order logic is enough to do almost all of mathematics.
- andi999 6y agoThanks a lot! I think now I start to understand this.