Positive & Negative Arity - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T14:23:17Z http://mathoverflow.net/feeds/question/56077 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56077/positive-negative-arity Positive & Negative Arity Olix 2011-02-20T16:54:50Z 2011-02-20T17:42:33Z <p>Hi,</p> <p>You can talk about the arity of a function or an operation - something like addition could have an arity of 2, and negation usually has an arity of 1.</p> <p>A paper I am reading is talking about positive arities and negative arities, and I don't understand what this means. The author gives an example in classical logic: he says disjunction and conjuction have a positive arity of 2, while negation has a negative arity of 1. I suppose I am reading a bit above my level here, but I don't get why there needs to be a distinction between these.</p> <p>The paper in question:</p> <p><a href="http://drops.dagstuhl.de/opus/volltexte/2010/2649/" rel="nofollow">http://drops.dagstuhl.de/opus/volltexte/2010/2649/</a></p> <p>Definition 2.1 and Example 2.3 are the relevant bits.</p> <p>Can anyone lend any insight here?</p> http://mathoverflow.net/questions/56077/positive-negative-arity/56084#56084 Answer by Jason Rute for Positive & Negative Arity Jason Rute 2011-02-20T17:41:41Z 2011-02-20T17:41:41Z <p>While I have never seen this notion before (it may be common or this may be the first paper that uses those terms), Comment 1 basically explains the idea. A relation $r$ in $\mathcal{R}_{n,m}$ is an $n+m$-arity relation (on propositional formulas I believe), where the first $n$ inputs are considered "positive", and the last $m$ are "negative".</p> <p>To see what these mean, consider the following case. Say $r$ is a $\mathcal{R}_{1,0}$ relation, i.e. the only input is positive. Further, say $B$ is deducible from $A$. (You will have to look in the paper to see what deducible exactly means here.) Then since the arity is positive, $r(B)$ is deducible from $r(A)$. An example would be the trivial relation $r(A) := A$. Another example with a positive arity of $2$ is conjunction in classical logic. If $B_0$ and $B_1$ are deductible from $A_0$ and $A_1$ respectively, then $B_0 \wedge B_1$ is deducible from $A_0 \wedge A_1$. </p> <p>In the negative case, it is the opposite. Say $r$ is a $\mathcal{R}_{0,1}$ relation, i.e. the only input is negative. Again, say $B$ is deducible from $A$. Then since the arity is negative, $r(A)$ is deducible from $r(B)$---the opposite direction as before. An example would be the negation relation in classical logic; if $B$ is deducible from $A$, then $\neg A$ is deducible from $\neg B$. (The contrapositive.)</p> <p>These can be combined so that a relation has both positive and negative arities. An example is implication in classical logic, which is a $\mathcal{R}_{1,1}$ relation, i.e. it has one positive arity and one negative arity. If $B_0$ and $B_1$ are deducible from $A_0$ and $A_1$ respectively, then $A_0 \rightarrow B_1$ is deductible from $B_0 \rightarrow A_1$. (This is basically $A_0$ implies $B_0$ implies $A_1$ implies $B_1$.) The antecedent is the negative input, while the consequent is the positive one.</p> <p>I hope this helps.</p> http://mathoverflow.net/questions/56077/positive-negative-arity/56085#56085 Answer by Finn Lawler for Positive & Negative Arity Finn Lawler 2011-02-20T17:42:33Z 2011-02-20T17:42:33Z <p>Edit: Jason Rute beat me to it by 52 seconds.</p> <p>From a quick look at that paper it seems negative arity refers to <em>contravariance</em>: e.g. if $A \vdash B$, then $\lnot B \vdash \lnot A$. It's all explained in Comment 1, below Definition 2.1.</p>