All Questions
Tagged with infinite-combinatorics order-theory
18 questions
2
votes
1
answer
284
views
Size of antichains in powerset of $\mathbb N$
Take a countably infinite set $S$, say $\mathbb N$. Is it possible for there to be an antichain in $\mathcal P(S)$ (with the inclusion ordering) of continuum cardinality?
- 33
0
votes
0
answers
117
views
"Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$
$\newcommand{Po}{{\cal P}(\omega)}$
$\newcommand{lh}{\leq_{\text{hom}}}$
If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...
- 48.8k
-3
votes
1
answer
101
views
Order-embeddability of ${\frak b}$ and ${\frak d}$ in $\mathbb{R}$ [duplicate]
The starting point of this question is the observation that in ${\sf (ZFC)}$, all ordinals $\alpha < \omega_1$ can be order-embedded in $\mathbb{R}$.
Let $\omega^\omega$ denote the set of all ...
- 48.8k
7
votes
2
answers
495
views
Counterexample for Chvatal's conjecture in an infinite set
Let $X \neq \emptyset$ be a set. We say that ${\cal F} \subseteq {\cal P}(X)$ is a down-set if ${\cal F}$ is closed under taking subsets. Whenever $a \in X$, we let ${\cal F}_a = \{ S \in F : a \in S\}...
- 48.8k
5
votes
1
answer
270
views
Question about a family of nested countable subsets of $\mathbb{R}$
Let $\mathcal{F}$ denote a family of countable subsets of $\mathbb{R}$, such that for each $U, V\in\mathcal{F}$ we have that $U\subseteq V$, or $V\subseteq U$. Let $(\mathcal{F}, \preceq)$ denote the ...
- 291
4
votes
1
answer
119
views
Searching for cofinal subsets of directed sets subject to finite constraints
Let $(P,\leq)$ be a directed set with uncountable cofinality. For every element $p\in P$, we are given a finite set $c_p\subset P\smallsetminus \{p\}$ of "incompatible elements". We say that ...
- 380
1
vote
2
answers
142
views
Embedding $^\omega\omega$ and $S_\omega$ with lexicographic order into $\mathbb{R}$
Let $^\omega\omega$ be the collection of all functions $f:\omega\to\omega$. We order $^\omega\omega$ lexicographically, that is: For $f\neq g \in \,^\omega\omega$ let $m(f,g):= \min\{n\in\omega:f(n)\...
- 48.8k
6
votes
1
answer
256
views
Maximal independent sets in MAD families
We call ${\cal A}\subseteq {\cal P}(\omega)$ almost disjoint if ${\cal A}\neq \varnothing$, every member of ${\cal A}$ is infinite, and for $A_1\neq A_2\in {\cal A}$ we have that $A_1\cap A_2$ is ...
- 48.8k
6
votes
1
answer
111
views
Tameable hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $I\subseteq V$ is an independent set if $e\not\subseteq I$ for all $e\in E$.
We say that $H$ is tameable if every independent set is contained in a maximal ...
- 48.8k
1
vote
1
answer
93
views
Minimizing the set of monochromatic edges
For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.
Let $H = (V,E)$ be a hypergraph such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a ...
- 48.8k
5
votes
1
answer
356
views
Calculate the $\downarrow$, $\downarrow\uparrow$ and $\uparrow\downarrow$ cofinalities of the poset of nontrivial finitary partitions of $\omega$
Let $(P,\le)$ be a poset. For a point $x\in P$ let
$${\downarrow}x=\{p\in P:p\le x\}\quad\text{and}\quad{\uparrow}x=\{p\in P:x\le p\}$$be the lower and upper sets of the point $x$, and for a subset $...
- 41.8k
1
vote
1
answer
140
views
Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets
This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement.
A partition $\...
- 48.8k
0
votes
1
answer
52
views
Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...
- 48.8k
6
votes
2
answers
1k
views
Poset dimension and width (Dilworth's theorem)
For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...
- 1,006
2
votes
2
answers
186
views
Infima and suprema in the "transfer" function ordering
Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
- 48.8k
7
votes
2
answers
344
views
Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$
Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
- 48.8k
4
votes
3
answers
395
views
Problem understanding a passage of the proof of $\mathfrak{p}=\mathfrak{t}$ involving forcing
I've a problem with a passage of the proof of Claim 14.7 of the paper "Cofinality spectrum theorems in model theory, set theory, and general topolgy" by Malliaris and Shelah, or equivalently ...
- 775
11
votes
1
answer
803
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 ...
- 503