Subset relation in a sequence of sets (Proof by induction)
up vote
0
down vote
favorite
I am trying to prove this claim:
Let $G$ be a set of ordered pairs (it is supposed to denote the graph of a relation on a set). Consider the following sequence of sets: $G_1= G$ and $G_{n+1}=G_ncup G_nG_n$. For each $i, jinmathbb{Z}^+$, if $ile j$, then $G_isubseteq G_j$.
I know that the proof is supposed to be done by induction but I am having a hard time with what I'm supposed to carry out induction on. Should I assume that $G_i ⊆ G_j$ as my induction hypothesis to show that $G_{i+1} ⊆ G_{j+1}$ (I'm not even sure if that's valid for induction)? Any help would be much appreciated.
elementary-set-theory induction relations
edited Nov 13 at 23:54
egreg
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
add a comment |
up vote
0
down vote
favorite
I am trying to prove this claim:
Let $G$ be a set of ordered pairs (it is supposed to denote the graph of a relation on a set). Consider the following sequence of sets: $G_1= G$ and $G_{n+1}=G_ncup G_nG_n$. For each $i, jinmathbb{Z}^+$, if $ile j$, then $G_isubseteq G_j$.
I know that the proof is supposed to be done by induction but I am having a hard time with what I'm supposed to carry out induction on. Should I assume that $G_i ⊆ G_j$ as my induction hypothesis to show that $G_{i+1} ⊆ G_{j+1}$ (I'm not even sure if that's valid for induction)? Any help would be much appreciated.
elementary-set-theory induction relations
edited Nov 13 at 23:54
egreg
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
2
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am trying to prove this claim:
Let $G$ be a set of ordered pairs (it is supposed to denote the graph of a relation on a set). Consider the following sequence of sets: $G_1= G$ and $G_{n+1}=G_ncup G_nG_n$. For each $i, jinmathbb{Z}^+$, if $ile j$, then $G_isubseteq G_j$.
I know that the proof is supposed to be done by induction but I am having a hard time with what I'm supposed to carry out induction on. Should I assume that $G_i ⊆ G_j$ as my induction hypothesis to show that $G_{i+1} ⊆ G_{j+1}$ (I'm not even sure if that's valid for induction)? Any help would be much appreciated.
elementary-set-theory induction relations
edited Nov 13 at 23:54
egreg
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
I am trying to prove this claim:
Let $G$ be a set of ordered pairs (it is supposed to denote the graph of a relation on a set). Consider the following sequence of sets: $G_1= G$ and $G_{n+1}=G_ncup G_nG_n$. For each $i, jinmathbb{Z}^+$, if $ile j$, then $G_isubseteq G_j$.
I know that the proof is supposed to be done by induction but I am having a hard time with what I'm supposed to carry out induction on. Should I assume that $G_i ⊆ G_j$ as my induction hypothesis to show that $G_{i+1} ⊆ G_{j+1}$ (I'm not even sure if that's valid for induction)? Any help would be much appreciated.
elementary-set-theory induction relations
elementary-set-theory induction relations
edited Nov 13 at 23:54
egreg
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
edited Nov 13 at 23:54
egreg
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
edited Nov 13 at 23:54
egreg
174k1383198
edited Nov 13 at 23:54
egreg
174k1383198
edited Nov 13 at 23:54
egreg
174k1383198
174k1383198
asked Nov 13 at 23:37
DiscipleOfKant
526
asked Nov 13 at 23:37
DiscipleOfKant
526
asked Nov 13 at 23:37
DiscipleOfKant
526
526
2
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41
add a comment |
2
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41
2
2
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Base case(s) for all $iinBbb Z^+$ we clearly see $G_isubseteq G_i$.
For the induction show for all $(i,j)inBbb Z^{+2}:ileq j$ that if $G_isubseteq G_j$ then $G_isubseteq G_{j+1}$
(Ps: easily done by demonstrating for all $jin Bbb Z^+$ that $G_jsubseteq G_{j+1}$)
You are proving induction on iterations of $j$. $$begin{split}forall iinBbb Z^+~&~P(i,i)\ forall iinBbb Z^+~forall jinBbb Z^+~&~(P(i,j)to P(i,j+1))\hlinethereforequad forall iinBbb Z^+~forall jinBbb Z^+~&~P(i,j)end{split}$$
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Base case(s) for all $iinBbb Z^+$ we clearly see $G_isubseteq G_i$.
For the induction show for all $(i,j)inBbb Z^{+2}:ileq j$ that if $G_isubseteq G_j$ then $G_isubseteq G_{j+1}$
(Ps: easily done by demonstrating for all $jin Bbb Z^+$ that $G_jsubseteq G_{j+1}$)
You are proving induction on iterations of $j$. $$begin{split}forall iinBbb Z^+~&~P(i,i)\ forall iinBbb Z^+~forall jinBbb Z^+~&~(P(i,j)to P(i,j+1))\hlinethereforequad forall iinBbb Z^+~forall jinBbb Z^+~&~P(i,j)end{split}$$
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
add a comment |
up vote
1
down vote
accepted
Base case(s) for all $iinBbb Z^+$ we clearly see $G_isubseteq G_i$.
For the induction show for all $(i,j)inBbb Z^{+2}:ileq j$ that if $G_isubseteq G_j$ then $G_isubseteq G_{j+1}$
(Ps: easily done by demonstrating for all $jin Bbb Z^+$ that $G_jsubseteq G_{j+1}$)
You are proving induction on iterations of $j$. $$begin{split}forall iinBbb Z^+~&~P(i,i)\ forall iinBbb Z^+~forall jinBbb Z^+~&~(P(i,j)to P(i,j+1))\hlinethereforequad forall iinBbb Z^+~forall jinBbb Z^+~&~P(i,j)end{split}$$
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Base case(s) for all $iinBbb Z^+$ we clearly see $G_isubseteq G_i$.
For the induction show for all $(i,j)inBbb Z^{+2}:ileq j$ that if $G_isubseteq G_j$ then $G_isubseteq G_{j+1}$
(Ps: easily done by demonstrating for all $jin Bbb Z^+$ that $G_jsubseteq G_{j+1}$)
You are proving induction on iterations of $j$. $$begin{split}forall iinBbb Z^+~&~P(i,i)\ forall iinBbb Z^+~forall jinBbb Z^+~&~(P(i,j)to P(i,j+1))\hlinethereforequad forall iinBbb Z^+~forall jinBbb Z^+~&~P(i,j)end{split}$$
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
Base case(s) for all $iinBbb Z^+$ we clearly see $G_isubseteq G_i$.
For the induction show for all $(i,j)inBbb Z^{+2}:ileq j$ that if $G_isubseteq G_j$ then $G_isubseteq G_{j+1}$
(Ps: easily done by demonstrating for all $jin Bbb Z^+$ that $G_jsubseteq G_{j+1}$)
You are proving induction on iterations of $j$. $$begin{split}forall iinBbb Z^+~&~P(i,i)\ forall iinBbb Z^+~forall jinBbb Z^+~&~(P(i,j)to P(i,j+1))\hlinethereforequad forall iinBbb Z^+~forall jinBbb Z^+~&~P(i,j)end{split}$$
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
edited Nov 14 at 3:15
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
answered Nov 13 at 23:53
Graham Kemp
84.2k43378
84.2k43378
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2997526%2fsubset-relation-in-a-sequence-of-sets-proof-by-induction%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
2
What do you mean by $G_nG_n$? Is $G$ a subset of $mathbb{R}^2$ or something? If so, tell us what. If not, what do you mean? However, it doesn't actually matter what $G_nG_n$ is for the question: you could replace it with any old set that you like, and the result would still hold: note that, by definition of $G_{i+1}$, $G_i subseteq G_{i+1}$. A simple induction argument will then show you that $G_i subseteq G_j$ for all $j geq i$ (via the transitivity of $subseteq$: if $G_i subseteq G_j$ for some $j geq i$, then $G_i subseteq G_j subseteq G_{j+1}$, so $G_i subseteq G_{j+1}$.
– user3482749
Nov 13 at 23:46
Sorry for the delayed response, but thank you for your help. G is the graph of a binary relation on a set. For example, suppose the relation R = < $D , G$ > (where the domain and codomain of the relation are both the set D, then G is a subset of $D^2$. By $G_nG_n$, I simply mean the composition of the graph with itself.
– DiscipleOfKant
Nov 16 at 14:41