Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal U}\to X$ is called a choice function if $f(A)\in A$ for all $A\in {\cal U}$. A marriage is an injective choice function.

We say that ${\cal U}$ is critical if

  1. there is a marriage $f:{\cal U}\to X$, and
  2. every marriage $f:{\cal U}\to X$ is surjective.

As Noah Schweber showed in his posthis post, critical coverings of $\omega$ need to contain at least a finite set.

Given $n\in \omega$ is there a critical covering ${\cal U}$ of $\omega$ such that every member of ${\cal U}$ contains at least $n$ elements? (I would also appreciate to know whether it's possible that ${\cal U}$ contains only finitely many finite sets, but this is a side question.)

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal U}\to X$ is called a choice function if $f(A)\in A$ for all $A\in {\cal U}$. A marriage is an injective choice function.

We say that ${\cal U}$ is critical if

  1. there is a marriage $f:{\cal U}\to X$, and
  2. every marriage $f:{\cal U}\to X$ is surjective.

As Noah Schweber showed in his post, critical coverings of $\omega$ need to contain at least a finite set.

Given $n\in \omega$ is there a critical covering ${\cal U}$ of $\omega$ such that every member of ${\cal U}$ contains at least $n$ elements? (I would also appreciate to know whether it's possible that ${\cal U}$ contains only finitely many finite sets, but this is a side question.)

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal U}\to X$ is called a choice function if $f(A)\in A$ for all $A\in {\cal U}$. A marriage is an injective choice function.

We say that ${\cal U}$ is critical if

  1. there is a marriage $f:{\cal U}\to X$, and
  2. every marriage $f:{\cal U}\to X$ is surjective.

As Noah Schweber showed in his post, critical coverings of $\omega$ need to contain at least a finite set.

Given $n\in \omega$ is there a critical covering ${\cal U}$ of $\omega$ such that every member of ${\cal U}$ contains at least $n$ elements? (I would also appreciate to know whether it's possible that ${\cal U}$ contains only finitely many finite sets, but this is a side question.)

Source Link

Size of smallest set in critical covering of $\omega$

A covering of a non-empty set $X$ is a collection ${\cal U} \subseteq ({\cal P}(X)\setminus\{\emptyset\})$ such that $\bigcup {\cal U} = X$. If ${\cal U}$ is a covering of $X$ then a function $f:{\cal U}\to X$ is called a choice function if $f(A)\in A$ for all $A\in {\cal U}$. A marriage is an injective choice function.

We say that ${\cal U}$ is critical if

  1. there is a marriage $f:{\cal U}\to X$, and
  2. every marriage $f:{\cal U}\to X$ is surjective.

As Noah Schweber showed in his post, critical coverings of $\omega$ need to contain at least a finite set.

Given $n\in \omega$ is there a critical covering ${\cal U}$ of $\omega$ such that every member of ${\cal U}$ contains at least $n$ elements? (I would also appreciate to know whether it's possible that ${\cal U}$ contains only finitely many finite sets, but this is a side question.)