Intereting Posts

Orthogonal matrices form a compact set
An Introduction to Tensors
Proving $\sin (x)=\cos (90^\circ-x)$
Area between two circles as a double integral in polar coordinates
How to Compare two multiplications without multiplying?
Evaluating series of zeta values like $\sum_{k=1}^{\infty} \frac{\zeta(2k)}{k16^{k}}=\ln(\pi)-\frac{3}{2}\ln(2) $
lim (a + b) when lim(b) does not exist?
Operators such that $T\circ S=I$ but $S\circ T\neq I$.
Proving that if two linear transformations are one-to-one and onto, then their composition is also.
Integrate :$\int\frac{1}{\sqrt{\tan(x)}}dx$
Fourier transform of $f(x)=\frac{1}{e^x+e^{-x}+2}$
Find periodic solution of differential equation
A contradiction involving derivative
How to prove that $\frac{x^2}{yz+2}+\frac{y^2}{zx+2}+\frac{z^2}{xy+2}\geq \frac{x+y+z}{3}$ holds for any $(x,y,z)\in^3$
Max dimension of a subspace of singular $n\times n$ matrices

I am confused by this sentence in the Wikipedia article for “Well-ordering theorem”:

…the well-ordering theorem is equivalent to the axiom of choice, in the sense that either one together with the Zermelo–Fraenkel axioms is sufficient to prove the other, in first order logic (The same applies to Zorn’s Lemma.) . In second order logic, however, the well-ordering theorem is strictly stronger than the axiom of choice: from the well-ordering theorem one may deduce the axiom of choice, but from the axiom of choice one cannot deduce the well-ordering theorem

Isn’t second-order logic stronger than first-order logic? How is it that the equivalence proof in first-order logic is no longer valid in second-order logic?

- Proof of a basic $AC_\omega$ equivalence
- Infinite dimensional vector space. Linearly independent subsets and spanning subsets
- Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF
- Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice?
- Mathematical questions whose answer depends on the Axiom of Choice
- Is there any motivation for Zorn's Lemma?

- What is finite in a finite model
- First-Order Logic vs. Second-Order Logic
- dense linear orders DLO
- How to find the logical formula for a given truth table?
- Reference request, self study of cardinals and cardinal arithmetic without AC
- Axiom of Choice, Continuity and Intermediate Value Theorem
- Lack of implication and logical quantifiers
- Are proofs by contradiction really logical?
- Congruence of terms
- Big Bang Theory Reference to Formal Logic

If you follow the references given in the Wikipedia article, you will find out that the context of this theorem is very different.

While a lot of mathematics is done inside models of $\sf ZFC$ with first-order logic (and so we can make statements about high order logic inside the model). However one can use second-order logic (or rather some systems of second-order logic) as a foundation for mathematics. That is, we no longer work in $\sf ZFC$, we work in a context of second-order logic.

In certain systems which include the axiom of choice, the well-ordering principle is not provable. However without using the axiom of choice it is not hard to show that the well-ordering principle still implies the axiom of choice.

This is essentially theorem 5.4 which you can find on page 107 in the book by Shapiro.

There is a separate issue with trying to interpret this claim from the Wikipedia article:

In second order logic, however, the well-ordering theorem is strictly stronger than the axiom of choice: from the well-ordering theorem one may deduce the axiom of choice, but from the axiom of choice one cannot deduce the well-ordering theorem

In second-order arithmetic, the “well ordering theorem” is trivial: it is usually taken to mean that every set *of natural numbers* has a least element, which is a trival consequence of an induction axiom. It is hard to even state in second-order arithmetic that “there is a well ordering of the class $S$ of all subsets of $\mathbb{N}$” because, syntactically, that is a third-order statement. One could assert that there is a definable well-ordering of $S$ by referring to a particular formula that defines the well-ordering, but there is no reason to suspect that there is, in fact, a definable well ordering of $S$ unless we also assume something like $V = L$.

However, in second-order arithmetic, the “axiom of choice” is typically phrased as an axiom scheme. And, it is usually studied in a form where the objects being chosen are sets, not natural numbers. A typical instance of the scheme says:

$$

(\forall n)(\exists Y)\Phi(n,Y) \to (\exists Z)(\forall m)\Phi(m,(Z)_m)

$$

where $(Z)_m = \{ k : \langle m,k\rangle \in Z\}$. See Simpson, *Subsystems of Second-order Arithmetic*, section VII.6.

Now the well-ordering theorem *for numbers* does not imply the scheme for the axiom of choice *for sets* that I just described. Indeed, the full axiom system for second-order arithmetic, with comprehension for all formulas, does not even prove all instances of the axiom of choice in which $\Phi$ is $\Sigma^1_3$ (Simpson VII.6.3).

The key issue here is that, while “axiom of choice” makes fine sense in terms of type theory, such as second-order arithmetic and second-order logic more generally, it does not mean at all the same thing that it does in the “untyped” language usually used for set theory.

- Prove that the additive groups $\mathbb{R}$ and $\mathbb{Q}$ are not isomorphic.
- Möbius Transforms that preserve the unit disk
- Evaluate the limit of $\sum\limits_{i=1}^n\frac{2}{n}\left$ when $n\to\infty$
- $|e^a-e^b| \leq |a-b|$
- Can Spectra be described as abelian group objects in the category of Spaces? (in some appropriate $\infty$-sense)
- Prove that $\Diamond\Box p \rightarrow \Diamond (\Box (p\land q) \lor \Box(p\land\neg q))$ does not define a first-order condition on frames
- Showing a function is not uniformly continuous
- convergence of alternating series — weakening a hypothesis
- free software to create equations and export to various formats
- Does weak compactness imply boundedness in a normed vector space (not necessarily complete)?
- Prove ${\large\int}_0^1\frac{\ln(1+8x)}{x^{2/3}\,(1-x)^{2/3}\,(1+8x)^{1/3}}dx=\frac{\ln3}{\pi\sqrt3}\Gamma^3\!\left(\tfrac13\right)$
- Rating system incorporating experience
- The number of solutions to $\frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N$
- $2$-dimensional Noetherian integrally closed domains are Cohen-Macaulay
- How to prove $1$,$\sqrt{2},\sqrt{3}$ and $\sqrt{6}$ are linearly independent over $\mathbb{Q}$?