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

Nota bene: all rings are supposed commutative with $1$ and all ring homomorphism should be unital.

Let $B$ be the set of truth values {True, False}. For a formula $\phi$ denote by $[\phi]\in B$ it's truth value. E.g. $[x=x] = True$ for all $x$.

Let $o\colon B^n \to B$ a $n$-ary truth-operation, $0≠n\in \mathbb{N}$.
Let $B$ be a Rings $\mathfrak p\subset B$ a prime Ideal. We say the triple $(o,\mathfrak p,B)$ is $A$-guessable if $B$ is an $A$-Algebra (i.e. there is a chosen ring homomorphism $A\to B$) and there exists a polynomial $f_o=f_o(T_1,\ldots,T_n)\in A[T_1,\ldots,T_n]$ such that for all $x_1,\ldots, x_n\in B$ we have $[f_o(x_1,\ldots,x_n)\in\mathfrak{p}]=o([x_1\in \mathfrak{p}],\ldots,[x_n\in\mathfrak{p}])$.

Clearly for any Ring $A$ a triple $(o,\mathfrak p,B)$ is $B$-guessable (with $id\colon B\to B$) if it is $A$-guessable if it is $\mathbb{Z}$-guessable (with the obvious map $\mathbb{Z}\to B$).
Call a triple $(o, \mathfrak p,B)$ guessable if it is $B$-guessable
Call $o$ (very) easy if every triple $(o, \mathfrak p,B)$ is ($\mathbb{Z}$-) guessable.

Examples:
if $o=pr_i\colon(v_1,\ldots,v_n)\mapsto v_i$ for some $i$, then trivially every $(o, \mathfrak p,B)$ is guessable by $\mathbb{Z}$ via $f_o=T_i$
if $o=\vee\colon (v_1,\ldots,v_n)=v_1\vee\ldots\vee v_n$, then every $(o', \mathfrak p,B)$ is guessable by $\mathbb{Z}$ via $f_{o'}=T_1\cdot T_2\cdots T_n$. (because $\mathfrak{p}$ is prime)
So both $o$ and $o'$ are very easy.

Question 1: Are there other easy or very easy $n$-ary truth-operations other than $\vee$ and $pr$? In particular I would like to know if $\wedge$ is (very) easy.
Question 2: Is there a difference between guessable and $\mathbb{Z}$-guessable, i.e. are there triples which are guessable but not $\mathbb{Z}$-guessable? For which rings $B$ can such a difference occur?

share|improve this question

1 Answer 1

The only easy operations are the constant operation $\operatorname{False}$ (represented by $0$), the constant operation $\operatorname{True}$ (represented by $1$), and the operation where we apply OR to a subset of the variable (basically a combination of your two examples).

To see this, like $k$ be any field that's an $A$-algebra. Let $B=k[x_1,\dots,x_n]$. We divide into two cases: $f=0$ or $f \neq 0$.

If $f=0$, then clearly the logical operation must be $\operatorname{True}$.

If $f\neq 0$, then if $\mathfrak p=(0)$ then $x_1,\dots,x_n,f\not\in \mathfrak p$, so $o(\operatorname{False},\dots,\operatorname{False})=\operatorname{False}$. Next, we can factor $f$ into irreducible polynomials. We will show that each irreducible factor of $f$ is one of the variables $x_1,\dots,x_n$. Suppose for contradiction that $g$ is an irreducible factor of $f$ that is not one of $x_1,\dots,x_n$. If $\mathfrak p=(g)$, then $x_1,\dots x_n \not \in \mathfrak p$ but $f \in \mathfrak p$, so $o(\operatorname{False},\dots,\operatorname{False})=\operatorname{True}$.

So the only irreducible factors are $x_1,\dots x_n$, so $f=c x_1^{r_1} \dots x_n^{r_n}$ for $c$ a nonzero constant. Clearly in this case we can check that $f$ is one of the operations I describe - it is just OR applied to the set of $v_i$ such that $r_i$ is nonzero.

For a fixed $B$, more logical operations may be possible. For instance, over $\mathbb F_2$ it is clear that every logical operation is possible. One can also see this for any finite field $\mathbb F_q$. But for a general ring, these are all.

share|improve this answer

Your Answer

 
discard

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.