All Questions
Tagged with set-theory theories-of-arithmetic
79 questions
43
votes
1
answer
2k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
- 32.5k
42
votes
7
answers
3k
views
How would one even begin to try to prove that a simple number-theoretic statement is undecidable?
This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...
- 29k
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
30
votes
2
answers
3k
views
Even XOR Odd Infinities?
Modular Arithmetic (MA) has the same axioms as first order Peano Arithmetic (PA) except $\forall x (Sx \ne 0)$ is replaced with $\exists x(Sx = 0)$.
(http://en.wikipedia.org/wiki/Peano_axioms#First-...
- 687
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
27
votes
5
answers
4k
views
What is induction up to $\varepsilon_0$?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
- 156k
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 236k
21
votes
5
answers
2k
views
Alternative Arithmetics
Although, beyond any doubts, $ZFC$ is by and large the predominantly accepted theory of sets, there have been a few attempt to establish some serious competitors in town.
I just quote two of them (...
- 7,853
19
votes
3
answers
2k
views
Is platonism regarding arithmetic consistent with the multiverse view in set theory?
A "truth" platonist for arithmetic believes, given a statement in the language of arithmetic, that the problem whether the statement is true has a definite answer.
Prof. Hamkins has argued for a ...
- 261
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
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
18
votes
3
answers
2k
views
Is Robinson Arithmetic biinterpretable with some theory in LST?
Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
- 3,267
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
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 "...
- 20.5k
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
14
votes
4
answers
1k
views
Boolean Valued Models of PA
O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...
- 631
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
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
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}\...
- 20.5k
11
votes
1
answer
2k
views
Uncountable nonstandard models of PA
Standard techniques (no pun intended) can be used to show that countable nonstandard models of Peano Arithmetic are order isomorphic to $\mathbb{N} + \mathbb{Z} \cdot \mathbb{Q}$. Once we have used ...
- 2,762
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
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
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
10
votes
1
answer
761
views
Forcing, cuts, and Dedekind-finite cardinalities
Tl;dr version: there are two natural classes of cuts in the nonstandard model of arithmetic consisting of the Dedekind-finite sets (if, in fact, they constitute such a model); both these classes are ...
- 20.5k
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
- 1,465
9
votes
1
answer
873
views
Is there any set theory $T$ such that $T$ plus true arithmetic is complete with respect to statements in set theory?
Is there an effective set theory $T$ such that $T + $$TA$ is consistient and complete. It should at least prove all theorems of $ZF$ true, so that it is a "standard" set theory. In particular, the ...
- 6,353
9
votes
1
answer
580
views
Interpreting Robinson arithmetic in a very weak set theory
It is known that adjunctive set theory interprets Robinson arithmetic, and that extensionality is not needed for that. (Montagna and Mancini, "A minimal predicative set theory", Notre Dame Journal of ...
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 ...
8
votes
2
answers
2k
views
Axiom to exclude nonstandard natural numbers
In Peano Arithmetic, the induction axiom states that there is no proper subset of the natural numbers that contains 0 and is closed under the successor function. This is intended to rule out the ...
- 295
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
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
0
answers
1k
views
What's Reeb's take on naive integers?
Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
- 16.6k
7
votes
1
answer
198
views
A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$
The question has relevance for constructing Scott sets with certain extra desirable properties.
Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...
- 2,240
6
votes
3
answers
1k
views
Set theory inside arithmetics via the Ackermann yoga
Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent ...
- 7,853
6
votes
1
answer
382
views
Formal systems needed to formalize relative independence results
We know that Con(ZF) implies Con(ZFC+GCH), Con(ZF+neg(AC)) and Con(ZFC+neg(CH)). But what are some weak theories in which these relative independence results are provable? In particular, are they ...
- 4,985
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
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
6
votes
1
answer
209
views
Is $PRA$ + $TI({\epsilon_0})$ mutually interpretable with some theory in the language of set theory?
As is well known, the following theory is equiconsistent with $PA$:
$ZFC$ with the axiom of infinity replaced by its negation.
Since this theory is equiconsistent with $PA$, it would seem ...
- 6,132
6
votes
1
answer
986
views
Nonstandard models of PA of large cardinal size
It is easy to overlook the fact that the existence of a given large cardinal provides us with a true arithmetical statement that would otherwise be false if the large cardinal notion were not ...
- 2,762
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
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
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
5
votes
1
answer
483
views
Extensions of the Ackermann interpretation to nonstandard theories of arithmetic
In their paper, " On Interpretations of Arithmetic and Set Theory" (Notre Dame Journal of Formal Logic, Vol. 8, No. 4 (2007), pp. 497-510) in section 7, "Fragments of Arithmetic and Set ...
- 6,132
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
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
3
votes
3
answers
2k
views
"Interesting" properties of sets of natural numbers
On Wikipedia, there is a list of properties of sets of reals, which are in some sense "interesting": just have a look.
I could not find a comparable list of properties of sets of natural numbers (...
3
votes
2
answers
624
views
Models of the natural numbers in ultrapowers in the universe.
Our question arises from wondering about the systems of natural numbers in models ZFC + Con(ZFC) and ZFC + $\neg$Con(ZFC). In thinking of the systems of natural numbers of these models, we came to ...
user10290
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
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
3
votes
2
answers
993
views
Neither Even Nor Odd Natural Numbers
Modular arithmetic (MA) has the same axioms as first order Peano arithmetic (PA) except $\forall x(Sx \neq 0)$ is replaced with $\exists x(Sx=0)$. In Even XOR Odd Infinities? I asked if this statement ...
- 687