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)

1
vote
0answers
25 views

embdedding standard models of PA into nonstandard models [migrated]

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...
-2
votes
0answers
173 views

Proof theory and the generalized Riemann hypothesis [on hold]

Is there a disproof of the following? CONJECTURE: Let $\chi$ be a Dirichlet character modulo $q$. Let $\varepsilon$ be a positive number with $0 < \varepsilon < \frac{1}{2}$. Let $T$ be a ...
10
votes
1answer
487 views

Applications of set theory in physics

In the introduction of the paper "Links between physics and set theory", the following quote of Eris Chric is stated: ...
3
votes
0answers
102 views

A property of the Frechet filter and every ultrafilter

(Joint question with Piotr Szewczak.) Definitions and notation. By filter we mean a filter on $\omega$ containing the cofinite sets at least. For a filter $\mathcal{F}$, let ...
1
vote
1answer
52 views

Injecting premises into two implicational premises connected by a tensor (multiplicative conjunction) in linear logic

I have another question regarding linear logic: I want to get to the proof E, using the premises in (1-4). Is this at all possible? 1: $A$ 2: $C$ 3: $(A\multimap B)\otimes(C\multimap D)$ 4: ...
2
votes
0answers
116 views

Relationship between coherent toposes/coherent logic and coherent sheaves

I've heard it claimed that the adjective "coherent" in logic/topos theory (i.e. coherent logic, coherent toposes, coherent categories) was adopted to fit in with the terminology of coherent sheaves in ...
2
votes
1answer
163 views

Mal'cev “rational equivalence” and model theory

