Follow

I'll do an AoC this year: each day post another statement equivalent to the Axiom of Choice.

about the daily AoC (axiom of choice)

In these posts "P is equivalent to axiom of choice" will have its standard meaning of "ZF ⊢ P → AC; ZFC ⊢ P", using classical logic.

My first post each days will contain the statement equivalent to AC. You are encouraged to try to write the equivalence proofs yourself, I'll give my own proof in the replies if requested, so beware spoilers.

daily AoC (axiom of choice), day 5

Zorn's Lemma is a formulation of the axiom of choice that looks very abstract, but in my experience is the most useful in practice.

The statement goes:

If X is a partial order such that each chain of X has an upper bound in X, then X contains a maximal element.

(A chain of X is a subset C ⊆ X, such that all c₁, c₂ ∈ C are comparable: c₁ ≤ c₂ or c₂ ≤ c₁.)

daily AoC (axiom of choice), day 6

Let's get the other famous equivalent out of the way: the well-ordering principle states that every set can be well-ordered.

More precisely, for any set S there exists a function min : P(S) \ {∅} → S such that:

* min X ∈ X

* min (Y ∪ {min X}) = min X for Y ⊆ X

* if min {x, y} = x and min {y, z} = y, then min {x, z} = x

DO-TIP: prove that defining x ≤ y as "min {x, y} = x" gives a linear order and min returns the minimum of each set according to this order.

daily AoC (axiom of choice), day 8

Krull's theorem is an equivalent to Zorn's lemma I see used quite a lot:

All rings where 0 ≠ 1 contain a maximal ideal.

(An ideal I of R is a subset of R closed under addition by elements of I and multiplication by elements of R. A maximal ideal is an ideal that is a subset of exactly two ideals: itself and of the ideal consisting of all elements of R.)

daily AoC (axiom of choice), day 10

Going back to set theory, here's a formulation of König's theorem which is not so hard to show equivalent to choice:

Let A_i, B_i be families of sets such that there is an injection A_i -> B_i but no injection the other way (written A_i < B_i). Then the union of all A_i has an injection into the cartesian product of all B_i but not the other way.

Q. What fruit says that, "a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element?"

A. Zorn's lemon. 🍋

@hhardy01

Did you hear about the school administrator who commands sources of water?

It's the well-ordering principal.

God cannot be conceived not to exist. –God is that, than which nothing greater can be conceived. –That which can be conceived not to exist is not God.

Hence, if that, than which nothing greater can be conceived, can be conceived not to exist, it is not that, than which nothing greater can be conceived. But this is an irreconcilable contradiction. There is, then, so truly a being than which nothing greater can be conceived to exist...

St. Anselm

Proslogion

c 1078

* Define God to be the pinkest thing imaginable.

* Things that do not exist cannot be seen, thus are not very pink.

* Therefore, if you can imagine a very pink thing then something that has the same qualities but is real, is pinker because you can actually see the pinkness.

* Therefore, God is real and extremely pink.

Sounds legit. :)

By including the phrase “Constantinople fishing nasty pink” in the English language, Weaver has shifted its entropic structure...

Coding Irony: Friedrich Schlegel, Claude Shannon, and Twitter

Leif Weatherby

2019

belated AoC day 3

@Vierkantor hmm I don't get this one?

belated AoC day 3

@IngaLovinde @socks This is a bit of a surprising one indeed, but you really need the Axiom of Choice to make sense of cardinalities. I'll try and write up the proof soon, but first dinner!

belated AoC day 3

