Predicate Logic Natural Number Problems
$begingroup$
I am trying to translate the following statements into predicate logic using the following predicates: $E(x) = x$ is even, $P(x) = x$ is prime, $L(x,y) = x < y$
(i): Some Primes are Odd.
(ii): Every even number is greater than 1.
(iii): There are infinitely many primes.
(iv): The only even prime is 2.
My attempts were
(i): $neg (forall x P(x) implies E(x))$
My reasoning behind this was that saying $exists x(P(x) land neg E(x))$ just says there is at least 1, rather than some odd primes.
(ii): $forall x E(x) implies L(1,x)$
(iii): $forall x exists y (P(x) land P(y) land L(x,y)$
My reasoning for this one was that this means that for every prime, there is a prime that is greater than it, which means there are infinitely many primes.
I am not really sure how to go about (iv)
Any help is greatly appreciated!!
logic predicate-logic logic-translation
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
$endgroup$
add a comment |
$begingroup$
I am trying to translate the following statements into predicate logic using the following predicates: $E(x) = x$ is even, $P(x) = x$ is prime, $L(x,y) = x < y$
(i): Some Primes are Odd.
(ii): Every even number is greater than 1.
(iii): There are infinitely many primes.
(iv): The only even prime is 2.
My attempts were
(i): $neg (forall x P(x) implies E(x))$
My reasoning behind this was that saying $exists x(P(x) land neg E(x))$ just says there is at least 1, rather than some odd primes.
(ii): $forall x E(x) implies L(1,x)$
(iii): $forall x exists y (P(x) land P(y) land L(x,y)$
My reasoning for this one was that this means that for every prime, there is a prime that is greater than it, which means there are infinitely many primes.
I am not really sure how to go about (iv)
Any help is greatly appreciated!!
logic predicate-logic logic-translation
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
$endgroup$
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01
add a comment |
$begingroup$
I am trying to translate the following statements into predicate logic using the following predicates: $E(x) = x$ is even, $P(x) = x$ is prime, $L(x,y) = x < y$
(i): Some Primes are Odd.
(ii): Every even number is greater than 1.
(iii): There are infinitely many primes.
(iv): The only even prime is 2.
My attempts were
(i): $neg (forall x P(x) implies E(x))$
My reasoning behind this was that saying $exists x(P(x) land neg E(x))$ just says there is at least 1, rather than some odd primes.
(ii): $forall x E(x) implies L(1,x)$
(iii): $forall x exists y (P(x) land P(y) land L(x,y)$
My reasoning for this one was that this means that for every prime, there is a prime that is greater than it, which means there are infinitely many primes.
I am not really sure how to go about (iv)
Any help is greatly appreciated!!
logic predicate-logic logic-translation
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
$endgroup$
I am trying to translate the following statements into predicate logic using the following predicates: $E(x) = x$ is even, $P(x) = x$ is prime, $L(x,y) = x < y$
(i): Some Primes are Odd.
(ii): Every even number is greater than 1.
(iii): There are infinitely many primes.
(iv): The only even prime is 2.
My attempts were
(i): $neg (forall x P(x) implies E(x))$
My reasoning behind this was that saying $exists x(P(x) land neg E(x))$ just says there is at least 1, rather than some odd primes.
(ii): $forall x E(x) implies L(1,x)$
(iii): $forall x exists y (P(x) land P(y) land L(x,y)$
My reasoning for this one was that this means that for every prime, there is a prime that is greater than it, which means there are infinitely many primes.
I am not really sure how to go about (iv)
Any help is greatly appreciated!!
logic predicate-logic logic-translation
logic predicate-logic logic-translation
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
edited Dec 18 '18 at 1:44
Bram28
63.8k44793
63.8k44793
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
asked Dec 17 '18 at 22:17
martinhynesonemartinhynesone
367
367
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01
add a comment |
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For $ (i) $, both your attempt and the proposition you argue against are actually equivalent, as
$$neg (forall x, P(x) rightarrow E(x)) iff exists x, neg(P(x) rightarrow E(x))$$
$$iff exists x, neg( neg P(x) vee E(x))$$
$$iff exists x, P(x) wedge neg E(x)$$
Your attempt for $ (ii) $ is correct.
Your attempt for $ (iii) $ is incorrect, as that is stating that for all $x$, there exists $y$ such that both $x$ and $y$ are prime and that $x$ is less than $y$. But of course, not every natural number is prime, so the statement must be false. What you want is something like
$$ forall x, exists y, L(x, y) wedge P(y) .$$
This loosely says that primes can be arbitrarily large.
$ (iv) $ corresponds to $$ (P(x) wedge E(x)) rightarrow (L(1, x) wedge L(x, 3))$$
if we're given that $ x in mathbb{N} $ and only have access to predicates $L, E, P$.
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
$endgroup$
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
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
});
}
});
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%2f3044529%2fpredicate-logic-natural-number-problems%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
$begingroup$
For $ (i) $, both your attempt and the proposition you argue against are actually equivalent, as
$$neg (forall x, P(x) rightarrow E(x)) iff exists x, neg(P(x) rightarrow E(x))$$
$$iff exists x, neg( neg P(x) vee E(x))$$
$$iff exists x, P(x) wedge neg E(x)$$
Your attempt for $ (ii) $ is correct.
Your attempt for $ (iii) $ is incorrect, as that is stating that for all $x$, there exists $y$ such that both $x$ and $y$ are prime and that $x$ is less than $y$. But of course, not every natural number is prime, so the statement must be false. What you want is something like
$$ forall x, exists y, L(x, y) wedge P(y) .$$
This loosely says that primes can be arbitrarily large.
$ (iv) $ corresponds to $$ (P(x) wedge E(x)) rightarrow (L(1, x) wedge L(x, 3))$$
if we're given that $ x in mathbb{N} $ and only have access to predicates $L, E, P$.
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
$endgroup$
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
add a comment |
$begingroup$
For $ (i) $, both your attempt and the proposition you argue against are actually equivalent, as
$$neg (forall x, P(x) rightarrow E(x)) iff exists x, neg(P(x) rightarrow E(x))$$
$$iff exists x, neg( neg P(x) vee E(x))$$
$$iff exists x, P(x) wedge neg E(x)$$
Your attempt for $ (ii) $ is correct.
Your attempt for $ (iii) $ is incorrect, as that is stating that for all $x$, there exists $y$ such that both $x$ and $y$ are prime and that $x$ is less than $y$. But of course, not every natural number is prime, so the statement must be false. What you want is something like
$$ forall x, exists y, L(x, y) wedge P(y) .$$
This loosely says that primes can be arbitrarily large.
$ (iv) $ corresponds to $$ (P(x) wedge E(x)) rightarrow (L(1, x) wedge L(x, 3))$$
if we're given that $ x in mathbb{N} $ and only have access to predicates $L, E, P$.
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
$endgroup$
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
add a comment |
$begingroup$
For $ (i) $, both your attempt and the proposition you argue against are actually equivalent, as
$$neg (forall x, P(x) rightarrow E(x)) iff exists x, neg(P(x) rightarrow E(x))$$
$$iff exists x, neg( neg P(x) vee E(x))$$
$$iff exists x, P(x) wedge neg E(x)$$
Your attempt for $ (ii) $ is correct.
Your attempt for $ (iii) $ is incorrect, as that is stating that for all $x$, there exists $y$ such that both $x$ and $y$ are prime and that $x$ is less than $y$. But of course, not every natural number is prime, so the statement must be false. What you want is something like
$$ forall x, exists y, L(x, y) wedge P(y) .$$
This loosely says that primes can be arbitrarily large.
$ (iv) $ corresponds to $$ (P(x) wedge E(x)) rightarrow (L(1, x) wedge L(x, 3))$$
if we're given that $ x in mathbb{N} $ and only have access to predicates $L, E, P$.
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
$endgroup$
For $ (i) $, both your attempt and the proposition you argue against are actually equivalent, as
$$neg (forall x, P(x) rightarrow E(x)) iff exists x, neg(P(x) rightarrow E(x))$$
$$iff exists x, neg( neg P(x) vee E(x))$$
$$iff exists x, P(x) wedge neg E(x)$$
Your attempt for $ (ii) $ is correct.
Your attempt for $ (iii) $ is incorrect, as that is stating that for all $x$, there exists $y$ such that both $x$ and $y$ are prime and that $x$ is less than $y$. But of course, not every natural number is prime, so the statement must be false. What you want is something like
$$ forall x, exists y, L(x, y) wedge P(y) .$$
This loosely says that primes can be arbitrarily large.
$ (iv) $ corresponds to $$ (P(x) wedge E(x)) rightarrow (L(1, x) wedge L(x, 3))$$
if we're given that $ x in mathbb{N} $ and only have access to predicates $L, E, P$.
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
edited Dec 18 '18 at 4:07
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
answered Dec 17 '18 at 22:31
Klint QinamiKlint Qinami
1,137510
1,137510
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
add a comment |
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
1
1
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
although the answer is correct I want to give 2 notes: (1) in the first part you used both $implies$ as part of formula and $iff$ to show equivalent formalization, this is a bad notation, you should either use $rightarrow$ and $iff$ or $implies$ and $equiv$ to make thing clearer. (2) usually it is acceptable that we don't write ∃x, A but (∃x)A or ∃xA.(the overall answer is great +1)
$endgroup$
– Holo
Dec 17 '18 at 22:36
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
$begingroup$
Thank you very much for your answer, it was very helpful!
$endgroup$
– martinhynesone
Dec 17 '18 at 22:44
add a comment |
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.
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%2f3044529%2fpredicate-logic-natural-number-problems%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
$begingroup$
at least one=some, for (iv), The only even prime is 2=all numbers that are prime and not 2 are not even
$endgroup$
– Holo
Dec 17 '18 at 22:28
$begingroup$
The answer for (ii) needs parentheses, to show that $forall x$ applies to the whole implication, not just to $E(x)$.
$endgroup$
– Andreas Blass
Dec 17 '18 at 23:01