Mixing
Which part of this theorem and corresponding proof about relations is incorrect?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have a theorem and corresponding proof whose correctness I need to verify. The theorem is:
For any sets $A$, $B$, $C$, and $D$: $A$ x $B subseteq C$ x $D$ $implies$ $A subseteq C$ $land$ $B subseteq D$
The proof is:
Suppose $A$ x $B subseteq C$ x $D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an aribtrary element of $B$. Then $(a, b) in A$ x $B$. So since $A$ x $B subseteq C$ x $D$, $(a, b) in C$ x $D$. Therefore $a in C$ and $b in D$. Since $a$ and $b$ were arbitrary elements of $A$ and $B$, respectively, this shows that $A subseteq C$ and $B subseteq D$.
The above proof is demonstratably wrong with the case where $A = 1$, and $B = C = D = emptyset$, but I cannot find the flaw in the logic.
Following my own reasoning gives me:
$1)$ Assuming the 'P' of the conditional: $Givens = $$A$ x $B subseteq C$ x $D$, $Goals = A subseteq C, B subseteq D$
$2)$ Assuming arbitrary $a$ and $b$, assuming $a in A$ and $b in B$: $Givens = $$A$ x $B subseteq C$ x $D, a in A, b in B$, $Goals = a in C, b in D$
$3)$ Note that $(a, b) in A$ x $B implies (a, b) in C$ x $D implies a in C land b in D$
$4)$ Since $a in A land b in B$, we can create an ordered pair, $(a, b)$ such that $(a, b) in A$ x $B$, which appears to lead to the conclusion noted in $3)$, thus satisfying our goals.
Which is just a rambling version of the original proof.
elementary-set-theory relations
asked Jul 25 at 22:19
user2780519
133
add a comment |Â
up vote
0
down vote
favorite
I have a theorem and corresponding proof whose correctness I need to verify. The theorem is:
For any sets $A$, $B$, $C$, and $D$: $A$ x $B subseteq C$ x $D$ $implies$ $A subseteq C$ $land$ $B subseteq D$
The proof is:
Suppose $A$ x $B subseteq C$ x $D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an aribtrary element of $B$. Then $(a, b) in A$ x $B$. So since $A$ x $B subseteq C$ x $D$, $(a, b) in C$ x $D$. Therefore $a in C$ and $b in D$. Since $a$ and $b$ were arbitrary elements of $A$ and $B$, respectively, this shows that $A subseteq C$ and $B subseteq D$.
The above proof is demonstratably wrong with the case where $A = 1$, and $B = C = D = emptyset$, but I cannot find the flaw in the logic.
Following my own reasoning gives me:
$1)$ Assuming the 'P' of the conditional: $Givens = $$A$ x $B subseteq C$ x $D$, $Goals = A subseteq C, B subseteq D$
$2)$ Assuming arbitrary $a$ and $b$, assuming $a in A$ and $b in B$: $Givens = $$A$ x $B subseteq C$ x $D, a in A, b in B$, $Goals = a in C, b in D$
$3)$ Note that $(a, b) in A$ x $B implies (a, b) in C$ x $D implies a in C land b in D$
$4)$ Since $a in A land b in B$, we can create an ordered pair, $(a, b)$ such that $(a, b) in A$ x $B$, which appears to lead to the conclusion noted in $3)$, thus satisfying our goals.
Which is just a rambling version of the original proof.
elementary-set-theory relations
asked Jul 25 at 22:19
user2780519
133
2
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have a theorem and corresponding proof whose correctness I need to verify. The theorem is:
For any sets $A$, $B$, $C$, and $D$: $A$ x $B subseteq C$ x $D$ $implies$ $A subseteq C$ $land$ $B subseteq D$
The proof is:
Suppose $A$ x $B subseteq C$ x $D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an aribtrary element of $B$. Then $(a, b) in A$ x $B$. So since $A$ x $B subseteq C$ x $D$, $(a, b) in C$ x $D$. Therefore $a in C$ and $b in D$. Since $a$ and $b$ were arbitrary elements of $A$ and $B$, respectively, this shows that $A subseteq C$ and $B subseteq D$.
The above proof is demonstratably wrong with the case where $A = 1$, and $B = C = D = emptyset$, but I cannot find the flaw in the logic.
Following my own reasoning gives me:
$1)$ Assuming the 'P' of the conditional: $Givens = $$A$ x $B subseteq C$ x $D$, $Goals = A subseteq C, B subseteq D$
$2)$ Assuming arbitrary $a$ and $b$, assuming $a in A$ and $b in B$: $Givens = $$A$ x $B subseteq C$ x $D, a in A, b in B$, $Goals = a in C, b in D$
$3)$ Note that $(a, b) in A$ x $B implies (a, b) in C$ x $D implies a in C land b in D$
$4)$ Since $a in A land b in B$, we can create an ordered pair, $(a, b)$ such that $(a, b) in A$ x $B$, which appears to lead to the conclusion noted in $3)$, thus satisfying our goals.
Which is just a rambling version of the original proof.
elementary-set-theory relations
asked Jul 25 at 22:19
user2780519
133
I have a theorem and corresponding proof whose correctness I need to verify. The theorem is:
For any sets $A$, $B$, $C$, and $D$: $A$ x $B subseteq C$ x $D$ $implies$ $A subseteq C$ $land$ $B subseteq D$
The proof is:
Suppose $A$ x $B subseteq C$ x $D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an aribtrary element of $B$. Then $(a, b) in A$ x $B$. So since $A$ x $B subseteq C$ x $D$, $(a, b) in C$ x $D$. Therefore $a in C$ and $b in D$. Since $a$ and $b$ were arbitrary elements of $A$ and $B$, respectively, this shows that $A subseteq C$ and $B subseteq D$.
The above proof is demonstratably wrong with the case where $A = 1$, and $B = C = D = emptyset$, but I cannot find the flaw in the logic.
Following my own reasoning gives me:
$1)$ Assuming the 'P' of the conditional: $Givens = $$A$ x $B subseteq C$ x $D$, $Goals = A subseteq C, B subseteq D$
$2)$ Assuming arbitrary $a$ and $b$, assuming $a in A$ and $b in B$: $Givens = $$A$ x $B subseteq C$ x $D, a in A, b in B$, $Goals = a in C, b in D$
$3)$ Note that $(a, b) in A$ x $B implies (a, b) in C$ x $D implies a in C land b in D$
$4)$ Since $a in A land b in B$, we can create an ordered pair, $(a, b)$ such that $(a, b) in A$ x $B$, which appears to lead to the conclusion noted in $3)$, thus satisfying our goals.
Which is just a rambling version of the original proof.
elementary-set-theory relations
asked Jul 25 at 22:19
user2780519
133
asked Jul 25 at 22:19
user2780519
133
asked Jul 25 at 22:19
user2780519
133
asked Jul 25 at 22:19
user2780519
133
133
2
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47
add a comment |Â
2
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47
2
2
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
If we rewrite the proof, the flaw becomes more apparent:
Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.
answered Jul 25 at 22:41
Acccumulation
4,4352314
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
If we rewrite the proof, the flaw becomes more apparent:
Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.
answered Jul 25 at 22:41
Acccumulation
4,4352314
add a comment |Â
up vote
0
down vote
accepted
If we rewrite the proof, the flaw becomes more apparent:
Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.
answered Jul 25 at 22:41
Acccumulation
4,4352314
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
If we rewrite the proof, the flaw becomes more apparent:
Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.
answered Jul 25 at 22:41
Acccumulation
4,4352314
If we rewrite the proof, the flaw becomes more apparent:
Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.
answered Jul 25 at 22:41
Acccumulation
4,4352314
answered Jul 25 at 22:41
Acccumulation
4,4352314
answered Jul 25 at 22:41
Acccumulation
4,4352314
answered Jul 25 at 22:41
Acccumulation
4,4352314
4,4352314
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862882%2fwhich-part-of-this-theorem-and-corresponding-proof-about-relations-is-incorrect%23new-answer', 'question_page');
);
Post as a guest
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
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
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
2
"Assuming $ain A$ and $bin B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid.
– JMoravitz
Jul 25 at 22:22
Thank you, so a corrected form of the theorem would be: $A$ x $B subseteq C$ x $D land A neq emptyset land B neq emptyset ...$ $implies$ $A subseteq C$ $land$ $B subseteq D$?
– user2780519
Jul 25 at 22:37
Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..."
– JMoravitz
Jul 25 at 22:40
Cheers, I always end up missing an edge case or two..
– user2780519
Jul 25 at 22:47