Why do we even need first order logic?
I don't understand why propositional logic isn't enough. Can't any first order statement be encoded in the form of a propositional logic? What does first order logic do for us that we cannot do in propositional logic?
logic definition propositional-calculus first-order-logic
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 10 more comments
I don't understand why propositional logic isn't enough. Can't any first order statement be encoded in the form of a propositional logic? What does first order logic do for us that we cannot do in propositional logic?
logic definition propositional-calculus first-order-logic
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
1
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
4
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
4
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
2
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35
|
show 10 more comments
I don't understand why propositional logic isn't enough. Can't any first order statement be encoded in the form of a propositional logic? What does first order logic do for us that we cannot do in propositional logic?
logic definition propositional-calculus first-order-logic
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I don't understand why propositional logic isn't enough. Can't any first order statement be encoded in the form of a propositional logic? What does first order logic do for us that we cannot do in propositional logic?
logic definition propositional-calculus first-order-logic
logic definition propositional-calculus first-order-logic
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 27 '18 at 0:00
James Prim
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 27 '18 at 0:00
James Prim
71
asked Dec 27 '18 at 0:00
James Prim
71
71
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
James Prim is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
1
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
4
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
4
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
2
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35
|
show 10 more comments
2
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
1
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
4
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
4
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
2
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35
2
2
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
1
1
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
4
4
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
4
4
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
2
2
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35
|
show 10 more comments
1 Answer
1
active
oldest
votes
Propositional logic cannot account for, amongst other things, the validity of such arguments as
Socrates is a man.
All men are mortal.
$therefore$ Socrates is mortal.
In propositional logic, we cannot do any better than to translate this argument as (e.g.)
$S$
$M$
$therefore R$
which is plainly invalid.
In first-order logic, we can formulate this intuitively valid argument in such a way that it does turn out valid, thanks to the universal quantifier:
$Ms$
$forall x(Mx to Rx)$
$therefore Rs$
To generalise, first-order logic allows us to get at the internal structure of certain propositions in a way that is not possible with mere propositional logic. The possession or non-possession of important logical properties turns on the precise nature of these internal structures. So it is important that we have adequate tools at hand to analyse them. First-order logic gives us many of these tools.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
James Prim is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053450%2fwhy-do-we-even-need-first-order-logic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Propositional logic cannot account for, amongst other things, the validity of such arguments as
Socrates is a man.
All men are mortal.
$therefore$ Socrates is mortal.
In propositional logic, we cannot do any better than to translate this argument as (e.g.)
$S$
$M$
$therefore R$
which is plainly invalid.
In first-order logic, we can formulate this intuitively valid argument in such a way that it does turn out valid, thanks to the universal quantifier:
$Ms$
$forall x(Mx to Rx)$
$therefore Rs$
To generalise, first-order logic allows us to get at the internal structure of certain propositions in a way that is not possible with mere propositional logic. The possession or non-possession of important logical properties turns on the precise nature of these internal structures. So it is important that we have adequate tools at hand to analyse them. First-order logic gives us many of these tools.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Propositional logic cannot account for, amongst other things, the validity of such arguments as
Socrates is a man.
All men are mortal.
$therefore$ Socrates is mortal.
In propositional logic, we cannot do any better than to translate this argument as (e.g.)
$S$
$M$
$therefore R$
which is plainly invalid.
In first-order logic, we can formulate this intuitively valid argument in such a way that it does turn out valid, thanks to the universal quantifier:
$Ms$
$forall x(Mx to Rx)$
$therefore Rs$
To generalise, first-order logic allows us to get at the internal structure of certain propositions in a way that is not possible with mere propositional logic. The possession or non-possession of important logical properties turns on the precise nature of these internal structures. So it is important that we have adequate tools at hand to analyse them. First-order logic gives us many of these tools.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
Propositional logic cannot account for, amongst other things, the validity of such arguments as
Socrates is a man.
All men are mortal.
$therefore$ Socrates is mortal.
In propositional logic, we cannot do any better than to translate this argument as (e.g.)
$S$
$M$
$therefore R$
which is plainly invalid.
In first-order logic, we can formulate this intuitively valid argument in such a way that it does turn out valid, thanks to the universal quantifier:
$Ms$
$forall x(Mx to Rx)$
$therefore Rs$
To generalise, first-order logic allows us to get at the internal structure of certain propositions in a way that is not possible with mere propositional logic. The possession or non-possession of important logical properties turns on the precise nature of these internal structures. So it is important that we have adequate tools at hand to analyse them. First-order logic gives us many of these tools.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Propositional logic cannot account for, amongst other things, the validity of such arguments as
Socrates is a man.
All men are mortal.
$therefore$ Socrates is mortal.
In propositional logic, we cannot do any better than to translate this argument as (e.g.)
$S$
$M$
$therefore R$
which is plainly invalid.
In first-order logic, we can formulate this intuitively valid argument in such a way that it does turn out valid, thanks to the universal quantifier:
$Ms$
$forall x(Mx to Rx)$
$therefore Rs$
To generalise, first-order logic allows us to get at the internal structure of certain propositions in a way that is not possible with mere propositional logic. The possession or non-possession of important logical properties turns on the precise nature of these internal structures. So it is important that we have adequate tools at hand to analyse them. First-order logic gives us many of these tools.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Dec 27 '18 at 1:31
solisoc
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Dec 27 '18 at 1:31
solisoc
313
answered Dec 27 '18 at 1:31
solisoc
313
313
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
solisoc is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
James Prim is a new contributor. Be nice, and check out our Code of Conduct.
James Prim is a new contributor. Be nice, and check out our Code of Conduct.
James Prim is a new contributor. Be nice, and check out our Code of Conduct.
James Prim is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053450%2fwhy-do-we-even-need-first-order-logic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
What about the quantifiers?
– MJD
Dec 27 '18 at 0:02
1
@MJD That's precisely what I am asking though
– James Prim
Dec 27 '18 at 0:32
4
You write "Can't any first order statement be encoded in the form of a propositional logic?" I'm not sure why you think this is the case. How would you encode "$forall x exists y(xnot=y)$" in propositional logic?
– Noah Schweber
Dec 27 '18 at 0:47
4
@JamesPrim "Who says it can't be infinitely long?" It's part of the basic definition of propositional logic, see e.g. the sources mentioned here. As to definability, that's a specific term in the context of first-order logic, and it's perfectly possible for a structure to have undefinable elements. I think one of the issues here is that you don't have a sufficiently clear picture of each of the logics in question, and should clear that up first.
– Noah Schweber
Dec 27 '18 at 1:27
2
@JamesPrim Yes, like I said, it's part of the definition. It's an important part too: drop it and you get something very different. Something quite interesting, but not propositional logic anymore, and with importantly different properties (e.g. compactness fails once you allow infinitely-long formulas).
– Noah Schweber
Dec 27 '18 at 1:35