Skip to main content
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, ...
Noah Schweber's user avatar
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 ...
Qiaochu Yuan's user avatar
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 ...
user21820's user avatar
  • 59.2k
11 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 ...
Derek Elkins left SE's user avatar
10 votes
Accepted

Is the set of all algorithms computable?

This depends on the definition of "algorithms". If as stated informally in Wikipedia (often used in introductory algorithm courses), Starting from an initial state and initial input (...
Just a user's user avatar
  • 17.8k
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 ...
Carl Mummert's user avatar
  • 82.2k
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})$.
Eric Wofsey's user avatar
6 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)|}$ ...
Kavi Rama Murthy's user avatar
6 votes
Accepted

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}\}$....
Noah Schweber's user avatar
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,...
Noah Schweber's user avatar
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{ ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
5 votes
Accepted

Is the empty set always an 'implicit member' of all sets under a pure set theory?

"Looking into a set long enough" means the same thing as looking into its transitive closure. As you indicate that's the same thing as iterating the union $\omega$ times. In other words, $\...
spaceisdarkgreen's user avatar
4 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 ...
Noah Schweber's user avatar
4 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 ...
Noah Schweber's user avatar
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 &...
Noah Schweber's user avatar
4 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 ...
Noah Schweber's user avatar
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 (...
Noah Schweber's user avatar
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 ...
Mitchell Spector's user avatar
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 ...
realdonaldtrump's user avatar
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)...
Noah Schweber's user avatar
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)$ ...
Eric Wofsey's user avatar
3 votes
Accepted

Constructive mathematics plus existence of discontinuous functions

The existence of any function $f:[0,1] \to (-\infty,0) \cup (0,\infty)$ with $f(0) < 0$ and $f(1) > 0$ implies WLPO for the natural numbers. (For the special case of (a slight modification of) ...
Jem's user avatar
  • 168
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(...
user170231's user avatar
  • 20.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+...
vitamin d's user avatar
  • 5,793
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 ...
SpectreDNZ's user avatar
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 ...
Noah Schweber's user avatar
2 votes
Accepted

Relationship between l'Hospital's rule and the least upper bound property.

Here let's assume $F$ is non-archimedean. For each infinitesimal* $x \in F^{\times}$, let $[x]$ denote the archimedean class $\bigcup \limits_{n \in \mathbb{N}^*} \left]-n |x|;-\frac{1}{n} |x|\right[ ...
nombre's user avatar
  • 5,125
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 ...
Noah Schweber's user avatar
2 votes
Accepted

Game theory and the Reverse mathematics theme

There is an extensive body of research on games (specifically determinacy principles) and reverse mathematics. Just to mention a few results: WKL$_0$ is equivalent to clopen determinacy for games on $...
Noah Schweber's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible