Timeline for Existence of Spanning Tree implies Well Ordering Principle
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2016 at 3:28 | comment | added | Noah Schweber | @ToddTrimble Ah, yes, I should have seen that. | |
| Jan 17, 2016 at 3:21 | comment | added | Todd Trimble | @NoahSchweber You can use the compactness theorem to show that every set can be totally ordered, and the compactness theorem requires only the ultrafilter principle (i.e., BPIT). You probably don't need it, but other readers who are curious can read this: ncatlab.org/nlab/show/compactness+theorem#totalorder | |
| Jan 17, 2016 at 3:17 | vote | accept | CommunityBot | ||
| Jan 17, 2016 at 2:55 | answer | added | bof | timeline score: 8 | |
| Jan 17, 2016 at 1:18 | comment | added | user81529 | @bof Oh wow, didn't realise you can do that. Brilliant proof for that implication! (: | |
| Jan 16, 2016 at 22:53 | history | reopened |
Joel David Hamkins Daniel Moskovich Yemon Choi Joonas Ilmavirta Stefan Kohl♦ |
||
| Jan 16, 2016 at 22:23 | comment | added | user81529 | @bof Yea, when I started constructing the graph I've overlook that as well. Somehow I feel that some modification should be able to prove the well-ordering principle but I have not succeeded so far. | |
| Jan 16, 2016 at 22:20 | comment | added | bof | @GuoXianYau Oh, right, I overlooked that. It seems that your graph is not connected if $X$ is an infinite set; there is no edge joining a vertex in $\{v_S:S\text{ is finite}\}$ to a vertex in $\{v_S:S\text{ is infinite}\}.$ Since the graph is not connected, statement 1 does not apply. | |
| Jan 16, 2016 at 22:06 | comment | added | user81529 | @bof In my construction not all edges are in the graph, for example, $v_{\emptyset}$ and $v_{\{x,y\}}$ does not have an edge joining them. Anyway, thanks for the help, proving well-ordering principle directly from spanning tree has been puzzling me for a while, at least I was wondering if it is even possible to prove it directly. | |
| Jan 16, 2016 at 22:02 | comment | added | bof | @GuoXianYau It seems unlikely that a spanning tree will be directly useful in a proof of the well-ordering theorem. The graph you suggested in the question has an obvious spanning tree, no choice needed: the "star graph" in which each vertex $v_S (\emptyset\ne S\subseteq X)$ is joined by an edge to $v_\emptyset.$ This tree is not going to help you well-order $X.$ | |
| Jan 16, 2016 at 21:47 | comment | added | user81529 | @JoelDavidHamkins Yes, I should have mentioned that I have the proof for that implication. Thanks for voting to reopen though. (: | |
| Jan 16, 2016 at 21:45 | comment | added | user81529 | @bof I agree with your construction, in fact, i believe using existence of spanning tree to prove axiom of choice directly is standard question in infinite graphs. I am curious about whether or not there is a direct way of proving well-ordering without having to prove axiom of choice. | |
| Jan 16, 2016 at 15:53 | review | Reopen votes | |||
| Jan 16, 2016 at 22:53 | |||||
| Jan 16, 2016 at 15:39 | comment | added | Joel David Hamkins | I think the question is on-topic for MO, and that @bof's comment should be an answer. I have voted to re-open. | |
| Jan 16, 2016 at 8:14 | history | closed |
Andrés E. Caicedo Noah Schweber András Bátkai Tony Huynh Sam Nead |
Not suitable for this site | |
| Jan 16, 2016 at 7:40 | comment | added | Wojowu | See theorem 2. | |
| Jan 16, 2016 at 7:21 | history | edited | bof | CC BY-SA 3.0 |
corrected spelling
|
| Jan 16, 2016 at 7:11 | comment | added | bof | @NoahSchweber It's all over my head but Wikipedia says that the ordering principle is weaker than the order-extension principle, which is weaker than the Boolean prime ideal theorem, which is weaker than the axiom of choice. | |
| Jan 16, 2016 at 6:43 | comment | added | Noah Schweber | 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. | |
| Jan 16, 2016 at 6:37 | comment | added | bof | 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.$ | |
| Jan 16, 2016 at 6:21 | review | Close votes | |||
| Jan 16, 2016 at 8:15 | |||||
| Jan 16, 2016 at 6:06 | comment | added | Noah Schweber | This is a good question, just not for this site - you should ask it at math.stackexchange. | |
| Jan 16, 2016 at 2:46 | history | asked | user81529 | CC BY-SA 3.0 |