All Questions
Tagged with set-theory theories-of-arithmetic
79 questions
1
vote
0
answers
89
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
-4
votes
0
answers
133
views
Which arithmetic\set theory is synonymous with this theory?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x$
Define: $x \leq y \iff x < y \lor x=y$
$ \textbf{...
- 11.3k
-4
votes
1
answer
173
views
To which arithmetic\set theory this theory is bi-interpretable?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
$ \textbf{Axioms:}$
$ \textbf{Order:} \ x < y < z \to x < z $
$ \textbf{...
- 11.3k
1
vote
1
answer
179
views
Natural functions outside $\sf PA$?
Can theories stronger than $\sf PA$ manage to define functions from the naturals to the naturals, that $\sf PA$ cannot? If so, what are examples of those functions?
- 11.3k
1
vote
1
answer
146
views
Can PA define functions related to higher theories?
Working in $\sf ZFC$ we can define a function $F$ from naturals to naturals such that $F(0) = \, ^\circ\ulcorner r({\sf Z}) \urcorner$, where $r({\sf Z})$ is the Rosser sentence of Zermelo set theory $...
- 11.3k
1
vote
2
answers
335
views
Heuristic interpretations of the PA-unprovability of Goodstein's Theorem
I've relatively recently learned about Goodstein's Theorem and its unprovability in Peano arithmetic (the Kirby-Paris Theorem). I do not have any real knowledge of formal logic; but I think I've seen ...
- 708
1
vote
0
answers
123
views
Is possibile to define transfinite sum and product recursively? [closed]
On mathstackexchange a few days ago I published the following question where I asked about "transfinite" sum and products but actually nobody answered or gave an opinion with a comment: thus ...
4
votes
1
answer
515
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
- 1
5
votes
2
answers
432
views
Models of second-order arithmetic closed under relative constructibility
I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
- 2,286
-2
votes
1
answer
211
views
Would this alteration safeguard the resulting theory from inconsistency?
If we replace "Emergence" axiom in the theory $T$ presented at posting "What is the set theory synonymous with this order-set theory?" with the following axiom, call the resulting ...
- 11.3k
3
votes
1
answer
169
views
Would this alteration of $T$ affect its synonymy with PA?
If we replace the single axiom "Emergence" in the axiomatic system $T$ presented at posting [What is the set theory synonymous with this order-set theory], by the following schema. Would the ...
- 11.3k
1
vote
1
answer
313
views
What is the set theory synonymous with this order-set theory?
Let $ T$ be a theory written in Mono-sorted first order logic with equality, with extralogical primitives: $<, \in$.
Define: $x \leq y \iff x < y \lor x=y$
Axioms:
$\textbf{Well ordering: }\\\...
- 11.3k
12
votes
4
answers
1k
views
Is this theory synonymous with PA?
Language: Mono-sorted first order logic with equality.
Extralogical Primitives: $<, \in$
Define: $x \leq y \iff x < y \lor x=y$
$\textbf{Well ordering: }\\\textit{Transitive:} \ x < y \land ...
- 11.3k
15
votes
5
answers
2k
views
In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?
It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...
- 961
6
votes
0
answers
407
views
Can Set Theory be turned into Infinite Arithmetic?
The following system I'd label as "Infinite Arithmetic" is simply an endeavor to extend second order arithmetic to the infinite ordinal world, and extending with it the representation of ...
- 11.3k
1
vote
0
answers
129
views
Is set theory interpretable in infinite primitive recursive arithmetic?
In A Formalization of the Theory of Ordinal Numbers, Takeuti interprets $\sf ZFC$ in a first order theory extending first order arithmetic to the infinite ordinal realm, while at the same time ...
- 11.3k
2
votes
1
answer
329
views
Can set theory be interpreted in infinite arithmetic?
Is the following system of infinite arithmetic consistent?
If so, can it interpret $\sf ZFC$?
Language: first order logic
Primitives: $\operatorname{Card}, <, + , \times,\text{^}$
where $\...
- 11.3k
-3
votes
1
answer
638
views
Analysis I, simpler proof of Tao's construction of the integers [closed]
In chapter 4 of Analysis I by Terence Tao, we have the following note about the set theoretic construction of the integers:
In the language of set theory, what we are doing here is starting with the ...
- 23
11
votes
2
answers
379
views
Can singular long models require less than PA?
Say that a long model is an $\mathfrak{A}\models\mathsf{I\Sigma_1}$ such that $\mathfrak{A}$ has strictly greater cardinality than each of its proper initial segments (in the case $\vert\mathfrak{A}\...
- 21.2k
10
votes
2
answers
600
views
Is diamond consistent with 2nd order PA?
If $T$ is a theorem of ZF which says something only about reals, then one may want to prove $T$ using a theory like 2nd order PA or related theories like ZFC$^-$ or GBC$^-$ (minus accounts for the ...
- 2,281
2
votes
0
answers
137
views
Can we extend the projectively extended real line with a single number that stands for division of zero by zero?
If we work within $\hat{\mathbb R} = \mathbb R \cup \{\infty\}$, i.e. one point compactification of the real line.
We extend $<$ relation on $\mathbb R$ to $\hat <$ defined as:
$ x \ \hat{<} \...
- 11.3k
6
votes
1
answer
232
views
Interpretation of $ZFC^-$ in 2nd order Peano arithmetic
Let $Z_2^-$ be the 2nd order Peano arithmetic without the schema of Countable Choice. It has been known, since 1960s at least, that $ZFC^-$ (without the power set) admits an interpretation in $Z_2$ ...
- 2,281
3
votes
1
answer
140
views
Can we always know if an algebraic rule over the reals is preserved over the extended reals or not?
Recall a prior posting titled Is there an effective way to generalize this approach of affinely extending the number line?, and especially the accepted answer given to it. So we are working in $\sf ...
- 11.3k
1
vote
1
answer
213
views
Is there an effective way to generalize this approach of affinely extending the number line?
The general approach here is a follow up of the approach outlined in a prior posting on extending the projectively extended real line. In particular arithmetic operators break down to ternery ...
- 11.3k
-2
votes
1
answer
369
views
Is this extension of the projectively extended real line, consistent?
This posting has been Edited. The edited material shall be noted.
The projectively extended real line $\hat {\mathbb R}= \mathbb R \cup \{\infty\}$ is one system which allows division by zero! Yet it ...
- 11.3k
1
vote
0
answers
117
views
Can this type theory interpret second order arithmetic?
Language: multi-sorted first order logic with equality and membership, where for each natural $t$ there is a set $x^t$ of sort $t$. Equality "$=$" only occurs between variables of the same ...
- 11.3k
32
votes
2
answers
3k
views
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
There are many interpretations of arithmetic in set theory. The
Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor:
$$0=\{\ \}$$
$$1=\{0\}$$
...
- 236k
0
votes
0
answers
152
views
What is the strength of allowing multiple predecessor numbers?
If we have a theory of numbers, pairs of numbers, and sets of those, and axiomatize that the relation $<$ on numbers is both extensional and well founded, then this theory would prove all PA axioms ...
- 11.3k
2
votes
1
answer
147
views
Representation of the equality relation between hereditarily finite sets in weak set theories
Consider General Set Theory ($ \mathsf { GST } $) axiomatized by the following.
Axiom of Extensionality: The sets $ x $ and $ y $ are the same set if they have the same members:
$$ \forall x \forall ...
- 346
5
votes
0
answers
317
views
$\Sigma_n$-complete sets in the Levy hierarchy
Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
- 1,882
11
votes
1
answer
400
views
What is the Turing degree of the monadic theory of the real line?
The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...
- 4,597
16
votes
2
answers
1k
views
How special is first-order $\mathsf{PA}$?
This is a modified version of a question which was asked and bountied at MSE without success.
Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic.
There are various "...
- 21.2k
3
votes
0
answers
191
views
Set theories that are complete modulo finite-order arithmetic
In a previous question, I asked whether there can be effectively axiomatizable set theories (at least as strong as, say, ZF) that are complete modulo first-order arithmetic, to which the answer is no; ...
- 675
1
vote
1
answer
396
views
Complete and consistent first-order theories that contain interesting phenomena
Gödel has shown that a consistent recursively axiomatizable first-order theory that can interpret Robinson arithmetic is incomplete.
I think there is some sentimental value in working with a theory ...
user158636
5
votes
3
answers
1k
views
Are there first-order statements that second order PA proves that first order PA does not?
Are there first-order statements that second order PA proves that first order PA does not? Is this known one way or the other? Could you share an example? (edit: to clarify, by 'second order PA' I don'...
- 117
9
votes
0
answers
325
views
Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?
Assume ZFC. Is there a formula of $\mathcal{L}_\in$ (without parameters) defining a model $\mathcal{M}$ of PA whose domain is a proper class but the complete theory of that model is not definable by ...
16
votes
2
answers
2k
views
Could Kronecker accept a proof of Goodstein's theorem?
A famous result of Goodstein asserts that the Goodstein sequence of integers terminates.
For a precise statement and a short proof, see https://en.wikipedia.org/wiki/Goodstein%27s_theorem.
A well ...
- 28k
3
votes
0
answers
301
views
What does second order set theory give us that is new?
There is a natural analogy between the theories PA and ZFC. See the linked question by Gro-Tsen here.
Peano arithmetic (PA) is a first order approximation to the natural numbers. As is well known, ...
- 18.7k
29
votes
10
answers
4k
views
Defining the standard model of PA so that a space alien could understand
First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
- 18.7k
18
votes
1
answer
3k
views
Existence of a model of ZFC in which the natural numbers are really the natural numbers
I know that, from compactness theorem, one can prove that there are models of first order arithmetic in which there is some "number" which is not a successor of zero, in the sense that it is strictly ...
- 1,514
10
votes
1
answer
541
views
Looking for “Set theory for a small universe” by Ketonen
In the paper Partition theorems for systems of finite subsets of integers, Pudlák and Rödl show a Ramsey-type result. The main feature of this result is that the sizes of sets in such systems are not ...
- 1,124
19
votes
1
answer
747
views
What non-standard model of arithmetic does Hofstadter reference in GEB?
Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
- 1,288
6
votes
1
answer
727
views
What is the consistency strength of this theory?
Language: first-order logic
Primitives: $=, S, \in $ (the first denotes identity, the second denotes “is a successor of”, and the third denotes membership relation).
Axioms: those of identity ...
- 11.3k
1
vote
0
answers
346
views
approaching the border between absolute convergence and divergence of series
Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
- 88
3
votes
0
answers
144
views
A conservativity result of intuitionistic set theory over arithmetic
In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...
- 355
8
votes
0
answers
344
views
What arithmetic is interpretable in Mayberry's Euclidean set theory?
John Mayberry published what he calls a Euclidean set theory in his book The Foundations of Mathematics in the Theory of Sets. It is ZF with the axiom of infinity replaced by an axiom saying "the ...
- 11.1k
8
votes
1
answer
535
views
Is ZFC+(negation of a large cardinal axiom) arithmetically sound?
My knowledge in set theory is very limited, so I apologize if this question is naive or trivial:
Let $A$ to be a large cardinal axiom. $T=ZFC+\neg A$ is a consistent theory. My question is:
Question ...
- 870
1
vote
2
answers
777
views
Can you remove all the extra arithmetic from ZFC (or other theories)?
Let $\mathbb{N}$ be the standard model of the natural numbers. For any statement in the language of arithmetic, we can translate into a statement in the language of set theory by asking if it is true ...
- 6,353
12
votes
2
answers
1k
views
Trouble with models of PA and ZFC
I have a big trouble in my mind, here is my false reasoning:
The Goodstein's theorem is undecidable in (first order) Peano Arithmetic.
There exist a non standard model N of PA where the Goodstein's ...
- 129
2
votes
1
answer
142
views
Does $WKL_0$ plus CON(PA+X) give a binary tree model of PA+X?
In the context of reverse mathematics $WKL_0$ is considered equivalent to Gödel's completeness theorem over $RCA_0$. Does this mean that e.g. $WKL_0$ plus the consistency statement CON(PA+X) gives a ...
- 3,574