Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 1 result · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs; all 1 also cleared it.

Halpern–Läuchli and BPI Without Choice — Examples

1 · Prerequisites

2 · Summary

The examples compute the distinctions among common-level products, full products, dense matrices, and unequal cone heights. The dimension-two word calculation displays every legal rearrangement, while the finite--cofinite algebra makes the compactness-tree prime ideal concrete.

The final countermodel explains why BPI does not well-order every set. In the basic Cohen model its infinite Dedekind-finite set of reals cannot be well-ordered, since repeatedly taking the least unused member would enumerate infinitely many distinct elements.

3 · Logical flowchart

4 · Definitions, theorems and proofs

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-14Open item page →

A two-tree level product and dense matrix

Example

Let $T_{1} = T_{2} = 2^{< ω}$ , ordered by extension. The level product, the full product, and a dense matrix can be seen explicitly and are not the same notion.

Facts & Assumptions

Given: The two full binary trees in the example.

[F1]

The local definition distinguishes common-level products, full products, and coordinatewise $(h, k)$ -matrices. Finitistic trees, level products, density, and matrices

Verification

1.1F1given

Since $T_{i} (2) = {00, 01, 10, 11}$ , its level-2 product consists of the sixteen pairs ${(00, 00), (00, 01), (00, 10), (00, 11), (01, 00), (01, 01), (01, 10), (01, 11), (10, 00), (10, 01), (10, 10), (10, 11), (11, 00), (11, 01), (11, 10), (11, 11)}$ . Every pair has common coordinate height $2$ .

1.2F1construct

For $h = 1, k = 2$ , use roots $0 \in T_{1} (1)$ and $1 \in T_{2} (1)$ and put $A_{1} = {000, 0010, 010, 011}$ and $A_{2} = {100, 101, 110, 111}$ . The height-3 frontier above $0$ is ${000, 001, 010, 011}$ ; the listed members of $A_{1}$ respectively dominate those four nodes. The height-3 frontier above $1$ is exactly $A_{2}$ . Thus both factors are $(1, 2)$ -dense, and $A_{1} \times A_{2}$ is a $(1, 2)$ -matrix.

2.1F1step 1.1

The pair $(0, 101)$ belongs to the full product $T_{1} \times T_{2}$ , but its coordinate heights are $1$ and $3$ , so it belongs to no common-level product.

3.1F1step 1.2step 2.1∎

This matrix is a subset of the full product but not of the level product: it contains $(0010, 100)$ , whose heights are $4$ and $3$ . Hence the level product imposes equal heights, the full product imposes none, and being a matrix imposes coordinatewise domination rather than equal height.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-14Open item page →

The common-height cone repair in the complement case

Example

In two binary trees, take cone roots of heights $1$ and $3$ . Extending the first root to the common height $3$ before restricting the dense frontiers produces a genuine common-height matrix.

Facts & Assumptions

Given: $T_{1} = T_{2} = 2^{< ω}$ , the roots $t_{1} = 0$ and $t_{2} = 101$ , and a finite $k \geq 0$ .

[F1]

Common-height cone extension and restriction preserve the adjusted density parameters. Finitistic trees, level products, density, and matrices

Verification

1.1F1givenconstruct

The roots have heights $1$ and $3$ , so they cannot themselves witness one $(h, k)$ -matrix. Put $h = 3$ , extend $t_{1}$ to $s_{1} = 011$ , and take $s_{2} = t_{2} = 101$ .

2.1F1step 1.1

Let $p = h + k$ and $B_{i} = T_{i} (p)$ . Then $B_{i}$ is $p$ -dense. Set $C_{1} = B_{1} \cap {u : 011 ≼ u}$ and $C_{2} = B_{2} \cap {u : 101 ≼ u}$ . Each $C_{i}$ is exactly the height- $(3 + k)$ frontier above $s_{i}$ , hence is $(3, k)$ -dense, and $C_{1} \times C_{2}$ is a $(3, k)$ -matrix.

3.1F1step 2.1

For example, when $k = 2$ , $C_{1} = {01100, 01101, 01110, 01111}$ and $C_{2} = {10100, 10101, 10110, 10111}$ . Each listed set dominates all four height-5 nodes above its height-3 root; when $k = 0$ , the calculation instead gives the singleton sets ${011}$ and ${101}$ .

4.1F1step 1.1step 2.1∎

