Post AQAh0fHALTdmGycLRI by Vierkantor@mastodon.vierkantor.com
(DIR) More posts by Vierkantor@mastodon.vierkantor.com
(DIR) Post #AQAh0EKQXFCqhGw4H2 by Vierkantor@mastodon.vierkantor.com
2021-12-04T18:39:58Z
0 likes, 0 repeats
I'll do an AoC this year: each day post another statement equivalent to the Axiom of Choice.
(DIR) Post #AQAh0F6ddzlr6nUZQ8 by Vierkantor@mastodon.vierkantor.com
2021-12-04T22:07:31Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0FdbfQ8sl2uto8 by Vierkantor@mastodon.vierkantor.com
2021-12-05T16:23:04Z
0 likes, 0 repeats
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₁.)
(DIR) Post #AQAh0FrQq1CXRvNwMC by Vierkantor@mastodon.vierkantor.com
2021-12-04T18:44:01Z
0 likes, 0 repeats
let's start off with the traditional one:∀ X. ¬(∅∈X) → ∃ f. ∀ x ∈ X. f(x) ∈ x
(DIR) Post #AQAh0G3U7CqI3J1Z8y by uxor@mastodon.xyz
2022-12-01T18:22:23Z
0 likes, 0 repeats
@Vierkantor "Zorn's Lemma? This isn't a lemma and it is not from me!"Max Zorn
(DIR) Post #AQAh0GehsocHukRIA4 by timorl@qoto.org
2022-12-01T18:46:18Z
0 likes, 0 repeats
@uxor *Kuratowski sitting annoyed in the corner.* @Vierkantor
(DIR) Post #AQAh0HI3WW5lsmqiUi by Vierkantor@mastodon.vierkantor.com
2021-12-06T22:15:15Z
0 likes, 0 repeats
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} = xDO-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.
(DIR) Post #AQAh0IpPnyN2eXSs88 by Vierkantor@mastodon.vierkantor.com
2021-12-04T18:51:20Z
0 likes, 0 repeats
you can also specify it on subsets rather than elements of X:∀ X. ∃ f. ∀ x ⊆ X. X ≠ ∅ → f(x) ∈ x
(DIR) Post #AQAh0JAgWtNtiVPrHc by Vierkantor@mastodon.vierkantor.com
2021-12-17T23:02:48Z
0 likes, 0 repeats
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".
(DIR) Post #AQAh0JYR6aNouAWpIu by Vierkantor@mastodon.vierkantor.com
2021-12-07T23:39:28Z
0 likes, 0 repeats
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.)
(DIR) Post #AQAh0KNq1TV3TaZsQK by Vierkantor@mastodon.vierkantor.com
2021-12-04T19:01:55Z
0 likes, 0 repeats
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).
(DIR) Post #AQAh0LAP6uLduDIf7g by Vierkantor@mastodon.vierkantor.com
2021-12-08T22:01:55Z
0 likes, 0 repeats
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.)
(DIR) Post #AQAh0Lz64QtiRR198a by Vierkantor@mastodon.vierkantor.com
2021-12-04T19:07:02Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0MjXHm2olSkEWO by Vierkantor@mastodon.vierkantor.com
2021-12-08T22:07:39Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0OBvrgLxHp2QQC by Vierkantor@mastodon.vierkantor.com
2021-12-08T22:09:53Z
0 likes, 0 repeats
Hint for showing the first formulation implies the second: use the ring R/I.
(DIR) Post #AQAh0Pbqaog1gUAdSC by Vierkantor@mastodon.vierkantor.com
2021-12-09T20:52:22Z
0 likes, 0 repeats
Another equivalent to the Axiom of Choice that people use a lot:All vector spaces have a basis.
(DIR) Post #AQAh0R4FAizACqSpM0 by Vierkantor@mastodon.vierkantor.com
2021-12-11T11:41:15Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0SRK4P2aSiGlxw by Vierkantor@mastodon.vierkantor.com
2021-12-11T22:15:26Z
0 likes, 0 repeats
In the product topology, the closure of a product is the product of the closures.
(DIR) Post #AQAh0TtieJLiz4Yxrk by Vierkantor@mastodon.vierkantor.com
2021-12-13T09:07:56Z
0 likes, 0 repeats
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".)
(DIR) Post #AQAh0VH9WfgjG2XC1w by Vierkantor@mastodon.vierkantor.com
2021-12-14T00:01:06Z
0 likes, 0 repeats
Every object of the category Set is projective.
(DIR) Post #AQAh0WbkZZl5ODB9m4 by Vierkantor@mastodon.vierkantor.com
2021-12-15T10:25:00Z
0 likes, 0 repeats
For all nonempty sets S, there is a map S × S → S giving a group structure on S.
(DIR) Post #AQAh0XsRqyi3KI00RM by Vierkantor@mastodon.vierkantor.com
2021-12-15T20:27:54Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0ZI0bQkXhqxvv6 by Vierkantor@mastodon.vierkantor.com
2021-12-16T23:51:16Z
0 likes, 0 repeats
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.
(DIR) Post #AQAh0amt272kLuQ6gi by Vierkantor@mastodon.vierkantor.com
2021-12-17T22:58:53Z
0 likes, 0 repeats
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).
(DIR) Post #AQAh0cHlSnKwzxsHSK by Vierkantor@mastodon.vierkantor.com
2021-12-18T22:08:50Z
0 likes, 0 repeats
All free abelian groups are projective. (See also day 13.)
(DIR) Post #AQAh0dlDykUpZcfK0u by Vierkantor@mastodon.vierkantor.com
2021-12-20T10:45:23Z
0 likes, 0 repeats
An abelian group is divisible iff it is an injective object of the category of abelian groups.
(DIR) Post #AQAh0fHALTdmGycLRI by Vierkantor@mastodon.vierkantor.com
2021-12-20T22:24:51Z
0 likes, 0 repeats
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).
(DIR) Post #AQAh0gsQOR2REp3c9Y by Vierkantor@mastodon.vierkantor.com
2021-12-21T23:55:24Z
0 likes, 0 repeats
Let S be a set of sentences in first-order predicate logic and B a consistent subset of S, then B is contained in a maximal consistent subset C of S, such that adding one extra sentence in S to C would make it inconsistent.In particular, types (of model theory, which have nothing to do with type theory types) are contained in complete types.
(DIR) Post #AQAh0iMEt4Ttpa0wGO by Vierkantor@mastodon.vierkantor.com
2021-12-22T21:19:13Z
0 likes, 0 repeats
Every small* category has a skeleton.* Obligatory remark that you should feel free to salt & pepper these kinds of statements with large enough cardinal axioms so that it makes sense meta-theoretically. Yes it's cheating since the basic idea is to start with ZF but meh.
(DIR) Post #AQAh0jnZWvwIIdoHVQ by Vierkantor@mastodon.vierkantor.com
2021-12-24T13:38:58Z
0 likes, 0 repeats
A full, faithful and essentially surjective functor between (small) categories has an inverse giving rise to an equivalence of categories.
(DIR) Post #AQAh0lOTbD3NFO5GfQ by Vierkantor@mastodon.vierkantor.com
2021-12-24T21:51:47Z
0 likes, 0 repeats
Freyd's adjoint functor theorem:Let G : C → D be a functor where C is complete. Then G has a left adjoint iff: * G preserves all limits and * for all x : D, there is an indexed family of arrows f_i : x → G y_i, such that all arrows x → Gy factor as G(y_i → y) ∘ f_i for some i.
(DIR) Post #AQAh0nG2fXUl1o9YnY by Vierkantor@mastodon.vierkantor.com
2021-12-25T22:34:48Z
0 likes, 0 repeats
For every set X there exists a natural number m ≥ 1, an ordinal number α, and a function f sending each β ∈ α to a set with at most m elements, such that X is the union of all f(β).
(DIR) Post #AQAh0ou8XxA48Rv5vs by Vierkantor@mastodon.vierkantor.com
2021-12-27T09:52:26Z
0 likes, 0 repeats
A set X is finite iff for all relations R that well-order X, the dual R' (given by a R' b ↔ b R a) also well-orders X.
(DIR) Post #AQAh0qIdMMLoSiOAkq by Vierkantor@mastodon.vierkantor.com
2021-12-27T21:57:58Z
0 likes, 0 repeats
Any relation restricts to a partial function with the same domain. In other words, let R be a relation, then there is a function f : {x | ∃ y, x R y} → {y | ∃ x, x R y} such that for all x, x R f(x).