In Universal Algebra, it is possible to say that two presentations denote the "same" kind of algebraic structures, if the two corresponding varieties are "rationally equivalent" (Mal'cev 1958). In ...
-3
votes
0answers
108 views

Interview Math question [closed]

Fill in the blank: Find the next number of the sequence: 16,47,64,81,121,? This is an interview math question of finding the proper number, I can't figure it out, could someone help?
4
votes
1answer
262 views

Does PA+Con(PA) entail the existence of non-standard models of PA?

Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$? Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...
4
votes
1answer
138 views

Generalizing a result of Kreisel on $\omega$-consistency

In (reference)The following result is attributed to Kreisel: Lemma1(Kreisel) If $T$ is an $\omega$-consistent theory in the language of arithmetic and $\pi$ is a true $\Pi_1$ sentence, then $T+\pi$ ...
13
votes
4answers
1k views

Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?

In a conversation where it came up that the Pythagoreans probably found an enumeration of the rational numbers I erroneously remarked that Georg Cantor found a natural bijection from $\mathbb{N}$ to ...
2
votes
2answers
115 views

Is there a good list of nomenclature for modal axioms?

I would like to see what names that has been suggested for useful modal axioms. By name here I mean some abbreviation such as $T$, $K$, $4$, $.2$, $E$ and so on. In particular I am interested in ...
8
votes
2answers
280 views

For a partition of $\mathbb{R}$ into countably infinite sets, must there be an almost-disjoint family of $2^{\frak c}$ many selectors?

My question arises from a construction I gave in my recent answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using the ...
0
votes
0answers
57 views

How create counterexample for some set in Complexity Theory? [closed]

We know from Martin Davis's book, $K$ is a Halting Set Problem as $K=\{e \mid e \in W_e\}$. $W_e$ is the set of inputs for which the program encoded by $e$ halts. I read in the book that written ...
1
vote
0answers
105 views

This modal logic semantics is not S5, but is it something else well-known?

The short form of the question is this: Is there a model of modal propositional calculus that gives the modal operators the meanings ...
2
votes
1answer
80 views

Representable cylindric algebras and correspondence with first-order models

The class $\textsf{Cs}_{\omega}^{reg}\cap \textsf{Lf}_{\omega}$ of locally finite and regular cylindric set algebras (of dimension $\omega$) can be seen as the algebraic counterpart of first-order ...
7
votes
0answers
126 views

Decidabilty of the Hilbert lattice and quantum logic

What is known about the decidability of (first-order formulas in) the structure $(\mathcal{L}(H),\leq)$, where $\mathcal{L}(H)$ is the collection of all closed linear subspaces of a (separable) ...
8
votes
1answer
319 views

If $\kappa$ is weakly inaccessible and $A\subset\kappa$, can $L[A]$ violate $\kappa^{\lt\kappa}=\kappa$?

In some current work, my co-authors and I had wanted in a certain argument to appeal to $\kappa^{\lt\kappa}=\kappa$ in $L[A]$, in a situation where $A\subset\kappa$ and $\kappa$ was weakly ...
4
votes
1answer
303 views

Inaccessible cardinal and $\Sigma_1$ reflection

A theorem of A. Levy says that, if $\kappa$ is an inaccessible cardinal, then $V_\kappa\prec_{\Sigma_1}V$ namely $V_\kappa$ is an elementary submodel when considering only $\Sigma_1$ formulas. Where ...
3
votes
1answer
185 views

Hamkins infinite time Turing machines: dovetailing ordinal time

It is claimed in the Hamkins and Lewis founding article "Infinite time Turing machines" (proof of the gap existence theorem 3.4) that for $\omega$ steps of a computation of a machine performing a ...
2
votes
0answers
271 views

A query on how to climb inaccessibles in £

I am investigating to what extent extensions of the librationist property or set theory £ may support relative inaccessible sets; see Librationist Closures of the Paradoxes and Elements of ...
1
vote
0answers
111 views

Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before. For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...
14
votes
2answers
491 views

Scott-Solovay unpublished paper on ``Boolean valued models of set theory''

I have read some papers from 1970$^{th}$, and in some of them, the paper of Scott and Solovay on ``Boolean valued models of set theory'' is given as a main reference, with many references to the ...
3
votes
3answers
820 views

Reverse Skolem's paradox

By using the Löwenheim–Skolem theorem & Mostowski collapse, in every model $V$ of $ZF+Con(ZF)$ there is a countable transitive set $M$ such that $(M,\in_M) \models ZF$. Is the following "converse" ...
7
votes
3answers
326 views

Decision problem on triviality of intersection of two subgroups

What is known about the following decision problem? Given two finite sets in a finitely generated group G, decide whether the subgroups generated by them have trivial intersection. Is this problem ...
9
votes
1answer
322 views

History of Tarski's problems on free groups

As is known, Tarski posed his questions about first-order theories of non-abelian free groups around 1945. However, the questions were not published in his papers or books. What is the original ...
8
votes
3answers
273 views

Model-theoretic accounts of feasibility in bounded arithmetic and related systems

Various weak theories of arithmetic have been partially motivated by a concern with numbers (or functions/proofs) that are feasible. This concern is sometimes connected to an interest in strictly ...
12
votes
6answers
734 views

Application of Fraïssé construction in set theory

As you know Fraïssé limit construction and its generalization, Hrushovski's construction, have many applications in model theory to build models with interesting property. Now I would like to know ...
6
votes
3answers
472 views

Category of Gödel Codings? [Reference Request]

Consider computation with the integers $\mathbb{Q}$. The traditional theory of recursive functions on $\mathbb{N}$ applies to $\mathbb{Q}$ by the identification of $\frac{a}{b} \in \mathbb{Q}$ with ...
5
votes
0answers
230 views

Quasi-disjoint subsets of an infinite set and $\neg \mathsf{AC}$

Is it consistent with $\mathsf{ZF}$ (without $\mathsf{AC}$) that there is an infinite set $X$ and a subset $S\subseteq\mathcal P(X)$ of the same cardinality as $\mathcal P(X)$ with the property that ...
12
votes
2answers
1k views

Do the real numbers “know” that they are countable in a larger model?

(This was first posted to math.stackexchange but had no answers there after several days): Let ${\mathbb R}$ be the set of real numbers in whatever is your favorite model of $ZFC$. Then (by Levy ...
2
votes
0answers
61 views

Potentiality classes and Borel reductions

In a 1998 paper by Hjorth, Kechris, and Louveau, there was a definition given of a "potentiality class." That is, given an invariant equivalence relation $E$ on a standard Borel space $X$, we say $E$ ...
5
votes
1answer
163 views

Uncountably categorical theories which are interpretable in a strongly minimal

Definition: Let $\lambda$ be a cardinal. An $\mathcal{L}$-theory $T$ is called $\lambda$-categorical whenever every two models of $T$ of cardinality $\lambda$ are isomorphic. Definition: An ...
6
votes
1answer
427 views

Adding sets not containing arithmetic progressions of length three by forcing

Consider the following forcing notion: conditions in $\mathbb{P}$ are pairs $(s, N),$ where: 1) $s\in 2^{<\omega}$, 2) $N\in \mathbb{N}$, 3) (by identifying $s$ with a subset of $lh(s)$) $s$ ...
6
votes
0answers
176 views