More generally, if $B_{i}$ is merely $(3 + k)$ -dense rather than the whole level, the same restrictions remain $(3, k)$ -dense: a height- $(3 + k)$ extension of $s_{i}$ is dominated by some member of $B_{i}$ , and that member automatically lies above $s_{i}$ . This is the exact common-height repair used in the complement case.

ExampleConstruction: Literature-sourcedVerification: AI-adaptedjudge pass (gpt-5.6-terra)audited 2026-09-14Open item page →

A dimension-two Halpern–Läuchli word rearrangement

Example

For $d = 2$ , the two endpoint words admit the following complete derivation:

$\forall a_{1} \forall a_{2} \exists x_{1} \exists x_{2} ⊢_{2} \exists A_{1} \exists A_{2} \forall x_{1} \forall x_{2} .$

Facts & Assumptions

Given: Dimension $d = 2$ and the endpoint words above.

[F1]

The preceding definition gives all legal Rule 1, Rule 2, and Rule 3 moves in $L_{2}$ . The finite word calculus for the Halpern–Läuchli argument

[F2]

The general endpoint rearrangement holds for every positive dimension. Finite word-calculus rearrangement

Verification

1.1F1given

Start with $W_{0} = \forall a_{1} \forall a_{2} \exists x_{1} \exists x_{2} \in L_{2}$ .

2.1F1step 1.1

Commute the universal symbols by Rule 1: $W_{0} ⊢_{2} W_{1} = \forall a_{2} \forall a_{1} \exists x_{1} \exists x_{2}$ .

3.1F1step 2.1

Apply Rule 2 to the adjacent coordinate-1 pair: $W_{1} ⊢_{2} W_{2} = \forall a_{2} \exists A_{1} \forall x_{1} \exists x_{2}$ .

4.1F1step 3.1

Apply Rule 3 with $r = 1$ and permutation $σ = (2, 1)$ : $W_{2} ⊢_{2} W_{3} = \exists A_{1} \forall a_{2} \forall x_{1} \exists x_{2}$ .

5.1F1step 4.1

Commute the adjacent universal symbols by Rule 1: $W_{3} ⊢_{2} W_{4} = \exists A_{1} \forall x_{1} \forall a_{2} \exists x_{2}$ .

6.1F1step 5.1

Apply the reverse direction of Rule 2 to coordinate 1: $W_{4} ⊢_{2} W_{5} = \forall a_{1} \exists x_{1} \forall a_{2} \exists x_{2}$ .

7.1F1step 6.1

Apply Rule 2 to coordinate 2: $W_{5} ⊢_{2} W_{6} = \forall a_{1} \exists x_{1} \exists A_{2} \forall x_{2}$ .

8.1F1step 7.1

Commute the adjacent existential symbols by Rule 1: $W_{6} ⊢_{2} W_{7} = \forall a_{1} \exists A_{2} \exists x_{1} \forall x_{2}$ .

9.1F1step 8.1

Apply Rule 3 with $r = 1$ and $σ = (1, 2)$ : $W_{7} ⊢_{2} W_{8} = \exists A_{2} \forall a_{1} \exists x_{1} \forall x_{2}$ .

10.1F1F2step 9.1∎

Apply Rule 2 to coordinate 1 and then commute the two existential symbols by Rule 1: $W_{8} ⊢_{2} \exists A_{2} \exists A_{1} \forall x_{1} \forall x_{2} ⊢_{2} \exists A_{1} \exists A_{2} \forall x_{1} \forall x_{2}$ . Every displayed word contains, for each coordinate, exactly one legal ordered pair, so all lie in $L_{2}$ ; this is the $d = 2$ instance of F2.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-5.6-terra)audited 2026-09-14Open item page →

A prime-ideal compactness tree for the finite–cofinite algebra

Example

For the finite–cofinite Boolean algebra on $ω$ , the canonical compactness-tree branch which always selects the cofinite remainder has the finite-set ideal as its zero fibre.

Facts & Assumptions

Given: $B = {A \subseteq ω : A is finite or ω ∖ A is finite}$ with union, intersection, and complement.

[F1]

Finite partial prime-ideal diagrams identifies a finite partial prime-ideal diagram with a homomorphism on its whole finite generated subalgebra and identifies the nonzero Boolean cells as its atoms.

[F2]

The compactness tree yields a prime ideal for an enumerated Boolean algebra proves that an enumerated nontrivial Boolean algebra has a prime ideal; the explicit levels and branch below are computed directly rather than attributed to this Statement.

