Can I use mathematical induction here?

Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Given any digraph $D=(V,E)$ such that for every finite subset $Ssubseteq V$ there exists a vertex $v_Sin V$ capable of reaching any vertex in $S$ via a directed path.
Can one deduce there is a vertex $uin V$ capable of reaching any vertex in $V$ via a directed path?
Do I have to assume $V$ itself is finite for this to work? Or can I make this deduction irregardless of the cardinality of $V$? I know if I have two subsets $A,Bsubseteq V$, where every vertex in $A$ is reachable by $v_A$ and every vertex in $B$ is reachble by $v_B$ then, since $v_A,v_Bsubseteq V$ there must exist a vertex $u$ capable of reaching both $v_A$ and $v_B$ which means $u$ is capable of reaching every vertex in $Acup B$.
graph-theory induction transfinite-induction
add a comment |Â
up vote
3
down vote
favorite
Given any digraph $D=(V,E)$ such that for every finite subset $Ssubseteq V$ there exists a vertex $v_Sin V$ capable of reaching any vertex in $S$ via a directed path.
Can one deduce there is a vertex $uin V$ capable of reaching any vertex in $V$ via a directed path?
Do I have to assume $V$ itself is finite for this to work? Or can I make this deduction irregardless of the cardinality of $V$? I know if I have two subsets $A,Bsubseteq V$, where every vertex in $A$ is reachable by $v_A$ and every vertex in $B$ is reachble by $v_B$ then, since $v_A,v_Bsubseteq V$ there must exist a vertex $u$ capable of reaching both $v_A$ and $v_B$ which means $u$ is capable of reaching every vertex in $Acup B$.
graph-theory induction transfinite-induction
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Given any digraph $D=(V,E)$ such that for every finite subset $Ssubseteq V$ there exists a vertex $v_Sin V$ capable of reaching any vertex in $S$ via a directed path.
Can one deduce there is a vertex $uin V$ capable of reaching any vertex in $V$ via a directed path?
Do I have to assume $V$ itself is finite for this to work? Or can I make this deduction irregardless of the cardinality of $V$? I know if I have two subsets $A,Bsubseteq V$, where every vertex in $A$ is reachable by $v_A$ and every vertex in $B$ is reachble by $v_B$ then, since $v_A,v_Bsubseteq V$ there must exist a vertex $u$ capable of reaching both $v_A$ and $v_B$ which means $u$ is capable of reaching every vertex in $Acup B$.
graph-theory induction transfinite-induction
Given any digraph $D=(V,E)$ such that for every finite subset $Ssubseteq V$ there exists a vertex $v_Sin V$ capable of reaching any vertex in $S$ via a directed path.
Can one deduce there is a vertex $uin V$ capable of reaching any vertex in $V$ via a directed path?
Do I have to assume $V$ itself is finite for this to work? Or can I make this deduction irregardless of the cardinality of $V$? I know if I have two subsets $A,Bsubseteq V$, where every vertex in $A$ is reachable by $v_A$ and every vertex in $B$ is reachble by $v_B$ then, since $v_A,v_Bsubseteq V$ there must exist a vertex $u$ capable of reaching both $v_A$ and $v_B$ which means $u$ is capable of reaching every vertex in $Acup B$.
graph-theory induction transfinite-induction
graph-theory induction transfinite-induction
asked Aug 30 at 0:09
davey5554
183
183
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
No, you can't deduce that such a vertex $u$ exists.
Consider the graph with vertex set $mathbb Z$, and an edge from $n$ to $n+1$ for every $n in mathbb Z$.
Then for every finite set $S$, the vertex $min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.
(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)
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
No, you can't deduce that such a vertex $u$ exists.
Consider the graph with vertex set $mathbb Z$, and an edge from $n$ to $n+1$ for every $n in mathbb Z$.
Then for every finite set $S$, the vertex $min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.
(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)
add a comment |Â
up vote
1
down vote
accepted
No, you can't deduce that such a vertex $u$ exists.
Consider the graph with vertex set $mathbb Z$, and an edge from $n$ to $n+1$ for every $n in mathbb Z$.
Then for every finite set $S$, the vertex $min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.
(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
No, you can't deduce that such a vertex $u$ exists.
Consider the graph with vertex set $mathbb Z$, and an edge from $n$ to $n+1$ for every $n in mathbb Z$.
Then for every finite set $S$, the vertex $min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.
(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)
No, you can't deduce that such a vertex $u$ exists.
Consider the graph with vertex set $mathbb Z$, and an edge from $n$ to $n+1$ for every $n in mathbb Z$.
Then for every finite set $S$, the vertex $min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.
(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)
answered Aug 30 at 0:42
Misha Lavrov
37.8k55093
37.8k55093
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%2f2898956%2fcan-i-use-mathematical-induction-here%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