39
votes
Is most of mathematics independent of set theory?
EDIT: for a variety of reasons, I think I should give an explicit caveat here. Obviously I believe the things in my answer below - otherwise I wouldn't have written it. But I am sure there are many, ...
- 237k
24
votes
Is most of mathematics independent of set theory?
You can think of set theory as a low-level programming language, like Assembly; it works directly with sets in a way analogous to how Assembly works directly with bits and bytes. Some people work with ...
- 409k
11
votes
Is most of mathematics independent of set theory?
Most mathematics can be translated into some suitable set theory such as ZFC. That is certainly true! However, it is totally different from the claim that most mathematics deals with sets. From the ...
- 56k
10
votes
Accepted
How are sets defined in reverse mathematics?
The answer is in the name of the book.
The system described is equivalent to a particular (monadic) second-order theory using Henkin semantics.
Instead of talking about "sets", Simpson could have ...
- 24.6k
8
votes
Accepted
Are there non-standard counterexamples to the Fermat Last Theorem?
I am going to respond to two questions quoted below, which come from this comment. Here "TP" means "transfer principle". I've switched the order of the questions.
... why it does not prove that ...
- 80.6k
7
votes
Applications of the Mean Value Theorem (but not Mean Value Inequality)
Consider the following proposition discussed by Hardy in A Course of Pure Mathematics.
Suppose $\lim_{x \to \infty} f(x) = L$ and $\lim_{x \to \infty} f'(x)$
exists. Then $\lim_{x \to \infty} f'(...
- 89.1k
7
votes
Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?
No: $L_\alpha$ is countable for any countable $\alpha$, so it cannot contain all of $P(\mathbb{N})$.
- 323k
6
votes
How are sets defined in reverse mathematics?
I'm not sure I've understood your question correctly, but let me take a stab at it:
The short version is that we can develop RCA$_0$ (and any other theory, for that matter) entirely "autonomously,...
- 237k
5
votes
Computable but Nonexistent Set
This is a common confusion faced when learning reverse mathematics. There are three different objects to consider here:
The function $g$.
The graph of $g$, $\{\langle n,g(n)\rangle: n\in\mathbb{N}\}$....
- 237k
5
votes
When do we need the axiom of choice to prove the existence of a basis?
Clearly if $X$ is finite, then the $\mathbb{R}$-vector space $F(X,\mathbb{R})$ of maps from $X$ to $\mathbb{R}$ has a basis - namely, consisting of the indicator functions $$\delta_a: x\mapsto 0\mbox{ ...
- 237k
5
votes
Accepted
Constructive proof of the Banach-Alaouglu theorem
If $X$ is separable then the closed unit ball $B$ of $X^{*}$ is metrizable in the $weak^{*}$ topology. [ $d(f,g)=\sum\limits_{k=1}^{\infty} \frac 1 {2^{i}} \frac {|f(x_i)-g(x_i)|} {1+|f(x_i)-g(x_i)|}$ ...
- 308k
5
votes
Accepted
Is it consistent for $P(\mathbb{N})$ to be present in a low layer of the Constructible Universe?
Let me compile my comments into an answer. I'll first explain (elaborating on Asaf's comment) why every model of ZF contains (things it thinks are) sets of naturals which (it thinks) have $L$-rank ...
- 237k
4
votes
Accepted
Why does the Cantor-Bendixson cupcake theorem need transfinite induction?
This is a great question! While the reverse mathematics of simple combinatorial or algebraic principles feels rather concrete, once we look at stronger principles - especially those connected with &...
- 237k
4
votes
Accepted
What is the difference between "Peano arithmetic," "second-order arithmetic," and "second-order Peano arithmetic?"
Yes, your understanding is basically right.
In more detail:
The term "Peano arithmetic" is used variously by different communities to refer to either first or second order Peano arithmetic (...
- 237k
4
votes
Accepted
Is the range of a total $\Pi^1_1$ function $\Delta^1_1$?
$a$ belongs to the range of $f$ iff $(\exists x\in\mathbb{N})(\forall y\in\mathbb{N})(y=a \lor f(x)\ne y).$
The two quantifiers in front are numeric, and $``f(x)\ne y”$ is $\Sigma_1^1,$ so the formula ...
- 9,338
3
votes
Accepted
Differences between real numbers in $ACA_0 + \lnot Con(PA)$ and standard real numbers?
You can find many examples about the topology of the reals in $ACA_0$ in Simpson's $\it Subsystems\ of\ Second$-$\it Order\ Arithmetic$. I don't think $Con(PA)$ itself has a usable topological ...
- 574
3
votes
Applications of the Mean Value Theorem (but not Mean Value Inequality)
Suppose $f:[a,b]\to R$ is continuous, with $a<b,$ and $f''(x)\geq 0$ for all $x\in (a,b)$. Then whenever $a\leq x<y\leq b$ and $s\in [0,1]$ we have $$s f(x )+(1-s) f(y))\geq f(x s +y(1-s)).$$ ...
- 57.4k
3
votes
Why restrict to $\Sigma_1^0$ formulas in $RCA_0$ induction?
This is a great question!
The short version in my opinion is that there is a decent argument that $\mathsf{I\Sigma_1}$ corresponds to "finitistic induction," and so is naturally ...
- 237k
3
votes
Accepted
atomic formula and $\Pi_1^0$ is still $\Pi_1^0?$
Yes, this is still $\Pi^0_1$ - we can just move the quantifier over (as Wojowu points out in their comment): $\varphi(x)\wedge\forall y(\psi(x,y))$ is equivalent to $\forall y(\varphi(x)\wedge\psi(x,y)...
- 237k
3
votes
Accepted
Satisfaction of theories like "second-order" arithmetic by models with "converse" comprehension
No. For instance, suppose the language has just one other symbol, a function $f:N\to N$. Let $X=\{0,1\}\times\mathbb{N}$ and let $T$ be the complete theory of the structure $X\sqcup\mathcal{P}(X)$ ...
- 323k
3
votes
What is the Turing degree of the set of true formula of Second Order Arithmetic?
I'll focus only on the second-order situation here, since my answer applies a fortiori to the higher orders.
It essentially$^1$ requires us to introduce a new notation, to the point that - in my ...
- 237k
3
votes
Accepted
How to get an original function from the limit definition of a derivative?
If I'm understanding your question correctly, it boils down to (1) identifying that a given limit is the derivative of a function $f(x)$ at some point $x=a$, namely
$$f'(a)=\lim_{h\to0}\frac{f(a+h)-f(...
- 16.7k
3
votes
How to get an original function from the limit definition of a derivative?
The derivative of a function $f$ at a point $a$ is defined as
$$f'(a)=\lim_{h\to 0}\frac{f(a+h)-f(a)}{h}.$$
Setting $f(x)=e^x$ and $a=0$ this yields
$$\frac{d}{dx}e^x\mid_0 = \lim_{h\to 0}\frac{e^{0+...
- 5,629
3
votes
Real numbers cannot be constructed?
This seems to me like a semantic issue: Nowadays, after the advent of the absolute infinite in mathematics, the axiom of infinity has begun being conventionally interpreted to posit the existence of ...
- 193
2
votes
Accepted
Justify the existence of a set by using $\Delta_1^0$ comprehension
This is the sort of thing that is, on one hand, often routine once you understand it, and, on the other hand, too long to actually write out by hand. To work in Reverse Mathematics, you need to ...
- 80.6k
2
votes
Accepted
Ramsey theorems for the naturals and for general infinite sets
Just use the order-preserving bijection $f:X\to\mathbb N$ to define a coloring of $[\mathbb N]^n$ which is isomorphic to the given coloring of $[X]^n.$ Namely, for $s\in[\mathbb N]^n,$ give $s$ the ...
- 75.8k
2
votes
Accepted
Theorem in ACA that is unprovable in $Π^1_1$-CA$_0$?
$\Pi^1_1$-CA is indeed strictly stronger than ACA. They both share the full induction scheme, so to compare them we only need to look at their comprehension parts. ACA contains comprehension for ...
- 237k
2
votes
Accepted
Could we take certain results as axioms and prove the original axioms using our new ones?
Yes, this has been intensely studied in a number of contexts. We pick some very small set of axioms, basically all the uninteresting ones; we then look at what implications this "base theory" can ...
- 237k
2
votes
What is the reverse mathematical strength of the assumption of the existence of a nontrivial ultrafilter?
Reverse mathematics is the wrong tool for this: it takes place in the context of second-order arithmetic (= natural numbers and sets of natural numbers) and so the existence of an ultrafilter (= a set ...
- 237k
2
votes
Accepted
If $x\in dom(\phi),$ we can use the code $\Phi$ and minimization theorem to prove within $RCA_0$ that $\phi(x)$ exists.
The key point is the definition of "$x \in \text{dom}(\Phi)$."
You want to view $(a,r)\Phi(b,s)$ as saying that if $x \in (a-r, a+r)$ then $\phi(x) \in [b-s, b+s]$. By definition (not in the ...
- 80.6k
Only top scored, non community-wiki answers of a minimum length are eligible