Verification

1.1givenconstruct

Enumerate the finite subsets as $F_{0} = \emptyset, F_{1} = {0}, F_{2} = {1}, F_{3} = {0, 1}, \dots$ by increasing binary code, and enumerate $B$ by $b (2 n) = F_{n}$ , $b (2 n + 1) = ω ∖ F_{n}$ . This is onto, including repetitions such as $b (0) = \emptyset$ and $b (1) = ω$ .

2.1F1step 1.1

At levels $0, 1, 2$ the generated algebra is ${\emptyset, ω}$ and has its unique homomorphism to $2$ . At level $3$ , after ${0}$ appears, the generated algebra has atoms ${0}$ and $ω ∖ {0}$ and hence two homomorphisms, with respective values $1$ and $0$ on ${0}$ . Level $4$ adds only its complement and has the same two nodes.

3.1F1step 2.1

At level $5$ , the generators include ${0}$ and ${1}$ ; the atoms are ${0}$ , ${1}$ , and $R_{2} = ω ∖ {0, 1}$ . The three homomorphisms select these atoms and have value pairs $(1, 0), (0, 1), (0, 0)$ on the two singletons. The last node restricts to the value- $0$ node at level $3$ .

4.1F1step 1.1step 2.1step 3.1construct

At any finite stage let $E$ be the finite union of all finite generators seen so far. The generated algebra has the finitely many atomic pieces inside $E$ and the single cofinite remainder $R = ω ∖ E$ . Evaluation at $R$ is the unique level node assigning $0$ to every finite member of that subalgebra and $1$ to every cofinite member. These nodes restrict coherently, so they form the branch illustrated by steps 2.1 and 3.1.

5.1F1F2step 4.1∎

The union homomorphism is $h (A) = 0$ when $A$ is finite and $h (A) = 1$ when $A$ is cofinite. Its zero fibre is therefore $F i n$ . This is proper and prime: if $A, B$ are both cofinite then $A \cap B$ is cofinite, so $A \cap B$ can be finite only when at least one of $A, B$ is finite. This explicit prime ideal agrees with F2's existence conclusion.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-14Open item page →

BPI well-orders every set

False statement

The Boolean Prime Ideal Theorem implies that every set can be well-ordered.

Why this is false

Whenever the basic Cohen symmetric construction in F1 is supplied, its model satisfies BPI and contains an infinite Dedekind-finite set of reals, which cannot be well-ordered. Independently, F2 gives the exact syntactic nonimplication conditional on $Con (Z F)$ .

Facts & Assumptions

Given: Assume $Con (Z F)$ for the conditional nonimplication.

[F1]

The basic Cohen model satisfies BPI and fails Choice supplies the basic Cohen model and its infinite Dedekind-finite symmetric set $A$ .

[F2]

Relative consistency of BPI without Choice over ZF supplies the exact syntactic consistency implication from ZF to ZF+BPI+ $\neg$ AC.

[F3]

The Axiom of Choice defines AC as the assertion that every family of nonempty sets has a choice function.

Proof

technique · conditional countermodel

1.1F1assume-contra

In the F1 model, suppose $A$ had a well-order. Recursively choose the least member not chosen earlier. If the recursion stopped, $A$ would be finite; if it did not, it would inject $ω$ into $A$ . Both alternatives contradict that $A$ is infinite and Dedekind-finite. Hence $A$ is not well-orderable although BPI holds.

2.1F2F3step 1.1discharge-contradiction∎

Universal well-orderability implies F3 directly. Given a family $F$ of nonempty sets, well-order $⋃ F$ and assign to every $X \in F$ its least member; Replacement produces the resulting choice function. Therefore, if ZF+BPI proved universal well-orderability, it would prove AC. This contradicts the consistency of ZF+BPI+ $\neg$ AC supplied by F2 and gives the syntactic conditional counterexample.

5 · Examples, counterexamples and false statements

None yet.

Halpern–Läuchli and BPI Without Choice — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

A two-tree level product and dense matrix

Example

Facts & Assumptions

Verification

The common-height cone repair in the complement case

Example

Facts & Assumptions

Verification

A dimension-two Halpern–Läuchli word rearrangement

Example

Facts & Assumptions

Verification

A prime-ideal compactness tree for the finite–cofinite algebra

Example

Facts & Assumptions

Verification

BPI well-orders every set

False statement

Why this is false

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources