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)

0
votes
1answer
151 views

Refutation of $A \land \lnot\lnot\lnot A$ by resolution [closed]

$ A \land \lnot\lnot\lnot A $ this is a very simple example. Resolution is refutation complete. So it should be able to refute this formula. However, I don't see how would it do that without using ...
3
votes
1answer
94 views

Is quasivariety generated by all perfect graphs finitely axiomatizable?

Fix logic $L$ with equality and a binary relation symbol $E$. The class of graphs can be identified with the class of models of the universal first-order Horn $L$-sentences $\forall x,y\; E(x,y) ...
4
votes
1answer
173 views

Countable model theory for $\omega$-stable theories?

This is a bit of a fishing expedition, because I'm not sure what I'm looking for. Very vaguely stated, here's the driving question: What conditions on an $\omega$-stable theory make the class of ...
5
votes
1answer
301 views

How do we know if Vaught's Conjecture is Absolute?

Please note that this might be some confusion on my part about the work surrounding Vaught's conjecture. First of all, Vaught Conjecture states that if a first-order complete theory $T$ in a ...
4
votes
1answer
282 views

Question about “Coding the universe”

The following is a result which I know as a weak form of Jensen's coding lemma$^*$ (first published in the book "Coding the universe"; also see http://www.jstor.org/stable/2273986): For any class ...
8
votes
1answer
127 views

Strongly compact cardinal with bad covering properties

This is a continuation of the question covering properties of strongly compact embedding. Recall that a cardinal $\kappa$ is $\nu$-strongly compact cardinal if there is an elementary embedding ...
12
votes
1answer
363 views

Main Gap Phenomenon

Shelah's Main Gap Theorem states that for all first-order, complete theories, T, in a countable language, we have that either $$I(T,\aleph_\alpha)=2^{\aleph_\alpha}$$ or ...
16
votes
0answers
414 views

If all reals are generic, is the set of reals generic?

Let $W\subseteq V$ be two models of $\sf ZFC$ with the same ordinals. Is the following situation consistent: For every $x\in\Bbb R^V$ there is some $P_x\in W$ such that for some $G\subseteq P_x$ ...
10
votes
1answer
618 views

Harrington's unpublished note “The constructible reals can be anything”

Around 1974, Leo Harringto wrote an unpublished note entitled "The constructible reals can be anything", in which he proved that it is consistent that being $\Delta^1_n$ is the same as being ...
6
votes
2answers
607 views

Is there one binary operation foundational for set theory?

The membership relationship "$\epsilon$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\epsilon$". Naturally, the question arises ...
4
votes
1answer
650 views

solvable word problem without algorithm

Let $G$ be a finitely generated group. I wonder if there are examples where: 1) The word problem is known to be solvable in $G$ but there is no algorithm known. 2) The word problem is known to be ...
8
votes
2answers
243 views

Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?

A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
6
votes
1answer
235 views

Does V=L imply transitive containment over, say, Z?

In Zermelo set theory, the axiom of constructibility V=L seems to imply every set has a transitive closure. But does that argument have to assume transitive closure in the first place, to get an ...
1
vote
1answer
186 views

Is anyone talking about partial interpretations of theories? (Edited)

Consider the concept of a module. This can be understood a multisorted algebraic theory $\mathsf{Mod}$ on two sorts, a scalarsort $S$ and a vectorsort $V$. An interpretation of $\mathsf{Mod}$ in ...
7
votes
1answer
292 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 ...
14
votes
1answer
958 views

How much of GCH do we need to guarantee well-ordering of continuum?

It's well known that, if GCH holds, then every cardinal can be well-ordered. However, I'm sure we don't need full power of GCH to prove it for specific cardinal, e.g. continuum. I have been wondering, ...
4
votes
2answers
910 views

Meta$^{n{-}th}$ mathematics [duplicate]

Metamathematics has a reasonably clear connotation, enough to have a Wikipedia page, with Gödel, Tarski, and Turing playing leading roles; Kleene's book (Introduction to Metamathematics (Amazon ...
11
votes
1answer
314 views

