# 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,334 questions
Filter by
Sorted by
Tagged with
1 vote
33 views

### How many satisfiable assignments does the following compound statement have?

I want to count satisfiable assignments to the following compound proposition: $((p→q)∧(¬q∨r)∧(¬s→¬r))→(¬p∨s)$ Is there any particular formula to calculate this? For small compound proposition we can ...
• 4,468
34 views

### Is there a structure or abstraction that genuinely generalizes both field extensions and (Cohen) forcing?

I'm just starting with the topic so I don't know much. But I'm always told that the similarity with field extensions is just an analogy and we shouldn't take it so seriously. However, I just must ask ...
• 1,387
16 views

### Composition of Boolean Functions in CNF

Suppose that I have some $n$ variable Boolean function that is in CNF and has $m$ clauses $$f(x_1,x_2,\ldots,x_n) = (x_1\lor x_2)\land(\lnot x_1\lor x_6 \lor x_7\lor x_3)\land\ldots$$ Now suppose ...
• 3,061
94 views

### Why ‘if not the citizen is ≥ 35’ ≡ ‘if the citizen is not ≥ 35’? [closed]

Baronett, Stan. Logic (5th ed, 2022). For brevity, let "president" be POTUS.         In order to translate the statement “A citizen cannot be president unless the citizenis at least 35 ...
1 vote
69 views

### What is a "Property" and what is "Induction Principle"? - Logic and Structure, Dirk van Dalen

Hello I've had some trouble understanding the following theorem in Logic and Structure, Dirk van Dalen: Let $A$ be a property, then $A(\phi)$ holds for all $\phi\in\mathrm{PROP}$ if (i) $A(p_i)$, for ...
40 views

### What is the difference between the following two types of induction

In Simpson's book, the induction axiom for second order arithmetic is : $(0 \in X \wedge \forall n(n \in X \to n+1 \in X)) \to \forall n (n\in X)$. However, the induction axiom for the subsystem of ...
17 views

### Three-player Avalon (transmitting private knowledge over a public channel)

Players There are total three players split in two teams Team Resistance has two players whose roles are assigned at the start of the game Team Spy has one player Before starting the game Both ...
• 2,032
60 views

### On proofs and their validity [closed]

Why every proof in mathematics is a valid argument, is there a proof of this fact or a logical and satisfactory explanation
34 views

### Find Conjunctive Normal Form of a compound proposition [duplicate]

I want to find CNF (Conjunctive Normal Formula) of the following proposition: $(¬p∨¬q∨¬r)→¬ ((a→¬b) ∨q)$ My attempt: If I use the result that $p→q ≡¬p ∨q$ then $(¬p∨¬q∨¬r)→¬ (¬a∨¬b ∨q)$. Again if I ...
• 4,468
58 views

### Why does universal generalization not prove $\forall x \in X \vdash P(x) \implies \vdash \forall x \in X P(x)$?

I have learnt that if $X$ is any set and $P(x)$ is any proposition defined for any $x \in X$, $\forall x \in X \vdash P(x)$ doesn't necessarily imply that $\vdash \forall x \in X P(x)$. However, I ...
• 3,047
52 views

### Questions on Effectively Denumerable Sets and Universal Programs in Computability Theory

I'm currently reading the book Computability: An Introduction to Recursive Function Theory by Nigel Cutland. I find this book very good, but I have two unresolved questions about it: Definition of &...
• 297
50 views

### Circular definition in propositional logic?

Please excuse me if this question has been raised before - I have absolutely no idea how phrase an appropriately detailed query, perhaps due to how philosophical this is. Consider the definition of a ...
• 139
53 views

### Can we conclude $\forall x \in X Q(x)$ from $\forall x \in X P(x)$ and $\forall x \in X P(x) \implies Q(x)$ here?

Let $X$ be any set, and let $P(x)$ and $Q(x)$ be propositions which are defined for any $x\in X$. Say that we know that $\forall x \in X P(x)$ and that $\forall x \in X P(x) \implies Q(x)$. I want to ...
• 3,047
1 vote
38 views

