Hot answers tagged

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 ...


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 ...


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 ...


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 ...


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.


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 ...


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,...


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 $\...


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

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 ...


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 ...


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 ...


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 ...


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 ...


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