Skip to main content
Post Undeleted by Adam P. Goucher
added 151 characters in body
Source Link
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

The indicator function of the following 96-element setYes, your conjecture is true.

Suppose otherwise. Then there exists a counter-examplecounterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f(X) = 1$.

There are $5440$ different choices of the tuple $(A, B, C) \in \mathcal{P}(8)^3$ satisfying your constraints. For each such tuple, we obtain two clauses which must be true of the counterexample $f$:

$$ \{ 0, 1, 02, 12, 03, 13, 023, 123, 04, 14, 024, 124, 034, 134, 0234, 1234, 05, 15, 025, 125, 035, 135, 0235, 1235, 045, 145, 0245, 1245, 0345, 1345, 02345, 12345, 06, 16, 026, 126, 036, 136, 0236, 1236, 046, 146, 0246, 1246, 0346, 1346, 02346, 12346, 056, 156, 0256, 1256, 0356, 1356, 02356, 12356, 0456, 1456, 02456, 12456, 03456, 13456, 023456, 123456, 7, 27, 37, 237, 47, 247, 347, 2347, 57, 257, 357, 2357, 457, 2457, 3457, 23457, 67, 267, 367, 2367, 467, 2467, 3467, 23467, 567, 2567, 3567, 23567, 4567, 24567, 34567, 234567 \} $$$$ (\neg P_C \lor \neg P_{A \cup C} \lor \neg P_{B \cup C} \lor \neg P_{A \cup B \cup C}) $$

where$$ (P_C \lor P_{A \cup C} \lor P_{B \cup C} \lor P_{A \cup B \cup C}) $$

This gives a succinct list of $10880$ clauses which must be true of the $256$ primitive propositions $\{ P_X : X \in \mathcal{P}(8) \}$.

Inputting this list of clauses into the SAT solver Glucose gives the response 'UNSAT' (for instancemeaning 'unsatisfiable') $2467$, so no such counterexample exists. It also exports a verifiable certificate of unsatisfiability which can be checked in polynomial time.

The proof is shorthand for the setsomewhat unilluminating, because it doesn't give any indication as to $\{2, 4, 6, 7\}$why your conjecture is true, just that it is.

The indicator function of the following 96-element set is a counter-example:

$$ \{ 0, 1, 02, 12, 03, 13, 023, 123, 04, 14, 024, 124, 034, 134, 0234, 1234, 05, 15, 025, 125, 035, 135, 0235, 1235, 045, 145, 0245, 1245, 0345, 1345, 02345, 12345, 06, 16, 026, 126, 036, 136, 0236, 1236, 046, 146, 0246, 1246, 0346, 1346, 02346, 12346, 056, 156, 0256, 1256, 0356, 1356, 02356, 12356, 0456, 1456, 02456, 12456, 03456, 13456, 023456, 123456, 7, 27, 37, 237, 47, 247, 347, 2347, 57, 257, 357, 2357, 457, 2457, 3457, 23457, 67, 267, 367, 2367, 467, 2467, 3467, 23467, 567, 2567, 3567, 23567, 4567, 24567, 34567, 234567 \} $$

where (for instance) $2467$ is shorthand for the set $\{2, 4, 6, 7\}$.

Yes, your conjecture is true.

Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f(X) = 1$.

There are $5440$ different choices of the tuple $(A, B, C) \in \mathcal{P}(8)^3$ satisfying your constraints. For each such tuple, we obtain two clauses which must be true of the counterexample $f$:

$$ (\neg P_C \lor \neg P_{A \cup C} \lor \neg P_{B \cup C} \lor \neg P_{A \cup B \cup C}) $$

$$ (P_C \lor P_{A \cup C} \lor P_{B \cup C} \lor P_{A \cup B \cup C}) $$

This gives a succinct list of $10880$ clauses which must be true of the $256$ primitive propositions $\{ P_X : X \in \mathcal{P}(8) \}$.

Inputting this list of clauses into the SAT solver Glucose gives the response 'UNSAT' (meaning 'unsatisfiable'), so no such counterexample exists. It also exports a verifiable certificate of unsatisfiability which can be checked in polynomial time.

The proof is somewhat unilluminating, because it doesn't give any indication as to why your conjecture is true, just that it is.

Post Deleted by Adam P. Goucher
Source Link
Adam P. Goucher
  • 12.4k
  • 2
  • 54
  • 105

The indicator function of the following 96-element set is a counter-example:

$$ \{ 0, 1, 02, 12, 03, 13, 023, 123, 04, 14, 024, 124, 034, 134, 0234, 1234, 05, 15, 025, 125, 035, 135, 0235, 1235, 045, 145, 0245, 1245, 0345, 1345, 02345, 12345, 06, 16, 026, 126, 036, 136, 0236, 1236, 046, 146, 0246, 1246, 0346, 1346, 02346, 12346, 056, 156, 0256, 1256, 0356, 1356, 02356, 12356, 0456, 1456, 02456, 12456, 03456, 13456, 023456, 123456, 7, 27, 37, 237, 47, 247, 347, 2347, 57, 257, 357, 2357, 457, 2457, 3457, 23457, 67, 267, 367, 2367, 467, 2467, 3467, 23467, 567, 2567, 3567, 23567, 4567, 24567, 34567, 234567 \} $$

where (for instance) $2467$ is shorthand for the set $\{2, 4, 6, 7\}$.