Mixing
What is my mistake in proving that $Asubseteq B$ implies $Bsubseteq A$?
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited yesterday
Asaf Karagila♦
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse 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 |
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited yesterday
Asaf Karagila♦
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
edited yesterday
Asaf Karagila♦
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
It's legitimate to use a tautology in any proof at any time right? Also whenever P and P $implies$ Q appears I Can announce Q, the reason being modes pones rule. So where is the mistake here?
Proof that $A subseteq B implies B subseteq A$:
- Assume $A subseteq B$
- Suppose $x in A$
$A subseteq B implies (x in A implies x in B)$ (Definition of subset)
$x in A implies x in B$ (Modus pones step 1 and 3)
$x in B$ (Modus pones step 2 and 4)
$x in A implies (x in B implies x in A )$ (tautology $q implies (p implies q)$)
$x in B implies x in A$ (Modus pones step 2 and 6)
$x in B implies x in A implies B subseteq A$ (Definition of subset)
$B subseteq A$ (Modus pones step 7 and 8)
$B subseteq A implies (A subseteq B implies B subseteq A)$ (tautology)
$A subseteq B implies B subseteq A$ (Modus pones step 9 and 10).
elementary-set-theory logic
elementary-set-theory logic
edited yesterday
Asaf Karagila♦
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Asaf Karagila♦
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Asaf Karagila♦
299k32420750
edited yesterday
Asaf Karagila♦
299k32420750
edited yesterday
Asaf Karagila♦
299k32420750
299k32420750
asked yesterday
tnstse
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
tnstse
111
asked yesterday
tnstse
111
111
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
tnstse is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday
add a comment |
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday
1
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
1
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday
add a comment |
2 Answers
2
active
oldest
votes
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered yesterday
Mauro ALLEGRANZA
63.4k448110
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered yesterday
Graham Kemp
83.9k43378
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered yesterday
Mauro ALLEGRANZA
63.4k448110
add a comment |
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered yesterday
Mauro ALLEGRANZA
63.4k448110
add a comment |
up vote
5
down vote
up vote
5
down vote
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered yesterday
Mauro ALLEGRANZA
63.4k448110
Long comment
The wrong proof is :
1) Assume : $A ⊆ B$
2) Suppose : $x ∈ A$
3) $forall x (x∈A⟹x∈B)$ --- definition of subset [not used]
4) $x ∈ A ⟹ x∈B$ --- by Universal instantiation [not used]
5) $x∈B$ --- from 2) and 4) by Modus pones [not used]
6) $x∈A ⟹ (x∈B ⟹ x∈A)$ --- from tautology : $q⟹(p⟹q)$
7) $x∈B ⟹ x∈A$ --- by Modus pones from 2) and 6)
But we cannot apply the definition of subset to 7) in order to conclude with $B⊆A$ because we have not yet proved : $forall x (x∈B ⟹ x∈A)$.
The "obvious" step is to apply Universal generalization to 7), but this move is invalid, because $x$ is free in assumption 2).
Intuitively, we have chosen an $x$ such that $x$ belongs to $A$ and we have derived, with this assumption, that $x∈B ⟹ x∈A$; but this does not mean that the formula that we have derived holds for $x$ whatever.
answered yesterday
Mauro ALLEGRANZA
63.4k448110
edited yesterday
answered yesterday
Mauro ALLEGRANZA
63.4k448110
answered yesterday
Mauro ALLEGRANZA
63.4k448110
answered yesterday
Mauro ALLEGRANZA
63.4k448110
63.4k448110
add a comment |
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered yesterday
Graham Kemp
83.9k43378
add a comment |
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered yesterday
Graham Kemp
83.9k43378
add a comment |
up vote
1
down vote
up vote
1
down vote
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered yesterday
Graham Kemp
83.9k43378
Your definition of subset is incorrect, as it should be a universal quantified statement.
Certainly should we suppose that for any $x$ which satisfies $xin A$, we may derive $xin Bto xin A$. However, this is not the same as deriving $forall x~(xin Bto xin A)$ , which is the actual definition for $Bsubseteq A$. All you can prove from this line of reasoning is that $Acap Bsubseteq A$.
$$forall x~(xin Ato(xin Bto xin A))\forall x~((xin Awedge xin B)to xin A)\forall x~(xin Acap Bto xin A)\Acap Bsubseteq A$$
answered yesterday
Graham Kemp
83.9k43378
answered yesterday
Graham Kemp
83.9k43378
answered yesterday
Graham Kemp
83.9k43378
answered yesterday
Graham Kemp
83.9k43378
83.9k43378
add a comment |
add a comment |
tnstse is a new contributor. Be nice, and check out our Code of Conduct.
tnstse is a new contributor. Be nice, and check out our Code of Conduct.
tnstse is a new contributor. Be nice, and check out our Code of Conduct.
tnstse 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%2f3004613%2fwhat-is-my-mistake-in-proving-that-a-subseteq-b-implies-b-subseteq-a%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
1
The definition of subset : $A subseteq B$ is : $forall x (x in A to x in B)$. It is a predicate logic formula and not a priopositional one.
– Mauro ALLEGRANZA
yesterday
1
$Bsubseteq A$ means $forall x(xin Bimplies xin A)$, but you have only obtained $forall x(xin Aimplies(xin Bimplies xin A))$.
– Lord Shark the Unknown
yesterday
The set A = {1, 2} is a subset of B = {1, 2, 3}, the expressions A ⊆ B is true but is B ⊆ A? This is probably true only if A=B.
– NoChance
yesterday
@NoChance thanks for the counter example, but i did point out that the proof is invalid. I wanted to know which step is wrong. frustratingly, none of the comments helped me.
– tnstse
yesterday
As @LordSharktheUnknown points out, the problem is that in step 8, your definition of subset uses the label $x$ to denote any element. In the previous lines you use the label $x$ to denote any element of $A$. You then conflate the two, essentially applying the subset definition only to those elements that are already in $A$ instead of to all possible elements, and thereby ignoring all elements in $B$ $A$.
– Jaap Scherphuis
yesterday