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,776 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
6
votes
0
answers
166
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
vote
1
answer
160
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 ...
0
votes
1
answer
203
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), (...
15
votes
1
answer
423
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$ ...
-2
votes
0
answers
137
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 ...
3
votes
0
answers
125
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(...
1
vote
1
answer
215
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$ ...
5
votes
1
answer
346
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: ...
4
votes
1
answer
281
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 ...
17
votes
1
answer
568
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)...
0
votes
1
answer
267
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\...
15
votes
1
answer
742
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-...
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 ...
5
votes
0
answers
76
views
Decision problem for finite (unordered) trees
One of the strongest results on the decidability of theories is Rabin's Tree Theorem. One way to state it is the following: tThe problem of deciding whether a sentence on the monadic second order (MSO)...