# Tagged Questions

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

54 views

### Prove that if $\Gamma$ is inconsistent, then $\Gamma \vdash \beta$ for every formula $\beta$

Considering that $\Gamma$ is inconsistent if $\Gamma \vdash ¬(\alpha \rightarrow \alpha)$ for some formula $\alpha$. How to prove that if $\Gamma$ is inconsistent, then $\Gamma \vdash \beta$? ...
64 views

### Which theorems of classical mathematics cannot be proved without using the law of excluded middle?

The law of excluded middle is a logical principle that says that for any sentence $A$, the sentence $A\lor\,\neg A$ is true. This is a valid law of classical logic, but is rejected by intuitionistic ...
37 views

### How to prove equivalence of different definitions for compactness?

My workbook considers three different definitions for compactness in logic. It says that it can be shown that these are equivalent, but what would be a strategy to show this? I'm familiar with showing ...
25 views

### negating propositional formula with quantifiers

In order to solve an exercise in computer sciences (proving a language $L$ to not be context-free) I need to negate the Pumping-Lemma. I was provided with the definition in the following form: If $L$ ...
20 views

### How to find the best way with the least amount of steps to find the matching hole (2 balls and 100 holes given)? [duplicate]

To extend the heading a little bit further. There are 100 holes ordered from min to max (min-hole with minimal radius, max-hole with maximum radius). There are two balls given which are to be used to ...
70 views

### Proof by mathematical induction (conditional statements)

Suppose we need to prove a statement of the form $$\forall n\in\mathbb{N}(P(n)\to Q(n))$$ where $P(n)$ and $Q(n)$ are propositions using mathematical induction. Say for the base case $n=1$ it is true. ...
34 views

28 views

41 views

### Non model-theoretic, constructive proof that it is valid to introduce new unique constants in a first order theory with equality

I'm currently reading through Mendelson's `Introduction to Mathematical Logic', and one of the proofs has left me dissatisfied. In general, I am fine with seeing metamathematical results proven ...
44 views

### Are these two sentences logically equivalent?

What i'm essentially asking is if the following statement is true: $\forall x \exists y (R(x) \lor Q(y)) :\Leftrightarrow \exists y \forall x (R(x) \lor Q(y))$ where $:\Leftrightarrow$ means ...
34 views

### Confusion about there exist and forall

Which of the following is a correct predicate logic statement for "every natural number has [at least] one successor?" \begin{align*} A: \quad & \forall x\exists y\left(\operatorname{succ}(x,y)\...
24 views

### Logic determine whether a set is consistent

I got a question regarding defining whether a set of formulas is consistent in predicate logic. For example if we have the following sets: ...
89 views

### Definition of “Differentia” in Lewis Carroll's Symbolic Logic?

I am reading chapter $2$, and from what I understand, it seems like the differentia of a class is not well-defined. The book gives some definitions: The class "Things" here refers to the class ...
79 views

### Appealing axioms incompatible with large cardinal axioms

I'm interested to know what are some 'appealing' axioms that are inconsistent with ZFC plus some large cardinal axiom. I saw the question On the contradictory nature of large cardinals & choice-...
25 views

### A lemma for interpolation for propositional logic

I'm working on an exercise for William Craig's Interpolation Theorem for propositional logic, and I'm having troubles proving the following lemma: Let ϕ and ψ be sentences of propositional logic and ...
53 views

### Is there a schsim between classical logic and categorical logic?

I've been trying to learn a little bit more about the foundations of mathematics, and it has strike me that there seems to be two competing points of view about what the foundations should be. While ...