What is the large cardinal strength of the assertion that every $\kappa$-complete filter on $\kappa$ extends to a $\kappa$-complete ultrafilter?

It is well-known that an uncountable regular cardinal $\kappa$ is strongly compact if and only if every $\kappa$-complete filter on any set extends to a $\kappa$-complete ultrafilter on that set. The ...
5
votes
1answer
237 views

If questions are formalized as ideals of a boolean algebra, what kind of algebra of questions appears from Stone representation theorem?

Affirmative propositions make up a Boolean algebra, and Boolean algebras became part of classical algebra for over one century ago - in this sense they are "simple". But I did not encounter in ...
4
votes
1answer
193 views

Elementary chains of $\aleph_1$-saturated models

If $X$ and $Y$ are two sets linearily ordered by $<$, $X$ is called cofinal in $Y$ if $X \subseteq Y$ and and for every $y \in Y$, there is a $x \in X$ with $y < x$. If $M$ is some model and ...
2
votes
1answer
92 views

A question on Carnap's modal semantics on the basis of Cochiarelli's primary semantics

I believe I learned that Carnap's state description semantics for propositional modal logic suffered from validating $\lozenge p$ for all atomic variables p. Re-reading Nino Cochiarelli's primary ...
6
votes
0answers
203 views

Does Sageev's result need an inaccessible?

In 1981, building on work by Ellentuck in 1974, Sageev showed ("A model of ZF + there exists an inaccessible, in which the Dedekind cardinals constitute a natural non-standard model of arithmetic," ...
4
votes
1answer
260 views

What axioms (other than choice) have a taming effect on the ordering of cardinalities?

Axiom of choice arranges all cardinalities into a well-ordered chain but without it their ordering can be wild in general ZF models, e.g. two cardinalities may not even have inf or sup. However, ...
1
vote
2answers
231 views

Valid statement in submodel? (Consistency lemma in Cohen's CH book)

In Paul Cohen's Set Theory and the Continuum Hypothesis (Page 71) there is a lemma with the assumption that $\exists x\, P(x)$. The ''proof'' there, uses the following argument: Intuitively the ...
0
votes
0answers
96 views

How to prove a Lefschetzesque principle for relative homology and absolute homology

Here is my conjecture: If H is some homology theory from some abelian category A to some abelian category B, E is the class of all epimorphism in A, E' is some closed class of epimorphisms in A and ...
10
votes
1answer
458 views

Does Turing determinacy imply full determinacy?

The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined. In "Turing ...
4
votes
1answer
174 views

The number of countable models [duplicate]

Let $\mathcal{L}$ be a countable first order language. For a natural number n, can we find a complete $\mathcal{L}$-Theory $T$ which has exactly n non-isomorphic countable models ?
3
votes
0answers
92 views

Is every union-closed family of set the set of solutions of some co-HORNSAT formula?

Related to the Union-closed sets conjecture. Let $\phi$ be a co-HORNSAT on variables $x_1 \ldots x_n$ in CNF format. This means in every close at most one literal is negative. The solutions of ...
9
votes
2answers
337 views

When is $A$ “$L$-ish” whenever $B$ is “$L$-ish”?

My question is about a kind of relative constructibility in set theory. Fix a countable transitive model $W\models ZFC$ which is much bigger than $L^W$. There is a natural way within $W$ to compare ...
12
votes
1answer
408 views

Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?

Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
10
votes
1answer
316 views

Elements of the method of forcing in some papers of N. N. Luzin

In the paper Eléments de la méthode de forcing dans quelques travaux de N. N. Lousin. (French) [Elements of the method of forcing in some papers of N. N. Luzin] Amphora, 469–479, Birkhäuser, ...
10
votes
1answer
416 views

Higher recursion theory and reverse mathematics: What is to $\Pi^1_1-CA_0$ as $RCA_0$ is to $ACA_0$?

There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" - indeed, this is the starting point of metarecursion theory, and $\alpha$-recursion theory in ...
7
votes
1answer
216 views

Stationary sets in HOD

My questions concern the following quote from “The HOD Dichotomy”, page 8. "… notice that $\ cof(\omega)\cap\lambda$ belongs to $HOD$ even though it might mean something else there. Also, ...
7
votes
1answer
367 views

On Consistency of an Existence

Let $\omega \leq \kappa <2^{\omega}$ , $\omega \leq\lambda \leq \kappa$ and $D(\kappa, \lambda)$ be the statement: For all $ \mathfrak{B} \subseteq \mathbf{P}(\omega)$ with ...
3
votes
1answer
327 views

“the” random permutation

I recently looked at Permutations on the random permutation which seems to talk about the notion of random permutuation as a notion from logic rather than probability. The random permutation is ...
19
votes
2answers
1k views

Is the Invariant Subspace Problem arithmetic?

Invariant Subspace Conjecture: A bounded operator on a separable Hilbert space has a non-trivial closed invariant subspace. Can this conjecture be reformulated as an arithmetic statement, that is, ...
1
vote
0answers
83 views

Interesting fragments of first-order logic induced by sorting?

In first approximation, modal logic (I'm using the term loosely) can be understood as an interesting fragment of first-order logic (for simplicity I ignore e.g. how modal logic relates to ...
6
votes
2answers
183 views

Models of PRA/EFA with induction on $X$ but not $\omega^X$

As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...
7
votes
0answers
190 views

Co-Heyting Valued Models of Paraconsistent Set Theory

I've been trying to do some forcing arguments in intuitionistic ZF using Heyting valued models where the Heyting algebra I'm using is actually a bi-Heyting algebra (both a Heyting algebra and a ...
12
votes
2answers
319 views

Producing no non-constructible reals

The following is stated without proof in Shelah's book "Cardinal arithmetic" (page 276), and is attributed to Uri Abraham: Suppose that $L[A], L[B]$ have no non-constructible reals and that ...
2
votes
2answers
192 views

What do we call functions that behave like predicate symbols?

Assume a metatheory that supports lambda-abstraction, and an object language that is merely first-order. Now let $\varphi$ denote a formula in the object language with one free variable $x$. Then we ...
2
votes
1answer
217 views

Partial interpretation of an iteration

Suppose that $\langle\mathbb{P_\alpha,\dot Q_\beta}\mid \beta<\delta,\alpha\leq\delta\rangle$ is a system of iterated forcing. Let $\dot a$ be a name in $\mathbb P_\delta$, and let $G_\alpha$ be a ...
1
vote
1answer
123 views

Free monoids and full transformation monoids

I asked this question on math stack exchange, but I didn't get any responses. So, now I am motivated to ask it here. Is the class of free monoids first order axiomatizable? And what about the class of ...
6
votes
1answer
308 views

Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
2
votes
3answers
769 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
6
votes
1answer
229 views

Characterization of intermediate submodels of generic extensions

Question 1: Suppose that $V[G]$ is a set generic extension of $V$ by some forcing notion $P\in V,$ and suppose that $W$ is a model of $ZFC, V \subset W \subset V[G].$ Can we find a forcing notion ...
3
votes
0answers
326 views

Topological proof of a result in Logic

I proved the result below using logic. My questions: Can this theorem be proved by purely topological means? Do you know any theorems that either can be used to prove the same result, or which give ...
10
votes
2answers
870 views

Is there any research on set theory without extensionality axiom?

In practice (say, in computer science), collections with many "labels" ("identities"), or collections which occur in many copies, are more frequently used than sets. Such collections do not satisfy ...
2
votes
1answer
488 views

Is this system incomplete?

Let $\mathbf{SBM}$ be the normal modal logic system defined as $\mathbf{T}$ plus the following two axioms: $$\mathrm{SB}: \Box(\Diamond p \rightarrow p)\rightarrow (p \rightarrow \Box p)$$ ...
4
votes
1answer
88 views

Counterexample for closedness under union of $\prec_{\infty,\kappa}$ chains

Assume $\kappa$ is uncountable and $\phi$ is an $L_{\infty,\kappa}$ sentence. Let $K$ be the collection of models of $\phi$ partially ordered by $\prec_{\infty,\kappa}$. It is well-known that $K$ is ...