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, ...

learn more… | top users | synonyms (1)

3
votes
1answer
210 views

When can you canonically extend an ultrafilter after forcing?

Suppose that $V$ is a model of $\sf ZFC$, and fix some regular $\kappa$, say $\omega_1$ for practical purposes. Let $\cal U$ be an ultrafilter on $\omega_1$ in $V$ which is non-principal and even ...
1
vote
2answers
360 views

Was “arithmetical translation” (coding in the Goedel sense) ever a part of Hilbert's Program?

Was "arithmetical translation" (that is, coding in the Goedel sense) ever a part of Hilbert's Program? I ask this question for several reasons: i) it gives the numerals |, ||, |||,.... an ersatz ...
0
votes
0answers
147 views

Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ? How can we prove the ...
2
votes
2answers
263 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
4
votes
1answer
74 views

Proving moduli of uniform continuity in RCA_0

Simpson's Subsystems of Second Order Arithmetic (pp. 134ff.) uses RCA$_0$ to prove various theorems of analysis for all continuous functions with a suitable modulus of uniform continuity. And he ...
1
vote
0answers
53 views

Fully residually free groups and completion

Let $G$ be a fully residually free group with a finitely generated profinite completion. Is $G$ necessarily finitely generated?
8
votes
2answers
566 views

Did Bishop, Heyting or Brouwer take partial functions seriously?

