All Questions
Tagged with axiom-of-choice infinite-combinatorics
9
questions
3
votes
1
answer
255
views
A possible ${\sf (ZF)}$-theorem in the spirit of the $3$-set-lemma
The number $3$ plays an interesting role in the following statement:
$\newcommand{\S}{\sf(S_3)}\S$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in ...
4
votes
0
answers
146
views
The monochromatic principle and the axiom of choice
For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...
3
votes
0
answers
165
views
Ramsey's infinite principle and the axiom of choice
Frank Plumpton Ramsey, best known for giving his name to Ramsey Theory, presented the following theorem in On a Problem of Formal Logic, that was submitted in 1928 and published posthumously.
Let $\...
- 37.4k
9
votes
1
answer
498
views
Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$?
For any set $X$ and cardinal $\mu \neq \emptyset$, we denote by $[X]^\mu$ the collection of subsets of cardinality $\mu$. If $\kappa, \mu \neq \emptyset$ are cardinals and $f: [X]^\mu\to \kappa$ is a ...
8
votes
1
answer
226
views
Aronszajn Trees when AC fails
This question may be easy and indicative of my ignorance about the failure of the axiom of choice. If so, I apologize. Below assume $\mathsf{DC}$ but not $\mathsf{AC}$. Suppose we have a partial order ...
- 1,832
1
vote
1
answer
84
views
Maximizing "happy" vertices in splitting an infinite graph
This question is motivated by a real life task (which is briefly described after the question.)
Let $G=(V,E)$ be an infinite graph. For $v\in V$ let $N(v) = \{x\in V: \{v,x\}\in E\}$. If $S\subseteq ...
4
votes
0
answers
127
views
Graphs without maximal vertex-transivite subgraphs
The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-...
9
votes
2
answers
676
views
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\...
- 27.7k
11
votes
1
answer
786
views
Is it known whether every $\omega$-tree with an infinite antichain has an infinite chain in $\mathsf{ZF}$?
In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5:
Each of the following statements imply those beneath it.
The countable union of finite ...
- 493