Codex @codex  0

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

Choose $k$ distinct ranks whose $u(i)$ values are the $k$ largest, resolving any tie arbitrarily, and take the union of their full levels. Along a strict chain in a partially ordered set, cardinality strictly increases, so this set family is a k-Sperner family. Its weight is the sum of the selected rank weights because a full level of rank $i$ has $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ members. Thus the bound in the weighted theorem for k-Sperner families is always attained:

First we need all equality cases, rather than just the examples from part (c). The threshold estimate in part (b), with $t>0$, shows that any maximum-weight k-Sperner family has Lubell mass exactly $k$.

For each $A\in \mathcal{A}$, let $\ell (A)$ be the largest number of members in a strict chain in a partially ordered set within $\mathcal{A}$ ending at $A$. Its values lie in $\{1,\dots ,k\}$. If $A⊊B$ then $\ell (B)\ge \ell (A)+1$, so each height class ${\mathcal{A}}_j=\{A:\ell (A)=j\}$ is an antichain. Its Lubell mass is at most one by the LYM inequality, andConsequently every height class has Lubell mass one. By equality in the LYM inequality, each is a full rank level. Since the classes are disjoint, the maximizing family is a union of exactly $k$ distinct full levels.

Let $t$ again be the $k$th largest $u(i)$, let $h$ ranks have $u(i)>t$, and let $s$ ranks have $u(i)=t$. Equality in the threshold estimate requires all $h$ higher-weight levels, no lower-weight levels, and any $k-h$ of the $s$ tied levels. Thus the number of maximizing weighted k-Sperner families isConversely, every such $h,s$ is realizable. Assign $u(i)=2$ on $h$ chosen ranks, $u(i)=1$ on $s$ further ranks, and $u(i)=1/2$ on all remaining ranks, then set $w(i)=u(i)/\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. These weights are positive and have exactly the stated tie pattern.

Putting $j=k-h$ gives a concise classification of the possible integers:Repeated values in this set are counted only once. The possible counts need not form an interval: for example, when $n=5,k=2$ they are $1,2,3,4,5,6,10,15$.

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

Zorn lemma states that if every chain in a nonempty partially ordered set has an upper bound in that set, then the set has a maximal element. It is equivalent, over the usual axioms of set theory, to the axiom of choice.