Predicate Logic Natural Number Problems












0












$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!!










share|cite|improve this question











$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
















0












$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!!










share|cite|improve this question











$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














0












0








0





$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!!










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 18 '18 at 1:44









Bram28

63.8k44793




63.8k44793










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


















  • $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










1 Answer
1






active

oldest

votes


















2












$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$.






share|cite|improve this answer











$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











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
});


}
});














draft saved

draft discarded


















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









2












$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$.






share|cite|improve this answer











$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
















2












$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$.






share|cite|improve this answer











$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














2












2








2





$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$.






share|cite|improve this answer











$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$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 18 '18 at 4:07

























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














  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Plaza Victoria

Puebla de Zaragoza

Musa