Follow

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

belated AoC day one 

let's start off with the traditional one:
∀ X. ¬(∅∈X) → ∃ f. ∀ x ∈ X. f(x) ∈ x

belated AoC day 2 

you can also specify it on subsets rather than elements of X:
∀ X. ∃ f. ∀ x ⊆ X. X ≠ ∅ → f(x) ∈ x

belated AoC day 3 

The Axiom of Choice is equivalent to the statement that for any two nonempty sets A, B, either there is a surjection A → B, or there is a surjection B → A (or both).

AoC day 4 

The "foundations of mathematics" course I followed in my Bachelor's used the following formulation of the Axiom of Choice:

If f : A → B is a surjection, then it has a section, i.e. there is a function g : B → A such that f(g(x)) = x.

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 7 

Here's a statement I didn't know was equivalent to the axiom of choice one week ago:

For all infinite sets A, the cartesian product A × A is in bijection with A.

(Hint: show that this implies the well-ordering principle.)

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 8 (cont'd) 

A popular alternative formulation of the theorem is that any ideal I ≠ R is contained in a maximal ideal.

It's a nice exercise in ring theory to show the two formulations are equivalent.

daily AoC (axiom of choice), day 8 (hint) 

Hint for showing the first formulation implies the second: use the ring R/I.

daily AoC (axiom of choice), day 9 

Another equivalent to the Axiom of Choice that people use a lot:

All vector spaces have a basis.

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.

daily AoC (axiom of choice), day 11 

In the product topology, the closure of a product is the product of the closures.

daily AoC (axiom of choice), day 12 

Another topology one:

A uniform space is compact iff it is complete and totally bounded.

(This reminds me of "A subset of ℝ^n is compact iff it is closed and bounded".)

daily AoC (axiom of choice), day 13 

Every object of the category Set is projective.

daily AoC (axiom of choice), day 14 

For all nonempty sets S, there is a map S × S → S giving a group structure on S.

daily AoC (axiom of choice), day 15 

Kind of opposite to Zorn's lemma:

Any partial order has a maximal antichain: a maximal subset such that any two distinct elements are incomparable.

daily AoC (axiom of choice), day 16 

Cardinalities are a preorder. In particular, for any two sets A, B, either there is an injection A → B, an injection B → A, or a bijection A ≈ B.

daily AoC (axiom of choice), day 17 

Let V be a normed ℝ-vector space, and V' the dual of V. Then the closed unit ball B in V' has an extreme point (a point in B that does not lie on a line segment through two different points in B).

daily AoC (axiom of choice), day 18 

All free abelian groups are projective. (See also day 13.)

daily AoC (axiom of choice), day 19 

An abelian group is divisible iff it is an injective object of the category of abelian groups.

daily AoC (axiom of choice), day 20 

A connected infinite graph (for any partition of the vertices into V and W, there is an edge from V into W) has a spanning tree (a connected subgraph containing all vertices such that removing any one edge would make the resulting subgraph disconnected).

Show newer

I think I'll set up an Axiom of Choice tournament in the new year. Every day let people choose between two AoCs, until one statement remains that shall be crowned the "2022 Choice of Axiom of Choice".

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. 🍋

@Vierkantor

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

It's the well-ordering principal.

@Vierkantor

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

@hhardy01 also God is pink:
* 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.

@Vierkantor

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

boundary2.org/2019/06/leif-wea

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 (en.wikipedia.org/wiki/Hartogs_), 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 

@IngaLovinde @socks

* 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 :blobcat:

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 😆

Show newer

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?

Sign in to participate in the conversation
Vachtnoes

Mastodon is a server for a federated social network: everyone can run a server if they want to, including me. So this is a Mastodon server for me (Vierkantor) and my friends.