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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
304 views

Can a power set be equal in cardinality to a subset of it that is non-exhaustively overlapping?

Definition: a set $X$ is to be labeled as "non-exhaustively overlapping" if and only if each element of $X$ is not a subset of any other element of $X$; formally:$$ X \text { is non-exhaustively ...
Zuhair Al-Johar's user avatar
8 votes
3 answers
1k views

How much of concrete mathematics can be expressed in the language of category theory?

Question 1 How much of group/ring/lattice/... theory can be expressed in purely categorical terms (only using the notions object, morphism, identity morphism, and composition), that is, as properties ...
1 vote
1 answer
238 views

Interpreting PA2 in second-order logic + existence of infinitely many objects

I've heard that if you assume the existence of (Dedekind) infinitely many objects, you can derive -- in second-order logic, given suitable definitions -- the (second-order) Peano axioms for arithmetic....
Thomas Schindler's user avatar
10 votes
2 answers
347 views

Source on smooth equivalence relations under continuous reducibility?

This question was asked and bountied at MSE, but received no answer. In the context of Borel reducibility, smooth equivalence relations (see the introduction of this paper) are rather boring since ...
Noah Schweber's user avatar
0 votes
1 answer
423 views

Are there known type-level infinite tuple implementations in ZFC?

Quine-Rosser ordered pair is type-level; i.e., it is definable by a stratified formula that assigns to it the same type it assigns to its projections. It is known that if $\langle A,B \rangle$ is type-...
Zuhair Al-Johar's user avatar
4 votes
0 answers
252 views

Proof theory and subsystems of second-order arithmetic: in particular the reverse mathematics of Godel's system $T$

While doing some research on reverse mathematics, I came across the following document under the address, http://www.andrew.cmu.edu/user/avigad/Talks/survey1.pdf: Proof theory and Subsystems of ...
Thomas Benjamin's user avatar
2 votes
1 answer
233 views

Nonconstructive reasoning in Skolem's proof of the Löwenheim-Skolem Theorem

I am trying to understand where nonconstructive reasoning occurs in this passage from Skolem’s (1922) proof of the Löwenheim-Skolem theorem. As background, Skolem’s “solutions” are assignments of ...
Mallik's user avatar
  • 583
0 votes
0 answers
62 views

Can we have relations of the same type of their composing ordered pairs?

Is it possible to define a binary function $P$ in the language of set theory that obeys the characteristic property of ordered pairs and such that for any two sets $A,B$, for any definable relation $R$...
Zuhair Al-Johar's user avatar
3 votes
1 answer
194 views

Is there an analog of Tennenbaum's theorem for real arithmetic?

In other words, does the first order theory of $(\mathbb{R},+,\times,0,1)$ have a computable countable model? What do we know more generally about countable models of real arithmetic?
Thinniyam Srinivasan Ramanatha's user avatar
0 votes
1 answer
566 views

Can Godel's incompleteness theorems be in some sense circumvented this way?

New foundations "NF" (formulated in the language of $\small \sf FOL(\in)$), can define a kind of ordered pair relation $``\rho"$ such that we can have a set $E$ of those pairs where NF proves the ...
Zuhair Al-Johar's user avatar
0 votes
1 answer
241 views

Is Cantor-Bernstein-Schroeder theorem for skew cardinality, consistent with NF?

Define: $n$-skew pair of $x,y$, denoted by $\langle x,y \rangle^n$, as: $(singleton^n(x), y)$ Define: $(-n)$-skew pair of $x,y$, denoted by $\langle x,y \rangle^{-n}$, as: $(x, singleton^n(y))$ ...
Zuhair Al-Johar's user avatar
3 votes
1 answer
198 views

Is self-escaping without self-dominating possible?

For a countable structure $\mathcal{S}$, let the cospectrum of $\mathcal{S}$ be the set $CS(\mathcal{S})$ of reals (non-uniformly) computable in every copy of $\mathcal{S}$ (we can also make sense of ...
Noah Schweber's user avatar
0 votes
2 answers
357 views

A sequence in the hierarchy of universes

The HoTT Book states in the first chapter that universes are cumulative and that every universe is in some other universe. Obviously, there needs to be an infinite number of universes then, but ...
Bolpat's user avatar
  • 123
3 votes
0 answers
127 views

Is there a name for this operation on integer functions?

Suppose $f$ and $g$ are functions from $\mathbb N^+$ to itself. I want to consider the function $f^g$, where $f^g(n) = f \circ \dots \circ f(n)$, where composition is done $g(n)$-many times. Note ...
Monroe Eskew's user avatar
  • 18.1k
0 votes
3 answers
973 views

Regarding Gentzen's note regarding 'Godel-points' (i.e., "Where is the Godel-point hiding?")

Consider the following note written by Gerhard Gentzen in early 1932, on the onset of his work on a consistency proof for arithmetic: The axioms of arithmetic are obviously correct, and the ...
Thomas Benjamin's user avatar
1 vote
0 answers
244 views

Skolem's proof of Konig's infinity lemma

I am trying to understand the following passage from Skolem’s (1922) proof of the Lowenheim-Skolem theorem by reference to the contemporary proof of Konig’s infinity lemma: Let $L_{1,n},L_{2,n},...,...
Mallik's user avatar
  • 583
1 vote
0 answers
206 views

Uncountable chain of nested sets without choice

Let $\kappa$ be an uncountable cardinal. Given a set of S of cardinality $\kappa$, I want to construct a chain {$S_\lambda : \lambda \in \kappa$ } such that: 1) Each $S_\lambda$ is a proper subset of ...
Anindya's user avatar
  • 665
2 votes
1 answer
269 views

Possible to prove a lemma from Godel's completeness theorem in intuitionistic logic?

I am trying to determine whether a particular theorem used in the course of Godel’s (1930) proof of the completeness of predicate logic could be proven in an intuitionistic metatheory. Theorem VI (p....
Mallik's user avatar
  • 583
3 votes
1 answer
324 views

Lower bound for polyhedral real quantifier elimination

All known examples for double exponential lower bounds for real quantifier elimination involves polynomial inequalities with degree $>1$. Is there an example of double exponentiality with ...
VS.'s user avatar
  • 1,816
1 vote
1 answer
231 views

What are the known conditions for a restriction on naive comprehension that enables a generalization of a property all so constructed sets meet?

Let $\mathcal Q$ be some qualification on formulas in the first order language of set theory (FOL($\in$)), that is met by at least one formula; Let $T$ be the first order set theory whose extra-...
Zuhair Al-Johar's user avatar
9 votes
1 answer
488 views

Solovay’s model

Solovay proved that if $\kappa$ is inaccessible, then if we adjoin a generic $G \subseteq \mathrm{Col}(\omega,{<}\kappa)$, then in the extension, every set of reals in $L(\mathbb R)$ is Baire- and ...
Monroe Eskew's user avatar
  • 18.1k
6 votes
0 answers
282 views

Weaker versions of Gandy ordinals

Gostanian's paper "The next admissible ordinal" (see https://www.sciencedirect.com/science/article/pii/0003484379900251 ), is concerned with the supremum of the $\alpha$-recursive ordinals for various ...
M Carl's user avatar
  • 335
0 votes
1 answer
119 views

Can removal of extensionality avoid cardinality errors in stratified theories?

Let $SF$ be the schema of stratified comprehension. Take the theory $SF + Infinity + Choice + \text {Extensionality fails everywhere}$. Are the following consistent with this theory? $\forall X (|...
Zuhair Al-Johar's user avatar
19 votes
0 answers
790 views

"Compactness for computability" - does it ever happen?

Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable." Say that a computable structure $...
Noah Schweber's user avatar
0 votes
1 answer
82 views

Can global failure of Extensionality in fragments of NFU permit existence of singleton relation set?

Let $SF$ be the schema of stratified comprehension. Take the theory $SF + Infinity + Choice + \text {Extensionality fails everywhere}$ Is the following consistent with this theory? $\exists \iota \...
Zuhair Al-Johar's user avatar
0 votes
2 answers
1k views

Can ZFC commit cardinality errors?

Add a primitive a one place function symbol $c$ to represent "True cardinality" of a set, to the first order language of set theory. Add the following axiom schema: 1. Cardinal Equality: If $\phi(x,...
Zuhair Al-Johar's user avatar
2 votes
0 answers
2k views

Compatible and incompatible sets [closed]

Definition of the compatibility relation I have defined a relation $\mathsf{C}$ for sets that captures (to some extent) the notion of compatibility. In order to do this, we need an operation $': \...
lfba's user avatar
  • 121
4 votes
3 answers
759 views

Compact definition of ordinals

This question is about von Neumann's informal definition of ordinals as "sets of all smaller ordinals" and was discussed in this math.stackexchange question. When trying to formalize this definition, ...
Alexander Kuleshov's user avatar
-5 votes
1 answer
373 views

Can we blend ZFC with true arithmetic?

Can we have a consistent theory whose signature is $(=,\in, S, +, \times)$ standing for identity and membership binary relations and the successor total unary function, addition and multiplication ...
Zuhair Al-Johar's user avatar
2 votes
1 answer
321 views

Is second-order logic *with standard semantics* necessary to categorically characterise the natural number structure?

Is second-order logic with standard semantics necessary to categorically characterise the natural number structure? One can prove that any two models of Dedekind-Peano arithmetic are isomorphic (...
sdlkgjh45's user avatar
-1 votes
2 answers
300 views

Can we have a theory that define small (ZFC set sizes) collections of big sets?

I want to coin a theory that can speak about big sets like some of those present in NF, but at the same time comprehend over small collections of them as it is the case in ZFC. Is this known to be ...
Zuhair Al-Johar's user avatar
3 votes
1 answer
269 views

Infinitary generalizations of HOD

Say that a set is ordinal$_{\kappa\lambda}$-definable if it is definable by a formula in the infinitary language $\mathcal{L}_{\kappa\lambda}$ with parameters from $\mathsf{On}$. Let $HOD_{\kappa\...
Beau Madison Mount's user avatar
1 vote
0 answers
204 views

Completeness or soundness? Understanding a claim by Gödel

My question concerns a statement by Gödel in 1967. Commenting on Skolem’s failure to infer completeness from his (1922) proof of the Lowenheim-Skolem theorem, Gödel observes that Skolem did not ...
Mallik's user avatar
  • 583
15 votes
7 answers
1k views

Examples of proofs by making reduction to a finite set [closed]

This is a very abstract question, I hope this is appropriate. Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...
21 votes
2 answers
1k views

Is the union of a chain of elementary embeddings elementary?

I am a little confused about what I think must be either a standard theorem or a standard counterexample in model theory, and I am hoping that the MathOverflow model theorists can help sort me out ...
Joel David Hamkins's user avatar
0 votes
0 answers
174 views

Can second order ordinal arithmetic be extended to the same extent as ZFC?

In a prior posting, I've posed the idea of reducing set theory to an extended kind of second order ordinal arithmetic $\small \sf`` 2 oO A"$. The idea was to have a domain of ordinals and sets of ...
Zuhair Al-Johar's user avatar
3 votes
1 answer
87 views

Is the quasi-equational theory of groups the same as cancellative semigroups?

Consider the class of groups in the signature {*}. Is the quasi-equational theory of that class axiomatized by the associative law and the left and right cancellative laws?
user107952's user avatar
  • 2,063
0 votes
2 answers
204 views

Collection $\cal{C}$ of uncountable subsets of $\mathbb{R}$ such that every countable subset is contained in exactly one member of $\cal{C}$

If $\kappa$ is a cardinal and $X$ is a set, let $[X]^\kappa$ denote the collection of subsets of $X$ that have cardinality $\kappa$. Let $\beta>\omega$ and $\beta \leq 2^{\omega}$. Is there ${\cal ...
Dominic van der Zypen's user avatar
6 votes
1 answer
265 views

Borel / Wadge hierarchies on subsets closed under prepending a finite prefix

I'm interested in subsets $X$ of the Cantor space ($2^\omega$) or the Baire space ($\omega^\omega$) that are closed under prepending an arbitrary finite prefix: $$ (x_1, x_2, \dots) \in X \implies (...
user1020406's user avatar
1 vote
0 answers
162 views

Induction on open formulas vs. Induction on $\Pi_1$ formulas

There are infinitely many extension to Robinson's $Q$ arithmetic many of which are defined by adding an axiom schema of induction for particular set of formulas. I am confused about the theory $\text{...
Punga's user avatar
  • 173
18 votes
2 answers
1k views

Are buttons really enough to bound validities by S4.2?

Joel Hamkins recently claimed on twitter that buttons suffice to bound the validities of a potentialist system to the modal logic S4.2 (see here), and that switches are not necessary. We have been ...
Robert Passmann's user avatar
14 votes
1 answer
721 views

Coend calculus as a deductive system

I've always had in the back of my head the feeling that co/end calculus, regarded as a set of rules allowing to mechanically prove nontrivial statements as initial and terminal points of a chain of ...
fosco's user avatar
  • 13k
8 votes
2 answers
578 views

Is the equational theory of groups axiomatized by the associative law?

Consider the class of groups in the signature {*}. Is the equational theory of that class axiomatized by the associative law? I asked this on math stack exchange but I didn't receive a satisfactory ...
user107952's user avatar
  • 2,063
5 votes
1 answer
486 views

Failure of SVC in Grothendieck toposes

The axiom SVC (for "small violations of choice") asserts that there is a set $S$ such that for every set $X$ there is a choice set $A$ such that $X$ is a subquotient of (i.e. admits a surjection from ...
Mike Shulman's user avatar
  • 64.8k
1 vote
0 answers
219 views

topological properties of $G_{\delta}$ sets in a compact Hausdorff space

I am trying to understand a family of types $\mathcal{F}$ in the set $S(A)$,the set of complete types over $A$ (in the sense of types in model theory) which is a compact and Haurdorff space equipped ...
user350168's user avatar
5 votes
0 answers
257 views

Generic properties of dominating/etc. reals with non-Cohen working parts

The first and foremost forcing that adds a real is the Cohen forcing which approximates a new real number by giving finite approximations to its characteristics function. But very quickly after that, ...
Asaf Karagila's user avatar
  • 37.9k
1 vote
0 answers
180 views

End-extension in Gödel's constructible universe

Given two ordinals $\alpha < \beta$, considering the subsets of Gödel's constructible universe, one say that $L_\beta$ is a $\Sigma_n$ end-extension of $L_\alpha$ (and $L_\alpha$ is an $\Sigma_n$ ...
Johan's user avatar
  • 491
6 votes
1 answer
554 views

Survey article model theory research

I've taken a graduate course in model theory and I like it so much that I can imagine doing research in this area. Are there survey articles or review papers on the current research topics in model ...
user144513's user avatar
5 votes
2 answers
593 views

A weak (?) form of Shelah cardinals

The following definition of a large cardinal property combines parts of the definitions of "Shelah cardinal" and "Woodin cardinal": A cardinal $\kappa$ is weakly Shelah if for all $f : \kappa \to \...
Trevor Wilson's user avatar
2 votes
1 answer
82 views

On Asymptotic classes of finite structures (2)

As I mentioned in my previous question, I am reading the following paper: One-dimensional asymptotic classes of finite structures. by: Macpherson and Steinhorn I have some crazy questions! What is ...
Mark Smith's user avatar

1
33 34
35
36 37
103