Reputation
2,438
Next privilege 2,500 Rep.
Create tag synonyms
Badges
11 19
Newest
 Excavator
Impact
~116k people reached

Feb
10
revised What is a Kelley ring?
deleted 168 characters in body
Feb
5
answered Frankl's union-closed sets conjecture for infinite families
Feb
5
comment question about literature in the field of Ramsey's theory
Would you please state the form of Ramsey's theorem you want proved? As for the classical finite Ramsey theorem that was already proved (not as a consequence of the infinite Ramsey theorem) in Ramsey's original 1930 paper.
Feb
5
answered Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Jan
23
awarded  Excavator
Jan
23
revised References for the Keisler Order
corrected spelling
Jan
23
revised Extremally disconnected spaces and a measure theoretic property
corrected spelling
Jan
17
revised Existence of Spanning Tree implies Well Ordering Principle
deleted 6 characters in body
Jan
17
answered Existence of Spanning Tree implies Well Ordering Principle
Jan
16
comment Existence of Spanning Tree implies Well Ordering Principle
@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
comment Existence of Spanning Tree implies Well Ordering Principle
@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
revised Existence of Spanning Tree implies Well Ordering Principle
corrected spelling
Jan
16
comment Existence of Spanning Tree implies Well Ordering Principle
@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
comment Existence of Spanning Tree implies Well Ordering Principle
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
15
awarded  Scholar
Jan
15
comment A strengthening of Frankl's union-closed sets conjecture?
Thank you for the nice counterexample. I accept it now, but I will move the acceptance if someone provides a counterexample to the weaker conjecture.
Jan
15
accepted A strengthening of Frankl's union-closed sets conjecture?
Jan
15
revised A strengthening of Frankl's union-closed sets conjecture?
added 7 characters in body
Jan
12
comment Edge chromatic number of hypergraphs
@DouglasZare Since the OP didn't mention the axiom of choice, I took it for granted that he's working in ZFC. There is no injection $\binom X2\to X$ if $X$ is a Dedekind-finite set with at least $4$ elements. I've heard that "$|X\times X|=|X|$ for all infinite $X$" is equivalent to AC, but I don't know if that works for $\binom X2.$
Jan
12
comment Edge chromatic number of hypergraphs
@DouglasZare Suppose $|a|=2$ for all $a\in\mathcal F.$ We may assume $|X|=n\lt\infty.$ Then the question is, can a graph of order $n$ have edge chromatic number greater than $n$? I.e., can the complete graph $K_n$ have edge chromatic number greater than $n$? It's an elementary result in graph theory that $K_n\ (n\gt1)$ has edge chromatic number $n$ or $n-1$ according as $n$ is odd or even. We could also cite Vizing's theorem: a simple graph $G$ has $\chi'(G)\le\Delta(G)+1$ where $\chi'$ is the edge chromatic number and $\Delta$ the maximum degree, so $\chi'(K_n)\le\Delta(K_n)+1=n.$