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 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 internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure 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 superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorJohn Baez
   • CommentTimeDec 9th 2016
   • PermaLink
   Author: John Baez
   Format: MarkdownItexIn [the study of databases](https://simons.berkeley.edu/talks/phokion-kolaitis-2016-12-09) and maps between databases, certain formulas in first-order logic are particularly important. They're called [GLAV constraints](https://www.google.com/search?q=GLAV+constraint), and they're of the form $$ \forall \vec{x} (P(\vec{x}) \implies \exists \vec{y} Q(\vec x, \vec y)) $$ where $\vec x, \vec y$ are lists of variables and $P$, $Q$ are atomic predicates. This reminds me a bit of coherent logic or geometric logic, but it's not. What kind of logic uses only GLAV constraints as formulas?

   In the study of databases and maps between databases, certain formulas in first-order logic are particularly important. They’re called GLAV constraints, and they’re of the form

   $$\forall \vec{x} (P(\vec{x}) \implies \exists \vec{y} Q(\vec x, \vec y))$$

   where $\vec x, \vec y$ are lists of variables and $P$, $Q$ are atomic predicates.

   This reminds me a bit of coherent logic or geometric logic, but it’s not. What kind of logic uses only GLAV constraints as formulas?

2. • CommentRowNumber2.
   • CommentAuthorTodd_Trimble
   • CommentTimeDec 9th 2016
   • (edited Dec 9th 2016)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexThat just looks like a sentential form of something you could just as easily express as a sequent between predicates $P(x) \vdash (\exists y)\; Q(x, y)$, and so it looks like something accommodated by coherent/geometric logic or even something weaker. Am I missing something?

   That just looks like a sentential form of something you could just as easily express as a sequent between predicates $P(x) \vdash (\exists y)\; Q(x, y)$, and so it looks like something accommodated by coherent/geometric logic or even something weaker. Am I missing something?

3. • CommentRowNumber3.
   • CommentAuthorKeithEPeterson
   • CommentTimeDec 9th 2016
   • PermaLink
   Author: KeithEPeterson
   Format: MarkdownItexCan we view the expression on the right as an instance of a co-end?

   Can we view the expression on the right as an instance of a co-end?

4. • CommentRowNumber4.
   • CommentAuthorTodd_Trimble
   • CommentTimeDec 10th 2016
   • (edited Dec 10th 2016)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexKeith: yes. A predicate $Q(x, y)$ can be viewed as a $\mathbf{2}$-enriched profunctor $Q: X^{op} \times Y \to \mathbf{2}$ where $X$ is the type of the variable $x$, and $Y$ is the type of $y$. In usual logic $X$ and $Y$ are interpreted as sets and $X^{op}$ is the same as $X$. There is always a trivial or tautological profunctor $\top: Y^{op} \times 1 \to \mathbf{2}$ which is in usual logic is denoted "true". Then the $\mathbf{2}$-enriched profunctor composite $Q \otimes \top$ is given by $(Q \otimes \top)(x, \ast) = \int^y Q(x, y) \wedge \top(y, \ast) = \exists_y Q(x, y) \wedge \top = \exists_y Q(x, y)$.

   Keith: yes. A predicate $Q(x, y)$ can be viewed as a $\mathbf{2}$-enriched profunctor $Q: X^{op} \times Y \to \mathbf{2}$ where $X$ is the type of the variable $x$, and $Y$ is the type of $y$. In usual logic $X$ and $Y$ are interpreted as sets and $X^{op}$ is the same as $X$. There is always a trivial or tautological profunctor $\top: Y^{op} \times 1 \to \mathbf{2}$ which is in usual logic is denoted “true”. Then the $\mathbf{2}$-enriched profunctor composite $Q \otimes \top$ is given by $(Q \otimes \top)(x, \ast) = \int^y Q(x, y) \wedge \top(y, \ast) = \exists_y Q(x, y) \wedge \top = \exists_y Q(x, y)$.

5. • CommentRowNumber5.
   • CommentAuthorKeithEPeterson
   • CommentTimeDec 10th 2016
   • (edited Dec 10th 2016)
   • PermaLink
   Author: KeithEPeterson
   Format: MarkdownItexI really need to study more (co)end calculus.

   I really need to study more (co)end calculus.

6. • CommentRowNumber6.
   • CommentAuthorJohn Baez
   • CommentTimeDec 10th 2016
   • (edited Dec 10th 2016)
   • PermaLink
   Author: John Baez
   Format: MarkdownItexWhoops - I'd forgotten that sequents implicitly give you universal quantifiers. So the logic of GLAV constraints is weaker than coherent logic. Does it fit in [regular logic](https://ncatlab.org/nlab/show/regular+logic)? The nLab article on regular logic is a bit reticent about what counts as a legitimate sequent in that form of logic.

   Whoops - I’d forgotten that sequents implicitly give you universal quantifiers. So the logic of GLAV constraints is weaker than coherent logic. Does it fit in regular logic? The nLab article on regular logic is a bit reticent about what counts as a legitimate sequent in that form of logic.

7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeDec 10th 2016
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexIt's usually easier (for me, anyway) to focus on semantics, i.e., what this would mean in regular categories. So we have some subobject $P \hookrightarrow X$ and a subobject $Q \hookrightarrow X \times Y$, and $(\exists y)\; Q(x, y)$ represents the image $p_1(Q) \hookrightarrow X$ of the projection $p_1: X \times Y \to X$, and so an axiom of type $P(x) \vdash (\exists y)\; Q(x, y)$ is interpreted by a condition $P \leq p_1(Q)$ on subobjects. (I'm assuming that a GLAV theory is given by axioms of the type you specified.) So yes, regular categories/logic at least have enough in them to express such sequents. But, there are some restrictions on the strength of the logic with which you reason with them (i.e., not enough rules of deduction in regular logic to do some things). I'm afraid that our articles on "internal logics" are a little skimpy on the rules of deduction allowed in each case, but again it's probably easier just to consider in each case the semantics. For example, in regular logic, we shouldn't expect to be able to prove that $R \wedge (S \vee T)$ and $(R \wedge S) \vee (R \wedge T)$ are equivalent for formulas $R, S, T$ of the same type, since subobject lattices in regular categories typically aren't distributive (this is false for example in abelian groups). But we should expect to be able to prove (even if we don't exactly know the rules of deduction!) that $R(x) \wedge (\exists y) Q(x, y)$ is equivalent to $(\exists y) R(x) \wedge Q(x, y)$, because pulling back along $R \hookrightarrow X$ preserves images in a regular category.

   It’s usually easier (for me, anyway) to focus on semantics, i.e., what this would mean in regular categories. So we have some subobject $P \hookrightarrow X$ and a subobject $Q \hookrightarrow X \times Y$, and $(\exists y)\; Q(x, y)$ represents the image $p_1(Q) \hookrightarrow X$ of the projection $p_1: X \times Y \to X$, and so an axiom of type $P(x) \vdash (\exists y)\; Q(x, y)$ is interpreted by a condition $P \leq p_1(Q)$ on subobjects. (I’m assuming that a GLAV theory is given by axioms of the type you specified.)

   So yes, regular categories/logic at least have enough in them to express such sequents. But, there are some restrictions on the strength of the logic with which you reason with them (i.e., not enough rules of deduction in regular logic to do some things). I’m afraid that our articles on “internal logics” are a little skimpy on the rules of deduction allowed in each case, but again it’s probably easier just to consider in each case the semantics. For example, in regular logic, we shouldn’t expect to be able to prove that $R \wedge (S \vee T)$ and $(R \wedge S) \vee (R \wedge T)$ are equivalent for formulas $R, S, T$ of the same type, since subobject lattices in regular categories typically aren’t distributive (this is false for example in abelian groups). But we should expect to be able to prove (even if we don’t exactly know the rules of deduction!) that $R(x) \wedge (\exists y) Q(x, y)$ is equivalent to $(\exists y) R(x) \wedge Q(x, y)$, because pulling back along $R \hookrightarrow X$ preserves images in a regular category.

8. • CommentRowNumber8.
   • CommentAuthorMike Shulman
   • CommentTimeDec 10th 2016
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexin regular logic you can't even write down $R\wedge (S\vee T)$: the connective $\vee$ doesn't exist. Semantically, subobject posets in a regular category don't even necessarily have joins.

   in regular logic you can’t even write down $R\wedge (S\vee T)$: the connective $\vee$ doesn’t exist. Semantically, subobject posets in a regular category don’t even necessarily have joins.

9. • CommentRowNumber9.
   • CommentAuthorMike Shulman
   • CommentTimeDec 10th 2016
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexBut beyond that, there's no restriction on the inference rules of regular logic --- they're just all the rules of ordinary intuitionistic natural deduction or sequent calculus except the ones involving connectives like $\vee,\to,\forall$ that don't exist in regular logic.

   But beyond that, there’s no restriction on the inference rules of regular logic — they’re just all the rules of ordinary intuitionistic natural deduction or sequent calculus except the ones involving connectives like $\vee,\to,\forall$ that don’t exist in regular logic.

10. • CommentRowNumber10.
    • CommentAuthorTodd_Trimble
    • CommentTimeDec 11th 2016
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexOops! Yes, you're right.

    Oops! Yes, you’re right.