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)

4
votes
1answer
191 views

Set-theoretic tautologies

Let us consider unquantifed formulas of a set theory (for example, NBG), more precisely, the formulas, constructed from variables and the constants $\emptyset, V$ (the empty set and the class of all ...
0
votes
1answer
62 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 ...
0
votes
1answer
81 views

Preserving Predimension Functions under Functional Convergences

Definition 1. If ‎$‎‎‎\mathcal{L}‎$ ‎is a‎ ‎countable relational ‎language, ‎a ‎predimension ‎class ‎‎‎‎‎$‎C‎$ is a class ‎of $‎‎\mathcal{L}$-structures with ‎the ‎following ‎properties:‎ ‎C1: ...
0
votes
1answer
128 views

Refutation of $A \land \lnot\lnot\lnot A$ by resolution [on hold]

$ 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 ...
0
votes
0answers
30 views

Is the pseudomenon a statement? [migrated]

I'm asking this because I'm teaching a class on paradoxes for kids, and I realized I have no idea what the answer to this question is. It is a research question in the pedagogical sense, I suppose. ...
2
votes
1answer
67 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) ...
2
votes
0answers
61 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 ...
8
votes
1answer
269 views

Canonical model for $\neg\mathsf{CH}$ and $\Omega$-logic

Recently I found this book by Woodin. In the introduction of it the author writes the following: The main result of this book is the identification of a canonical model in which the Continuum ...
4
votes
1answer
214 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 ...
8
votes
0answers
176 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 ...
4
votes
1answer
240 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 ...
7
votes
1answer
107 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 ...
15
votes
0answers
345 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
373 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 ...
7
votes
2answers
178 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 ...
7
votes
2answers
479 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 ...
70
votes
9answers
11k views

Solutions to the Continuum Hypothesis

Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? Completion of ZFC ) Background The Continuum Hypothesis (CH) posed by Cantor in 1890 asserts that $ ...
14
votes
2answers
825 views

Decomposing $\mathbf{\Pi}^1_1$ sets into closed sets

It is well known that every $\mathbf{\Pi}^1_1$-set is a union of $\aleph_1$-many Borel sets. I wonder whether it can be improved under certain reasonable set theory axioms assumption. For example, ...
4
votes
1answer
571 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 ...
22
votes
7answers
2k views

What is the general opinion on the Generalized Continuum Hypothesis?

I'm community wikiing this, since although I don't want it to be a discussion thread, I don't think that there is really a right answer to this. From what I've seen, model theorists and logicians ...
6
votes
1answer
208 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 ...
31
votes
5answers
2k views

Does “compact iff projections are closed” require some form of choice?

There are many equivalent ways of defining the notion of compact space, but some require some kind of choice principle to prove their equivalence. For example, a classical result is that for $X$ to be ...
1
vote
1answer
182 views

Normal form in second-order logic

In a first-order logic, L, it is possible to transform a sentence, S, containing variables into a sentence S' in so-called 'clause form' - i.e. with a matrix in conjunctive normal form and a prefix ...
1
vote
1answer
174 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 ...
8
votes
3answers
593 views

What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
13
votes
1answer
835 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, ...
7
votes
1answer
179 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 ...
5
votes
1answer
354 views

Comparability implies well-orderability?

I am trying to prove a small proposition that got me completely stumped, and I cannot find a single counterexample. (ZF) Suppose that $E$ is such that for every $A\subseteq\mathcal P(E)$ either ...
35
votes
1answer
1k views

When does $A^A=2^A$ without the axiom of choice?

Assuming the axiom of choice the following argument is simple, for infinite $A$ it holds: $$2\lt A\leq2^A\implies 2^A\leq A^A\leq 2^{A\times A}=2^A.$$ However without the axiom of choice this doesn't ...
0
votes
0answers
58 views

What is semantics of “type”? Do “types” of “type theory” semantically differ from “set” of set theory? [migrated]

"To be of a (certain type)" is a fundamental relationship for ontology and the computer science "ontologies" are in the core of Semantic Web (which is my interest). But I did not encounter a ...
3
votes
1answer
283 views

Why is adopting Russell's Axiom of Reducibility as strong as eliminating the Ramified Hierarchy?

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is ...
2
votes
2answers
551 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 ...
10
votes
1answer
262 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 ...
3
votes
1answer
96 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 ...
3
votes
1answer
149 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 ...
13
votes
0answers
553 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
-2
votes
0answers
19 views

Can variables of quantification be repeated? [migrated]

For example, is the following valid? $\forall x \forall x \alpha$ Is so, then how is it evaluated user the basic semantic definition?
31
votes
5answers
3k views

Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence? More formally, 2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA? (This is mentioned in P. ...
10
votes
4answers
1k views

Does formalizing math require search and creativity, or is it near-mechanical?

I remember reading somewhere that it takes about a week to convert a page of math into something a proof-assistant like Isabelle or HOL Light would accept. Is this type of conversion something that ...
0
votes
0answers
40 views

How to study first order logic, without the use of sets? [migrated]

I am interested in learning first order logic. In particular, I would like to be comfortable enough with first order logic in order to fully tackle, say, the Axioms of Zermelo-Fraenkel, as in Jech's ...
6
votes
0answers
185 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," ...
0
votes
0answers
86 views

A Question on an extension of the Friedman-Sheard set theory and truth theory with complements of unions

The Friedman-Sheard logic of Truth has been studied much; see e.g. Andre Cantinis $\textit{Logical Frameworks fro Truth and Abstraction}$, Elsevier 1996 §66 and a number of articles by Volker Halbach. ...
3
votes
1answer
212 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, ...
0
votes
2answers
213 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
94 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
410 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 ...
3
votes
0answers
84 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 ...
2
votes
1answer
134 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 ?
8
votes
2answers
297 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
352 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, ...