Skip to main content
deleted 6 characters in body
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$$r\in V.$ For each vertex $v\in V\setminus\{v_0\},$$v\in V\setminus\{r\},$ choose a vertex $v'\in V$ sosuch that $v'$ is adjacent to $v$ and $d(v',v_0)\lt d(v,v_0).$$d(v',r)\lt d(v,r).$ The set of all edges $\{v',v\}$$\{v,v'\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the connected graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph$G$. Choose a vertex $a\in A.$$r\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$$r,$ and $P_i$ contains a unique edge $\{i,v_i\}$$\{i,a_i\}$ where $v_i\in A_i.$$a_i\in A_i.$ Now $i\mapsto v_i$$i\mapsto a_i$ is a choice function for the family $A_i (i\in I).$

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',v_0)\lt d(v,v_0).$ The set of all edges $\{v',v\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $r\in V.$ For each vertex $v\in V\setminus\{r\},$ choose a vertex $v'\in V$ such that $v'$ is adjacent to $v$ and $d(v',r)\lt d(v,r).$ The set of all edges $\{v,v'\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the connected graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for $G$. Choose a vertex $r\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $r,$ and $P_i$ contains a unique edge $\{i,a_i\}$ where $a_i\in A_i.$ Now $i\mapsto a_i$ is a choice function for the family $A_i (i\in I).$

fixed some typos
Source Link
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',w)\lt d(v,w).$$d(v',v_0)\lt d(v,v_0).$ The set of all edges $\{v',v\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',w)\lt d(v,w).$ The set of all edges $\{v',v\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',v_0)\lt d(v,v_0).$ The set of all edges $\{v',v\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$

Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.

AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',w)\lt d(v,w).$ The set of all edges $\{v',v\}$ is a spanning tree.

(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$