# 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,258 questions
Filter by
Sorted by
Tagged with
23 views

### Foundations of Math - Algebraic Logic

Has there been any recent work using algebraic logic as opposed to set theory or homotopy type theory for a foundation of mathematics?
1k views

### Paradox in Prisoner's dilemma

I have come across a curious paradox concerning The Prisoner's Dilemma Suppose 4 things : prisoners A and B are rather stupid people and decide to use an artificial intelligence program to decide ...
24 views

### Number of lattices over a finite set

I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality. For instance, how many lattices over $\{1, 2, 3\}$ are ...
116 views

### Is my understanding of the definition of a metric space correct?

The definition of metric space that I am using is as follows: Let $X$ be a nonempty set. A function $d:X\times X\to \Bbb R$ is said to be a metric or a distance function on $X$ if $d$ satisfies the ...
27 views

### Is there a propositional proof system that is not known to be simulated by extended Frege?

As far as I know, it's not know yet whether any optimal propositional proof system exists. That means it's unknown whether extended Frege simulates every other propositional proof system. This leads ...
1 vote
62 views

### Proving the Negation of a Formula does not Require the Formula as an Assumption

The following lemma states that if we can prove negation of a Well Formed Formula (WFF) $\alpha$ by assuming the formula itself, then we can do it without such an assumption. Lemma. Let $\Sigma$ be a ...
60 views

### Studying modal logic using category theory

When reading about modal logic, namely general frames and algebras, I've been seeing a lot of potential functors and/or universal properties. Like constructing an algebra with Boolean operators from a ...
1 vote
70 views

### A property of $\lt$ in Primitive recursive arithmetic

In Primitive recursive arithmetic (PRA), we can introduce $\lt$ by introducing its representing function $K_{\lt}$, where $K_{\lt}(x,y) =sg(x+1-y)$. Here "sg" and "-" are the ...
423 views
+250

### Functional completeness over a structure

The set of propositional connectives $\{\wedge,\vee\}$ is of course not functionally complete; correspondingly, the logical vocabulary $\{\forall,\exists,=,\wedge,\vee\}$ is not sufficient for ...
88 views

### in definition of assigment, what's means 'except possibly a'?

in frist-order logic, part of assignments practice represent like this "if 𝜙is ∀𝛼𝜓, where 𝛼 is a variable, then ⊨vℳ 𝜙 iff for every assignment 𝑣' that agrees with 𝑣 on the values of every ...
39 views

1 vote
36 views

### Is this restricted variant of predicate logic decidable, but expressive enough to be encoded by STLC ($\lambda \to$)?

As in the question, is it the case that a predicate calculus with these properties is decidable? n-ary predicates quantifiers finite domain of discourse impredicativity disallowed no function terms ...
34 views

64 views

### Proof-Theoretic Advantages to Using Only NANDs in Infinitary Logics

This question comes out of a question on Philosophy Stack Exchange, and a particular difference of opinion in regards to the initial question stated in 'Is there any major benefit to using NAND in ...
141 views

### Logic behind uniqueness proof [closed]

The standard approach to proving uniqueness of an object, say A is to assume there are two objects A and B and show they are equal. Don't laugh, but I don't understand how this proves uniqueness. Can ...
5k views

132 views

### Why is the Axiom of Choice Necessary in ZFC

Within the framework of Zermelo-Fraenkel set theory with the Axiom of Choice $(ZFC)$, when we considered the method of constructing the set of natural numbers, we regarded it as the smallest inductive ...
### Must both conditions of operator "OR ($\vee$)" be defined in mathematics? [closed]
I am in the process of writing an article and to explain my question, am providing to you a smaller instance of my wondering so that you can understand it, suppose that $A=\{0,1\}$ and that I define ...