@IngaLovinde @socks Ok, I'm back. First I'll show that the Axiom of Choice (in the form of Zorn's Lemma) implies that there is a surjection A → B or there is a surjection B → A.

Consider the set X ⊆ A×B containing all relations where each a∈A and each b∈B appears only once:

X={r∈A×B | ∀ a₁ a₂ b₁ b₂,

(((a₁, b₁) ∈ r ∧ (a₁, b₂) ∈ r) → b₁ = b₂) ∧

(((a₁, b₁) ∈ r

∧ (a₂, b₁) ∈ r) → a₁ = a₂) }.

I claim a maximal element of X is either a surjection A → B or a surjection B → A.

belated AoC day 3

@IngaLovinde @socks Note that each elements of X is a bijection between a subset of A (the A-image) and a subset of B (the B-image). So let r∈X be maximal, and suppose it is not a surjection either way: then the A-image and B-image are both missing elements, let's say (a, b). Then r ∪ {(a, b)} is an element of X and strictly larger than r, contradiction: so maximal r has maximal A-im or B-im.

So by Zorn's lemma, it suffices to show all ascending chains in X have an upper bound.

belated AoC day 3

@IngaLovinde @socks Let C ⊆ X be a chain: for all c, c' ∈ C we have c ⊆ c' or c' ⊆ c. I claim the union ⋃C is an element of X. If so we are done, since that all c ⊆ ⋃C by definition of the union.

So let (a, b₁) and (a, b₂) ∈ ⋃C, we need to show b₁ = b₂; the other case goes symmetrically. By definition (a, b₁) and (a, b₂) ∈ ⋃C means there are c₁ ,c₂ ∈ C with (a, b₁) ∈ c₁ and (a, b₂) ∈ c₂. WLOG we have c₁ ⊆ c₂, so also (a, b₁) ∈ c₂. But c₂ ∈ X so this implies b₁ = b₂. QED

belated AoC day 3

@IngaLovinde @socks Now let's show that the existence of a surjection in either direction implies AoC, via the well-ordering principle.

Let A be an arbitrary set, I'll show two things: 1. There is an ordinal α with no surjection A → α. 2. If there is a surjection f : α → A for an ordinal α, then A is well-ordered.

The latter is not so hard: define min : P(A) → A to be min(X) = f(min(f⁻¹(X))), and you can check this is indeed a well-defined minimum function giving a well-order.

belated AoC day 3

@IngaLovinde @socks So claim 1: We use Hartogs' theorem (https://en.wikipedia.org/wiki/Hartogs_number), which (without AoC) gives an ordinal α s.t. there is no injection α → A.

So suppose there is a surjection f : A → α, then we'll find an injection g : α → A and find the contradiction that we're looking for.

Now without AoC the implication "f : A → B is surjective → there is an injection g : B → A" does not necessarily hold. But we can use that α is an ordinal:

belated AoC day 3

@IngaLovinde @socks Using transfinite induction on all ordinals β ≤ α define a right inverse g_β : β → A to f (so ∀ x, f(g_β(x)) = x) as follows:

* if β is a successor ordinal γ ∪ {x}, then surjectivity of f means there is some y ∈ f⁻¹(x). Moreover, since f is a function, y is not in the image of g_γ. So set g_β = g_γ ∪ {(x, y}, which is well-defined and a right inverse to f, since f(g_β(x)) = f(y) = x and f(g_β(x')) = f(g_γ(x')) = x' for x' ∈ β \ {x} = γ by assumption.

belated AoC day 3

* if β is a limit ordinal and suppose we have functions g_γ for all γ < β such that f(g_γ(x)) = x for x ∈ γ. Now for x ∈ β, let γ be the minimum ordinal containing x (this is strictly smaller than β since γ is a limit ordinal). Define g_β(x) = g_γ(x), then we indeed have f(g_β(x)) = x as required.

So by transfinite induction up to α, f has a right inverse g_α. Since right inverses are always injective, we have an injection α → A, contradicting Hartogs.

belated AoC day 3

@IngaLovinde @socks Therefore, there is no such surjection A → α, so we have proved claim 1.

Now putting everything together: Let A be an arbitrary set. Claim 1 gives an ordinal α with no surjection A → α. Our assumption therefore gives that there is a surjection α → A. By claim 2, this induces a well-ordering on A. Thus we conclude the assumption implies the well-ordering principle, which we know is equivalent to AoC. QED

belated AoC day 3

@IngaLovinde @socks Okay, I think that finishes the two proofs. I think everything is correct, but there might be mistakes — I came up with both parts myself and transfinite induction is always a bit suspicious. And if you have any questions, please let me know and I'll do my best to answer them!

belated AoC day 3

@Vierkantor @socks my math is too rusty to get the second part apparently, will try to figure it out later. Thank you!

re: belated AoC day 3

@Vierkantor Wait, really? You need choice for that? Huh

daily AoC (axiom of choice), day 17

@Vierkantor this is a weird one

daily AoC (axiom of choice), day 19

@Vierkantor quite an impressive list. Every time I see this my mind goes to "oeh, I wonder if they got to Tychonov's theorem yet" because that is actually one of the fewer known equivalences that I'm familiar with 😆

re: daily AoC (axiom of choice), day 9, spoiler

@Vierkantor hmm but this one is really easy?

Consider all subsets of linearly independent vectors. Introduce a standard "is a subset of" order on that set. Find a maximum element by Zorn's lemma; all the vectors in it are linearly independent, and the original space does not contain any vector that would not be a linear combination of these (or that element would not be maximum): a basis!

re: daily AoC (axiom of choice), day 9, spoiler

@IngaLovinde i would be more careful, the same reasoning apparently shows Z/2Z has a basis as a Z-module :P

re: daily AoC (axiom of choice), day 9, spoiler

@IngaLovinde (the difference being that in a vector space, a linear dependence cannot involve only one nonzero element because scalar multiplication by units is injective)

re: daily AoC (axiom of choice), day 9, spoiler

@Vierkantor but it's not a vector space?

That reasoning would find empty set to be a basis because it is a maximum set of linearly independent elements, but this issue does not apply to vector spaces?

Anne C.A. Baanen@Vierkantor@mastodon.vierkantor.combelated AoC day one

let's start off with the traditional one:

∀ X. ¬(∅∈X) → ∃ f. ∀ x ∈ X. f(x) ∈ x