Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Is there anything one can say type-theoretically about the use of WLOG in a proof? Some uses of it seem to involve a symmetric situation where a proof for one choice can be converted into a proof for any.
Some thoughts in the context of automated proof:
He mentions Klein’s Erlanger Program. I wonder if there’s scope for working in some group invariant context.
Here are some simple comments in that direction: We fix a group $G$ with delooping $B G$. We have a domain $X : B G \to U$ and a property $P : \prod_{t:B G} X^t \to Prop$. Since $B G$ is connected, the map
$\prod_{t:B G}\prod_{x:X^t} P^t\,x \to \prod_{x:X^{pt}} P^{pt}\,x$is an equivalence. This type on the left is equivalent to $\prod_{y:X//G} P\,y$ (where I reuse the name $P$ for the uncurried function), and (since $P$ is proposition-valued) to $\prod_{y:X/G} \tilde P\,y$, where $\tilde P : X/G \to Prop$ is the extension of $P$ to the orbit set $X/G := \| X//G \|_0$.
Now, the WLOG situation arises when we have a predicate $Q : X^{pt} \to Prop$ that describes a “fundamental region” of the domain, so that we have an equivalence $\varphi : \sum_{x:X^{pt}} Q\,x \simeq X/G$. Then the original universal quantification (the type on the right above) is equivalent to
$\prod_{x:X^{pt}} \prod_{q : Q\,x} \tilde P(\varphi(x,q)).$So the witness $q$ is the one we get “WLOG.”
For example, in the case that the action of $G$ on $X$ is transitive, the orbit set is contractible, and we can take $Q\, x := (x = x_0)$, i.e., WLOG $x$ is just $x_0$.
This is closely related to your, David’s, thoughts on formalizing “the”. If we may assume without lack of generality that we are dealing with $x \in X$, then $x$ is “the” element/term of $X$.
Except now we may not have $\mathrm{isContr}(X)$, just $||X||$. More generally, one could have side conditions that trim $X$ down to a connected component (for instance an orbit in an action groupoid) and then use WLOG.
Another way to think about WLOG is in terms of “normal forms”, which is when the projection from a sigma type $s : \sum_{x:X} Q\, x \to X$ is a section with retraction $r : X \to \sum_{x:X} Q\,x$. The first component of $r$ normalizes $x:X$, $nf : X \to X$ and the second component witnesses that $nf\,x$ is normal/$Q$: $is Q : \prod_{x:X} Q(nf\,x)$. The section-retraction property implies that $nf$ is the identity on normal elements: $\prod_{x:X} Q\,x \to nf\,x = x$.
Let $P : X \to Prop$. Then, if we have a map $t : \prod_{x:X} P(nf\,x) \to P(x)$, then to show $\prod_{x:X}P(x)$ it suffices (WLOG) to show $\prod_{x:X}\prod_{q:Q\,x}P(x)$. Because, given $x:X$ we have $is Q\,x : Q(nf\,x)$ and hence we know $P(nf\,x)$, and thus $P(x)$ from our map $t$.
From this point of view, there’s no group involved, just an equivalence relation that $P$ respects and a way to pick canonical representatives. The equivalence relation could of course be “$x$ and $y$ are in the same orbit”.
Re #4, yes it certainly feels like a ’dependent generalized the’ in a group context.
Re #3, looks interesting, Ulrik. What does that notation, $X^t, P^t, P^e$, denote? It’s not used at infinity-action, where we see things like $\mathbf{c} : \mathbf{B}G \vdash V(\mathbf{c}) : Type$.
Re #7, perhaps I should have explained, sorry. It’s just application, but I like to write $X^t$ instead of $X(t)$ for $X : B G \to U$ to denote the twist of the underlying type $X(pt)$ by a $G$-torsor $t : B G$. And $P^e$ should really be $P^{pt}$, i.e., the untwisted version. (I’ll edit that.) Then we can, by convention, leave out the superscript for the untwisted type when a type is wanted.
Relevant interesting quote from Terry Tao here:
At a more trivial (but still widely used) level, if there is so much invariance with respect to a parameter that the truth value of a given property does not actually depend on the choice of parameter, then the worst, average, and best case results are equivalent, so one can reduce the worst case to the best case (such arguments are generally described as “without loss of generality” reductions).
This is in the context of a qualitative breakdown of proofs, partial or otherwise, of results in his area into worst case, average case and best case (in that order, going from strongest proof to weakest proof)
1 to 9 of 9