#diagonal-argument — Public Fediverse posts

Cantor's claim is that the infinity of the set real numbers, |ℝ|, is larger than the infinity of the set of counting numbers, |ℕ|. If Cantor is wrong, then there must be a function 𝑓:ℕ⟶ℝ such that the set of real numbers, ℝ, is exactly the same as the image of all natural numbers under function 𝑓, 𝑓(ℕ) = { 𝑓(1), 𝑓(2), 𝑓(3), ... }. If Cantor is right, then there is no such function, 𝑓 where 𝑓(ℕ) = ℝ.

Cantor's diagonal argument is, at its heart, a proof that a set of size 2^n is strictly larger than n, is true for all n when n is the size of a set, and this works for infinite sets. If n is 3, we have A = {1, 2, 3}, B={000, 001, 010, 011, 100, 101, 110, 111}, and if 𝑓(1) = 𝑎𝑏𝑐, 𝑓(2) =𝑟𝑠𝑡, 𝑓(3) = 𝑥𝑦𝑧, the symbol D = 𝑎𝑠𝑧 might or might not be in 𝑓(A), but D̅ = 𝑎̅𝑠̅𝑧̅ cannot be. We know 𝑓(1) ≠ D̅ since 𝑎 ≠ 𝑎̅; we know 𝑓(2) ≠ D̅ since 𝑠 ≠ 𝑠̅; we know 𝑓(3) ≠ D̅ since 𝑧 ≠ 𝑧̅, so we know 𝑓(A) failed to include all the elements of B. The diagonal argument is not a procedure or task to be carried out, but logical reasoning about operating 𝑓 on the whole of A at once, even when A is an infinite set, like ℕ.

ℕ and ℝ are already concrete. ℝ^ℕ, the set of all injective functions from ℕ into ℝ, is already concrete. So 𝑓 is an element of ℝ^ℕ and 𝑓(ℕ) ≠ ℝ, because none of the injective functions from ℕ into ℝ is also an surjective function from ℕ onto every element of ℝ. That's pretty much the definition of "larger."

Since D̅ differs from 𝑓(𝑛) at the 𝑛th position, D̅ cannot be an element of 𝑓(ℕ) because there is no 𝑛 such that 𝑓(𝑛) = D̅.

Effectively, Cantor's diagonal argument is the proposition that describes a concrete 𝑔:ℝ^ℕ⟶ℝ such that for all 𝑓 in ℝ^ℕ, 𝑔(𝑓) = D̅, is in ℝ but not in 𝑓(ℕ).

#Cantor #DiagonalArgument

Cantor's claim is that the infinity of the set real numbers, |ℝ|, is larger than the infinity of the set of counting numbers, |ℕ|. If Cantor is wrong, then there must be a function 𝑓:ℕ⟶ℝ such that the set of real numbers, ℝ, is exactly the same as the image of all natural numbers under function 𝑓, 𝑓(ℕ) = { 𝑓(1), 𝑓(2), 𝑓(3), ... }. If Cantor is right, then there is no such function, 𝑓 where 𝑓(ℕ) = ℝ.

Cantor's diagonal argument is, at its heart, a proof that a set of size 2^n is strictly larger than n, is true for all n when n is the size of a set, and this works for infinite sets. If n is 3, we have A = {1, 2, 3}, B={000, 001, 010, 011, 100, 101, 110, 111}, and if 𝑓(1) = 𝑎𝑏𝑐, 𝑓(2) =𝑟𝑠𝑡, 𝑓(3) = 𝑥𝑦𝑧, the symbol D = 𝑎𝑠𝑧 might or might not be in 𝑓(A), but D̅ = 𝑎̅𝑠̅𝑧̅ cannot be. We know 𝑓(1) ≠ D̅ since 𝑎 ≠ 𝑎̅; we know 𝑓(2) ≠ D̅ since 𝑠 ≠ 𝑠̅; we know 𝑓(3) ≠ D̅ since 𝑧 ≠ 𝑧̅, so we know 𝑓(A) failed to include all the elements of B. The diagonal argument is not a procedure or task to be carried out, but logical reasoning about operating 𝑓 on the whole of A at once, even when A is an infinite set, like ℕ.

ℕ and ℝ are already concrete. ℝ^ℕ, the set of all injective functions from ℕ into ℝ, is already concrete. So 𝑓 is an element of ℝ^ℕ and 𝑓(ℕ) ≠ ℝ, because none of the injective functions from ℕ into ℝ is also an surjective function from ℕ onto every element of ℝ. That's pretty much the definition of "larger."

Since D̅ differs from 𝑓(𝑛) at the 𝑛th position, D̅ cannot be an element of 𝑓(ℕ) because there is no 𝑛 such that 𝑓(𝑛) = D̅.

Effectively, Cantor's diagonal argument is the proposition that describes a concrete 𝑔:ℝ^ℕ⟶ℝ such that for all 𝑓 in ℝ^ℕ, 𝑔(𝑓) = D̅, is in ℝ but not in 𝑓(ℕ).

#Cantor #DiagonalArgument

Substructural fixed-point theorems and the diagonal argument: theme and variations

This is just to give a pre-release sneak peek of a pre-preprint I want to put on the arXiv very shortly. It’s a slightly odd beast, since I think it might be of some interest to logicians/philosophers, computer science types and possibly also category theorists, but I can’t tell. It’s a further analysis of Lawvere’s diagonal argument/fixed point theorem, reducing the assumptions beyond what is probably sensible, and giving a few different versions of the fixed point theorem more general than Lawvere’s. Here’s the abstract:

This note generalises Lawvere’s diagonal argument and fixed-point theorem for cartesian categories in several ways. Firstly, by replacing the categorical product with a general, possibly incoherent, magmoidal product with sufficient diagonal arrows. This means that the diagonal argument and fixed-point theorem can be interpreted in some substructural type theories, and semantically in categories with a product functor satisfying no coherence axioms, for instance relevance categories. The second way is by showing that both of Lawvere’s theorems as stated for cartesian categories only concern the well-pointed quotient, and giving a version of the fixed-point theorem in the internal logic of an arbitrary regular category. Lastly, one can give a uniform version of the fixed-point theorem if the magmoidal category has the appropriate endomorphism object, and has a comonad (i.e. an (S4) necessity modality) allowing for potentially `discontinuous’ dependence on the initial data.

Perhaps it is just a bit of a curio, and really waiting for a killer app, but it’s been sitting on my plate for a while, and I think some level of feedback is warranted, since I really can’t tell how it will land with people inside and outside my sphere of expertise. Grab your copy here.

EDIT: the paper is published here:

• Substructural fixed-point theorems and the diagonal argument: theme and variations, Compositionality 5, 8 (2023), doi:10.32408/compositionality-5-8, arXiv:2110.00239.

#diagonalArgument #Lawvere #papers