The set $\mathcal{P}(X)$ of all Subsets of a Set $X$

The layers of $\mathcal{P}(X)$ are the 0-elements subsets, the 1-element susets, the k-elements subsets, etc., denoted $X^{(k)}$

Power set can be turned into a Graph by adding an edge between $A,B \subseteq X$ if $|A \triangle B| = 1$ (where $\triangle$ denotes Symmetric difference. This turns out to give Discrete cube $Q_{|X|}$. Can only connect only sets A and B that differ by one element as we want $|(A\cup B) \setminus (A \cap B)| = 1$. Called Hasse diagram

We can identify power set with the vector space $\mathbb{F}_2^n$ of characteristic vectors indicating which elements belong to a given subset.

The function $(A,B) \to |A \triangle B|$ is a Metric on the power set.

For Combinatorics, often we consider $\mathcal{P}([n])$, denoted $\mathcal{P}(n)$, where $[n]$ is the set of all Natural numbers up to and including $n$.

Chain and Antichains

We can explore the chains and Antichains of this Partially ordered set (under Set inclusion).

Every maximal chain in P(n) has n+1 elements includinng empty set and whole set [n].

How large can antichains be? Sperner's lemma: an antichain in P(n) has at most $\binom{n}{\lfloor{n/2}\rfloor}$. We can prove using Hall's theorem

Shadows

We can define two orders in a layer of P(x) $[n]^{(r)}$: the Lexicographic order (lex) and colexicographic order (colex)

Kruskal-Katona theorem

Intersections and traces

See here

A family $\mathcal{A}\subseteq \mathcal{P}(n)$ is intersecting if $|A \cap B| = \emptyset$ for all $A,B \in \mathcal{A}$.

It's not hard to show that $|\mathcal{A}| \leq 2^{n-1}$

Erdos-Ko-Rado theorem

There is no injective map from the power set of a set $X$ to the set $X$, and there is no surjective map from a set to its power set.

This implies that a set and its power set have different Cardinality