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

31 views
+300

### Richardson's Theorem - Simple example

Does anyone know an actual expression $E$ built according to the conditions of Richardson's Theorem that makes the predicate $E=0$ recursively undecidable?
28 views

### Is there a way to simplify the following logic proposition…

Is there a way to simplify the following logic proposition? $$(A \implies B) ∧ ( C \implies D)$$ Thanks!
71 views

### Is there a formal way to show that $X \cap Y \subseteq X$.

The question is in the title. It is trivial that $X \cap Y \subseteq X$. Because $X \cap Y$ only contains elements that are both in $X$ and in $Y$. So every element in $X \cap Y$ is also an element of ...
23 views

### What are m-placed relation symbols and function symbols?

In This Model Theory book, Weiss refers to "m-placed function symbols" and "m-placed relation symbols". Are these just supposed to be functions of $m$ objects and relations between $m$ objects? I'm ...
43 views

### Understanding direct proofs and proofs by cases?

I'm reviewing my book Mathematical Proofs a Transition to Advanced Mathematics and looking to understand things at a deeper level. I will try to explain what I've considered so far in regards to this ...
34 views

### Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
26 views

### model definitions for tautology, contradiction, and connectives quantify too much, no?

Occasionally I come across a definition based on what will happen in all models, for example, that a contradiction is a statement that is false in all models, that a tautology is a statement that is ...
34 views

### Two questions about first order theories having only finite models.

Let T be a consistent theory formalized in the first order predicate calculus, all of whose models are finite and have cardinal numbers less than some positive integer n(T). Is T necessarily decidable?...
97 views

### When is the Law of the Excluded Middle Valid/Not Valid?

Sometimes, you can use the Law of the Excluded Middle (LEM) to validly prove things by contradiction (e.g. irrationality of sqrt(2)). However, at other times, you can not, for example when you have ...
101 views

### What are “words”?

Related but not duplicate. I am reading Classical Mathematical Logic by Richard L. Epstein, page $3$: B. Types When we reason together, we assume that words will continue to be used in the ...
32 views

### Difference between set theory proof and logic proof of complete induction

Set theory proof: Let $\mathbf{A}$ be the set such that $\{0,1,2,...,n\} \subset \mathbf{A} \implies n+1 \in \mathbf{A}$. Our goal is to show that $\mathbf{A} = \mathbb{N}$. To do this, we construct ...
20 views

### Chain of implications shows equivalence of several conditions

In mathematical articles, theorems frequently have the following form: The following (conditions) are equivalent: (first condition) (second condition) (third condition) ... ...
71 views

### Does anyone know a no-nonsense intro to “logic for mathematics” that I can give to a Year 11 student?

I'm looking for material on propositional and first-order logic to give to a Year 11 student that explains how they're used "in practice." For example, I want to be able to write the null-factor law ...
28 views

### Limits to the principle of explosion

In propositional logic, the principle of explosion can be proven in the following way. $\phi \wedge \neg\phi$ (hypothesis) $\phi$ (simplification, 1) $\phi \vee \psi$ (disjunction introduction, 2)...
65 views

### Is there a 'definition' of truth based on sets of true statements?

been thinking a fair bit about how to think about truth recently. I at one point came up with a deficient theory of truth based on provability, and was directed to Tarski's semantic theory of truth ...
82 views

### Can we take definability and existence as primitive notions of a theory?

One of my friend tries to develop an alternative viewpoint of Set Theory. For this he has taken the terms binary relation, set, existence and definability as primitive notions of his Set Theory. After ...
65 views

### How could we formalize the introduction of new notation?

What I am thinking about is how in a textbook/proof/theorem/discussion/definition one states that from now on a new notation will be used in the appropriate scope. Example: Let $V^*$ denote the ...
386 views

### Show that equivalence can be derived

Show that the equivalence $$p \land \neg p \equiv F$$ can be derived using resolution together with the fact that a conditional statement with a false hypothesis is true. [Hint: Let $q=r=F$ in ...
30 views

### How to translate this statement to First Order Logic?

“Thus there exists a pet in this house being a cat or a dog” I am unsure of how this statements should be translated.
85 views

### Is there an error in this textbook about Peano Arithmetic?

I encountered this doubt in an online intro-logic open course offered by Stanford Uni. Under the section 9.4 of this textbook here: http://logic.stanford.edu/intrologic/secondary/notes/chapter_09....
521 views

### Puzzle : Truant List of Statements

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question: The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the ...
59 views

### Olympiad Books for Primary Students

I am a teacher of gifted program in primary school and currently I am developing Olympiad Curriculum (topic-wise) for my students. I have those topics that could need some help in terms of questions: ...
19 views

### Math logic which contains sum

I want say the following sentence in math logic but I don't know how to address the sum in the logic. The sentence is: Correlation(x->y) equals to (For all C as clusters, for all exists members in C ...
659 views

### Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
134 views

8k views

### What is the difference between an axiom and a postulate?

I hear about axioms in set theory and postulates in geometry, but they seem like the same thing. Do they mean the same thing but then are used in different instances or what? Is one word more ...
3k views

### From DNF to CNF

What is the most efficient way to switch from DNF to CNF?.
179 views

### Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?

I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me. In discussing matters around and about the ...
168 views

### Virtues of Presentation of FO Logic in Kleene's Mathematical Logic

I refer to Stephen Cole Kleene, Mathematical Logic (1967 - Dover reprint : 2002). What are the "pedagogical benefits" (if any) of the presentation chosen by Kleene, mixing Natural Deduction and ...
33 views

### Can someone explain to me this logic sentence using entailment?

Can someone please explain me what does it exactly mean? $KB \wedge B^- \not\models\square$ I understand the entailment symbol in this example here : $T \models A$ is if there's no model of $FS$ ...