Questions tagged [lo.logic]
first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, theories of truth, truth revision, consistency.
5,777 questions
1
vote
1
answer
390
views
Why Zermelo postulated the existence of a set with no finite limit to the ranks of its elements?
The original Zermelo set theory explicitly allowed for urelements.
What was the reason that led Zermelo to formulate the Axiom of Infinity in terms of the existence of a set of the kind that has an ...
- 13.1k
8
votes
0
answers
195
views
What is the strength of projective determinacy?
Consider the following theories:
$T_1$: $\mathsf{ZFC+PD}$ where $\mathsf{PD}$ is stated as a schema.
$T_2$: $\mathsf{ZFC+PD}$ where $\mathsf{PD}$ is a single sentence in the language of set theory.
$...
- 1,519
1
vote
1
answer
166
views
Is the product of "non-coding" forcings also "non-coding"?
Say that a forcing notion $\mathbb{P}$ is slow iff there is some $f:\mathbb{R}\rightarrow\mathbb{R}$ (in $V$) such that for every $\mathbb{P}$-name for a real, $\nu$, we have $\Vdash_\mathbb{P}\exists ...
- 19.5k
0
votes
1
answer
211
views
General truth functions on a topos
I was reading Topoi from Goldblat and noted that to calculate the disjunction of the internal logic of a category Set, we have to construct a characteristic function of the set:
$$A = \{(1,1), (1,0), (...
- 197
15
votes
1
answer
444
views
What can be computed without collapsing $\omega_1$
Below work in $\mathsf{ZFC+CH}$ for simplicity.
Say that a (set) forcing notion $\mathbb{P}$ captures a map $f:\mathbb{R}\rightarrow\mathbb{R}$ iff there is some $\mathbb{P}$-name for a real $\nu$ ...
- 19.5k
-2
votes
0
answers
138
views
Is it possible that the Goldbach's conjecture or the twin prime conjecture be undecidable? [duplicate]
There are many famous unsolved problems in number theory that can be formulated by basic concepts. Two examples are
Goldbach's conjecture:
Every even natural number greater than 2 is the sum of two ...
4
votes
0
answers
127
views
Characterize nonzero integers via a polynomial in two variables
In a paper published in 1985, Shih-Ping Tung observed that an integer $m$ is nonzero if and only if $m=(2x+1)(3y+1)$ for some $x,y\in\mathbb Z$. In fact, we can write a nonzero integer $m$ as
$\pm3^a(...
- 18.1k
2
votes
1
answer
220
views
Do we have ${\frak b} \leq {\frak s}$ in ZFC?
Let ${}^\omega\omega$ denote the set of functions $f:\omega\to \omega$. For $f, g \in {}^\omega\omega$ we define
$f\leq^* g$ if there is $N\in\omega$ such that $f(n)\leq g(n)$ for all $n\in \omega$ ...
- 54.1k
6
votes
1
answer
348
views
Higher analogues of Gandy basis theorem
For $n\in\omega$ and $x$ a real let $C_n^x$ be the canonical $\Pi^1_n(x)$-complete set. E.g. $C_1^x=\mathcal{O}^x$, etc. I recall seeing long ago the fact that, assuming large cardinals (precisely: ...
- 19.5k
5
votes
1
answer
283
views
Are the powers of a set with the Baire Property in a Polish group a set with the Baire Property?
Let $G$ be a Polish group and let $A\subseteq G$ be a subset with the Baire Property. Does it follow that for any $n\in \mathbb{N}$, the power $A^{n}$ also has the Baire Property?
Of course, if $A$ is ...
1
vote
0
answers
170
views
Formalizing the Completeness Theorem given languages of infinite cardinality
I am reading Kunen's books on set theory and logic. In his approach, the metatheory is finitistic (which can be approximated in PRA).
This implies that in the finitistic metatheory, one can do formal ...
- 235
17
votes
1
answer
582
views
The strength of representing open sets
Is the following (second-order) formula schema provable in ATR$_0$?
Let $\varphi$ be an arithmetical formula satisfying
For all $x, y\in \mathbb{R}$,
we have that $x=_\mathbb{R}y$ implies $\varphi(x)...
- 4,712
0
votes
1
answer
269
views
Type defined by quantifying another type
The following material is quoted from A Crèche Course in Model Theory by Domenico Zambella, Section 15.3.
$\mathcal{U}$ is how we denote the Monster model.
For every $a\in\mathcal{U}^{x}$ and $b\in\...
- 19
15
votes
1
answer
744
views
Is 0# still unique in ZFC without powerset?
Working in $ZFC$, the statement "$0^\sharp$ exists" is often liberally taken to be one of many known equivalent statements.
However, working in $Z_2$ or $ZFC^-$ (with collection, well-...
- 397
21
votes
4
answers
2k
views
Why and how do (classical) reverse mathematics and intuitionistic reverse mathematics relate?
Broadly speaking, the idea of “reverse mathematics” is to find equivalents to various standard mathematical statements over a weak base theory, in order to gauge the strength of theories (sets of ...
- 38.8k