• 1
1 vote
63 views

### Is My Proof of This Set's Property Rigorous?

I have a set $A$ which is a non-empty set of real numbers, and it does not contain zero. The set $A$ satisfies the following properties: Property $P_1$: For any $x, y \in A, xy \in A$. Property $P_2$:...
• 393
72 views

### Why do we need to show $\lnot \lnot P \implies P$ when justifying proof by contradiction here? Does my proof work without doing this?

I am confused of the justifications I hear for why proof by contradiction works, including the one on wikipedia. I am confused why people say we need the law of the excluded middle, and why Wikipedia ...
• 3,047
60 views

### Did Gödel use the term "mathematical logic" to mean the same thing it means today? [closed]

Today the term mathematical logic usually refers to a part of mathematics that includes proof theory, model theory, set theory and recursion theory, some of which originated with Godel's famous ...
• 51
93 views

### Let $P,Q$ be statements. If $P$ is a false statement, then $P\implies Q$ is true. This convention works perfectly anytime. Why? [duplicate]

I learned the following convention. Convention 1: Let $P,Q$ be statements. If $P$ is a false statement, then $P\implies Q$ is true. Convention 1 works perfectly anytime. Why? For example, ...
• 1,260
161 views

### Intuition behind Gödel's diagonal lemma?

I'm trying to develop a good intuition for how Gödel's first incompleteness theorem works. I think I've got most of it, but there's one step involving a lemma I haven't been able to really get. Here's ...
60 views

58 views

### To what extent can Primitive Recursion perform wellfounded recursion?

Ordinarily, primitive recursive functions are such that each value is recursively defined from the value immediately prior. It's not hard to improve that to several values, by a clever encoding of ...
• 2,211
63 views

### Difficulties with an existence and uniqueness proof

Have been trying to prove this for 2 hours straight. I'm asked to prove that there is a unique $A \in P(U)$ such that for every $B \in P (U)$, $A \cap B = A$. I understand that $A=\emptyset$ satisfies ...
• 33
126 views
+50

### Formalizing a Theory in a Universe and Model vs Universe question

A basic question about a terminology on fondation of set theory: What does it mean to "formalize a formal theory (ie a collection of syntactically welldefined sentences with resp. to some ...
• 7,851
1 vote
100 views

### How do I calculate the points within in a polygon that changes height and width to create a hollow frame shape?

I am using JavaScript to create a shape using clip-path. I have no issues with the code but my issue lies with the math. I can get close to my goal but it fails once the shape's height or width is ...
• 45
168 views

### Metalanguage Integers

In context on set theory & model theory of set theory what does exactly mean "metalanguage integer(s)"? Recall a metalanguage ( where one reasons about object theory phrased in object ...
• 7,851
1 vote
109 views

### Is my proof correct? Suppose $A \cap B \subseteq C \setminus D$. Prove that if $x \in A$, then if $x \in D$, then $x \notin B$

I'm a high school student studying Velleman's How To Prove It without any help from a professional mathematician. I came across this problem in chapter 3 problem 9 and I am not really sure if my proof ...
• 41
23 views

• 119
98 views

### Analytic sets vs recursively enumerable sets

I have long thought (due to my limited knowledge in both subjects) that analytic sets of reals are analogous to recursively enumerable sets of natural numbers: Analytic sets are images of continuous ...
• 562
74 views

### $( A \subseteq B \land B\subset C ) \implies (A \subset C)$ [ proof by quantification theory]

I had a problem to find out the proper quantified sentence to prove this theorem. I saw an answer in this platform and here's the link. But I want to prove the theorem using only logic (I mean ...
192 views

### External Integers and First-Order Formulas in Set Theory

So far I know it is not possible to express the natural numbers $\Bbb N$ in terms of a first order sentence in language from ZFC. More precisely, one can in ZFC prove only it's existence as "...
• 7,851
47 views

### What is the "Godel ordering of algorithms"?

I was reading this paper, and in example 3.8 appeared the ideia of "Godel ordering of algorithm". Does anyone know what is this ordering? I've seen some things about Godel ordering, but ...
• 41