A simple arc does not separate the plane #
thm:arc-complement. Two points off a simple arc A are covered by a chain of small
axis-parallel squares strung along A; the two points lie in the outer face of every
consecutive pair of links, hence — by lem:outer-chain — in the outer face of the whole chain,
which is an open connected set missing A. lem:polygonal-connected then joins them there.
The single-ambient-graph obligation, and how it is met #
Graph.IsPlaneChain requires every link Γ i to be a subgraph of one ambient plane graph
with one drawing. A link built as the polygonal overlay of its own squares would not
qualify: the total overlay cuts those same segments at the crossings with the squares of other
links as well, so a sub-overlay has edges the total overlay has subdivided further.
The construction is therefore inverted. familyPieces c N r is one list holding the four
sides of every small square; familyOverlay c N r is the one overlay of that list; and a link
is carved out of it by restricting the edge set:
segGraph S— the plane graph spanned by a setSof straight edges, with the ends of those edges as vertices.overlayGraph pieces points = segGraph {Q | Q ∈ overlayPieces pieces points}holds byrfl, sosegGraph_monoturns a subset of the overlay's edges into a subgraph of the overlay with nothing to prove.squareGraph pieces points c r— the edges of the overlay lying on the boundary of the square of radiusraboutc, spanned. It occupies exactly that boundary (pointSet_squareGraph), and every cut point on the boundary is one of its vertices (mem_vertexSet_squareGraph), which is whatGraph.IsTwoConnected.unionneeds.familyChain c N m r i— thei-th link:Graph.chainUnionof them + 1square graphs of thei-th coarse subarc. Consecutive links share the square at the sample they have in common; nonconsecutive links are disjoint.
isPlaneChain_familyChain is the theorem that this family is a Graph.IsPlaneChain, stated for
an arbitrary family of centres c : ℕ → Plane with two geometric hypotheses — consecutive
centres closer than one radius, nonconsecutive-block centres further apart than two radii. The
arc enters only in exists_face_of_notMem_arc, where c j = α(j/N).
What is assumed #
Three hypotheses, all named in the statements that carry them.
SquaresTwoConnected— the part of a polygonal overlay lying on the boundary of one of its squares is 2-connected. That part is the subdivided boundary cycle of an axis-parallel square: four sides, cut at finitely many interior points, every cut point a vertex, the four corners among the vertices. It is a cycle, soGraph.IsLongCycle.isTwoConnectedfinishes; what a discharger must build is the cyclic order of the cut points along the four sides, for whichSchoenflies/SegmentOrder.leanis the tool. Nothing about the arc, the chain or the outer face enters the statement.Graph.CrosscutExistsandGraph.CrosscutEncloses— the two halves of the descent step oflem:outer-chain, quoted fromSchoenflies/OuterChain.leanunchanged. Because the chain is built from choices made inside the proof ofexists_face_of_notMem_arc, they appear there in ∀-form:CrosscutExistsconditioned onGraph.IsPlaneChain(which is how a discharger will state it) andCrosscutEnclosesfor every point.
Blueprint #
segGraph,squareGraph,familyPieces,familyOverlay,familySquare,familyChain— the construction of the proof ofthm:arc-complement: "around every sample draw the boundary of the axis-parallel square ofℓ^∞-radiusδ/4, and letΓ_ibe the polygonal overlay (lem:polygonal-overlay) of the square boundaries associated withA_i".familyChain_isTwoConnected— "it follows inductively fromlem:union-two-connectedthatΓ_iis 2-connected".isPlaneChain_familyChain— "consecutive graphsΓ_i, Γ_{i+1}share the square at their common sample. If|i-j| ≥ 2, thenΓ_iandΓ_jare disjoint".outer_of_notMem_closedSquare,outerOnPairs_familyChain— "the graphΓ_i ∪ Γ_{i+1}is contained in theℓ^∞-square of radius3dcentered ata_i… bothpandqlie outside this containing square and hence in the outer face of the pair".notMem_face_of_mem_openSquare— "if it lies inside, the boundary cycle of that square separates it from the outer face ofG".exists_face_of_notMem_arc— the whole proof ofthm:arc-complementup to the last sentence.isConnected_compl_arc,exists_simple_poly_compl_arc—thm:arc-complement: the complement of a simple arc is connected, and any two of its points are joined in it by a simple polygonal arc.
Part 1: the subgraph of the plane spanned by a set of straight edges #
The plane graph spanned by a set of straight edges. Its vertices are the ends of
those edges and an edge links its two ends in either order — the shape of
Schoenflies.overlayGraph, with the edge list replaced by an arbitrary set.
This exists so that a part of one overlay can be spoken about as a graph in its own right
while remaining a subgraph of the whole overlay (segGraph_mono). Building the part as an
overlay of its own source segments would not do: the total overlay cuts those segments at more
points, so a sub-overlay is not a subgraph of it.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The overlay graph is the graph spanned by its own edge list. Definitional, so that a subset of the overlay pieces spans a subgraph of the overlay with nothing to prove.
What a spanned graph occupies is the union of its segments: every vertex is an end of an edge, so the vertices add nothing.
Part 2: the part of an overlay lying on one square #
The chain graphs are assembled out of these. Each is the set of overlay edges whose segment
lies on one small square boundary, spanned by segGraph — so it is a subgraph of the total
overlay, not an overlay of the four sides of that square alone.
Every point of a source segment lies on an overlay edge inside that source segment.
Schoenflies.exists_overlayPiece_end_subset is the same statement for a cut point, with the
edge pinned so as to have that point among its ends; this is the plain covering form, and it is
what makes the part of the overlay on a square occupy the whole of that square's boundary.
The edges of an overlay whose segment lies on the boundary of the square of ℓ^∞-radius
r about c.
Equations
- Schoenflies.squareEdges pieces points c r = {Q : Schoenflies.Piece | Q ∈ Schoenflies.overlayPieces pieces points ∧ Q.seg ⊆ frontier (c.closedSquare r)}
Instances For
The part of one overlay lying on one square boundary. A subgraph of that overlay by
construction (squareGraph_le), which is the single-ambient-graph obligation of
Graph.IsPlaneChain discharged at the bottom of the tower.
Equations
- Schoenflies.squareGraph pieces points c r = Schoenflies.segGraph (Schoenflies.squareEdges pieces points c r)
Instances For
The part of the overlay on a square occupies the whole square boundary. Every point of the boundary lies on one of the four sides, and the overlay subdivides that side into pieces that stay inside it.
A cut point on a square boundary is a vertex of the part of the overlay on that
square. This is what turns "two nearby squares meet in two points" into the two common
vertices that Graph.IsTwoConnected.union consumes.
Two nearby congruent squares contribute two common vertices, each a vertex of the part of the overlay lying on its own square. With equal centres this produces two vertices of one square, which is how consecutive links of the chain are shown to meet.
Part 3: the chain of square boundaries #
Everything here is about a family of centres c : ℕ → Plane and one radius r; the arc enters
only in Part 5, where c j = α (j / N). Separating the two keeps the single-ambient-graph
bookkeeping free of parametrisation arithmetic.
The one list of source segments: the four sides of the square of ℓ^∞-radius r
about each of the centres c 0, …, c N.
The whole proof rests on this being one list. A chain link built as the overlay of its own squares would not be a subgraph of the total overlay, because the total overlay cuts those segments at the crossings with squares of other links as well.
Equations
- Schoenflies.familyPieces c N r = List.flatMap (fun (j : ℕ) => Schoenflies.squarePieces (c j) r) (List.range (N + 1))
Instances For
The cut points of that list, chosen once and for all. Schoenflies.exists_cut_points
produces them existentially; naming them here is what lets every chain link be a subgraph of
the same overlay.
Equations
- Schoenflies.familyPoints c N r = ⋯.choose
Instances For
The single ambient plane graph of the whole proof: the polygonal overlay of every small
square at once (lem:polygonal-overlay).
Equations
- Schoenflies.familyOverlay c N r = Schoenflies.overlayGraph (Schoenflies.familyPieces c N r) (Schoenflies.familyPoints c N r)
Instances For
The part of the ambient overlay lying on the j-th small square.
Equations
- Schoenflies.familySquare c N r j = Schoenflies.squareGraph (Schoenflies.familyPieces c N r) (Schoenflies.familyPoints c N r) (c j) r
Instances For
The i-th link of the chain, Γ_i: the squares at the m + 1 fine samples
i·m, …, i·m + m of the i-th coarse subarc. Consecutive links share the square at the
sample they have in common.
Equations
- Schoenflies.familyChain c N m r i = Graph.chainUnion (Schoenflies.familySquare c N r) (i * m) m
Instances For
The drawing of the ambient overlay: every edge is a straight segment.
A point of a chain link lies on one of that link's squares.
Assumed: the part of a polygonal overlay lying on the boundary of one of its squares is 2-connected.
It is the subdivided boundary of an axis-parallel square — four sides, cut at finitely many
points, each cut point a vertex — so it is a cycle, and Graph.IsLongCycle.isTwoConnected
finishes. What a discharging module must build is the cyclic order of the cut points along the
four sides; Schoenflies/SegmentOrder.lean is the tool. Nothing about the arc, the chain or
the outer face enters the statement.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Two squares whose centres are within one radius contribute two common vertices to the two parts of the overlay lying on them. With equal centres this gives two vertices of one square, which is how consecutive links of the chain are shown to meet.
Each link of the chain is 2-connected: consecutive squares in it share two vertices, so
lem:union-two-connected applies all the way along.
Part 4: the chain satisfies Graph.IsPlaneChain #
This is the obligation Schoenflies/OuterChain.lean flagged: every link must be a subgraph of
one ambient plane graph with one drawing. It is discharged by construction — every link
is a Graph.chainUnion of familySquares, and every familySquare is a segGraph on a subset
of the edges of the one overlay familyOverlay c N r.
The chain of square boundaries is a plane chain.
The two geometric hypotheses are the blueprint's: consecutive centres are closer than one square
radius (hstep), and centres belonging to nonconsecutive links are more than two radii apart
(hfar). Everything else — one ambient graph, one drawing, finiteness, polygonality — is
discharged by the construction.
Part 5: the outer face of the chain #
Two plane facts, both general, and then the hypothesis of lem:outer-chain on consecutive
pairs.
The outside of a square containing the whole drawing lies in one unbounded face.
Graph.beyondSquare_subset_face is this statement for a square centred at the origin; the
chain argument needs it about a square centred at a sample of the arc, and the connectedness of
the outside of an arbitrary square is Plane.isConnected_compl_closedSquare.
The complement of a square's boundary has the open square as one whole component.
"If it lies inside, the boundary cycle of that square separates it from the outer face." A point strictly inside a square whose boundary the drawing carries is not in any unbounded face: the face would be a connected subset of the complement of that boundary meeting the inside, hence inside, hence bounded.
The hypothesis of lem:outer-chain on consecutive pairs. Every consecutive pair of
links is contained in one square of radius R about the pair's first centre, and x is outside
that square.
lem:outer-chain, applied to the chain of squares. Stated with the two halves of the
descent step exactly as Schoenflies/OuterChain.lean defines them and for this chain, so that
a discharger's terms substitute here with nothing to adapt.
Part 6: from the Euclidean distance to the sup distance #
The only place the two metrics have to be compared. ‖·‖ ≤ √2‖·‖∞ and √2 < 2, so half the
Euclidean distance is a strict lower bound for the sup distance — which is what turns the
blueprint's separation constants into square radii.
Part 7: thm:arc-complement #
The blueprint's proof, in its own order. The two hypotheses hce and hcen are the two halves
of the descent step of lem:outer-chain, quoted verbatim from Schoenflies/OuterChain.lean;
h2c is the 2-connectivity of one subdivided square, discussed at SquaresTwoConnected.
The heart of thm:arc-complement: two points off a simple arc lie in a common open
connected set missing the arc — the outer face of the chain of small squares along the arc.
thm:arc-complement, the polygonal half. Two distinct points off a simple arc are
joined, off the arc, by a simple polygonal arc. This is the form lem:accessible-dense
consumes; the joining is lem:polygonal-connected inside the outer face.
thm:arc-complement. The complement of a simple arc in the plane is connected.