Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [foundations]

This tag is for questions about the foundations of mathematics, and the formalization of mathematical concepts in foundational theories (e.g. set theory, category theory, and type theory).

1
vote
0answers
36 views

Legitimacy of Consistency Proofs

In this question I asked yesterday I put forward two interpretations of a statements such as "System X is consistent". (a) we can think of it as saying no finite sequence of applications of logical ...
3
votes
0answers
59 views

Consistency of PA from a Formalist Perspective

In this lengthy thread there's people bickering back and forth about the consistency of PA (Peano Arithmetic) and misunderstandings abound. In reading it I came to an understanding I found useful, ...
1
vote
2answers
130 views

Well-definedness of uncomputable functions.

I have been reading about Rayo's function and uncomputable functions in general, and have gotten very confused. There is apparently concern over the well-definedness of Rayo's function, but I never ...
1
vote
2answers
36 views

What function $f(n)$ is defined by $f(1)=2$ and $f(n+1)=2f(n)$ for $n\geq 1$

I have to 2 qusetions in a mathematical induction homework: 1-What function $f(n)$ is defined by $f(1)=2$ and $f(n+1)=2f(n)$ for $n\geq 1$ My attempt: $f(1)=2$ $f(2)=2f(1)=2(2)=2^2$ $f(3)=2f(2)=...
1
vote
1answer
68 views

Development of topology and differential geometry in ETCS

I would like to ask for some reference textbooks or articles, or any information that you know about developing topological concepts and differential geometric concepts using as a foundation ETCS ...
6
votes
1answer
80 views

What is the Turing degree of Truth?

First of all by Truth I mean the set $T$ of the Gôdel numbers of the true formulas of first order arithmetic. First order arithmetic is not decidable and $T$ is not decidable, additionally the ...
1
vote
1answer
82 views

Hilbert Program: Consistency vs Soundness

I have been wondering why exactly Hilbert asked for a decidable, complete, and consistent set of axioms for mathematics, rather than a decidable, complete, and sound set of axioms. Consistency being: ...
0
votes
1answer
45 views

How to define substitution using ZFC

One question I've had regarding ZFC is how to define substitution. I cannot see how it's possible, despite the frequent use of substitution within both pure and applied mathematics. Just to be clear, ...
1
vote
1answer
39 views

Question on the reasoning behind determining surjectivity of a function

I understand the idea of surjectivity and its definition: "A function f is surjective if f:A->B if $\forall y\in Y,\exists x \in X$ such that $y=f(x)$" However I have a question on the following ...
1
vote
0answers
58 views

Limit of a sequence related to non-well founded set theory [closed]

Consider the following: $$\alpha_0 = \{\} $$ $$\alpha_1 =\{\{\}\}$$ $$\alpha_2 =\{\{\{\}\}\}$$ $$...$$ Clearly $\alpha_i$ is considered a set for all $i \in \omega$. Then consider $ \alpha=\lim_{i \...
0
votes
2answers
66 views

Need help with proof by contradiction of implication.

Question reads: $$\forall n \in \mathbb{N}, \forall m \in \mathbb{N}, (n^4 + n^2 + 1 \ne m^2)$$ In english, this reads: for every n and m in the set of natural numbers, $n^4 + n^2 + 1$ does not ...
1
vote
0answers
23 views

Sequence of Number System Construction

After constructing the naturals, why construct integers before rationals? Is there a historical explanation? Couldn't ordered pairs of fractions constructed from the naturals be used to represent ...
1
vote
1answer
64 views

What is the difference between the logical formula $\alpha$ and expression “$\alpha$ is true”?

What is the difference between the logical formula $\alpha$ and expression "$\alpha$ is true"? I feel that there is a difference between those expressions. I think this difference is the difference ...
0
votes
0answers
37 views

The length of the sequence concatenated two sequences

Let $\alpha$ be a finite sequence, and $|\alpha|$ be the length of $\alpha$. Let $\alpha_1, \alpha_2$ be two finite sequences. Prove that $|\alpha_1 \alpha_2| = |\alpha_1 |+|\alpha_2|$. Where $\...
1
vote
0answers
106 views

Why the 'natural' consistency proof of PA cannot be carried out $\textbf{in}$ PA

In my proof theory monograph there is this exercise: "The natural proof of PA cannot be carried out in PA. Why? (This proof consists in showing that all theorems of PA are ture.)" Apparently, by '...
0
votes
1answer
18 views

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$.

The relation $T$ on $\mathbb{R}\times \mathbb{R}$ given by $(x,y)T(a,b)$ iff $x^2+y^2=a^2+b^2$. Sketch the equivalence class of $(1,2)$; of $(4,0)$. $T$ is an equivalence relation on $\mathbb{R}\...
0
votes
0answers
45 views

Questions in proof theory (PRA-provability of EA-theorems, Girards book from '87)

I am working through the above mentioned book, 'proof theory and logical complexity, volume 1', with some trouble here and there. I would be glad if someone can help me with some of the exercises, ...
1
vote
1answer
73 views

Alternative axioms for NBG or MK

While I was thinking about NBG and MK I had the idea for two alternative axioms. As usual $V$ is the class of sets. The first one: For a boolean function $f : \{T,F\}^n \to \{T,F\}$ let $\varphi_f(...
6
votes
2answers
113 views

How badly does foundation fail in NF(etc.)?

The strongest antifoundation axiom I know is due to Boffa. Roughly, it asserts that every graph which could represent a set, does. For example, considering a graph consisting of (a root connected to) ...
8
votes
1answer
85 views

Without foundation: Not transitive model of ZFC?

Let's assume that ZFC is consistent. It is easy to show that there is an illfounded model (with compactness, e.g. here). If we have the axiom of foundation at the background level we can conclude ...
1
vote
1answer
59 views

Questions in proof theory (Definition of an interpretation of one theory in another, Girards Book from '87)

I am working through the above mentioned book, 'proof theory and logical complexity, volume 1', with some trouble here and there. I would be glad if someone can help me with some of the exercises, ...
1
vote
0answers
60 views

Questions in proof theory (PRA-provability of an EA-axiom, Girards Book from '87)

I am working through the above mentioned book, 'proof theory and logical complexity, volume 1', with some trouble here and there. I would be glad if someone can help me with some of the exercises, ...
1
vote
0answers
46 views

Prospects of teaching/learning elementary math with computed-checked type theory

I've read as much as I can understand about type theory and homotopy type theory (HoTT) and it seems like these are very promising directions for re-foundationalizing mathematics in a way where ...
2
votes
2answers
75 views

Are there mathematical premises that don't hold true whithin other mathematical systems/ways of thinking? [closed]

I do not really know how to phrase the question, but it is as follows: Are there mathematical premises that don't hold truth given different systems? And can someone give me examples? For example ...
3
votes
1answer
90 views

Is every model of MK (Morse-Kelley-Set-Theory) well-founded?

On page 2 in "The Hyperuniverse Project and Maximality" is written: The models $\mathcal{M}$ of MK are of the form $\langle M, \in, \mathcal{C} \rangle$, where $M$ is transitive model of ZFC, $\...
2
votes
0answers
141 views

Principia Mathematica, chapter *117: a false proposition?

I was reading Principia Mathematica of Whitehead and Russell and I have found what I think is a false proposition. The proposition in question is *117.632 click on the link to see the formula and the "...
1
vote
0answers
30 views

Category theory using 2-sorted logic

Can anyone give some reference text that axiomatizes category theory using first order logic using 2 sorts (if that makes sense)? I have found reference about 1 sorted axiomatization but I also found ...
2
votes
3answers
54 views

Proving Equivalence Relations, Constructing and Defining Operations on Equivalence Classes

I think I have an intuitive sense of how ordered pairs can function to specify equivalence classes when used in the construction of integers and rationals, for example. I put the cart before the horse,...
0
votes
1answer
44 views

Definition of < in Construction of Reals

In the section of Spivak's Calculus on the construction of the reals, < is defined: if alpha and beta are real numbers, then a < b means that a is contained in b (that is, every element of a is ...
3
votes
0answers
54 views

Model for the type-theoretic axiom of choice in Coq.

This is the request for references. It is a known fact that there is a model of ZFC in ZF, so ZFC is consistent if ZF is consistent. It is also know that there is a double-negation Godel-Gentzen ...
0
votes
1answer
54 views

Is it possible to prove Regularity with Transfinite Induction only?

Let us assume that we have only statement of transfinite induction. (And maybe some other well-know axioms) My question: "Is it possible to derive from it a regularity axiom as a theorem?". Some of ...
0
votes
1answer
85 views

Formal definition of a functor in $\mathsf{ZFC}$

Let $\mathcal{C}$ and $\mathcal{D}$ be categories. The first thing that comes to mind when considering a definition of a functor between $\mathcal{C}$ and $\mathcal{D}$ in $\mathsf{ZFC}$ is that it ...
1
vote
1answer
88 views

Category of functors $[C,D]$ and Grothendieck universes

A set $U$ is a universe if for any $x \in U$ we have $x \subseteq U$, for any $x,y \in U$ we have $\{x,y\} \in U$, for any $x \in U$ we have $\mathcal{P}(x) \in U$, for any family $(x_i)...
2
votes
1answer
62 views

Why we can safely treat objects like mathematical entities?

In the study of number systems we learn the axioms of real numbers. For example: The commutative axiom $X.Y = Y.X$ The distributive axiom $X.Z + Y.Z = (X+Y).Z$ Well, the thing is that we are ...
7
votes
5answers
760 views

How do we know our definitions don't lead to contradictions

How do we assure ourselves when defining an operation that it does not lead to contradictions? For example 0! := 1. I understand the practicality of why it is defined this way, but I am wary of what ...
-2
votes
1answer
68 views

Are there number systems that fix divide-by-zero? [duplicate]

Natural numbers are closed under addition and multiplication, but not subtraction. Fixed by... Integers are closed under subtraction, but not division. Fixed by... Rational numbers are closed under ...
2
votes
2answers
55 views

Translate the following English sentences into symbolic sentences with quantifiers.

this is my solution of my homework, is that true 100%? Please if there is any mistake tell me because my professor is so careful. Thanks. (Sorry, I don’t speak English well) i) Translate the ...
1
vote
0answers
77 views

Is everything a set? [closed]

ZFC set theory has the surprising property of being able to represent many mathematical objets that have intuitively nothing to do with sets. For example, a couple is represented by a Kuratowski pair, ...
3
votes
0answers
57 views

What part of arithmetic can be founded on recursive functions and without unbounded quantification?

Reading Skolem's 1923 Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlicher mit unendlichem Ausdehnungsbereich (Foundation of elementary ...
1
vote
1answer
68 views

Uniqueness of the empty set

When reading about set theory, I came across a simple question about the "uniqueness" of the empty set: Let $\mathfrak{M} \models ZF$, let $M$ be the domain of $\mathfrak{M}$. Let's create an inner ...
2
votes
1answer
26 views

Using this definition of ordinals, do I need foundation?

Definition. A set is an ordinal if it is a transitive set of transitive sets. This is the simplest definition of an ordinal I have ever encountered, and I happen to like it a lot for this reason. ...
-1
votes
1answer
29 views

Is applied statistical mathematics also can be explained by the zfc set theory?

I know that here there is already a lot of explanations about the zfc/zf/aca axioms but i wanted to ask if hypothetically people realy wanted to explain applied statistics to a creature that only ...
1
vote
2answers
41 views

How does the well-orderedness of the set of natural numbers follow assuming the inductive-set definition of natural numbers

Assume that $\mathbb R$ is an ordered field (i.e. $\mathbb R$ is a model of real numbers). We define the set of natural numbers $\mathbb N$ as the smallest inductive set containing $1_\mathbb R$ (...
6
votes
3answers
766 views

Why is the principle of explosion accepted in constructive mathematics?

I think something is wrong with the principle of explosion, because according to it, if I know $P\wedge \lnot P$, I can deduce $Q$ though I don't know anything about $Q$. Is it really constructive to ...
-1
votes
1answer
46 views

What makes a structured set a set of numbers?

I wonder which characteristics of a (structured) set $X$ let us consider it a set of numbers. Does the existence of two operations $+: X \times X \rightarrow X$ and $\times: X \times X \rightarrow X$...
-2
votes
1answer
35 views

manners of collection [duplicate]

I encountered idea of considering Sample space $\Omega$ as collection of function so far as I saw. Can you show the proof of thesis $x \neq \{x\}$? In a book I saw this thesis is included in context ...
3
votes
1answer
68 views

How to prove $\sqrt{2}\in \Bbb{R}$ with Dedekind cuts?

Problem statement: Prove that $\sqrt{2}\in\Bbb{R}$ by showing $x\cdot x=2$ where $x=A\vert B$ is the cut in $\Bbb{Q}$ with $A=\{r\in\Bbb{Q}\quad : \quad r\leq 0\quad \lor \quad r^2\lt 2\}$. Denote the ...
0
votes
0answers
42 views

Why is the axiom of choice necessary? [duplicate]

For long time, I cannot appreciate the axiom of choice: $\forall \lambda \in \Lambda (A_\lambda \ne \emptyset) \Rightarrow \Pi_{\lambda \in \Lambda} A_\lambda \ne \emptyset$. For any $\lambda \in \...
1
vote
1answer
104 views

Existence of Natural Numbers as an Axiom

By natural numbers $\mathbb{N}$ I understand any set satisfying Peano axioms: $0 \in \mathbb{N}$ $\sigma : \mathbb{N} \to \mathbb{N}$ $\forall n \in \mathbb{N} \; . \; \sigma(n) \neq 0$ $\forall n,m \...
0
votes
1answer
42 views

Transfinity of $\mathbb{Q}$ and $\mathbb{Z}$ [closed]

I have read in here: https://math.stackexchange.com/a/2899795/588260 that $\mathbb{Q}$ is 'larger' than $\mathbb{Z}$. I assume it has to do with transfinities in which the one of $\mathbb{Q}$ has a ...