A Simple Proof of Zorn’s Lemma

Just a personal rephrase of JONATHAN LEWIN’s simple proof of the Zorn Lemma, which I would really like to remember… so let’s work out all the details…

(… The proof is simple in the sense that it needs neither transfinite induction, nor Ordinals, just the Axiom of Choice (AC) and elementary extremality arguments …)

Theorem (Zorn’s Lemma). Suppose (X,\leq) is a partial order in which every chain is bounded from above. Then (X,\leq) has a maximal element.

Def. If C\subseteq X is a chain (i.e. total order) and x\in X, then \displaystyle I_C(x) = \{y\in C \mid y<x\} is named the initial segment of x in C.

Proof. Suppose (X,\leq) has no maximal element, towards a contradiction. If C is any chain in X, let u\in X be an upper bound of C. Since X has no maximal element, there exists v\in X such that u<v. So, C admits a strict upper bound. By AC, there is a choice function f which assigns to every chain C\subseteq X a strict upper bound f(C).

The sought contradiction will be that of finding a chain U\subseteq X such that f(U)\in U. This is catalysed by the following notion of conforming subset.

Def. Say that a subset A\subseteq X is conforming if the following two conditions hold:

  1. (A,\leq) is a well order (i.e. A is a chain such that every subset of A has a least element);
  2. for every a\in A, it holds a=f(I_A(a)).

Comparability Lemma. If A,B\subseteq X are conforming and A\neq B, then one of these two sets is an initial segment of the other.

Proof of Comparability Lemma. Since A\neq B we can assume w.l.o.g. A\setminus B\neq \emptyset.

Let x=\min (A\setminus B).

Then I_A(x)\subseteq B. So the Claim reduces to show B\subseteq I_A(x).

Towards a contradiction, assume B\setminus I_A(x) \neq \emptyset.

Let y = \min (B\setminus I_A(x)).

Let z = \min(A\setminus I_B(y)).

Closure Lemma. Given any u\in I_B(y), if v\in A and v<u then:

  • v<y (by definition of I_B(y) and y)
  • v\in B (since u\in I_B(y), so u\in I_A(x) by definition of y, thus v\in I_A(x) too, and I_A(x)\subseteq B by definition of x)

so v\in I_B(y).

With this, we can show that \displaystyle I_A(z)=I_B(y). Indeed, I_A(z)\subseteq I_B(y) follows already by definition of z, so the actual claim is that I_B(y)\subseteq I_A(z). Let u\in I_B(y), then u\in I_A(x) (by def. of y), so u\in A; also u\neq z (by def. of z); finally, it is not possible that u>z, otherwise by Closure Lemma it would be z\in I_B(y) against z own definition. Therefore, u<z. Since u\in A and u<z, then u\in I_A(z).

Also, z\leq x. Indeed, x\not\in B (by definition) so x\not\in I_B(y) but x\in A, therefore z\leq x (by definition of z at this point).

Since z=f(I_A(z))=f(I_B(y))=y, and since y\in B, we cannot have z=x (because x\not\in B by definition). Therefore, z<x, and we conclude y=z\in I_A(x), against definition of y.

This implies that B\setminus I_A(x) = \emptyset, i.e. B\subseteq I_A(x), closing the proof of the Comparability Lemma.

By the Comparability Lemma, it is clear that the union U of all conforming subsets of X is conforming. Thus, if x=f(U) is a strict upper bound, then U\cup \{x\} is conforming too. Since U is the union of all conforming sets, then x\in U , contradicting that x is a strict upper bound of U.

So (X,\leq) has one maximal element.

Sorting with Forbidden Intermediates goes to DAM

An extended version of our paper “Sorting with Forbidden Intermediates (Searching (s,t)-Paths avoiding Forbidden Vertices in Hypercube Graphs)” has been accepted for publication in international journal (https://doi.org/10.1016/j.dam.2019.10.025):

Discrete Applied Mathematics, Elsevier

(journal of combinatorial algorithms, informatics and computational sciences).

Screenshot 2019-07-27 at 10.16.54.pngdownload

Joint work with Stéphane Vialette (CNRS and UPEM, Paris, France), Anthony Labarre (UPEM, Paris, France) and Romeo Rizzi (Univ. Verona, Italy)

Linear Time Safe-Alternating DFS and SCCs

An alternating graph is a directed graph whose vertex set is partitioned into two classes, existential and universal. This forms the basic arena for a plethora of infinite duration two-player games where Player \square and \circ alternate in a turn-based sliding of a pebble along the arcs they control.

We study alternating strongly-connectedness as a generalization of strongly-connectedness in directed graphs, aiming at providing a linear time decomposition and a sound structural graph characterization. For this a refined notion of alternating reachability is introduced: Player \square attempts to reach vertices without leaving a prescribed subset of the vertices, while Player \circ works against. This is named safe alternating reachability. It is shown that every alternating graph uniquely decomposes into safe alternating strongly-connected components where Player \square can visit each vertex within a given component infinitely often, without having to ever leave out the component itself.

Our main result is a linear time algorithm for computing this alternating graph decomposition.

Both the underlying graph structures and the algorithm generalize the classical decomposition of a directed graph into strongly-connected components.
The algorithm builds on a linear time generalization of the depth-first search on alternation, taking inspiration from Tarjan 1972 machinery.

Our theory has direct applications in faster solving well-known infinite duration pebble games. Dinneen and Khoussainov showed in 1999 that deciding a given Update Game costs O(mn) time, where n is the number of vertices and m is that of arcs. We solve that task in \Theta(m+n) linear time. With this the complexity of Explicit McNaughton-Muller Games also improves from cubic to quadratic.

Download: manuscript.

Screenshot 2020-12-08 at 11.28.16

Screenshot 2019-06-09 at 13.15.47