71

Set theory provides a foundation for mathematics in roughly the same way that Turing machines provide a foundation for computer science. A computer program written in Java or assembly language isn't actually a Turing machine, and there are lots of good reasons not to do real programming in Turing machines - real languages have all sorts of useful higher ...

37

I haven't read the paper carefully, but this appears to be a standard undecidability result, of the sort of which there are dozens if not hundreds in the literature, of the same ilk as the undecidability of Wang tilings, the undecidability of the existence of solutions to Diophantine equations, the word problem for groups, and many others.
It's a formal ...

28

To my way of thinking, there are at least three distinct
perspectives one can naturally take on when undertaking work in
nonstandard analysis. In addition, each of these perspectives can
be varied on two other dimensions, independently. Those dimensions are, first,
the order of nonstandardness (whether one
wants nonstandardness only for objects, or also for ...

answered Dec 17 '15 at 22:55

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

27

I prefer to think of ZFC as a proposed model of mathematics. I want to emphasize both words "proposed" and "model". For comparison, consider quantum mechanics. It can be modeled — as far as we know, perfectly — by the theory of Hilbert spaces. But the state right now of the electron in your retinal cell being excited by photon being emitted by the leftmost ...

answered Nov 29 '16 at 0:05

Theo Johnson-Freyd

48.7k1010 gold badges108108 silver badges292292 bronze badges

23

A very famous and important example of a counterexample that was found to be defective occurred in set theory. As Georg Cantor developed the theory of infinite sets, he proved that some infinite sets are larger than others, by showing that there was not a one-to-one function between them. Most famously, he showed that the real numbers $a\leq x\leq b$ are ...

21

There are already some excellent answers explaining in what senses ZFC can still be a foundation for most mathematics. But it also seems appropriate to mention some ways in which ZFC is insufficient as a foundation for modern mathematics. [Disclaimer: throughout this answer I will talk about "ZFC", but the remarks apply just as well to its variations ...

answered Nov 30 '16 at 7:47

Mike Shulman

57.1k66 gold badges129129 silver badges312312 bronze badges

21

The relationship between toposes and set theories was studied comprehensively in
Steve Awodey, Carsten Butz, Alex Simpson, Thomas Streicher: Relating first-order set theories, toposes and categories of classes.
Annals of Pure and Applied Logic, Volume 165, Issue 2, February 2014, Pages 428-502
Regularity is discussed under the name "well-foundedness&...

20

I interpret your question to be asking about the transition from
computable undecidability to Gödelian or logical
undecidability, and furthermore about the extent to which this
logical undecidability might depend on which axioms of mathematics
we have adopted.
The answer is that one may quite generally deduce that there are
concrete instance of logical ...

answered Dec 12 '15 at 13:00

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

20

There's a certain confusion underlying your question, which Andreas Blass's answer is trying to point out. Let me see if I can explain it in different words.
You say, “the negation of Con(ZFC) proves it halts in finite time” and you are trying to use this fact to argue about which axioms beyond ZFC to accept. The best sense I can make out of your comment is ...

18

$\DeclareMathOperator\BB{BB}$Philosophical issues, like acceptance (or non-acceptance) of large cardinals, won't affect $\BB(n)$, because the busy beaver function is defined arithmetically and so depends only on the natural numbers. Specifically, suppose I believe in some large cardinal, say supercompact. Then within my set-theoretic world, there is the ...

13

The original is Alfred Tarski's book "The completeness of elementary algebra and geometry", which was due to appear in 1940 but never made it into print because of the outbreak of WW2. An edition appeared after all in 1967 (Institut Blaise Pascal, Paris), but is not easy to come by.
Essentially the same argument is presented in Tarski's 1948/51 "A decision ...

12

KP (Kripke-Platek set theory) is the most well-known fragment of $\sf{ZF}$ which suffices for the development of the rank function, thus $\sf{KPR}$ = $\sf{KP}$ + "for all ordinals $\alpha$, $V(\alpha)$ exists" is the usual minimal theory in which one can be assured of the stratification of the universe into $V(\alpha)$s.
On the other hand, as ...

12

Accepting the convention that it is a logical axiom that the universe is nonempty, the answer is yes. We will formalize the transitive closure axiom schema (TC) as follows: for any definable (with parameters) binary relation $R,$ if for all $x,$ $\{y: y R x\}$ is a set, then for all $x,$ there is a set $T$ such that $x \in T$ and $T$ is closed downwards ...

12

Although you prefer models other than permutation models, let me point out an appearance of permutation models, particularly the basic Fraenkel model, at the border between computer science and logic. The topic concerns operators that bind variables, like $\forall$ and $\exists$ in logic, the $\lambda$ in lambda-calculus, and $\int$ in calculus. The actual ...

11

I feel like this is an instance of a larger question:
When might it be nice to work with an axiomatic description of a theory rather than an explicit construction?
This comes up all the time, e.g. in topology, cohomology, algebra (e.g. abstract groups rather than permutation groups), and more recently with homotopy type theory.
Some possible answers to ...

11

In my blog post Transfinite recursion as a fundamental principle in set theory, I prove that the principle of transfinite recursion is equivalent to the replacement axiom.

answered Mar 2 '18 at 12:00

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

11

No. Consider the model $\langle V_{\omega_1},\in\rangle$. This is a model of Zermelo's theory, but all ordinals in it are countable. Thus, it satisfies the ordinal-replacement axiom, since the image of a countable ordinal under any function will be countable, and $V_{\omega_1}$ contains all its countable subsets, since $\omega_1$ is regular.
In fact, in ...

answered Mar 16 '18 at 18:05

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

11

(I made my answer community wiki because the previous comments cover the important points of the answer.)
You can find the relationship between inaccessible cardinals and Grothendieck universes on Wikipedia (!)
Theorem. The followings are equivalent:
Tarski's axiom A: every set is contained in a Grothendieck universe, and
There is a proper class of ...

10

Yves Diers has the notion of a Zariski category in [Categories of commutative algebras], which apparently suffices to carry out a lot of commutative algebra in an axiomatic fashion. I reproduce the definition:
A Zariski category is a category $\mathcal{A}$ satisfying the following conditions:
$\mathcal{A}$ is cocomplete.
$\mathcal{A}$ has a ...

10

Many people find it natural to consider the set-theoretic analogue of mereology to be the inclusion relation $\subseteq$ rather than $\in$, since after all, $\subseteq$ is reflexive and transitive and admits relative complements, and these are all axioms listed on the mereology page to which you link, but $\in$ does not have these features. (For this reason,...

answered Mar 15 '18 at 1:09

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

10

Yes, indeed this kind of choice in general doesn't imply $\mathsf{AC}$ over $\mathsf{ZF}-\mathsf{Reg}$.
I will reason in $\mathsf{ZFC}$ and construct an interpretation of $\mathsf{ZF}-\mathsf{Reg}$, where $\mathsf{AC}$ fails, but choice for definable sets holds. The idea is to define a modified permutation model $M$ of $\mathsf{ZFU}+\lnot\mathsf{AC}$, where ...

9

If you make your requirement only for regular cardinals $\kappa$, then we can easily get an equiconsistency.
Theorem. The following theories are equiconsistent over ZFC:
There are unboundedly many inaccessible cardinals.
The continuum function $\kappa\mapsto 2^\kappa$ is injective and $2^\kappa$ is weakly inaccessible for any infinite regular cardinal $\...

answered May 8 '14 at 16:03

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

9

This complements the other answers. Let's take the natural numbers as an example for discussion.
When we use mathematics, we typically want to use properties of the natural numbers: after every natural number there's a next one, adding two of them yields another one, same with multiplying, those two operations play nice together (distributive laws), the ...

9

### Can you formulate a theory stating that a truth predicate does not exist for first order set theory?

The assertion that there is (or is not) a truth predicate is expressible in the second-order language of set theory, but assuming consistency, not by any first-order assertion.
Second-order. In the second-order case, one simply says that there is a class $T$ satisfying the Tarskian recursion $$\exists T\ (T\text{ is a truth predicate}).$$ I gave the ...

answered Jul 12 '17 at 14:05

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

9

Replacing separation with injective replacement is equivalent to adding the usual replacement axiom, and so your theory $Z^{inj}$ is the same as ZF. From this, you can easily answer all your questions.
The first thing is to note [thanks to Emil in the comments below] is that because you have stated your injective replacement axiom to concern only partial ...

answered Feb 7 '18 at 11:02

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

9

Your transfer principle contradicts the axiom of foundation.
To see this, observe that under foundation, every nonempty finite set $x$ has an $\in$-maximal element, a set $z\in
x$ with $z\notin u$ for any $u\in x$, since one can simply climb up via $\in$ inside $x$ until one
reaches a maximal element.
But not every infinite set is like that, since the set
...

answered Apr 30 '18 at 15:22

Joel David Hamkins

192k3333 gold badges591591 silver badges10401040 bronze badges

9

The Pauli exclusion principle for identical particles (fermions) may be one of the "finite predictions" of quantum mechanics dependent on set theory. S. Tarzi argues in Exclusion Principles as Restricted Permutation Symmetries (2003) that the description of collections of sets of identical particles requires a failure of the Axiom of Choice and proposes ...

answered Feb 15 '19 at 9:31

Carlo Beenakker

136k1212 gold badges329329 silver badges470470 bronze badges

8

A stark demonstration of why precisely defining how you form $PA_{\lambda +1}$ for $\lambda$ a limit ordinal: in 1939 Turing showed that if $\varphi$ is a true $\Pi^0_1$ statement, there is a notation for $\omega+1$ according to which $PA_{\omega+1}$ proves $\varphi$.
Less pathologically, I believe (although I can't at present find a reference) that there ...

8

Does it represent a new way of proving independence results compared to forcing, etc.? In other words, is it an advance on Gödel sentences and the continuum hypothesis?
No one's quite said it yet, so: the answer to both of these questions is no. As far as I can tell, the result is a standard reduction from the halting problem. The paper shows that computing ...

answered Dec 12 '15 at 8:47

Qiaochu Yuan

106k3434 gold badges382382 silver badges671671 bronze badges

8

Let $\kappa$ be an inaccessible cardinal. By reflection principle, we can find $\lambda>\kappa$ such that $V_\lambda$ is a model of $\mathsf{ZC}$ with $\Sigma_2$-replacement. Since the truth relation for $\Sigma_2$ formulas are definable on $\mathsf{ZFC}$, we can postulate $\Sigma_2$-replacement as a single formula.
Note that we only need to reflect $\...

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

#### Related Tags

axioms × 104set-theory × 72

lo.logic × 61

foundations × 12

reference-request × 10

large-cardinals × 9

axiom-of-choice × 8

model-theory × 7

ct.category-theory × 5

mathematical-philosophy × 5

pr.probability × 4

soft-question × 4

euclidean-geometry × 4

mp.mathematical-physics × 3

computability-theory × 3

type-theory × 3

theories-of-arithmetic × 3

higher-category-theory × 2

infinite-combinatorics × 2

quantum-mechanics × 2

decidability × 2

metamathematics × 2

continuum-hypothesis × 2

independence-results × 2

induction × 2