# Questions tagged [foundations]

Mathematical logic, Set theory, Peano arithmetic, Model theory, Proof theory, Recursion theory, Computability theory, Univalent foundations, Reverse mathematics, Frege foundation of arithmetic, Goedel's incompleteness and Mathematics, Structural set theory, Category theory, Type theory.

315 questions
Filter by
Sorted by
Tagged with
1 vote
162 views

### Which is richer Set or Graph Theory?

This theory about structures, defined as abstractions over isomorphic graphs, can interpret Set Theory in a rather creepy manner. Though the theory is largely technical, yet it is not far from being ...
• 9,636
131 views

### Suitability of formal type theory for mathematical thinking (vs. traditional set theory)

Type theory has advantages over set theory for the (computer) formalisation of mathematics, but has anybody who does mathematics with pen and paper found proof assistants or automated theorem provers, ...
2k views

### What governs our "perception?" about the platonic realm of sets?

Here, I want to delve into what do we exactly feel about what constitutes a platonic existence of a set? Or what makes us think or actually a kind of feel or sense the existence of a set in the ...
• 9,636
496 views

### The "first-order theory of the second-order theory of $\mathrm{ZFC}$"

$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...
• 4,587
542 views

### Why not $\sf ZFC+[V=HOD]$?

Why not $\sf ZFC+[V=HOD]$ as the standard set theory? It implies the existence of a definable global choice and well-order, and it is compatible with all large cardinal axioms extending $\sf ZFC$, so ...
• 9,636
184 views

• 19.4k
279 views

### Bounded alternatives to powerset that interpret ZFC

In set theory, many properties/relations of interest can be expressed as $\Delta_0$ formulas (formulas with only bounded quantifiers): \begin{align} \text{empty}(a) &\equiv \forall x \in a . \...
• 1,803
438 views

### How much Dependent Choice is provable in $Z_2$? And what about Projective Determinacy?

So, second order arithmetic, $Z_2$, is capable of proving quite a few things. One thing which would be of use is dependent choice for $\mathbb{R}$. Basically, dependent choice on $\mathbb{R}$ says ...
• 173
1k views

### Existence of skeletons in ZFC

Influenced by this question from a fellow lagomorph, I would like to get to the bottom of existence of a skeleton of a category. I want to stay in ZFC, so I do not assume the global axiom of choice. ...
• 12.1k
319 views

### Second order theory of a real-closed field

It is well known that the first-order theory of any real-closed field is complete, and consequently not capable of interpreting the majority of modern mathematics. Is this still true for the second-...
• 9,047
4k views

### Lists as a foundation of mathematics

I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
• 61.7k
182 views

### Is Vopěnka's principle inherited by Grothendieck topoi?

I call the Vopěnka's principle: Every subfunctor of an accessible functor is accessible but other formulations (which may lose equivalence in weak contexts?) are also interesting to me. If this is ...
• 6,562
283 views

### In HoTT with LEM, are sets and pointed sets the same thing?

The operations of adding and removing a point (where removing is a consideration of a subset of elements x such that $(x = *) \to 0$) implements the equivalence of these 1-types, as far as I can see. ...
• 6,562
241 views

### How did Szmielew prove that Pasch's axiom is a consequence of the circle axiom?

It is alleged that Szmielew proved that Pasch's axiom is a consequence of the circle axiom. The source is said to be The Pasch axiom as a consequence of the circle axiom, Bull.Acad.Polon.Sci.Sér.Sci....
983 views

### Propositional calculus, first order theories, models, completeness

In the usual context of model theory one studies first order theories: the Gödel completeness theorem asserts that $\varphi$ is a theorem of a theory $T$ (i.e. $\varphi$ is provable from the axioms of ...
• 9,180
4k views

### How much of the axiom of choice do you need in mathematics?

Say we have DC-λ where λ is some inaccessible cardinal. Is that enough to develop all of ordinary mathematics? If not, is there a strengthening that is but that nevertheless does not assume full ...
• 357
2k views

### Real reverse mathematics

Standard mathematical developments, be they set theoretic, type theoretic, synthetic, etc. all follow the same basic pattern: Lay out a language, assume some stuff in this language, then prove that ...
• 9,047
1 vote
93 views

### What computable pseudo-ordinals are there with initial segment $\omega_1^{CK}(1+\eta+1)$?

The notion of a “computable pseudo-ordinal”, i.e. a computable linear order with no hyperarithmetical descending chains, is an old one going back to Stephen Kleene. Joe Harrison wrote the definitive ...
• 4,529
119 views

### Higher-order oracle computation of reals and axiom of constructibility

Certain real numbers can be approximated arbitrarily well by computable functions. If we introduce halting oracles, then more real numbers can be "computed", like Chaitin's constant or the ...
142 views

• 281
65 views

### Is the centroid property equivalent to the middle line property of the triangle?

By a Tarski plane I understand a set $X$ endowed with a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ satisfying all Tarski axioms except ...
• 41k
2k views

### Why do we care about small sets?

I have been a user of category theory for a long time. I recently started studying a rigorous treatment of categories within ZFC+U. Then I become suspecting the effect of the smallness of sets. We ...
• 363
231 views

### Does $\text{ACA}_0$ + True Arithmetic prove the well-foundedness of every recursive ordinal?

As discussed in Noah Schweber's answer to What is the proof-theoretic ordinal of true arithmetic?, it is somewhat ambiguous what “the proof-theoretic ordinal of True Arithmetic” might mean. In one ...
• 4,529
1 vote
114 views

### Is it possible to set up multiple automorphisms over a structureless object inside single-sort defined category?

I was trying to understand the behaviour of the primitive equality (=) in the axiomatization of category, which takes morphisms as primitives and objects as derivatives in bijection to identity ...
• 13
64 views

### Comparing the areas of polygons via equidecomposability in the hyperbolic plane

It is well-known that in the Euclidean plane two simple polygons have the same area if and only if they are equidecomposable, i.e., can be decomposed into congruent triangles. Question. Is an ...
• 41k
368 views

• 41k
498 views

### A textbook on foundations of geometry in spirit of Tarski

I am interested in a textbook for studying (and teaching) foundations of geometry in the spirit of Tarski. I know that there is a rather old German book [W. Schwabhäuser, W. Szmielew, A. Tarski, ...
• 41k
167 views

### How strong is separation + reflection of unbounded quantifiers?

Consider a set theory with the following axioms: separation: $\exists y \forall x (x \in y \leftrightarrow \phi \land x \in a)$ where $y$ is not free in $\phi$ reflection: $\phi \to \exists u \phi^u$ ...
• 1,803