CounterexampleConstruction: AI-adaptedVerification: AI-adaptedSession-authored (Fable 5 assisted)precheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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.

A list of six distinct reals with no strictly increasing sublist of length four and no strictly decreasing sublist of length three

Statement refuted

Refuted claim: FALSE: every list of $mn$ pairwise distinct reals has a strictly increasing sublist of length $m+1$ or a strictly decreasing sublist of length $n+1$ at $m = 3$ and $n = 2$ , that is, the assertion that every pairwise distinct list of $mn = 6$ reals has a strictly increasing sublist of length $m+1 = 4$ or a strictly decreasing sublist of length $n+1 = 3$ .

The witness is the list $a : 6 \to \mathbb{R}$ with values

$\big(a_0, a_1, a_2, a_3, a_4, a_5\big) = \big(\iota(2), \iota(1), \iota(4), \iota(3), \iota(6), \iota(5)\big),$

that is $2, 1, 4, 3, 6, 5$ read through the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field). It is the instance at $m = 3$ , $n = 2$ of the construction of For all $m$ and $n$ there is a list of $mn$ pairwise distinct reals with no strictly increasing sublist of length $m+1$ and no strictly decreasing sublist of length $n+1$ : three blocks of two positions each, decreasing inside a block and increasing across blocks.

Its longest strictly increasing sublist has length $3$ , for example $a_0, a_2, a_4$ , and its longest strictly decreasing sublist has length $2$ , for example $a_0, a_1$ .

Facts & Assumptions

Given: The list $a : 6 \to \mathbb{R}$ above, and the three index blocks $P_0 := \{0,1\}$ , $P_1 := \{2,3\}$ , $P_2 := \{4,5\}$ , with $\mathrm{blk}(i) := b$ for $i \in P_b$ .

[L1]

A sublist of length $L$ is a strictly increasing $s:L\to6$ . It is strictly increasing when $a_{s(p)}<a_{s(q)}$ for every $p<q<L$ , and strictly decreasing when $a_{s(p)}>a_{s(q)}$ for every such pair (A finite list of reals, and its strictly increasing and strictly decreasing sublists, Injection, surjection, bijection).

[L2]

$\iota$ is strictly increasing, so the comparisons between the six values are those between $1,2,3,4,5,6$ in $\mathbb{N}$ ; natural order satisfies trichotomy, so distinct indices can be put in increasing order and $K<L$ fails exactly when $L\le K$ (Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ , clause 7, Ordered field, Order on the natural numbers, Trichotomy of the order on $\mathbb{N}$ ).

[L3]

If a finite set $S$ has $|S|=K<L$ , there is no injection $L\to S$ : composing one with a bijection $S\to K$ supplied by finite cardinality would contradict the natural-number pigeonhole principle (The cardinality $\lvert A\rvert$ of a finite set, Injection, surjection, bijection, The pigeonhole principle on $\mathbb{N}$ , clause 2).

[L4]

For every $m,n\in\mathbb N$ , a pairwise distinct list of length $mn+1$ has a strictly increasing sublist of length $m+1$ or a strictly decreasing sublist of length $n+1$ ; the length- $mn$ block construction shows this bound is sharp when $m,n\ge1$ (Every list of $mn+1$ pairwise distinct reals has a strictly increasing sublist of length $m+1$ or a strictly decreasing sublist of length $n+1$ , For all $m$ and $n$ there is a list of $mn$ pairwise distinct reals with no strictly increasing sublist of length $m+1$ and no strictly decreasing sublist of length $n+1$ , FALSE: every list of $mn$ pairwise distinct reals has a strictly increasing sublist of length $m+1$ or a strictly decreasing sublist of length $n+1$ ).

Counterexample

technique · constructive

1.1

The list is pairwise distinct: its values are $\iota(2), \iota(1), \iota(4), \iota(3), \iota(6), \iota(5)$ , and the naturals $1,2,3,4,5,6$ are pairwise distinct, so their canonical naturals are too by [L2].

givenL2construct

1.2

Inside a block the values decrease. $a_0 = \iota(2) > \iota(1) = a_1$ , $a_2 = \iota(4) > \iota(3) = a_3$ and $a_4 = \iota(6) > \iota(5) = a_5$ , by [L2].

givenL2

1.3

Across blocks the values increase. Every value at a position of $P_0$ is $\iota(1)$ or $\iota(2)$ , every value at a position of $P_1$ is $\iota(3)$ or $\iota(4)$ , and every value at a position of $P_2$ is $\iota(5)$ or $\iota(6)$ ; so $b < b'$ implies that every value on $P_b$ is smaller than every value on $P_{b'}$ , by [L2]. Also $i < i'$ implies $\mathrm{blk}(i) \le \mathrm{blk}(i')$ , since the blocks list the positions in increasing order.

givenL2

2.1

No strictly increasing sublist of length $4$ . Let $s : L \to 6$ be a strictly increasing sublist. If $p < q < L$ had $\mathrm{blk}(s(p)) = \mathrm{blk}(s(q))$ , then $s(p) < s(q)$ lie in one block, so $a_{s(p)} > a_{s(q)}$ by step 1.2, contradicting that the values increase. Natural trichotomy in [L2] makes this sufficient for $\mathrm{blk}\circ s$ to be an injection of $L$ into $3$ ; [L3] and [L2] then give $L \le 3$ , hence $L \ne 4$ .

step 1.2L1L2L3

2.2

No strictly decreasing sublist of length $3$ . Let $s : L \to 6$ be a strictly decreasing sublist and let $p < q < L$ . Then $s(p) < s(q)$ , so $\mathrm{blk}(s(p)) \le \mathrm{blk}(s(q))$ by step 1.3; and a strict inequality there would give $a_{s(p)} < a_{s(q)}$ by step 1.3, contradicting that the values decrease. So all positions of $s$ lie in one block, and $s$ is an injection of $L$ into a two-element set; [L3] and natural trichotomy in [L2] give $L \le 2$ , hence $L \ne 3$ .

step 1.3L1L2L3

3.1

The list of step 1.1 is therefore a pairwise distinct list of $6 = 3\cdot 2$ reals with neither of the two sublists the refuted claim asserts, so that claim is false at $m = 3$ , $n = 2$ ; what holds instead is [L4] at length $3\cdot 2 + 1 = 7$ .

step 1.1step 2.1step 2.2L4discharge-construct∎

Remarks

The two bounds come from the two block counts. An increasing sublist takes at most one position from each block, so its length is bounded by the number of blocks; a decreasing sublist stays inside one block, so its length is bounded by the block size. Exchanging the roles of the block count and the block size would give a witness for the pair $(2,3)$ instead.
Both bounds are attained, by $a_0, a_2, a_4$ and by $a_0, a_1$ respectively, so the witness is not merely short of the two thresholds: it sits exactly one below each.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 67 results over 24 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Erdos-Szekeres theorem (Wikipedia) (standard reference, not scraped)
Longest increasing subsequence (Wikipedia) (standard reference, not scraped)