Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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.

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.

The paper in question:


Definition 2.1 and Example 2.3 are the relevant bits.

Can anyone lend any insight here?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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

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

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

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.

I hope this helps.

share|improve this answer
Thanks a bunch. That also makes other bits that were confusing me make sense. I don't know how I managed to glance over that comment in the paper. –  Olix Feb 20 '11 at 18:07
add comment

Edit: Jason Rute beat me to it by 52 seconds.

From a quick look at that paper it seems negative arity refers to contravariance: e.g. if $A \vdash B$, then $\lnot B \vdash \lnot A$. It's all explained in Comment 1, below Definition 2.1.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.