Rules of distribution of quantifiers over conditional and biconditional
$begingroup$
Which of the following propositional logic statements are true and why?
- $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
- $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
- $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
$(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$
Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?
Also rules for distribution of existential quantifier over conditional and binconditional?
Recently I came across distribution of quantifiers over $vee$ and $wedge$, which gave set theoretic interpretation of them as follows:
$((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$
In set theoretic terms,
if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$
$(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$
In set theoretic terms,
if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$
Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?
logic predicate-logic first-order-logic quantifiers
asked Jan 1 '16 at 21:20
anir123anir123
8801029
$endgroup$
add a comment |
$begingroup$
Which of the following propositional logic statements are true and why?
- $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
- $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
- $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
$(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$
Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?
Also rules for distribution of existential quantifier over conditional and binconditional?
Recently I came across distribution of quantifiers over $vee$ and $wedge$, which gave set theoretic interpretation of them as follows:
$((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$
In set theoretic terms,
if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$
$(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$
In set theoretic terms,
if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$
Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?
logic predicate-logic first-order-logic quantifiers
asked Jan 1 '16 at 21:20
anir123anir123
8801029
$endgroup$
$begingroup$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
1
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33
add a comment |
$begingroup$
Which of the following propositional logic statements are true and why?
- $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
- $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
- $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
$(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$
Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?
Also rules for distribution of existential quantifier over conditional and binconditional?
Recently I came across distribution of quantifiers over $vee$ and $wedge$, which gave set theoretic interpretation of them as follows:
$((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$
In set theoretic terms,
if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$
$(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$
In set theoretic terms,
if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$
Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?
logic predicate-logic first-order-logic quantifiers
asked Jan 1 '16 at 21:20
anir123anir123
8801029
$endgroup$
Which of the following propositional logic statements are true and why?
- $(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))$
- $(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))$
- $(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))$
$(∀x(P(x)⇔Q(x)))⟹(∀x(P(x))⇔(∀x(Q(x))))$
Are their any standard laws/rules of distribution of universal quantifier over conditional and binconditional that can help me solve this?
Also rules for distribution of existential quantifier over conditional and binconditional?
Recently I came across distribution of quantifiers over $vee$ and $wedge$, which gave set theoretic interpretation of them as follows:
$((∀x)G(x)∨ (∀x)H(x))→ (∀x)(F(x)∨ G(x))$
In set theoretic terms,
if we have that $(f(G) = D ∨ f(H) = D)$, then we have $(f(G) ∪ f(H)) = D$
$(∃x)(G(x)∧ H(x))→((∃x)G(x)∧ (∃x)H(x))$
In set theoretic terms,
if we have that $(f(G) ∩ f(H)) ≥ 1$, then we have $(f(G) ≥ 1 ∧ f(H) ≥ 1)$
Can we say similar for distribution of quantifiers over conditional and biconditional (just to bring in more clarity)?
logic predicate-logic first-order-logic quantifiers
logic predicate-logic first-order-logic quantifiers
asked Jan 1 '16 at 21:20
anir123anir123
8801029
asked Jan 1 '16 at 21:20
anir123anir123
8801029
edited Jan 1 '16 at 21:50
anir123
asked Jan 1 '16 at 21:20
anir123anir123
8801029
asked Jan 1 '16 at 21:20
anir123anir123
8801029
asked Jan 1 '16 at 21:20
anir123anir123
8801029
8801029
$begingroup$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
1
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33
add a comment |
$begingroup$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
1
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33
$begingroup$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
1
1
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Formulas (1) and (4) are valid, i.e. they are true in every first-order $mathcal{L}$-structure.
Formulas (2) and (3) are not valid, i.e. there exists a $mathcal{L}$-structure in which they are not true. For instance, take the $mathcal{L}$-structure $mathcal{N}$ whose domain is $mathbb{N}$ and whose interpretation of $P$ is $2mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $mathbb{N} smallsetminus 2mathbb{N}$ (the set of odd natural numbers). You have that the formula $forall xP(x) Rightarrow forall x Q(x)$ is vacuously true in $mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $forall x(P(x) Rightarrow Q(x))$ is false in $mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $mathcal{N}$. Similarly for the formula (3), since $A Leftrightarrow B$ is equivalent to $(A Rightarrow B) land (B Rightarrow A)$.
In general, when one talks about distributivity of something over something else (for instance, distributivity of $land$ over $lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $forall xP(x) Rightarrow forall x Q(x)$ is not logically equivalent to the formula $forall x(P(x) Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $forall xP(x) Leftrightarrow forall x Q(x)$ is not logically equivalent to formula $forall x(P(x) Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
$endgroup$
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
|
show 3 more comments
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%2f1596451%2frules-of-distribution-of-quantifiers-over-conditional-and-biconditional%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$
Formulas (1) and (4) are valid, i.e. they are true in every first-order $mathcal{L}$-structure.
Formulas (2) and (3) are not valid, i.e. there exists a $mathcal{L}$-structure in which they are not true. For instance, take the $mathcal{L}$-structure $mathcal{N}$ whose domain is $mathbb{N}$ and whose interpretation of $P$ is $2mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $mathbb{N} smallsetminus 2mathbb{N}$ (the set of odd natural numbers). You have that the formula $forall xP(x) Rightarrow forall x Q(x)$ is vacuously true in $mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $forall x(P(x) Rightarrow Q(x))$ is false in $mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $mathcal{N}$. Similarly for the formula (3), since $A Leftrightarrow B$ is equivalent to $(A Rightarrow B) land (B Rightarrow A)$.
In general, when one talks about distributivity of something over something else (for instance, distributivity of $land$ over $lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $forall xP(x) Rightarrow forall x Q(x)$ is not logically equivalent to the formula $forall x(P(x) Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $forall xP(x) Leftrightarrow forall x Q(x)$ is not logically equivalent to formula $forall x(P(x) Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
$endgroup$
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
|
show 3 more comments
$begingroup$
Formulas (1) and (4) are valid, i.e. they are true in every first-order $mathcal{L}$-structure.
Formulas (2) and (3) are not valid, i.e. there exists a $mathcal{L}$-structure in which they are not true. For instance, take the $mathcal{L}$-structure $mathcal{N}$ whose domain is $mathbb{N}$ and whose interpretation of $P$ is $2mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $mathbb{N} smallsetminus 2mathbb{N}$ (the set of odd natural numbers). You have that the formula $forall xP(x) Rightarrow forall x Q(x)$ is vacuously true in $mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $forall x(P(x) Rightarrow Q(x))$ is false in $mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $mathcal{N}$. Similarly for the formula (3), since $A Leftrightarrow B$ is equivalent to $(A Rightarrow B) land (B Rightarrow A)$.
In general, when one talks about distributivity of something over something else (for instance, distributivity of $land$ over $lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $forall xP(x) Rightarrow forall x Q(x)$ is not logically equivalent to the formula $forall x(P(x) Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $forall xP(x) Leftrightarrow forall x Q(x)$ is not logically equivalent to formula $forall x(P(x) Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
$endgroup$
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
|
show 3 more comments
$begingroup$
Formulas (1) and (4) are valid, i.e. they are true in every first-order $mathcal{L}$-structure.
Formulas (2) and (3) are not valid, i.e. there exists a $mathcal{L}$-structure in which they are not true. For instance, take the $mathcal{L}$-structure $mathcal{N}$ whose domain is $mathbb{N}$ and whose interpretation of $P$ is $2mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $mathbb{N} smallsetminus 2mathbb{N}$ (the set of odd natural numbers). You have that the formula $forall xP(x) Rightarrow forall x Q(x)$ is vacuously true in $mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $forall x(P(x) Rightarrow Q(x))$ is false in $mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $mathcal{N}$. Similarly for the formula (3), since $A Leftrightarrow B$ is equivalent to $(A Rightarrow B) land (B Rightarrow A)$.
In general, when one talks about distributivity of something over something else (for instance, distributivity of $land$ over $lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $forall xP(x) Rightarrow forall x Q(x)$ is not logically equivalent to the formula $forall x(P(x) Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $forall xP(x) Leftrightarrow forall x Q(x)$ is not logically equivalent to formula $forall x(P(x) Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
$endgroup$
Formulas (1) and (4) are valid, i.e. they are true in every first-order $mathcal{L}$-structure.
Formulas (2) and (3) are not valid, i.e. there exists a $mathcal{L}$-structure in which they are not true. For instance, take the $mathcal{L}$-structure $mathcal{N}$ whose domain is $mathbb{N}$ and whose interpretation of $P$ is $2mathbb{N}$ (the set of even natural numbers), and whose interpretation of $Q$ is $mathbb{N} smallsetminus 2mathbb{N}$ (the set of odd natural numbers). You have that the formula $forall xP(x) Rightarrow forall x Q(x)$ is vacuously true in $mathcal{N}$ (it claims that "if every natural number is even then every natural number is odd"), but the formula $forall x(P(x) Rightarrow Q(x))$ is false in $mathcal{N}$ (it claims that "for every natural number, if it is even then it is odd"), therefore your formula (2) is false in $mathcal{N}$. Similarly for the formula (3), since $A Leftrightarrow B$ is equivalent to $(A Rightarrow B) land (B Rightarrow A)$.
In general, when one talks about distributivity of something over something else (for instance, distributivity of $land$ over $lor$), one means that two formulas are logically equivalent. With this meaning, the answer to your question "Does the universal quantifier distribute over conditional or biconditional?" is negative since the formula $forall xP(x) Rightarrow forall x Q(x)$ is not logically equivalent to the formula $forall x(P(x) Rightarrow Q(x))$ (your formula (1) is valid, but your formula (2) is not valid), and similarly the formula $forall xP(x) Leftrightarrow forall x Q(x)$ is not logically equivalent to formula $forall x(P(x) Leftrightarrow Q(x))$ (your formula (4) is valid, but your formula (3) is not valid).
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
edited Jan 2 '16 at 16:09
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
answered Jan 1 '16 at 21:42
TaroccoesbroccoTaroccoesbrocco
5,64271840
5,64271840
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
|
show 3 more comments
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
Well I have not taken a dedicated course on mathematical strucutres or read any books specifically on mathematical structures. So I am finding it difficult to deal with $L$-structure thingy...
$endgroup$
– anir123
Jan 2 '16 at 9:10
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...However,if interprete $P(x)$ as "x is a boy" & "$Q(x)$ is clever". Then, $(∀x(P(x)⇔Q(x)))$ means "If any $x$ is a boy then he is clever & vice versa". This definitely implies $(∀x(P(x))⇔(∀x(Q(x))))$, "If all $x$ are boys then all are clever & vice versa". But converse does not seem valid as $(∀x(P(x))⇔(∀x(Q(x))))$ puts restriction: "if all $x$ are boys". $(∀x(P(x)⇔Q(x)))$ requires that "for any $x$, if $x$ is a boy", but does not require that "all $x$ are boys", so there may be a person who is not boy, but still $(∀x(P(x)⇔Q(x)))$ will be valid but $(∀x(P(x))⇔(∀x(Q(x))))$ will not be...
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
...So 3 seems invalid to me, while 4 seems valid. Also what about distributing existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 9:11
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
@PardonMeForMySuperPoorMaths: Sorry, there was a typo in my answer, now I fixed it. Your formula (4) is the "biconditional version" of your formula (1), and your formula (3) is the "biconditional version" of your formula (2).
$endgroup$
– Taroccoesbrocco
Jan 2 '16 at 10:14
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
$begingroup$
any comment about the same but involving existential quantifier?
$endgroup$
– anir123
Jan 2 '16 at 12:50
|
show 3 more comments
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%2f1596451%2frules-of-distribution-of-quantifiers-over-conditional-and-biconditional%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$
The above formulas are not propositional, since they use quantifiers. They are just formulas of first-order logic.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:23
$begingroup$
Do you want me to change the title to something else?
$endgroup$
– anir123
Jan 1 '16 at 21:25
$begingroup$
Yes, the title is misleading, as well as the tag "propositional calculus".
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:27
1
$begingroup$
Does the new one makes sense "Rules of distribution of quantifiers over conditional and biconditional makes sense?"
$endgroup$
– anir123
Jan 1 '16 at 21:31
$begingroup$
Now the title is ok for me.
$endgroup$
– Taroccoesbrocco
Jan 1 '16 at 21:33