Questions tagged [logic]
Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).
28,953 questions
3
votes
0
answers
61
views
Definition of hyperprojective sets
I've seen two definitions of hyperprojective sets:
sets that are both inductive and co-inductive (cf. p.315 of Moschovakis's book);
sets that belong to the smallest $\sigma$-algebra that contains ...
- 749
0
votes
0
answers
46
views
Equisatisfiable and its conditions
I need to understand the condition of Proposition 3.3.8 from the book: Logic in Computer Science by Hantao Zhang, Jian Zhang in page 97, that: $x$ is avariable not appearing in $S$. Then $S\approx S^{...
- 27
5
votes
1
answer
313
views
Exercise in Mathematical Logic by Ebbinghaus
Here is a problem I need help in Mathematical Logic by Ebbinghaus.
For the (effectively given) symbol set $S$, fix a Gödel numbering of the $S$-formulas; let $n^{\varphi}$ be the Gödel number of $\...
- 17.4k
2
votes
2
answers
414
views
Question in proof of Gödel's incompleteness theorem (Ebbinghaus Lemma 7.6)
On page 184 in Mathematical Logic by Ebbinghaus (2nd edition), the proof of Lemma 7.6 states:
By the consistency of $\Phi$ we get for an arbitrary $\alpha\in L_0^{S_{ar}}$ such that
$$
\Phi \vdash\neg\...
- 17.4k
4
votes
2
answers
428
views
Why is the Gödel numbering taken surjective in Ebbinghaus?
It is well known that Gödel numbers are not surjective but injective into $\Bbb{N}$. But on page 182 in Mathematical Logic by Ebbinghaus (2nd edition), it states that the Gödel numbering is surjective....
- 17.4k
1
vote
1
answer
91
views
How to properly understand $\text{Con}(\Gamma)$ expressing consistency
I've read in Kunen's Set Theory that given two theories (i.e. Axioms) $\Gamma$ and $\Lambda$, we have $\Lambda \lhd \Gamma$ if and only if $\Gamma \vdash \text{Con}(\Lambda)$, so that $\Gamma$ is ...
- 947
7
votes
1
answer
241
views
Can countably many giraffes guess the color of their own scarf correctly if each may be mistaken about the color of finitely many scarves?
This question is based on the question Is it possible to formulate the axiom of choice as the existence of a survival strategy? (MathOverflow).
Consider the following "computable giraffes, lion &...
- 4,970
0
votes
1
answer
82
views
Are normal forms in first order logic unique?
This is what I know so far:
If we have a block of all quantors w.r.t various variables, we can swap it as much as we like.
In general case we can't swap exists quantor with any other quantor
...
- 14.5k
3
votes
1
answer
75
views
Can We Prove the Completeness of Propositional Logic also with Structural Induction?
In propositional logic, the "semantics" $v[\![\varphi]\!]$ of a formula $\varphi$ with respect to some valuation $v$ is defined inductively on the syntactic structure of the formula $\varphi$...
- 43
3
votes
0
answers
211
views
Is there any mathematical theory that is isomorphic to its metatheory?
Gödel's constructions show that certain powerful enough theories can encode their own metatheory. But is there any theory that is isomorphic to its metatheory?
I'm not sure if there is a standard ...
- 1,679
-1
votes
1
answer
41
views
Need a conclusive example that explains why QBF Prenex Transformations require closed QBF formulas [closed]
The task is to show that:
$\forall p F \to G$ is not equivalent to $\exists p(F \to G)$ where F and G are propositional formulas.
I'm aware that when applying prenex rules to a formula to transform a ...
- 9
0
votes
1
answer
69
views
Generalization rule for universal quantifier and extended language
Let L be a language of first order logic. The generalization rule for universal quantifier says that, for $\phi\in L$, $\Sigma \vdash_L \forall x\phi(x) $ iff $\Sigma\vdash_{L\cup c}\phi([c/x])$, with ...
- 1
1
vote
2
answers
292
views
How does one derive involutivity of complement from the axioms of a Boolean algebra? [duplicate]
The book "Combinatorics: The Rota Way" gives the following definition of a Boolean algebra:
$\newcommand{\scp}{\wedge}$
$\newcommand{\scu}{\vee}$
$\newcommand{\ovl}[1]{\overline{#1}}$
A ...
- 1,506
2
votes
2
answers
263
views
Does the Axiom Schema of Separation in any sense "provide" only countably many definitions of subsets of $\mathbb{N}$?
Section 6 (pg. 24-25) of this paper contains the following excerpt (bold for emphasis added by me):
The axiom of Separation could also be called the axiom of Definable Subsets. A subset $T$ of $S$ is ...
- 2,303
13
votes
2
answers
2k
views
Is the transfer principle useless?
In this MathOverflow thread, a comment states:
Any proof using a transfer principle can be rewritten without it, so in some sense it can't play an “essential” role in a proof.
Is there a known ...
- 413