Can every β∈Eq(A) be represented by some terms using α1,α2,α3,α4∈Eq(A) and ∩,∨?

53 Views Asked by At

$A$ set $A$ is nonempty and finite. $Eq(A)$ is the set of all equivalence relations on a set $A.$ Then Eq(A)=$(Eq(A);\subset).$ How can I prove that we can choose $\alpha_1,\alpha_2,\alpha_3,\alpha_4\in Eq(A)$ such that every $\beta \in Eq(A)$ can be represented by some terms using $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ and $\cap,\lor?$

2

There are 2 best solutions below

0
On BEST ANSWER

Presumably you can find the proof in this paper.

Strietz, Heinrich
Finite partition lattices are four-generated.
Proceedings of the Lattice Theory Conference (Ulm, 1975),
pp. 257-259. Univ. Ulm, Ulm, 1975.

(I didn't read it.)

1
On

You can't.

If $A$ has at least $34$ elements $a_1,\ldots, a_{17}$ and $b_1\ldots, b_{17}$, then for any join/intersection-expression $\beta$ built from $\alpha_1,\ldots,\alpha_4$, the result whether $(a_i,b_i)\in\beta$ depend only on the four "bits" $$\langle (a_i,b_i)\stackrel ?\in\alpha_1,(a_i,b_i)\stackrel ?\in\alpha_2,(a_i,b_i)\stackrel ?\in\alpha_3,(a_i,b_i)\stackrel ?\in\alpha_4\rangle.$$ As there are only sixteen possible bit patterns, two of the seventeen pairs must have the same pattern, hence would have to be treated the same by every equivalence relation $\beta$. This is clearly not the case.