# 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).

17,532 questions
23 views

### How to deduce $\square p\to p$ from other modal axioms?

I'm trying to deduce the T axiom $\square p\to p$ from the B,D,5 (and also K) axioms. B: $q\to\square\diamond q$ D: $\square q\to\diamond q$ 5: $\diamond q\to \square \diamond q$ I tried to assume ...
17 views

### How to name a large number of variables in predicate logic?

What is the most common way of naming a large number of variables in predicate logic? I run out of variables pretty easy in long predicate logic sentences. The simple fact of using a lot of letters ...
37 views

113 views

### Is the following expression unsatisfiable because it is self-contradictory? [on hold]

Expressing Truth directly within a formal system with no need for model theory https://philpapers.org/archive/OLCETD.pdf --- This paper is prerequisite to the following: I am approaching these ...
46 views

### Are proofs by “maximality” equivalent to proofs by induction?

I apologize for the lack of proper terminology; I have zero experience in this field. What I mean by "proof by maximality": One way to show that a set $A$ has a certain property $p$ is to assume ...
13 views

### Show by Resolution that a set of clauses is unsatisfiable

Im trying to show by resolution that the following set of clauses is unsatisfiable: $\{ p(x,f(y)) \lor p(c,z), ¬p(y,f(f(y))) \lor ¬p(c,x) \}$. Now, I know that to show the unsatisfiability I need ...
41 views

### classical logic - rules for quantifiers

I have these formulas of CL: (a) ∀xP(x,x) (b) ∀x∀y∀z(P(x,y)∧P(y,z) → P(x,z)) (c) ∀x∀y(P(x,y) → ¬P(y,x) and I have been trying to prove weather (a),(b) ⊨ (c). First I would use ∀l and then my ...
107 views

### Does every effectively axiomatizable first-order theory have a finitely axiomatizable conservative extension?

There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. However $\sf NBG$ set theory is a conservative extension of $\sf ZFC$ ...
25 views

### Is every degree above ${\bf 0''}$ PA over something close to itself?

The low basis theorem says that there are PA degrees which are low - that is, which satisfy ${\bf a'}={\bf 0'}$. Appropriately relativized, given a degree ${\bf a}$ there is a degree ${\bf b}$ "not ...
26 views

### Puzzle game list problem

I'm working on a puzzle game with pygame and I'm stuck on what seems to be a math problem within my game, and I have no idea what it actually is. So I managed to copy a list of sprites that have ...
18 views

### Could anyone help me with Boole's Expansion Theorem?

I have searched online, and none of the websites I've looked at help me understand the theorem or the proof.
57 views

### About a topological proof of the compactness theorem

I'm trying to prove compactness theorem following this paper https://www.staff.science.uu.nl/~ooste110/syllabi/eric-poizat.pdf. Let $\mathcal{T}$ be the set of all complete theories over a fixed ...
43 views

### Show that there is a formula $F$ such that both $\Gamma \vdash_N F$ and $\Gamma\vdash_N \neg F$. [on hold]

Use the system $N$. Let $\Gamma=\{\neg(B\Rightarrow\neg A), A\Rightarrow \neg B\}$. Show that there is a formula $F$ such that both $\Gamma \vdash_N F$ and $\Gamma\vdash_N \neg F$. Show ...
121 views

### An example of incompleteness?

Is it fair to suggest that the fact a base's symbol which would exist in a higher base but is never truly reflected in the base itself is an example(see below) of incompleteness along the ideas of the ...
40 views

### Is this Modal (bisimulation) contraction correct?

Bellow I define model M=(W,R,V) and Model K=(W',R',V'). Is model K the model contraction (bisimulation contraction) of M? Model M: $W = {a, b, c}$, and $R = {(a, b), (a, c), (b, c), (c, a), (c, b)}$, ...
70 views

### What does this notation mean? $\Phi(x) \downarrow, \Phi(x) \uparrow$

I'm not sure how I am supposed to know this, I have never used notation like this in my previous school. Is this notation logic or is it something I should have learned in math class? What I am ...
3k views

### Why doesn't Gödel's incompleteness theorem apply to false statements?

I've read and heard in lectures that A way to prove that the Riemann hypothesis is true is to show that its negation is not provable. The argument (informally) usually goes like If a ...
35 views

35 views

### Is similar triangles have equal areas a proposition?

Suppose it is a proposition. So we have The conversion proposition is if two triangles have equal areas, then there are similar. The inversion proposition is that if two triangles are not similar, ...
Unique homomorphic extension says that for a freely generated set $X_+$(say generated from set $X$ and set of functions $F$ ), given a map $h: X \rightarrow B$ (where B is a set with a set of ...
Addition Closure (AC). Necessarily, if $S$ knows $p$ and competently deduces ($p4 or 4q$) from $p$, thereby coming to believe ($p$ or $q$), while retaining knowledge of $p$ throughout, then $S$ knows (...