Tree property and singular strong limit cardinals

I heard that the following theorem is proved recently by Foreman-Magidor, which answers a famous old open question: Theorem. It is consistent, relative to the existence of large cardinals, that ...
9
votes
2answers
451 views

Non-Forcing and Independence

I asked this question about two weeks ago on MSE and haven't gotten an answer, so I thought I would post the question here. Do there exists sentences which are independent of ZFC, cannot be shown to ...
0
votes
1answer
92 views

Completeness of a set of propositional formulas [closed]

A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas ...
11
votes
1answer
312 views

Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula. Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)? If not, why?
1
vote
1answer
226 views

Confusion with proof about a fact $\mathbb{P}$-name [closed]

Let $\mathbb{P}$ be poset. Let $B$ be a set. We say that a $\mathbb{P}$-name $\dot{b}$ is a nice name for member of $B$ if there is a maximal antichain $A\subseteq\mathbb{P}$ and a function ...
6
votes
1answer
112 views

Chains of forking extension in stable theories

Let $T$ be an stable theory. Further we work in the monster model of $T^{eq}$. We say that a chain of types of the form $$tp(a_1/A_1)\subset tp(a_2/A_2) ... \subset tp(a_n/A_n)$$ is a forking chain ...
3
votes
1answer
138 views

A question on many-one reducibility

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. For each $x\in\mathbb{N}$, let $W_x$ the domain of $\phi_x$, and let $K=\{x\in\mathbb{N}:W_x\neq\emptyset\}$. Is there a ...
6
votes
1answer
372 views

Alternate proof of Morley's theorem?

I'm trying to understand the result given in the first box at slide 45 of this talk. Specifically: 1) What is the source cited? I have not been able to find any article by Keisler, Chudnovsky and/or ...
5
votes
2answers
321 views
+50

Primitive Recursive Arithmetic via Universal Algebra

From the wikipedia article on Primitive Recursive Arithmetic (see http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic): "Primitive recursive arithmetic, or PRA, is a quantifier-free ...
7
votes
1answer
220 views

Is $ACA_0$ + `True Arithmetic exists' interpretable in $ACA$?

Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a ...
6
votes
1answer
274 views

Axiom of choice and the equality between second-order constructible universe and HOD

I try to prove $L_{SO}=\mathrm{HOD}$, where $L_{SO}$ is second-order constructible universe which has similar definition with $L$ but it uses second-order definability rather than the first-order ...
4
votes
1answer
187 views

Explicit bounds for transfer results in algebraic geometry

Assume you have an ideal $I\subseteq\mathbb{Z}[X_1,\ldots,X_n]$ of the polynomial ring in $n$ variables over the integers. For any field $\Bbbk$, I can consider the ideal ...
3
votes
1answer
216 views

Was $\Sigma x$ used as quantifier?

Kurt Gödel in 1931 used $x\Pi a$ where we in contemporary notation would use $(\forall x) A$ or $(x)A$, and $Ex a$ where we would use $(\exists x) A$. I believe that I remember that $\Sigma xA$ has ...
0
votes
0answers
116 views

Reference Request: Category of explicit maps between primitive recursive sets?

[Edited] Let $\mathsf{PR}$ be the category defined as follows: Choose a specific presentation of Primitive Recursive Arithmetic, that is, with a specific set of terms for primitive recursive ...
4
votes
1answer
132 views

presaturated ideals

In this paper, Gitik and Shelah make the following claim (part of Proposition 1.5): Claim (Gitik-Shelah): Suppose $\kappa < \lambda$ are regular, $2^\lambda = \lambda^+$, and $D$ is a normal ...
1
vote
0answers
155 views

Property theories

Property theory is, as I have understood it, first of all characterized by an attempt to approach naive comprehension type-freely and without committing to extensionality. There is e.g. the work of ...