Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

3
votes
3answers
849 views

Truth table, clarification of $2^n$ row rule?

My question is about truth tables and specifically why there is $2^n$ rows for $n$ inputs in a truth table? I understand that there's a finite amount of states a variable can be in, here it's 2 - ...
6
votes
3answers
293 views

Is the set of all deducible formulas decidable?

Consider any standard, "sufficiently expressive" first-order theory (say, $ZFC$ or Peano arithmetic) so that all the usual arithmetization and incompleteness results hold. The set $D$ of deducible ...
1
vote
1answer
235 views

Structure and Formula encoding for Turing Machine

During my study of Finite Model Theory I found that usually purely relational structure say $\mathcal{M} = \langle A, R_1,\ldots,R_k \rangle$ are encoded as ...
1
vote
1answer
111 views

Model-checking and Turing Machines

I am reading proof of Fagin's theorem, which says "A problem $\pi$ $\in$ NP iff there is a existential second-order sentence of the form $\phi$ = $\exists{R_1}\exists{R_2}...\exists{R_n}\psi$ , where ...
4
votes
3answers
655 views

Classifying Types of Paradoxes: Liar's Paradox, Et Alia

The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
-13
votes
1answer
674 views

How Can One Legitimately Use the Rules of Substitution and Repalcement in a Non-Mechanical Fashion? [closed]

Charles Stewart said I might ask the following as a question here. If an author doesn't use parentheses for logical expressions like x->y, say in propositional calculus, I don't see how the ...
15
votes
1answer
1k views

Infinite Set is Disjoint Union of Two Infinite Sets

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite. In ZF, can you prove that every infinite set is the union of two ...
0
votes
3answers
608 views

What Does it Mean Exactly to Claim Logical Theorems (Axioms) Independent?

The independence of theorems in some propositional calculus systems seems well studied. For example, if we just have the rules of detachment, substitution, and replacement, and every theorem of this ...
0
votes
3answers
378 views

Equality in Boolean Algebra

Say, $$A = C \lor (C\land D) = C \land(1\lor D) = C$$ $$A = C \lor (C\land D) = (C\lor D)\land(C\lor C) = C\land(C\lor D)$$ Now, the part I don't understand here is if we equate we get: $$C \land ...
1
vote
1answer
204 views

Does There Exist a Connection Between all n-valued Propositional Logics with Quantifiers and Classical Predicate Logic (see condition)?

If a theorem holds for all truth functions of all n-valued logics, in all n-valued logics with quantifiers, n>=2, will it also hold in classical predicate logic where the domain has at least two ...
8
votes
1answer
238 views

Reverse Mathematics of Well-Orderings

In Simpson's book, a well-ordered set $X$ is a linear ordering such that there are no functions $f : \mathbb{N} \rightarrow X$ which is decreasing. However, a familiar definition of well-ordering is ...
26
votes
5answers
2k views

Who invented $\vee$ and $\wedge$, $\forall$ and $\exists$?

I can rather easily imagine that some mathematician/logician had the idea to symbolize "it E xists" by $\exists$ - a reversed E - and after that some other (imitative) mathematician/logician had the ...
12
votes
1answer
374 views

Formalizing metamathematics

I am reading historical/philosophical stuff on the concept of "metamathematics" and am by now quite confused. Several questions emerged, but they are probably somehow confused and interrelated, I ...
1
vote
1answer
208 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
3
votes
3answers
401 views

Placing some sets in the arithmetic hierarchy

I'm working on the following problem: let $W_e$ be the computably enumerable set which is the domain of the $e$-th Turing program, and $K$ be the Halting problem, at which level of the arithmetic ...
3
votes
0answers
192 views

Formally undecidable problems on finitely presented quandles

In the literature, one sometimes sees the claim that finitely presented quandles (in particular, knot quandles) are "hard to deal with". Hence, a great deal of effort has gone into studying finite ...
2
votes
1answer
137 views

A problem about complete theory

