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.
5,127
questions
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 ...
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....
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 ...
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-...
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 ...
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 ...
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$...
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?
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 ...
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))$
...
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 ...
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 ...
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 ...
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 ...
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},...,...
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 ...
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....
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 ...
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-...
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 ...
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 ...
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 (|...
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 $...
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 \...
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,...
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 $': \...
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, ...
-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 ...
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 (...
-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 ...
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\...
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 ...
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 ...
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 ...
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?
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 ...
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 (...
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{...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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$ ...
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 ...
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 \...
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 ...