Mixing
Equivalence relation involving finiteness of symmetric difference of sets
$begingroup$
I'm posting this message so as to know if it would possible to get a hint so as to solve the following problem: A subset $A$ of $mathbb N$ is related to a subset $B$ of $mathbb N$ (A%B) if the symmetric difference of the two sets is a finite set.
I managed to prove the reflexive and symetric property of this relation but I'm stuck for proving the transitive proporty. As a matter of fact, I don't know how to deal with it when the sets are infinite. For example, I notice that if the set A = {2.k , $k in mathbb N$} - {2} is related to the set B = { 2.k | $k . in mathbb N$} $cup$ {3}. This would mean that the set $C$ has to be of the form C {2.k | $k in mathbb N$}. Nevertheless this is just an example, I don't know how to generalize it if it's transitive (it may seem that yes it's).
Thank you in advance for your feedback.
elementary-set-theory equivalence-relations
edited Feb 3 at 11:32
Jean Marie
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
$endgroup$
add a comment |
$begingroup$
I'm posting this message so as to know if it would possible to get a hint so as to solve the following problem: A subset $A$ of $mathbb N$ is related to a subset $B$ of $mathbb N$ (A%B) if the symmetric difference of the two sets is a finite set.
I managed to prove the reflexive and symetric property of this relation but I'm stuck for proving the transitive proporty. As a matter of fact, I don't know how to deal with it when the sets are infinite. For example, I notice that if the set A = {2.k , $k in mathbb N$} - {2} is related to the set B = { 2.k | $k . in mathbb N$} $cup$ {3}. This would mean that the set $C$ has to be of the form C {2.k | $k in mathbb N$}. Nevertheless this is just an example, I don't know how to generalize it if it's transitive (it may seem that yes it's).
Thank you in advance for your feedback.
elementary-set-theory equivalence-relations
edited Feb 3 at 11:32
Jean Marie
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
$endgroup$
$begingroup$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44
add a comment |
$begingroup$
I'm posting this message so as to know if it would possible to get a hint so as to solve the following problem: A subset $A$ of $mathbb N$ is related to a subset $B$ of $mathbb N$ (A%B) if the symmetric difference of the two sets is a finite set.
I managed to prove the reflexive and symetric property of this relation but I'm stuck for proving the transitive proporty. As a matter of fact, I don't know how to deal with it when the sets are infinite. For example, I notice that if the set A = {2.k , $k in mathbb N$} - {2} is related to the set B = { 2.k | $k . in mathbb N$} $cup$ {3}. This would mean that the set $C$ has to be of the form C {2.k | $k in mathbb N$}. Nevertheless this is just an example, I don't know how to generalize it if it's transitive (it may seem that yes it's).
Thank you in advance for your feedback.
elementary-set-theory equivalence-relations
edited Feb 3 at 11:32
Jean Marie
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
$endgroup$
I'm posting this message so as to know if it would possible to get a hint so as to solve the following problem: A subset $A$ of $mathbb N$ is related to a subset $B$ of $mathbb N$ (A%B) if the symmetric difference of the two sets is a finite set.
I managed to prove the reflexive and symetric property of this relation but I'm stuck for proving the transitive proporty. As a matter of fact, I don't know how to deal with it when the sets are infinite. For example, I notice that if the set A = {2.k , $k in mathbb N$} - {2} is related to the set B = { 2.k | $k . in mathbb N$} $cup$ {3}. This would mean that the set $C$ has to be of the form C {2.k | $k in mathbb N$}. Nevertheless this is just an example, I don't know how to generalize it if it's transitive (it may seem that yes it's).
Thank you in advance for your feedback.
elementary-set-theory equivalence-relations
elementary-set-theory equivalence-relations
edited Feb 3 at 11:32
Jean Marie
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
edited Feb 3 at 11:32
Jean Marie
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
edited Feb 3 at 11:32
Jean Marie
31.5k42355
edited Feb 3 at 11:32
Jean Marie
31.5k42355
edited Feb 3 at 11:32
Jean Marie
31.5k42355
31.5k42355
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
asked Feb 3 at 8:52
Hugo PeyronHugo Peyron
244
244
$begingroup$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44
add a comment |
$begingroup$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44
$begingroup$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44
$begingroup$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The symmetric difference of A and B is finite,
iff A and B differ in a finite number of points.
Is this sufficient insight to prove transitivity?
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
$endgroup$
add a comment |
$begingroup$
I'll denote the symmetric difference of $A$ and $B$ by $A Delta B$, as is customary.
Then $$A Delta C subseteq (A Delta B) cup (B Delta C)$$
Proof: let $x in A Delta C$. Case 1: $x in A$ and $x notin C$, then if $x in B$ then $x in B setminus C$ so $x in B Delta C$ and if $x notin B$, then $x in A setminus B$ so $x in A Delta B$. Case 2, where $x in C$ and $x notin A$ is similar, again two subcases depending on $x in B$ or not.
If then $A sim B$ and $B sim C$, then the above inclusion shows that $A Delta C $ is a subset of a union of two finite sets, hence finite and so $A sim C$ too.
In your example, $A Delta B = {2,3}$ and many sets $C$ are related to $B$, e.g. all sets of the form ${2n: n in mathbb{N}} cup F$, where $F$ is finite.
$C$ need not be of the exact form you mention.
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
add a comment |
$begingroup$
Here is a proof almost without words, using a Venn diagram, where symbol "F" means "finite". We use the fact that a subset of a finite set is itself a finite set.
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
$endgroup$
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
add a comment |
Your Answer
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%2f3098331%2fequivalence-relation-involving-finiteness-of-symmetric-difference-of-sets%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The symmetric difference of A and B is finite,
iff A and B differ in a finite number of points.
Is this sufficient insight to prove transitivity?
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
$endgroup$
add a comment |
$begingroup$
The symmetric difference of A and B is finite,
iff A and B differ in a finite number of points.
Is this sufficient insight to prove transitivity?
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
$endgroup$
add a comment |
$begingroup$
The symmetric difference of A and B is finite,
iff A and B differ in a finite number of points.
Is this sufficient insight to prove transitivity?
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
$endgroup$
The symmetric difference of A and B is finite,
iff A and B differ in a finite number of points.
Is this sufficient insight to prove transitivity?
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
answered Feb 3 at 9:43
William ElliotWilliam Elliot
9,1962820
9,1962820
add a comment |
add a comment |
$begingroup$
I'll denote the symmetric difference of $A$ and $B$ by $A Delta B$, as is customary.
Then $$A Delta C subseteq (A Delta B) cup (B Delta C)$$
Proof: let $x in A Delta C$. Case 1: $x in A$ and $x notin C$, then if $x in B$ then $x in B setminus C$ so $x in B Delta C$ and if $x notin B$, then $x in A setminus B$ so $x in A Delta B$. Case 2, where $x in C$ and $x notin A$ is similar, again two subcases depending on $x in B$ or not.
If then $A sim B$ and $B sim C$, then the above inclusion shows that $A Delta C $ is a subset of a union of two finite sets, hence finite and so $A sim C$ too.
In your example, $A Delta B = {2,3}$ and many sets $C$ are related to $B$, e.g. all sets of the form ${2n: n in mathbb{N}} cup F$, where $F$ is finite.
$C$ need not be of the exact form you mention.
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
add a comment |
$begingroup$
I'll denote the symmetric difference of $A$ and $B$ by $A Delta B$, as is customary.
Then $$A Delta C subseteq (A Delta B) cup (B Delta C)$$
Proof: let $x in A Delta C$. Case 1: $x in A$ and $x notin C$, then if $x in B$ then $x in B setminus C$ so $x in B Delta C$ and if $x notin B$, then $x in A setminus B$ so $x in A Delta B$. Case 2, where $x in C$ and $x notin A$ is similar, again two subcases depending on $x in B$ or not.
If then $A sim B$ and $B sim C$, then the above inclusion shows that $A Delta C $ is a subset of a union of two finite sets, hence finite and so $A sim C$ too.
In your example, $A Delta B = {2,3}$ and many sets $C$ are related to $B$, e.g. all sets of the form ${2n: n in mathbb{N}} cup F$, where $F$ is finite.
$C$ need not be of the exact form you mention.
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
add a comment |
$begingroup$
I'll denote the symmetric difference of $A$ and $B$ by $A Delta B$, as is customary.
Then $$A Delta C subseteq (A Delta B) cup (B Delta C)$$
Proof: let $x in A Delta C$. Case 1: $x in A$ and $x notin C$, then if $x in B$ then $x in B setminus C$ so $x in B Delta C$ and if $x notin B$, then $x in A setminus B$ so $x in A Delta B$. Case 2, where $x in C$ and $x notin A$ is similar, again two subcases depending on $x in B$ or not.
If then $A sim B$ and $B sim C$, then the above inclusion shows that $A Delta C $ is a subset of a union of two finite sets, hence finite and so $A sim C$ too.
In your example, $A Delta B = {2,3}$ and many sets $C$ are related to $B$, e.g. all sets of the form ${2n: n in mathbb{N}} cup F$, where $F$ is finite.
$C$ need not be of the exact form you mention.
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
I'll denote the symmetric difference of $A$ and $B$ by $A Delta B$, as is customary.
Then $$A Delta C subseteq (A Delta B) cup (B Delta C)$$
Proof: let $x in A Delta C$. Case 1: $x in A$ and $x notin C$, then if $x in B$ then $x in B setminus C$ so $x in B Delta C$ and if $x notin B$, then $x in A setminus B$ so $x in A Delta B$. Case 2, where $x in C$ and $x notin A$ is similar, again two subcases depending on $x in B$ or not.
If then $A sim B$ and $B sim C$, then the above inclusion shows that $A Delta C $ is a subset of a union of two finite sets, hence finite and so $A sim C$ too.
In your example, $A Delta B = {2,3}$ and many sets $C$ are related to $B$, e.g. all sets of the form ${2n: n in mathbb{N}} cup F$, where $F$ is finite.
$C$ need not be of the exact form you mention.
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
answered Feb 3 at 18:01
Henno BrandsmaHenno Brandsma
116k349127
116k349127
add a comment |
add a comment |
$begingroup$
Here is a proof almost without words, using a Venn diagram, where symbol "F" means "finite". We use the fact that a subset of a finite set is itself a finite set.
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
$endgroup$
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
add a comment |
$begingroup$
Here is a proof almost without words, using a Venn diagram, where symbol "F" means "finite". We use the fact that a subset of a finite set is itself a finite set.
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
$endgroup$
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
add a comment |
$begingroup$
Here is a proof almost without words, using a Venn diagram, where symbol "F" means "finite". We use the fact that a subset of a finite set is itself a finite set.
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
$endgroup$
Here is a proof almost without words, using a Venn diagram, where symbol "F" means "finite". We use the fact that a subset of a finite set is itself a finite set.
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
answered Feb 3 at 18:14
Jean MarieJean Marie
31.5k42355
31.5k42355
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
add a comment |
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
$begingroup$
Usually, people are reluctant to consider proofs using Venn (or Karnaugh diagrams) as true proofs. It's a pity because they are as valid as other proofs, accepting that a proof doesn't necessarily need to be verbalized. Your opinion ?
$endgroup$
– Jean Marie
Feb 4 at 10:46
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%2f3098331%2fequivalence-relation-involving-finiteness-of-symmetric-difference-of-sets%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$
Related : math.stackexchange.com/q/198657. Google query "finite symmetric difference" brings an amazing lot of answers, in particular in the domain of theoretical computer science.
$endgroup$
– Jean Marie
Feb 3 at 11:44