Not signed in (Sign In)

Not signed in

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

  • Sign in using OpenID

Site Tag Cloud

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 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 limit 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 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 subobject superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 7th 2019

    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.

    • CommentRowNumber2.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 8th 2019

    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.

    • CommentRowNumber3.
    • CommentAuthorUlrik
    • CommentTimeSep 8th 2019
    • (edited Sep 8th 2019)

    Here are some simple comments in that direction: We fix a group GG with delooping BGB G. We have a domain X:BGUX : B G \to U and a property P: t:BGX tPropP : \prod_{t:B G} X^t \to Prop. Since BGB G is connected, the map

    t:BG x:X tP tx x:X ptP ptx \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 y:X//GPy\prod_{y:X//G} P\,y (where I reuse the name PP for the uncurried function), and (since PP is proposition-valued) to y:X/GP˜y\prod_{y:X/G} \tilde P\,y, where P˜:X/GProp\tilde P : X/G \to Prop is the extension of PP to the orbit set X/G:=X//G 0X/G := \| X//G \|_0.

    Now, the WLOG situation arises when we have a predicate Q:X ptPropQ : X^{pt} \to Prop that describes a “fundamental region” of the domain, so that we have an equivalence φ: x:X ptQxX/G\varphi : \sum_{x:X^{pt}} Q\,x \simeq X/G. Then the original universal quantification (the type on the right above) is equivalent to

    x:X pt q:QxP˜(φ(x,q)). \prod_{x:X^{pt}} \prod_{q : Q\,x} \tilde P(\varphi(x,q)).

    So the witness qq is the one we get “WLOG.”

    For example, in the case that the action of GG on XX is transitive, the orbit set is contractible, and we can take Qx:=(x=x 0)Q\, x := (x = x_0), i.e., WLOG xx is just x 0x_0.

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeSep 8th 2019

    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 xXx \in X, then xx is “the” element/term of XX.

    • CommentRowNumber5.
    • CommentAuthorDavidRoberts
    • CommentTimeSep 8th 2019

    Except now we may not have isContr(X)\mathrm{isContr}(X), just ||X||||X||. More generally, one could have side conditions that trim XX down to a connected component (for instance an orbit in an action groupoid) and then use WLOG.

    • CommentRowNumber6.
    • CommentAuthorUlrik
    • CommentTimeSep 8th 2019
    • (edited Sep 8th 2019)

    Another way to think about WLOG is in terms of “normal forms”, which is when the projection from a sigma type s: x:XQxXs : \sum_{x:X} Q\, x \to X is a section with retraction r:X x:XQxr : X \to \sum_{x:X} Q\,x. The first component of rr normalizes x:Xx:X, nf:XXnf : X \to X and the second component witnesses that nfxnf\,x is normal/QQ: isQ: x:XQ(nfx)is Q : \prod_{x:X} Q(nf\,x). The section-retraction property implies that nfnf is the identity on normal elements: x:XQxnfx=x\prod_{x:X} Q\,x \to nf\,x = x.

    Let P:XPropP : X \to Prop. Then, if we have a map t: x:XP(nfx)P(x)t : \prod_{x:X} P(nf\,x) \to P(x), then to show x:XP(x)\prod_{x:X}P(x) it suffices (WLOG) to show x:X q:QxP(x)\prod_{x:X}\prod_{q:Q\,x}P(x). Because, given x:Xx:X we have isQx:Q(nfx)is Q\,x : Q(nf\,x) and hence we know P(nfx)P(nf\,x), and thus P(x)P(x) from our map tt.

    From this point of view, there’s no group involved, just an equivalence relation that PP respects and a way to pick canonical representatives. The equivalence relation could of course be “xx and yy are in the same orbit”.

    • CommentRowNumber7.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 8th 2019

    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 eX^t, P^t, P^e, denote? It’s not used at infinity-action, where we see things like c:BGV(c):Type\mathbf{c} : \mathbf{B}G \vdash V(\mathbf{c}) : Type.

    • CommentRowNumber8.
    • CommentAuthorUlrik
    • CommentTimeSep 8th 2019
    • (edited Sep 8th 2019)

    Re #7, perhaps I should have explained, sorry. It’s just application, but I like to write X tX^t instead of X(t)X(t) for X:BGUX : B G \to U to denote the twist of the underlying type X(pt)X(pt) by a GG-torsor t:BGt : B G. And P eP^e should really be P ptP^{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.

    • CommentRowNumber9.
    • CommentAuthorDavidRoberts
    • CommentTimeSep 15th 2019

    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)

    • CommentRowNumber10.
    • CommentAuthorsolson
    • CommentTimeDec 2nd 2019

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