1

I wonder whether it exists a formal system such that all (or a considerable number of) the others can be considered as a subsets or fragments of it.

I would say that, for instance, First-Order logic is a subset of Second-order logic (and so on if we keep with higher-order logics); on the other side, I would argue that, for instance, temporal logics also extend the logics in other directions, adding temporality operators.

So my question is: which is the most expressive logic that you have seen (even if it has no Computation uses, but just philosophical or even recreational) and the most expressive logic that you have seen that actually is used in any application in Computation.

This is obviously not a single answer question (as I use "expressivity" to say just, "what can be said"), just would like you to express what you think.

15
  • There is no "most expressive logic" for the simple reason that already some first order logics are incompatible with each other, e.g. classical, intuitionistic and paraconsistent ones. Already second order logic is not effectively axiomatizable, so of limited computational value, and it gets worse in higher orders, but they get ever more "expressive", and there is no upper bound to that. – Conifold Mar 17 at 19:40
  • Hello, and welcome. I have to point out that asking for opinions is generally considered bad practice here. This one is a bit of a border case, though, since it basically asks for expert experience, which could be seen as on the "good subjective" side. Will leave it to the community to decide upon that :) – Philip Klöcking Mar 17 at 19:47
  • Hey, sorry then, I thought this question's answers can provide interesting knowledge: it can be subjective whether it is the "most expressive or not", but the point is reasoning about arithmetics and so on :) – Theo Deep Mar 17 at 20:26
  • 1
    Note that "complete" has a different technical meaning than the informal way you use it to mean "expressive". It's easy to find complete logics that aren't all that expressive. In fact completeness in this technical sense is in tension with how expressive a logic is. E.g. 2nd order order logic is incomplete in this technical sense. – Fizz Mar 18 at 2:11
  • 1
    @polcott Just stop confusing logical boolean values with pragmatic epistemological truth, would you? All you end up with is an idiosyncratic language. You cannot have it both ways: Either you allow for it to be about something outside of it (the world), then it is not a closed system because the fundamental truths are not defined to be true within, but from without the system. Or you do not, then it may be complete, but idiosyncratic. – Philip Klöcking Mar 18 at 13:45
2

There is no perfectly expressive logic. Every logic powerful enough to include arithmetic is incomplete. Moreover, each one of those logics can be augmented by additional axioms to be more complete than it was - to yield more true theorems than it had. This means that you can always make a logic more complete, so there is no most complete one.

However, there is good news. Within first-order logic, you can "simulate" the rules of second-order logic and every other logic too. This is why ZFC (a first-order logic in which the objects are sets) can be considered a foundation for all of mathematics. What you do is define a proposition in second order logic as a particular kind of set in ZFC, and define second-order logic proofs also as particular sets in ZFC, according to rules for how to construct these sets. Then to ask whether a proposition in second-order logic has a proof, is the same question as whether a particular set exists in ZFC.

2
  • Seems like I have to read more about ZFC, thanks! Indeed I thought that Second-Order logic was the first one providing the quantification over sets, and that First-Order logic did not allow that. – Theo Deep Mar 17 at 20:32
  • @TheoDeep: The point is, if you can talk about it meaningfully, it is almost utterly surely that what you are talking about can be expressed in a suitable set theory. It doesn't really matter which set theory, but ZFC is the current conventional foundation for mathematics much for that reason. By the way, polcott is a crank who used sockpuppets (such as "pl_olcott") against SE rules and got suspended on Math SE (until july) for posting nonsense. – user21820 Mar 18 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.