The partial μ-recursive functions which may or may not be provably total seem to have some direct relation to the initial motivations for intuitionistic mathematics. (Following Kronecker, one ...
4
votes
2answers
294 views

A property of uncountable almost disjoint families

Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge ...
4
votes
0answers
174 views

Theories introduced by a class of forcing notions

The following notion is introduced by Mohammad Golshani. Let $V$ be a model of set theory and let $\mathcal{P}$ be a class consisting of non-trivial forcing notions in $V$. Let $$Th(V, ...
-5
votes
1answer
132 views

New hilbert system and theorem [closed]

Let we have following axioms and modus ponens : $$(A1):(B ⇒ (C ⇒B ))$$ $$(A2):((B ⇒ (C ⇒D )) ⇒ ((B ⇒C ) ⇒ (B ⇒D )))$$ $$(A3):( ( B ⇒C) ⇒(¬C ) ⇒ (¬B ))$$ now can we prove following theorem ? $\vdash ...
4
votes
1answer
295 views

Show that the positive existential theory is undecidable

To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: ...
6
votes
0answers
95 views

Finitely presented algebras with isomorphic semilattices of congruences

Let $\mathbb{T}$ be a finitary algebraic theory. For each $\mathbb{T}$-algebra $A$, let $Q (A)$ be the join semilattice of finitely generated congruences on $A$. There is an evident pushforward ...
3
votes
1answer
237 views

How can the critical point of an elementary embedding be omega_1?

I've seen an example of an elementary embedding such that $\omega_1$ is the critical point. I was wondering what's wrong with the following proof that this cannot be: Let $\phi(x_1,x_2)$ be the ...
2
votes
0answers
110 views

Is a finitely generated residually free group “almost LERF”?

Let $G$ be a finitely generated residually free group. (i.e. for each $1 \neq g \in G$ there exists a homomorphism $\tau \colon G \to F$ such that $F$ is a free group, and $\tau(g) \neq 1$.) ...
19
votes
3answers
641 views

Is being rational decidable?

Given a real number uniquely defined by a finite system of equations and inequalities with rational coefficients involving the standard elementary functions only. Is it decidable whether this number ...
14
votes
1answer
338 views

Joyal's construction of the spectrum of a commutative ring

I am trying to understand bits and pieces of Lawvere's article Continuously Variable Sets; Algebraic Geometry = Geometric Logic. I'm not doing very well. I know this is a lot to ask, but basically, I ...
2
votes
0answers
69 views

A Question on Provability Logic and Co-Necessitation

The provability logic $GL$ has the characteristic axioms: $K\hspace{15pt}\Box(\alpha\rightarrow \beta)\rightarrow(\Box\alpha\rightarrow\Box\beta)$ $L\hspace{15pt}\Box(\Box \alpha\rightarrow ...
3
votes
3answers
233 views

Semantic reflection

Let $\ulcorner \cdot \urcorner$ be a fixed encoding of formulas by numbers, e.g. let $\ulcorner \varphi \urcorner$ denote the Godel number of $\varphi$. Let $T$ be a first-order arithmetic theory, ...
7
votes
0answers
221 views

Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
4
votes
1answer
197 views

What is the right notion of generalized element of a category?

I've been working out how the internal language of a category C extends to taking the category itself as a type. The most obvious way to interpret $X : \mathbf{C}$ is, of course, that $X$ is an ...
18
votes
2answers
540 views

Removing large cardinals from an uncountable transitive model

The usual way of removing large cardinals from a given model of set theory is to cut off the model below the least large cardinal of interest. But this method may have dramatic effects on the external ...
6
votes
2answers
249 views

The role of the index set in the product of uncountably many topological spaces

Let $‎\langle‎ ‎‎X_i,\mathcal{T}_i \rangle_{i\in I}$ be a family of topological spaces. Consider $X=\prod_{i\in I} X_i$ with product topology. Question. Is there a topological property that holds in ...
3
votes
2answers
233 views

Do limit groups satisfy Howson's theorem?

Let $G$ be a limit group, and let $A,B \leq G$ be finitely generated subgroups generating $G$ (i.e. $\langle A \cup B \rangle = G$). Must $A \cap B$ be finitely generated? Recall that a limit ...
2
votes
1answer
218 views

Effectively non-recursiveness of some sets

A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$‎. ‎A set is effectively non-recursive if it is r.e‎. ‎and its ...
10
votes
1answer
198 views

Is there a (first-order) sentence which admits $(\aleph_2,\aleph_0)$ iff a Kurepa tree exists?

In Chang and Keisler's Model Theory I came across the following theorem (Theorem 7.2.13): Theorem There exists a (first-order) sentence $\sigma$ such that for all infinite cardinals $\alpha$, ...
7
votes
1answer
132 views

Consistency Strength of “HC is elementary in V[G]”

Let $P$ be the Levy-collapse of the ordinals, so $P$ is a class forcing notion that makes every ordinal countable. Note that since $P$ is weakly homogeneous, for any formula $\phi(\overline{a})$ ...
5
votes
0answers
130 views

Sacks minimality without choice

The usual argument for the minimality result for Sacks forcing uses choice. Theorem (Sacks): Let $s \subseteq \mathbb S_\kappa$ be generic for the forcing to add a Sacks subset to $\kappa$, where ...
11
votes
1answer
406 views

Is it consistent with ZFC that no nontrivial forcing notion has automatic mutual genericity?

A nontrivial forcing notion $\newcommand\Q{\mathbb{Q}}\Q$ exhibits automatic mutual genericity, if whenever $G,H\subseteq\Q$ are distinct $V$-generic filters (existing, say, in some forcing extension ...
7
votes
2answers
204 views

How to extend Morley's omitting type theorem to uncountable languages?

In his 1965 paper Omitting Classes of Elements (found in The Theory of Models: Proceedings of the 1963 International Symposium at Berkeley, published by North-Holland Publ. Co., Amsterdam (1965)), ...
7
votes
0answers
150 views

$V$ as a $HOD$ of its class generic extension

By an old result of Roguski, The theory of the class $HOD$, any model $V$ of $ZFC$ has a class generic extension $V[G]$ such that $HOD$ of $V[G]$ equals $V$. This result is also stated and generalized ...
9
votes
0answers
223 views

(A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see ...
10
votes
1answer
368 views

Extending an infinite simple group

Maybe the question does not fit here. Yesterday in my logic course, I presented a nice example about an application of model theory to group theory. The example is due to Hodges and as following: For ...
7
votes
0answers
204 views

A strengthening of Chang's conjectures

In the Handbook of Set Theory, Foreman has (essentially) the following proposition (3.9): Suppose $\kappa_n>...>\kappa_0$ and $\lambda_n>...>\lambda_0$ are regular cardinals and ...
2
votes
1answer
194 views

Is Extensionality needed for the incompleteness of very weak set theories?

$ST$ is the weak set theory built upon identity theory and containing the axiom for empty set, the axiom for adjunction and the axiom for extensionality. It is known that $ST$ interprets ...
6
votes
0answers
166 views

PCF conjecture and fixed points of the $\aleph$-function

Recently Moti Gitik refuted Shelah's PCF conjecture, by producing a countable set $a$ of regular cardinals with $|pcf(a)| \geq \aleph_1.$ See his papers Short extenders forcings I and Short ...
-2
votes
1answer
105 views

A question on a presumably admissible/derivable rule for (usual) formal systems [closed]

Suppose formal system $X$ has the rule $\vdash\beta\Rightarrow\hspace{2pt}\vdash\gamma$. Is the rule $\vdash\alpha\wedge\beta\Rightarrow\hspace{2pt}\vdash\alpha\wedge\gamma$ (usually) just admissible ...
12
votes
0answers
171 views

Is the game Hanabi NEXPTIME-complete?

The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards ...
2
votes
0answers
108 views

A question regarding an analogue of the Kleene $T$-predicate for Koepke's ordinal computability

Does Koepke's notion of ordinal computability admit an analogue of the Kleene $T$-predicate? If so, is the existence of such a $T$-predicate independent of $ZFC$? Also, if one assumes the existence ...
13
votes
0answers
139 views

Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where Cells on the tape can hold arbitrary elements of $\mathcal{S}$. The ...
1
vote
0answers
184 views

How may we define a bijection from $\wp(\mathbb{Q})$ to $\mathbb{R}$ in $ZFC$? [closed]

Some expressed difficulty understanding that there are more members in $\mathbb{R}$ than in $\mathbb{Q}$ according to classical set theories because there between all real numbers is a rational ...
10
votes
0answers
154 views

Can we find minimal-diameter metrics without computability?

A beautiful argument by Nabutovsky and Weinberger (see http://math.uchicago.edu/~shmuel/fractal.ps) shows that, if $M$ is any smooth compact manifold of dimension $\ge 5$, then the diameter functional ...
13
votes
2answers
420 views

Logical complexity of algebraically closed fields

One can define fields using a finite list of axioms that quantify over the field itself. However, the obvious way to define algebraically closed fields involves either an infinite list of axioms, or ...
7
votes
3answers
154 views

Ordinal-indexed transitive antichain of sets with urelements

Operate in ZFC. Can we find a function-class $\phi$ whose domain is the class of ordinals such that the following properties hold? If $x \in \phi(\alpha)$, then either $x \in \mathbb{N}$ or there ...
2
votes
0answers
66 views

Kripke semantics for fuzzy logics

I am interested in Fuzzy logic. I have a problem about Gödel Logic, I'm studying Kripke semantics for fuzzy logics and have found the necessary and sufficient conditions on Kripke frames for ...
35
votes
4answers
2k views

Hilbert's (cancelled) 24th problem

Hilbert's 23 problems, ten of which were presented at the 1900 ICM in Paris, are too famous for any mathematician to not know. If one reads the descriptions of the problems in Hilbert's paper, one ...
25
votes
0answers
547 views

Where do uncountable models collapse to?

Suppose $T$ is a complete first-order theory (in an finite, or at worst countable, language). Given any model $\mathcal{M}\models T$ of cardinality $\kappa$, we can ask whether $\mathcal{M}$ can be ...
12
votes
2answers
393 views

Woodin on Posner-Robinson for the hyperjump and sharp

The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ ...
11
votes
1answer
465 views

Can you have many independent reals?

Working in $\sf ZFC$, is it provable, or at least consistent (say, over $L$), that you have $\aleph_1$ forcings, $\Bbb P_\alpha$ such that: $\Bbb P_\alpha$ is c.c.c. $\Bbb P_\alpha$ adds a real ...
3
votes
0answers
383 views

“Nicely” strong measure zero sets

This question is essentially an expanded version of the unanswered half of Two strengthenings of "strong measure zero". A set $X$ of reals is strong measure zero if, for any $f: ...
7
votes
1answer
337 views

Is every ordinal potentially definable?

It is easy to see that, if $V\models\alpha>\omega_1^{CK}$, then $\alpha$ is not recursive in any forcing extension of $V$. The argument goes as follows: The relation "$\Phi_e=r$" is $\Pi^0_2$. ...