Theme

The same thing twice — page 2

Two constructions that look unrelated and turn out to be the same object wearing different clothes.
000001010011100101110111(p ∨ q) ∧ ¬r on the 3-cube of assignments — 3 of 8 cornerscorners next to each other differ in one variable, which every edge here was checkedagainst Logic

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

keeps 0keeps 1monotoneself-dualaffineenough alone?∧ and··no∨ or··no¬p not p···no↑ nand·····yes⊕ exclusive or···no→ implication····no6 connectives against Post's five classes — a tick means the connective stays insidenand escapes all five, and is therefore enough alone Logic

One connective is enough

Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.

ji123456123456∀i ∃j : trueevery row carries at least one mark∃j ∀i : falsesome one column is marked all the way downthe relation "j is one more than i, counting round", on 6 rows and 6 columnsevery row has a mark: yes · some column is all marks: no Logic

Every row, or one column

For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.

¬(((p → q) ∧ (q → r)) → (p → r))(p → q) ∧ (q → r)¬(p → r)p → qq → rp¬r¬p×q¬q×r×assume the formula false, then take it apart: ((p → q) ∧ (q → r)) → (p → r)every branch closes, so the assumption is impossible — the formula is valid Logic

The tree that closes

To prove a formula, assume it false and take it apart. Every branch ends in a contradiction, or one of them describes exactly how it could have been false — and either way the tree is the answer, drawn.

Pone line, one point off it, and 4 lines through the point that never meet itevery arc here meets the rim at a right angle, and every miss was checked for crossingsinside the disc Logic

Two worlds that both obey the rules

A statement is independent of a list of axioms when there is a structure satisfying the axioms where it holds and another where it fails. That is not a claim about what nobody has managed to prove — it is a proof that nobody can.

[0, 1](0, 1)01½0 goes to a half and 1/n goes to 1/(n+2); every other point of [0, 1] stays where it is8 moved points drawn, all distinct, all inside (0, 1) — and the two endpoints are gone Logic

Two injections make a bijection

If each of two collections fits inside the other without collisions, they are the same size. That sounds obvious and is not, because neither injection needs to be onto — and the proof is a rule for deciding which of the two to follow, one chain at a time.

U¬UU ∪ ¬U¬¬UU is an interval with 1 point taken out; ¬U is the inside of what is leftU and ¬U together miss the endpoints, and ¬¬U hands them back — so U ∨ ¬U is not everything and ¬¬U is not U Logic

The middle that is not excluded

Either it is raining or it is not. Drop that as an axiom and what is left is still a logic — one with models made of open sets and of stages of knowledge, in which a set and its negation between them miss the boundary.

All themes