1
$\begingroup$

Let $X$ be an infinite set, and let $E \subseteq {\cal P}(X)$ be a collection of subsets of $X$. We say that $E$ is $T_1$ (with respect to $X$) if for all $x\neq y\in X$ there is $e\in E$ with $x\in e$ and $ y\notin e$.

The set $E := \{X\setminus \{y\}: y\in X\}$ is an easy example for a $T_1$-set $E$ with $|E| = |X|$.

Is it possible that $|E| < |X|$ ?

$\endgroup$
4
  • $\begingroup$ If you pick sets of size ~|X|/2 at random, then each pair of vertices is separated with probability about 1/2. So, if you pick lots of sets in this way (say |X|/2) then the probability any pair isn't separated is exponentially small, whereas the number of pairs is only quadratic in |X|. Hence, if |X| is large, the expected number of pairs which aren't separated is <1, and so by the first moment method there is some set of |X|/2 edges which separate all the pairs. This probably shows that a logarithmically small number of edges suffices. $\endgroup$ Commented Sep 18, 2017 at 10:31
  • $\begingroup$ Interesting comment, thanks @JoshuaErde . I wonder what things look like in the infinite! $\endgroup$ Commented Sep 18, 2017 at 12:06
  • 1
    $\begingroup$ It is indeed trivial for $X$ finite. Let $X = \{1,2,3,\ldots, 9\}$, arrange these points in a $3\times 3$ square and let $E$ consist of the $3$ "horizontal" lines (each containing 3 points) and the $3$ vertical lines (again each containing 3 points). Then $E$ has the $T_1$ property, and $|E| = 6 < 9 = |X|$. So it appears the question is interesting in the infinite only. Will edit accordingly. $\endgroup$ Commented Sep 18, 2017 at 12:11
  • 1
    $\begingroup$ If you have a $T_0$ hypergraph, then you can make it $T_1$ by throwing in all the complements of all edges. Thus it is enough to answer the question in the case of $T_0$. Then just take $X$ to be the power set of $E$, where an edge $e$ 'contains' all those sets that is a member of. (To understand this construction better, it helps to think about the dual hypergraph, or to consider a hypergraph instead as a bipartite graph with $X$ on one side and $E$ on the other.) So we get $X = 2^E$, and this is clearly as large as $X$ can get for given $|E|$. $\endgroup$ Commented Sep 18, 2017 at 13:21

2 Answers 2

3
$\begingroup$

It depends on the cardinality of $X$:

The answer to your question is no if and only if $|X|$ is a strong limit cardinal.

Recall that $|X|$ is a strong limit cardinal iff $2^\lambda < |X|$ for every $\lambda < |X|$.

If $E \subseteq \mathcal P(X)$ is "$T_1$" then all the $|X|$-many sets of the form $$\{e \in E : x \in E\}$$ are distinct, so that we have an injection $X \rightarrow \mathcal P(E)$. Thus $2^{|E|} \geq |X|$, and we cannot have $|E| < |X|$ if $|X|$ is a strong limit.

For the other direction, suppose $|X|$ is not a strong limit cardinal and let $\lambda$ be any cardinal with $\lambda < |X|$ and $2^\lambda \geq |X|$. Identify $X$ with a subset of $2^\lambda$, and let $E$ consist of all sets of the form $$U_s = \{x \in X : x(\alpha) = s(\alpha) \text{ for all }\alpha \in \mathrm{dom}(s)\}$$ where $s$ is a function from a finite subset of $\lambda$ to $\{0,1\}$. In other words, identify $X$ with a subspace of the generlized Cantor space $2^\lambda$, and then observe that this space is $T_1$ and has a basis of size $\lambda$.

$\endgroup$
0
0
$\begingroup$

An easy example is $X = {\mathbb R}$ and $$E = \{B_{\frac{1}{n}}(q): q \in {\mathbb Q}, n\in\mathbb{N}\}$$ where $B_{\frac{1}{n}}(q): = \{x\in {\mathbb R}: |x-q| < \frac{1}{n}\}$. Then $|E| = \aleph_0<2^{\aleph_0} = |X|$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .