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.
4,992
questions
3
votes
0
answers
43
views
How exactly are realizability and the Curry-Howard correspondence related?
Consider, on the one hand:
the Curry-Howard correspondence between, on the one hand, types and terms (programs) in various flavors of typed $\lambda$-calculus, and on the other, propositions and ...
- 28.3k
-1
votes
1
answer
65
views
How to prove that increasing the number of constant symbols of a first-order logic by the number of formulas keeps the number of formulas the same [closed]
Let $S$ be a set of theory symbols for a first-order logic, and let $C$ be a set of constant symbols in $S$ such that $|C| = |L(S)|$, where $L(S)$ is the set of all formulas generated by $S$ in the ...
- 3
2
votes
0
answers
46
views
Can the set of parafinite congruences be descriptive-set-theoretically complicated?
Fix an algebra $\mathfrak{A}$ with underlying set $\mathbb{N}$ and finite language $\Sigma$. The set of congruences on $\mathfrak{A}$ is a closed subset $C_\mathfrak{A}$ of $2^\mathbb{N}$ (with the ...
- 19k
0
votes
1
answer
107
views
Congruences that aren't "finite from above," take 2: semigroups
This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
- 19k
4
votes
3
answers
396
views
Congruences that aren't "finite from above"
Let $\mathfrak{A}=(A;...)$ be an algebra in the sense of universal algebra. Say that a congruence $\sim$ on $\mathfrak{A}$ is parafinite iff there is an equivalence relation $E\subseteq A^2$ with ...
- 19k
0
votes
0
answers
101
views
Is "$\gamma$ is admissible" necessary in lemma V.5.10, Constructibility, Devlin?
This lemma is an early step of the proof of Jensen's covering lemma.
I feel that in this lemma, "$\gamma$ is admissible" is not required. $\gamma$ being a limit ordinal is enough.
In the ...
- 1,296
9
votes
1
answer
460
views
Con(PA) via non-well-foundedness?
Lumsdaine made the following interesting
comment:
if Con(PA) fails in a non-standard model, it means it contains a
“proof of non-standard length” of a contradiction from PA. With a
little work, one ...
- 14.8k
6
votes
0
answers
82
views
Locally presentable and accessible categories without the axiom of choice?
Is there a good reference for the study of locally presentable and accessible categories without the axiom of choice? For instance, it seems one will need to understand:
What is a good notion of $\...
- 58.6k
1
vote
0
answers
266
views
What's the definition of a mouse in Mitchell's handbook article "the covering lemma"?
In the book "handbook of set theory", in the chapter "the covering lemma", definition 3.24, Mitchell defines what is mouse.
However he did not give any definition of $\mathcal{U}_\...
- 1,296
9
votes
2
answers
2k
views
Is GCH useful in proving theorems?
By GCH I mean the Generalized Continuum Hypothesis. Let me give some context before presenting my question.
When the axiom of choice was introduced by Zermelo in his 1904 proof of Well-Ordering ...
- 2,445
1
vote
0
answers
13
views
Reference request for dinatural transformations arising from free Cartesian closed categories
Let $g_n$ be a discrete graph with $n$ nodes and $\operatorname{F}$ the free functor of the adjunction between the category of graphs and the category of Cartesian closed categories and functors, as ...
6
votes
1
answer
174
views
Is the Rado graph the unique countable graph that has all finite graphs as induced subgraphs?
I understand that since the Rado graph is the Fraïsse limit of the class of finite graphs, it is the unique homogeneous graph with this property. Is there another graph not isomorphic to the Rado ...
- 486
5
votes
0
answers
116
views
Elementary equivalence for rings
Let $\mathcal{L}$ be a first-order language, and $M$ and $N$ be two $\mathcal{L}$-structures. We say that $M$ and $N$ are elementarily equivalent (write $M \approx N$) if they satisfy the same first-...
- 2,445
6
votes
2
answers
522
views
Is "the purely probabilistic version of Freiling's axiom of symmetry" disprovable in ZFC?
I'm trying to pinpoint the "intuitive argument" for Freiling's Axiom of Symmetry. It's meant to be a "probabilistic" argument, so thinking about what seems to me to be the ...
- 638
2
votes
1
answer
115
views
Posets of equational theories of "bad quotients"
This is a follow-up to an older question of mine:
Suppose $\mathfrak{A}=(A;...)$ is an algebra (in the sense of universal algebra) and $E$ is an equivalence relation - not necessarily a congruence - ...
- 19k
1
vote
1
answer
210
views
Hahn-Banach theorem and ultrafilter lemma
I'm unable to understand a remark in "Two application of the method of construction by ultrapowers to analysis" by Luxemburg, which uses the ultrafilter lemma to prove the Hahn-Banach ...
- 75
5
votes
0
answers
249
views
An imaginary disaster scenario - second order arithmetic is inconsistent
I think my question is a natural follow up of What would be some major consequences of the inconsistency of ZFC?
Regarding the later question, I agree with the commentaries that probably an ...
- 2,445
6
votes
1
answer
276
views
Proving finiteness in Reverse Mathematics
In (second-order) Reverse Mathematics, a (code for an) open set $U\subset \mathbb{R}$ is given by two sequences of rationals $(a_n)_{n \in \mathbb{N}}, (b_n)_{n \in \mathbb{N}}$. The idea is that $U$ ...
- 3,657
-4
votes
0
answers
75
views
Is the following combinatorial identity correct? $\sum_{k=1}^{n}k \cdot 2^k = n \cdot 2^n$ [closed]
During my studies in mathematical logic, I learned a new concept called a truth table. I saw as an example that for $3$ atoms, in the context of a binary connector, there are $8$ different cases for ...
3
votes
1
answer
106
views
Classes of algebras axiomatizable by special formulas; and free objects
Let $\mathcal{L}$ be a first-order language without relation symbols, and let $\mathcal{K}$ be a class of $\mathcal{L}$-algebras. $\mathcal{K}$ is axiomatizable if there is a set $T$ of first-order ...
- 2,445
3
votes
1
answer
176
views
Is Morse-Kelley set theory with Class Choice bi-interpretable with itself after removing Extensionality for classes?
Let $\sf MKCC$ stand for Morse-Kelley set theory with Class Choice. And let this theory be precisely $\sf MK$ with a binary primitive symbol $\prec$ added to its language, and the following axioms ...
- 8,191
11
votes
5
answers
1k
views
In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?
It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...
- 119
1
vote
1
answer
72
views
Sizes of linearly ordered subalgebras of powers
On the grounds that I'm currently teaching a linear algebra class and I enjoy making my students furious, let a linear algebra be an algebra $\mathcal{A}$ in the sense of universal algebra equipped ...
- 19k
22
votes
4
answers
3k
views
A Löwenheim–Skolem–Tarski-like property
I am interested in the following Löwenheim–Skolem–Tarski-like property.
Given a cardinal $\kappa$, what (if any) is a property $\phi(x)$ such that if $\phi(\kappa)$ holds, then we can prove the ...
- 323
8
votes
1
answer
268
views
Two notions of generalized quotient/substructure
Given a language $\Sigma$ and a $\Sigma$-algebra (in the sense of universal algebra) $\mathcal{A}=(A;\dotsc)$ and a function $f:A\rightarrow A$, let $\mathcal{A}_f$ be the $\Sigma$-algebra whose ...
- 19k
13
votes
1
answer
1k
views
Are Berkeley cardinals easier to refute in ZFC than Reinhardt cardinals?
Kunen showed that Reinhardt cardinals are inconsistent in ZFC. But his proof is a bit technical for a non-set-theorist to follow. Berkeley cardinals are stronger than Reinhardt cardinals. You can ...
- 58.6k
17
votes
3
answers
2k
views
Why is an internal proof of consistency satisfactory for some systems?
I've only a shallow understanding of the relevant theory, but I don't understand how any internal proof of consistency is in any way satisfactory (even for systems that are so weak Gödel's ...
- 171
4
votes
2
answers
260
views
Hyperarithmetically least elements in $\Pi^1_1$ sets
My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is
Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
- 2,412
7
votes
0
answers
158
views
Strengthening Determinacy in constructive set theory?
Recall how games work. Let $X$ be a set (the "game space") and $\alpha$ an ordinal (the "game clock"). Alice and Bob take turns naming elements of $X$. We write them down in order ...
- 58.6k
3
votes
2
answers
297
views
Are there $2^{\aleph_0}$ pairwise non-isomorphic countable groups containing every finite group?
Let us call a group $(G,\cdot)$ finitarily complete if $G$ is countable, and every finite group is isomorphic to a subgroup of $(G,\cdot)$.
Is there a collection of $2^{\aleph_0}$ pairwise non-...
- 44.4k
11
votes
0
answers
277
views
Can Friedman's property fail at or above a supercompact cardinal?
If $\kappa>\omega_1$ is a regular cardinal, $FP_\kappa$ is the assertion that every stationary subset of $\kappa$ consisting of ordinals of countable cofinality has a closed subset of order type $\...
- 111
2
votes
0
answers
58
views
Relation of top and bottom types given multiple universes
This is something that I haven't seen mentioned in any literature.
In a type theory (extensional, intuitionistic, Martin Lof variant), given two ordered Tarski Universes such that $U_i < U_{i+1}$, ...
- 21
3
votes
0
answers
117
views
Can well-ordering of the universe due to global choice survive extensive failure of Extensionality?
That axiom of global choice leads to the well-ordering of the universe given the other axioms of Zermelo set theory is a famous result.
Now, if we weaken the power set axiom to the axiom stating that ...
- 8,191
4
votes
1
answer
117
views
$\aleph_0$-uniform non-bipartite linear hypergraph
A hypergraph $H= (V,E)$ is said to be bipartite if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $$S\cap e\neq \emptyset\neq (e\setminus S).$$ A hypergraph is said to be ...
- 44.4k
5
votes
0
answers
161
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
- 2,531
2
votes
1
answer
561
views
"Potency set" for power set?
Cross-posted at HSM.
Has the term "potency set" been used in English language mathematics for power set, and, if so, what are good references?
It is relevant that for historical reasons, &...
- 3,146
3
votes
1
answer
105
views
Oscillation functions and similar constructs
For given $f$ from reals to reals, the associated oscillation function is defined as follows:
$$\textstyle
osc_f(x):= \lim_{n\rightarrow \infty} [\sup_{y \in B(x, \frac{1}{2^n}) } f(y)-\inf_{z \in B(x,...
- 3,657
14
votes
1
answer
471
views
Extensions of $PA+\neg Con(PA)$ with large consistency strength
There is a large hierarchy of theories strengthening $PA$ eg $PA+Con(PA)$, $PA+Con(PA+Con(PA))$,..., second-order arithmetic and $ZFC$, ordered by consistency strength.
Is there an extension of $PA+\...
- 345
8
votes
0
answers
167
views
The approximate mean value theorem / Rolle's theorem in pure constructive mathematics
In the replies of this very similar question, there is a fascinating answer that is beautiful in its simplicity. In particular, it seems to use perhaps the most minimal assumptions one can possibly ...
- 81
12
votes
2
answers
378
views
Trading Choice for Comprehension (or Replacement)
This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
- 28.3k
2
votes
1
answer
149
views
Does allowing Ur-elements in $\sf ZF^*GC$ break bi-interpretability with $\sf ZF^*GC$?
Is $(\sf ZF^*GC - Extensionality)$ bi-interpretable with $\sf ZF^*GC$?
Where $\sf ZF^*GC$ is $\sf ZF - Replacement + Separation + Collection + Global \ Choice$
- 8,191
8
votes
1
answer
322
views
"Compactness length" of Baire space
Intuitively, my question is: how many times do we have to mod out by an closed equivalence relation with all classes compact in order to collapse Baire space $\omega^\omega$ to a singleton?
In more ...
- 19k
6
votes
1
answer
397
views
A strange product forcing
Given two forcing notions $\mathbb{P}_0,\mathbb{P}_1$, we know that the product $\mathbb{P_0}\times\mathbb{P_1}$ will produce the following diagram of models ordered by inclusion:
where $M$ is the ...
- 1,980
2
votes
1
answer
162
views
What's the benefit of adding a well-ordering over all classes to $\textsf{MK}$?
Working in $\textsf{ZF} + \text {there is a strongly inaccessible cardinal}$.
Let $\kappa$ be the first strongly inaccessible cardinal, and let $\lvert V_\kappa\rvert= \kappa$, then $(V_{\kappa+1}, \...
- 8,191
9
votes
1
answer
326
views
Natural set-theoretic principles implying the Ground Axiom
The Ground Axiom states that the set-theoretic universe is not a set-forcing extension of an inner model. By
Reitz, it is first-order expressible and easy to force over any given ZFC model with class-...
- 17.8k
7
votes
0
answers
171
views
Does the Affine Pappus Axiom imply the Affine Desargues Axiom in affine planes?
I am interested in the affine version of the well-known Hessenberg's Theorem (saying that Pappian projective planes are Desarguesian).
First I introduce all necessary definitions.
Definition L. A ...
- 40.1k
2
votes
0
answers
113
views
Can this theory of classes of ordinals interpret ZFC?
The following theory is a theory of classes of ordinals.
Language: Bi-sorted FOL with identity. First sort in lower case ranging over ordinals. Second sort in upper case ranging over classes of ...
- 8,191
7
votes
5
answers
2k
views
Standard models of N and R: An Alice/Bob approach
This is a question about a comment in a recent publication by Roman
Kossak. Kossak wrote:
"Nonstandardness in set theory has a different nature. In
arithmetic, there is one intended object of ...
- 14.8k
6
votes
0
answers
187
views
Reference for Understanding Shelah's Proof of Vaught's Conjecture for $\omega$-stable Theories
I'm looking for a source to help me better understand Shelah's proof of Vaught's Conjecture for $\omega$-stable Theories (https://shelah.logic.at/files/95409/158.pdf). An obvious candidate is Makkai's ...
- 173
3
votes
1
answer
291
views
Second order theory of a real-closed field
It is well known that the first-order theory of any real-closed field is complete, and consequently not capable of interpreting the majority of modern mathematics.
Is this still true for the second-...
- 8,878