Jachin Shen
Jachin Shen

Categories

Tags

homework

Feasible Intersection Patterns

Problem

Let us call a sequence $(a_1, a_2, \dots, a_n) \in \mathbb{N}_0 \quad feasible$ if there are sets $A_1, \dots, A_n$ such that all k-wise intersections have size $a_k$.

That is, $\lvert A_i \rvert = a_1$ for all $i$, $\lvert A_i \cap A_j \rvert = a_2$ for all $i \neq j$ and so on.

For example, $(5, 3, 1, 0)$ is not feasible, but $(6, 3, 1, 0)$ is.

Hint

A problem may become easier if you:

  1. make it more general
  2. change it a little bit

A-Table

Definition

Given $A_1, A_2, \dots, A_n$ , $I \subseteq {1, 2, \dots, n}$

define $A_I = \bigcap_{i \subseteq I} A_i$

Example

Then, $A_{ \lbrace 1, 2\rbrace } = A_1 \bigcap A_2 = \lbrace 3, 4 \rbrace$

Intersection table

I {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
$\lvert A_I \rvert$ 5 4 6 2 3 2 1

$(a_1, a_2, \dots, a_n)$ to A_Table

I {1} {2} $\dots$ {n} {1, 2} $\dots$ {n-1, n} $\dots$ {1, 2, $\dots$, n}
$\lvert A_I \rvert$ $a_1$ $a_1$ $\dots$ $a_1$ $a_2$ $\dots$ $a_2$ $\dots$ $a_n$

Is it easy to judge the table feasible?

Absolutely, No!!!

B-Table

Definition of B-Table

Given $A_1, A_2, \dots, A_n$, $\varnothing \neq I \subseteq [n]$

define $B_I = (\bigcap_{i \in I} A_i) \setminus (\bigcup_{j \notin I} A_j)$

Example of B-Table

Then, $B_{ \lbrace 1 \rbrace } = A_1 \setminus (A_2 \bigcap A_3) = \lbrace 7 \rbrace $

Table

I {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
$\lvert A_I \rvert$ 5 4 6 2 3 2 1
$\lvert B_I \rvert$ 1 1 2 1 2 1 1

Given a B-Table, is it easy to judge it feasible

Yes. Just every element is Non-negative integer.

Given a B-Table, how to compute an A-Table

For a set P in A-Table, adding all the set Q that $P \subset Q$.

Given a A-Table, how to compute an B-Table

Suppose we know B-Table. Express A-Table as above. Then solve equations to get B-Table.

Infinity sets

Examples

$ \mathbb{I, N_0, Q, R, N} $

Claim

$\mathbb{N_0, N}$ have same size

$\mathbb{N}$ 1 2 3 4 5 $\dots$
$\mathbb{N_0}$ 0 1 2 3 4 $\dots$

There is a bijection function that:

Definition of cardinality

Let $\mathbf{A, B}$ be sets if there is a bijection $\mathbf{A} \leftrightarrow \mathbf{B}$, then we can say $\mathbf{A}$ and $\mathbf{B}$ have the same cardinality (not use size because it sounds like science) and mark $\mathbf{A} \cong \mathbf{B}$

More examples

  • $\mathbb{N_0} \cong \mathbb{Z}$
$\mathbb{Z}$ $\dots$ -4 -3 -2 -1 0 1 2 3 4 $\dots$
$\mathbb(N_0)$ $\dots$ 7 5 3 1 0 2 4 6 8 $\dots$
  • $ \mathbb{Z} \times \mathbb{Z} \cong \mathbb{N} $

  • $ \mathbb{N_0} \cong \mathbb{Q} $

    So how?

    • Another Definition

      If there is an injection $f: \mathbf{A} \to \mathbf{B} $, then we can say $\mathbf{A} \subseteq \mathbf{B}$ and $\mathbf{A}$’s cardinality is at most $\mathbf{B}$’s cardinality.

    • Therefore, $\mathbb{Q} \le \mathbb{Z} \times \mathbb{Z}$

    • How about $\mathbb{Z} \times \mathbb{Z} \le \mathbb{Q}$?

    • So, how about $\mathbb{N_0} \cong \mathbb{Q}$

      • $\mathbb{Q} \subseteq \mathbb{Z} \times \mathbb{Z} \subseteq \mathbb{N_0} $
      • Obviously, $\mathbb{N} \subseteq \mathbb{Q}$
      • So, $\mathbb{N} \cong \mathbb{Q} $
  • $\lbrace 0, 1 \rbrace^N \cong 2^N$

    • $2^N$: power set, the set of all subsets. So every number $\in 2^N$
    • $\lbrace 0, 1 \rbrace^N$: the set of all infinite but sequence $(a_1, a_2, \dots) \quad a_i \in \lbrace 0, 1 \rbrace $

  • $ \lbrace 0, 1 \rbrace^N \cong \mathbb{R} $
    • $f: \mathbb{R} \mapsto \lbrace 0, 1 \rbrace^N$, injection?
    • $g: [0, 1) \mapsto \lbrace 0, 1 \rbrace^N$:x write in binary as $(x)_2 = 0.a_1 a_2 \dots $
    • Every $x \in [0, 1) \mapsto $binary, $x \mapsto (a_1, a_2, \dots, a_n) \in \lbrace 0, 1 \rbrace^N $
      • $\frac{1}{2}: 0.1000\dots$
      • $\frac{1}{3}: 0.010101\dots$
      • $\frac{1}{4}: 0.0100\dots$
    • Injection, but not surjection!