Using the Well-Ordering Principle, which is equivalent to the Axiom of Choice, it can be proved that
(S): for every simple, undirected graph $G$, finite or infinite, either $G$ or its complement $\bar{G}$ is connected.
Does (S) imply (AC)?
$\begingroup$
$\endgroup$
0
asked Apr 9, 2018 at 12:23
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
(S) is a theorem of ZF.
Proof: Let $G$ be a graph, and let $v$ be a vertex of $G$. Define $$P_v = \{w \,:\, \text{there is a path from } v \text{ to } w\}.$$ If $P_v$ is the vertex set of $G$, then $G$ is connected. If not, then $\overline{G}$ (the complement of $G$) contains the complete bipartite graph on $P_v$ and $V(G) \setminus P_v$. But then it's easy to see that any two vertices in $\overline{G}$ are connected by a path of length $1$ or $2$.
answered Apr 9, 2018 at 12:57
-
16
-
$\begingroup$ Is this also a theorem in a weaker theory? I seem to recall that Pv or something like it is not definable in pure graph theory (say language with equality and one binary relation of adjacency between vertices)? Gerhard "Can't Get There From Here" Paseman, 2018.04.09. $\endgroup$ Apr 9, 2018 at 17:11
-
6$\begingroup$ @GerhardPaseman: The smart-aleck in me would like to point out that every theorem of ZF is a theorem of some weaker theory, namely the theory consisting of the (finitely many) axioms actually used in the proof. The sincere mathematician in me thinks you might be thinking of this: en.wikipedia.org/wiki/Logic_of_graphs#Examples_2. $\endgroup$ Apr 9, 2018 at 18:00
-
$\begingroup$ Forgive my ignorance, but what does ZF mean exactly? Its not referenced anywhere in this answer or in the question. $\endgroup$– user1447Apr 10, 2018 at 6:28
-
$\begingroup$ @user1447: "ZF" stands for "the axioms of Zermelo-Fraenkel set theory" (see en.wikipedia.org/wiki/…). Saying "some statement (S) is equivalent to (AC)" means that using ZF, one can show that (S) implies (AC) and (AC) implies (S). $\endgroup$ Apr 10, 2018 at 10:59