Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorDavid_Corfield
   • CommentTimeSep 7th 2019
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexIs 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.

   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.

2. • CommentRowNumber2.
   • CommentAuthorDavid_Corfield
   • CommentTimeSep 8th 2019
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexSome thoughts in the context of automated proof: * John Harrison, _Without Loss of Generality_, ([pdf](https://www.cl.cam.ac.uk/~jrh13/papers/wlog.pdf)) He mentions Klein's Erlanger Program. I wonder if there's scope for working in some group invariant context.

   Some thoughts in the context of automated proof:

   • John Harrison, Without Loss of Generality, (pdf)

   He mentions Klein’s Erlanger Program. I wonder if there’s scope for working in some group invariant context.

3. • CommentRowNumber3.
   • CommentAuthorUlrik
   • CommentTimeSep 8th 2019
   • (edited Sep 8th 2019)
   • PermaLink
   Author: Ulrik
   Format: MarkdownItexHere 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$.

   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$.

4. • CommentRowNumber4.
   • CommentAuthorUrs
   • CommentTimeSep 8th 2019
   • PermaLink
   Author: Urs
   Format: MarkdownItexThis 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$.

   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$.

5. • CommentRowNumber5.
   • CommentAuthorDavidRoberts
   • CommentTimeSep 8th 2019
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexExcept 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.

   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.

6. • CommentRowNumber6.
   • CommentAuthorUlrik
   • CommentTimeSep 8th 2019
   • (edited Sep 8th 2019)
   • PermaLink
   Author: Ulrik
   Format: MarkdownItexAnother 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”.

   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”.

7. • CommentRowNumber7.
   • CommentAuthorDavid_Corfield
   • CommentTimeSep 8th 2019
   • PermaLink
   Author: David_Corfield
   Format: MarkdownItexRe #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 #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$.

8. • CommentRowNumber8.
   • CommentAuthorUlrik
   • CommentTimeSep 8th 2019
   • (edited Sep 8th 2019)
   • PermaLink
   Author: Ulrik
   Format: MarkdownItexRe #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.

   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.

9. • CommentRowNumber9.
   • CommentAuthorDavidRoberts
   • CommentTimeSep 15th 2019
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexRelevant interesting quote from Terry Tao [here](https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/#comment-521820): >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)

   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)

10. • CommentRowNumber10.
    • CommentAuthorsolson
    • CommentTimeDec 2nd 2019
    • PermaLink
    Author: solson
    Format: MarkdownItexThe [mathlib](https://github.com/leanprover-community/mathlib) project uses the Lean theorem prover which has a Coq-like tactic language, and they've defined a [`wlog` tactic](https://github.com/leanprover-community/mathlib/blob/c9cfafc922927c4fc157a4acc2e8df984d3e74bd/src/tactic/wlog.lean#L111-L152). This might be a bit too technical or Lean-specific for unfamiliar readers, but hopefully the documentation is generally readable, particularly the example. E.g. to prove `p n m` you are allowed to assume an extra hypothesis `n <= m` if you prove it always holds in at least one direction and you prove that `p n m` and `m <= n` imply `p m n` (i.e. `p` doesn't care about the ordering). Essentially you establish a lemma `f : ∀ (n m : nat) (h : n <= m) -> p n m` in the main flow of your proof, with an implied parenthetical that if `m` is *actually* the smaller value with proof `h : m <= n`, you just invoke `f m n h` which has the type `p m n`, and then swap it to `p n m`. The `wlog` principle then lets you simply conclude `∀ (n m : nat) -> p n m` without the extra hypothesis. So I think WLOG (at least in this sense) has a lot to do with symmetry as mentioned in #1, because it only works for predicates `p` where you can prove that the above swapping works. (Of course, the mathlib definition generalizes beyond arity 2, so it's not just symmetry, but any permutation of the variables passed to the predicate.)

    The mathlib project uses the Lean theorem prover which has a Coq-like tactic language, and they’ve defined a wlog tactic. This might be a bit too technical or Lean-specific for unfamiliar readers, but hopefully the documentation is generally readable, particularly the example.

    E.g. to prove p n m you are allowed to assume an extra hypothesis n <= m if you prove it always holds in at least one direction and you prove that p n m and m <= n imply p m n (i.e. p doesn’t care about the ordering).

    Essentially you establish a lemma f : ∀ (n m : nat) (h : n <= m) -> p n m in the main flow of your proof, with an implied parenthetical that if m is actually the smaller value with proof h : m <= n, you just invoke f m n h which has the type p m n, and then swap it to p n m. The wlog principle then lets you simply conclude ∀ (n m : nat) -> p n m without the extra hypothesis.

    So I think WLOG (at least in this sense) has a lot to do with symmetry as mentioned in #1, because it only works for predicates p where you can prove that the above swapping works. (Of course, the mathlib definition generalizes beyond arity 2, so it’s not just symmetry, but any permutation of the variables passed to the predicate.)