Intereting Posts

Sequence of surjections imply choice
Summation of weighted squares of binomial coefficients
Is speed an important quality in a mathematician?
What is the key to success for a mathematician?
“Plotting” an equation
Numbers representable as $x^2 + 2y^2$
Determinant of a adjoint
Find vector field given curl
Proving the every subset of $M$ is clopen.
Is the complement of a prime ideal closed under both addition and multiplication?
Tarski Monster group with prime $3$ or $5$
$\frac{(2n)!}{4^n n!^2} = \frac{(2n-1)!!}{(2n)!!}=\prod_{k=1}^{n}\bigl(1-\frac{1}{2k}\bigr)$
Is it wrong to tell children that $1/0 =$ NaN is incorrect, and should be $∞$?
A determinant inequality
Non-Linear Transformation

It’s said on Wikipedia page about Post’s lattice that DM clone(all monotone self-dual functions) has majority function $(xy + xz + yz)$ as one of its bases. What is the proof of this fact?

- Are variables logical or non-logical symbols in a logic system?
- Can every proof by contradiction also be shown without contradiction?
- Why is Skolem normal form equisatisfiable while the second order form equivalent?
- **Ended Competition:** What is the shortest proof of $\exists x \forall y (D(x) \to D(y)) $?
- Difference between proof of negation and proof by contradiction
- How is (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ≡ (p ∧ ¬r) ∨ (¬q ∧ q)? Is it really distributive property?
- How to find if a valuation satisfies a statement?
- Neither provable nor disprovable theorem
- Using $p\supset q$ instead of $p\implies q$
- Implies vs. Entails vs. Provable

I proved this a few years ago as a homework assignment. Even if it’s not *your* homework assignment, that makes me reluctant to give a complete solution; however, the hints below should be helpful.

**Method 1:** The proof I submitted is along the following lines: given a monotone self-dual function $f$, show by induction that for all sufficiently small nonnegative integers $l$, there is another function $g_l$ (of the same arity as $f$) such that $||f-g_l||_1 = 2l$ and $g_l$ is in the clone. (Here $||f-g||_1$ is the “$l_1$-norm,” which in this case is just the number of $x$ for which $f(x)\neq g(x)$.) The basis case is obvious: pick an arbitrary function you know is in the clone. For the inductive step, you have to figure out how to take $g_l$ and produce $g_{l-1}$, which I’ll leave out, but a hint is that there is a $g_{l-1}$ with $||g_l – g_{l-1}||_1 = 2$, i. e., $g_{l-1}$ is almost the same as $g_l$. The conclusion (by induction) is the case $l=0$, but $g_0$ has to be $f$, so $f$ is in the clone. (Informally: you can start at some function in the clone and “walk” by simple steps to any other monotone self-dual function of the same arity, and adjacent functions on the walk can be obtained from one another using the majority function.)

**Method 2:** However, there’s a much neater argument by induction on the arity of $f$. To simplify future notation, let $\bar{x} = (x_4,\ldots,x_n)$, so $f(x_1,\ldots,x_n) = f(x_1,x_2,x_3,\bar{x})$. Observe that if

$f:\{0,1\}^n\to \{0,1\}$ is monotone and self-dual and $n> 3$, then the

three functions of $n-1$ arguments $$f_1(x,y,\bar{x}) =

f(x,y,y,\bar{x}),$$ $$f_2(x,y,\bar{x}) = f(y,x,y,\bar{x}),$$

$$f_3(x,y,\bar{x}) = f(y,y,x,\bar{x}),$$ are monotone and self-dual

as well, and moreover, they determine $f$. (Indeed, out of $x_1,x_2,x_3$,

at least 2 must be equal, so for example, if $x_1 = x_2$, then

$f(x_1,\ldots,x_n) = f_3(x_3,x_2,\bar{x})$.) All you have to do now is reconstruct $f$ from $f_1,f_2,f_3$ using only the majority function. Thankfully, the construction is very simple, although it may not be obvious at first why it works: $$f(x_1,\ldots,x_n) = M(f_1(x_1,x_3,\bar{x}), f_2(x_2,x_1,\bar{x}), f_3(x_3,x_2,\bar{x}))$$ (where $M$ is the majority function). (Hint: prove the case $x_1=1,x_2=x_3=0$, and the rest should become obvious. You need monotonicity here, but surprisingly not self-duality.) The basis case is $n\leq 3$ (where self-duality is needed).

Oh, well; I guess that’s almost a complete solution anyway, but I don’t feel like going back and removing steps from the argument at the risk of making it cryptic and useless. 🙂

- The image of an ideal under a homomorphism may not be an ideal
- Laurent Series for $\cot(\pi z)$
- dA in polar coordinates?
- Induction and convergence of an inequality: $\frac{1\cdot3\cdot5\cdots(2n-1)}{2\cdot4\cdot6\cdots(2n)}\leq \frac{1}{\sqrt{2n+1}}$
- History of Dual Spaces and Linear Functionals
- Does set $\mathbb{R}^+$ include zero?
- Is this variant of the Jordan Curve Theorem true?
- Expectation (and concentration?) for $\min(X, n-X)$ when $X$ is a Binomial
- Construct the Green s function for the equation
- how can we convert sin function into continued fraction?
- Why hasn't GCH become a standard axiom of ZFC?
- Understanding implicit differentiation with concepts like “function” and “lambda abstraction.”
- If $T:X \to Y$ is a linear homeomorphism, is its adjoint $T^*$ a linear homeomorphism?
- How do you find the smallest of homeomorphic ordinals?
- $\mathbb Z_p^*$ is a group.