3
$\begingroup$
  1. Every connected graph has a spanning tree.
  2. Every non-empty set can be well ordered.

Basically I am trying to show that statement 1 implies statement 2. What I tried is as following: Let $X \ne \emptyset$, define a graph $G$ with $$V(G) := \{v_{S}:S \subseteq X\}$$ and $v_S v_T \in E(G)$ if and only if either $S \subseteq T$ and $|T| = |S| + 1$ or vice versa. By statement 1, there is a spanning tree so we choose the path (possibly infinite) that connects $v_{\emptyset}$ and $V_X$, and define a total order $\le$ on $X$ by the order each element $x \in X$ is added in the path that connects $v_{\emptyset}$ and $v_X$.

I talked to a professor about this, apparently connected means each pair of vertices is connected by a FINITE path, so my proof is technically wrong, but I think that's the general direction to proceed. Any hint on actually proving it?

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ This is a good question, just not for this site - you should ask it at math.stackexchange. $\endgroup$
    – Noah Schweber
    Commented Jan 16, 2016 at 6:06
  • 4
    $\begingroup$ As the well-ordering principle is equivalent to the axiom of choice, forget about well-ordering and just prove directly that (1) implies AC. Let $A_i,i\in I$ be a given family of nonempty sets. Let $A=\bigcup_{i\in I}A_i$. Assume w.l.o.g. that $I\cap A=\emptyset.$ Let $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.$ $\endgroup$
    – bof
    Commented Jan 16, 2016 at 6:37
  • $\begingroup$ Note also that a well-order is very different from a total order. I do not know whether "every set can be totally ordered implies the axiom of choice. $\endgroup$
    – Noah Schweber
    Commented Jan 16, 2016 at 6:43
  • 1
    $\begingroup$ See theorem 2. $\endgroup$
    – Wojowu
    Commented Jan 16, 2016 at 7:40
  • 3
    $\begingroup$ I think the question is on-topic for MO, and that @bof's comment should be an answer. I have voted to re-open. $\endgroup$
    – Joel David Hamkins
    Commented Jan 16, 2016 at 15:39

1 Answer 1

Reset to default
8
$\begingroup$

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).$

Improve this answer
$\endgroup$
1
  • $\begingroup$ I would agree as that is what I did basically. Will accept this as answer for now until someone actually showed a proof of statement 1 implies statement 2 without using other equivalent formulations of axiom of choice. Cheers! (: $\endgroup$
    – user81529
    Commented Jan 17, 2016 at 3:17

You must log in to answer this question.