The collection

Every essay — page 34

Page 34 of 44, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Logic

What can be said in a system, what follows from it, and what it cannot settle about itself.

A implies B, and r ∨ s sits between them. A = ((p ∨ q) ∧ (p → r)) ∧ (q → s) implies B = (r ∨ s) ∨ t. A resolution refutation of A with the negation of B yields the interpolant r ∨ s. It uses only the shared atoms r, s, follows from A and implies B, and lies between the strongest and weakest interpolants.

The sentence between a premise and its consequence

Two literals make an arrow

A failed search is a proof

4 axioms against 4 finite algebras. A table of candidate axioms against finite Heyting algebras built from small orders, marking which algebras validate which axiom at every valuation.

Not one step but a continuum

The smallest algebra that refutes each formula. A table of formulas against the smallest finite Heyting algebra refuting each, found by searching every order on a few points, with the formulas no such algebra refutes marked.

Refutable in something small

Two graphs every count agrees on, and one question that does not. Two sixteen-point graphs drawn on a four-by-four grid, with one point marked and its six neighbours highlighted in each, the neighbours forming two triangles in one and a six-cycle in the other.

One gadget defeats every refinement

Who survives with two pebbles and who with three, over 4 rounds. A table of three pairs of graphs with, for each, whether the duplicating player survives a two-pebble game and a three-pebble game played to a fixed depth.

The boundary at three variables

The order type of a nonstandard model of arithmetic. The ordinary numbers as a run of dots, followed by 9 galaxies — copies of the integers — at the positions of c/2 up to 2c, ordered densely like the rationals, with c² beyond. Infinitely many more galaxies lie between those drawn.

A number larger than every number

A countable structure grown by adding witnesses. Stages of a structure built from 0 and 1 by adding sums, products, negatives and roots of quadratics: 2, 4, 12, 158 elements between −3 and 3.

A countable field that passes for the line

An additive function that is nowhere a line. A square window with 1157 points of the graph of an additive function that sends √2 to 0, scattered across the window and meeting every part of it, beside a dashed diagonal marking the straight line y = x.

A function that adds and is nowhere a line

Infinitely many guessers, finitely many wrong. Three rows over the first 40 places: the hats worn, the chosen representative of their class, and a row of marks showing each guess right or wrong. The 5 wrong guesses all fall within the first 14 places, up to a marked place; every later guess is right.

Infinitely many guessers, finitely many wrong

Six sentences from two quantifiers, and which imply which. A diagram of the six sentences that can be built from two quantifiers and a relation, arranged from strongest to weakest with arrows for implication, each labelled with how many of the 512 relations on three points satisfy it.

Six sentences from two quantifiers

"There is an x" is a shadow: x² + ax + 1 = 0 has a solution exactly when |a| ≥ 2. A grid with a horizontal and x vertical, marking the cells the curve x squared plus a x plus one equals zero passes through; beneath it, a strip marking the columns that contain a mark, which are exactly those with a at least two in size.

A quantifier is a shadow

Weighted votes: two functions with a cut, and parity without one. For three functions of three letters, the eight assignments placed on a line by a weighted count, with true assignments filled and the threshold marked where one exists.

A plane through the cube

9 corners of the 4-cube: some corner always has 2 chosen neighbours. The 4-dimensional cube with 9 of its corners chosen so that no chosen corner has more than 2 chosen neighbours, the fewest possible, with the edges between chosen corners drawn heavy.

Half the cube and √n neighbours

A smallest model of ∀x (Ax → ∃y (By ∧ ¬Cy)) ∧ ∃x (Ax ∧ Cx) ∧ ∀x (Bx → ¬Ax). Three overlapping circles with some regions shaded as empty and a single dot in each occupied region, forming a model of a sentence of monadic first-order logic.

One thing in each region is enough

Carroll's babies and crocodiles, on four ellipses. Four overlapping ellipses labelled with the four classes of a sorites, the regions emptied by its premises shaded, and the regions its conclusion requires to be empty outlined.

The conclusion is what survives the erasing

Adjectives that describe themselves, and the one that cannot exist. A grid of 8 adjectives against the same adjectives as written words, marked where the property holds of the spelling; the diagonal marks self-describing adjectives, and a flipped diagonal row labelled heterological matches no row.

The word that cannot describe itself

Whole-number points in a strip, and the shadow they cast. The lattice points satisfying 2x ≤ 5y ≤ 2x + 1 for x from 0 to 30, and their projection onto the x-axis, which repeats every 5.

Arithmetic with addition alone

Gluing two countermodels: p ∨ ¬p. Two small Kripke models, each refuting one half of a disjunction, and the model made by placing both above a new first stage, at which neither half is forced.

A proof that says which half

Which chains of truth values validate Gödel's disjunctions. A grid of Gödel's pigeonhole formulas in m letters against chains of n truth values, marking which chains validate which formula, forming a staircase where m exceeds n.

No table of truth values is enough

Tseitin's clauses on the cube. the cube with a variable on each edge and a charge of 0 or 1 at each vertex, exactly one vertex charged 1. The parity demands give 32 clauses that cannot all be true.

A contradiction that is only a sum

Unifying f(x, g(x)) with f(h(y), g(z)). Three term trees: f(x, g(x)), f(h(y), g(z)), and their common instance f(h(y), g(h(y))) under the most general unifier x ↦ h(y), z ↦ h(y).

Two terms made equal, and no more

A program whose output is its own text. The 32-character program (f=>f(f))(f=>"(f=>f(f))("+f+")") beside its output, which is identical.

The program that prints itself