I'm working on the following problem which is exercise 3.5.1 in Rothmaler's Model Theory book. Show that theory $T$ is complete iff $\phi \vee \psi \in T$ implies $\phi \in T$ or $\psi \in T$ (keep in ...
-1
votes
1answer
359 views

Number Theory, Mathematical Fields, and Theoremhood

In classical logic, any given theorem implies any other given theorem (the soundness of classical logic comes as one way to help realize this). I realize the term "mathematics" has a certain ...
3
votes
2answers
143 views

Existence of a subset of infinite model that's not definable

I'm working on the following problem: Show that any infinite model $\mathcal{M}$ has a subset of its domain that's not definable in $\mathcal{M}$ using parameters. I tried to follow a contradiction ...
6
votes
1answer
343 views

Grothendieck universe consistency

Is ZFC with existence of Grothendieck universe (variant: Grothendieck universe containing every given set) provable in ZFC to be equiconsistent with ZFC? If not, what else it may be equiconsistent ...
2
votes
3answers
234 views

Logical propositions, which one is true and how to write a short proof?

I am studying for an entrance exam. Now I am stuck on this question: Suppose that P, Q are propositions such that "P or Q" is true. For each proposition (1), (2) and (3) which of the following ...
2
votes
1answer
375 views

Formalising real numbers in set theory

If I understand correctly, the real numbers can be formalised in a first-order, like in ZF. However, such a formalisation is not strong enough to ensure that all models of the reals are isomorphic. ...
1
vote
2answers
267 views

Why is $p\Rightarrow q$ equivalent to $\neg p\lor q$ and how to prove it

I don't know how to prove that $p\Rightarrow q$ is equivalent to $\neg p\lor q$ ,here is the link p=>q . And I don't know how wolframalpha generate "Minimal forms" . Can you prove $p\Rightarrow q ...
2
votes
1answer
256 views

How can i prove that the theory of random graph has a vaughtian pair?

I'm searching for theories that have a vaughtian pair. I've been given a hint, that $T_{RG}$ has at least one. I have also found many theorems stating in which cases a theory has no vaughtian pair, ...
5
votes
3answers
404 views

Undecidable conjectures

Suppose we work with a conjecture saying that something is true for any natural $n$. For each $n$ there exists an algorithm of finite length allowing one to decide whether it is true or false for this ...
2
votes
0answers
123 views

Can you express a logic system like S5 using only a Gödel number?

Since logic systems are just statements and/or axioms, can we formulate a logic system gödel numbering the system itself so that the system becomes nothing but a gödel number? For instance the modal ...
1
vote
1answer
93 views

If $\Sigma_1 \vdash \alpha$ for every $\alpha \in \Sigma_2$, is $\Sigma_1 \cup \Sigma_2$ consistent?

If $\Sigma_1$ and $\Sigma_2$ are consistent sets and if $\Sigma_1 \vdash \alpha$ for every $\alpha \in \Sigma_2$, is $\Sigma_1 \cup \Sigma_2$ consistent? Intuitively I think it is consistent, but I am ...
2
votes
1answer
278 views

Misprint in “Mathematical Logic” by Stephen Cole Kleene

Page 18 “Theorem 3. If $\models A$ and $\models A\to B$, then $\models B$.” Page 43 From prove of Theorem 12. “By Theorem 3, given that premises $A$ and $B$ for an application of modus ponens are ...
0
votes
2answers
139 views

Confirm some logical inferences for me please?

Sorry, I am just preparing some notes for my students and want to double check I have my facts right before I give the notes to them. So these are my premises: $\lnot p\rightarrow o$ $s\rightarrow ...
2
votes
1answer
98 views

satisfiable assignment close to an unsatisfiable assignment

Given a CNF formula $F$ and an unsatisfiable assignment $\alpha_u$ over the variables in $F$, I want to find a satisfiable assignment $\alpha_s$ which is as close as possible to $\alpha_u$, w.r.t. the ...
3
votes
2answers
270 views

Undecidability in ZFC of statements concerning logical validity

For every first-order sentence (in some vocabulary) $\varphi$ let us denote by $\varphi^+$ to the sentence (in the vocabulary of ZFC) expressing "$\varphi$ is logically valid (i.e., $\varphi$ is true ...
3
votes
2answers
5k views

Can someone please explain 3-CNF for me?

I was reading a textbook today and stumbled upon 3-CNF: 3-conjunctive normal form. Apparently, it's a conjunctive form, where every OR clause has at most 3 ...
1
vote
1answer
501 views

Rule C (Introduction to mathematical logic by Mendelson fifth edition)

By Existential Rule E4 $\mathscr B(t, t)\vdash (\exists x) \mathscr B(x, t)$. But how can we get back? How can we formalize $(\exists x) \mathscr B(x)\vdash \mathscr B(t)$? It is shown on page 74 and ...
3
votes
2answers
2k views

Modern Mathematics having serious problems with Real Numbers?

While watching this N. Wildberger video, at 12:34 it is mentioned that Modern Mathematics has serious problems with real numbers and that Mathematicians are aware of it. Can anyone point to what are ...
3
votes
1answer
195 views

Question about maximal consistency

Let $\sigma$ be a consistent set of propositions such that for every set $\gamma$, either $\sigma$ is proofwise stronger than $\gamma$ that is {$\alpha : \sigma \vdash \alpha$} $\supseteq$ {$\alpha ...
1
vote
1answer
201 views

For any $\alpha$, does a set $\gamma$ always exist so $\gamma\vdash\alpha$ or $\gamma\vdash\lnot\alpha$?

In propositional Calculus, for any proposition $\alpha$ does there always exist a set of propositions $\gamma$ such that $\gamma$ $\vdash$ $\alpha$ or $\gamma$ $\vdash$ $\neg\alpha$?
1
vote
3answers
338 views

Consistency of $\mathsf{PA}$

My reference book is A Course on Mathematical Logic by S.M. Srivastava. Not so long ago, MO linked me to a video of a conference by Voevodsky wherein he considered the possibility of arithmetic being ...
28
votes
3answers
909 views

Are the axioms for abelian group theory independent?

(I give a lengthy introduction to a concise question -- scroll down if you want to jump straight up to the question). Recall that abelian group theory consists of two primitive symbols: $\cdot$ which ...
5
votes
1answer
434 views

A logic that can distinguish between two structures

it's known that there are non-isomorphic structures that satisfy the same first-order sentences. Likewise it's known (by cardinality arguments) that there are non-isomorphic structures that satisfy ...
1
vote
2answers
193 views

$\exists$- introduction rule

My reference is "A Course on Mathematical Logic" by S.M. Srivastava. This question is about a certain inference rule for proofs in first order logic. If $L$ is a first order language and $T$ is a ...
0
votes
1answer
162 views

Substituting terms in place of variables inside formulas

My reference is "A Course on Mathematical Logic" by S.M. Srivastava. I have trouble understanding some points in this remarkable book. Substituting a term in place of a variable in a formula. Why ...
8
votes
1answer
394 views

Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$

I was reading about Ultrafinitism and the denial of existence of $\lfloor e^{e^{e^{79}}} \rfloor$ by ultrafinitists. I am wondering if they were to deny the existence of $\lfloor e^{e^{e^{79}}} ...
7
votes
1answer
205 views

A compactness problem for model theory

I'm working on the following problem: Assume that every model of a sentence $\varphi$ satisfies a sentence from $\Sigma$. Show that there is a finite $\Delta \subseteq \Sigma$ such that every model ...
1
vote
0answers
198 views

Can the reduced product construction generate boolean-valued models?

In model theory, the reduced product construction contains a collection of structures or models, a set I that indexes the collection, and a filter U on I. Ultraproducts are a special case of reduced ...
6
votes
1answer
263 views

Infinite field of characteristic p elementary equivalent to field with transcendental element over prime subfield

I'm trying to show that if F is an infinite field of characteristic p then it's elementary equivalent to a field F' of char p which contains an element transcendental over its prime subfield (the ...
1
vote
2answers
207 views

Model Theory Confusion

In an interpretation, are the domain and the subsets slated to go into the predicate letters, supposed to be well-defined sets? If the Axiom of Replacement is used to define a subset of the domain, ...
1
vote
1answer
185 views

Could wf $\exists x \mathscr B(x)$ be logically valid when wf $\forall x\mathscr B(x)$ is not logically valid?

Could wf $\exists x \mathscr B(x)$ be logically valid? Definitely. For instance, when wf $\forall x\mathscr B(x)$ is logically valid. But, could wf $\exists x \mathscr B(x)$ be logically valid when ...
2
votes
2answers
2k views

Using halting problem to prove undecidable problems

Let $\alpha_1$; $\alpha_2$ be any two different finite binary strings. Let $E_{\alpha_1\alpha_2}$ be the set of all codes of programs M such that M does not distinguish between the input ...
4
votes
3answers
939 views

What are the cases of not using (countable) induction?

In countably infinite union of countably infinite sets is countable the proof has been given, but when as a student I attempted the question, I tried using induction ( later to found it to be wrong ...
1
vote
2answers
173 views

Cofusing partial order “implies”, on logic and that on sets

I feel confused comparing partial order on sets and that on logic. $$x\ge 1 \implies x\ge 0$$ Here we see a smaller set "implies" a bigger set But, if we know three facts, fact1,fact2,fact3, we ...