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

Filter by
Sorted by
Tagged with
0
votes
1answer
15 views

Use the quantifiers to give the logical form of the following statement. Also negate it and prove it True or False.

For almost all great enough natural numbers $n$ we have: $$\frac{n-2}{n^2-4n+2}<0.07$$ I am not sure the "for almost all" here. Does it mean there exists great enough n for which the ...
0
votes
0answers
9 views

Converting logical functions to linear equations / hyperplanes

Given the following logical (boolean) functions: $$f(x_1, x_2, x_3, x_4) = (x_1 \lor x_2) \land (x_3 \lor x_4)$$ $$f(x_1, x_2) = (x_1 \land x_2) \lor (\neg x_1 \land \neg x_2)$$ I want to convert them ...
6
votes
0answers
26 views

Is there a space of all finite models?

Let $\mathcal{L}=\{R_i\}_{i \in I}$ be a relational language. There is a natural construction of a compact space of countable $\mathcal{L}$-structures, namely, the space $$ \prod_{R_i \in \mathcal{L}} ...
-1
votes
1answer
17 views

How to construct a construction sequence

How would one go about turning (p_7→¬⊥)↔((p_4∧¬p_7 )→p_1) into a construction sequence? I get that you can break it down into atomic formulas using a 'tree', but where would you go from here? Thanks!
-3
votes
0answers
23 views

how this number system works the examples provided with this thread?

A B 0,0 1 0,1 2 -1,1 3 -1,0 4 0,-1 5 1,-1 6 1,0 7 1,1 8 0,2 9 -1,2 10 -2,2 11 -2,1 12 -2,0 13 -1,-1 14 0,-2 15 1,-2 16 2,-2 17 2,-1 18 2,0 19 2,1 20 1,2 21 0,3 22 -1,3 23 for ...
0
votes
1answer
20 views

If $\forall y\in B, y=h(x)$ where $x\in A$, is it true that $\exists y$ s.t. $y=f(x), x\in A$ for every $y\in B$?

I know it is not great grammar, but is it logically incorrect to say something like If $\forall y\in B, y=h(x)$ where $x\in A$, it is true that $\exists y$ s.t. $y=f(x), x\in A$ for every $y\in B$ Or, ...
0
votes
2answers
34 views

Show non-standard interpretation on language of arithmetic s.t. for any formula, if $\mathcal{N} \vDash F(n)$, then $\mathcal{M} \vDash F[m]$

Let $\mathcal{L}$ be the language of arithmetic. Let $\Gamma$ be the set of sentences true in the standard interpretation $\mathcal{N}$ [natural numbers]. Let $F(x)$ be any formula. Show that if $\...
-6
votes
0answers
56 views

Can we have an approximately unequal sign? [closed]

I may be wrong, but my intuition is that we actually don’t need such sign, because: 1/ Human nature of problem solving & question answering favored equilibria aspects of Mathematics more than its ...
0
votes
1answer
29 views

Logic question with neither, nor help [closed]

I am so confused! Can someone tell me if this means that George is shorter? Neither is Kramer a comic in New York, nor is George not taller than Kramer.
2
votes
2answers
67 views

Am I missing something in the definition of universal generalization?

Today I came across the definition of universal generalization in first-order logic. The definition in my script goes as follows (translated): If we know, that for any element $a \in X: P(a)$ is true, ...
0
votes
0answers
24 views

logic question about conditional statements

Sentence 1: "I will go running only if it is sunny outside........ only if my muscles are not sore. To me this means: Only if my muscles are not sore, THEN (I will go running only if it is sunny ...
0
votes
1answer
48 views

Set-up for the Paris-Harrington Theorem

In his book "Models of Peano Arithmetic" Kaye proves the Paris-Harrington Theorem. He starts off by introducing a "simplification" then proves the short Lemma 14.11 about it (see ...
0
votes
0answers
27 views

What variables are free in this formula?.

So im new to logic and i get really confused on quantifier scope and bound namely what variables occur free in a formula im currently stuck on this one. $$\exists X. (\forall Y. F(X,Y)) \implies G(X, ...
1
vote
2answers
70 views

Is this definition of a function correct?

So im trying to teach myself some logic and how quantifier scope and bound works and I saw the following defintion of a function which left me scratching my head. $$\forall a\in A \exists b\in B:((a,b)...
0
votes
0answers
46 views

Difference between $\mathscr B$ and $\mathscr B[b_1, … , b_k]$ in first order logic.

This is from "Introduction to Mathmatical logic-forth edition" by Elliot Mendelson. In page 60 of the book, it says: A wf is true for the interpretation M (written $\vDash _M\mathscr B $) ...
3
votes
2answers
44 views

Finding contrapositive of a universal statement

For all $x$, if $x^2$ is even, then $x$ is even. The contrapositive to this statement is: For all $x$, if $x$ is odd, then $x^2$ is odd. Why do we ignore the "For all $x$" and not say &...
0
votes
1answer
27 views

Definition of Boolean truth value and its expression in meta theory.

In Bell's set theory book, the statement 'the axiom scheme of separation is true in $V^{B}$(Boolean valued model) for any complete Boolean algebra $B$' is proved in $ZFC$ by fixing arbitrary formula $\...
0
votes
0answers
19 views

Motivation of indicator construction in Kaye

Kaye says the following in his book about models of $\textbf{PA}$ on p. 198: I have no clue what motivates the definition of $f_n(x, y)$. The reference made to Propositions 14.1, 14.2 don't help me ...
2
votes
3answers
77 views

False logic argument

I have to proof the following theorem $$(q ⇒ s ∨ p) ∧ (s ⇒ ¬ t) ∧ (t ∧ p ⇒ r) ⇒ (t ∧ ¬ r ⇒ ¬ q)$$ Proof: Assuming $q ⇒ s ∨ p$, $s ⇒ ¬ t$, $t ∧ p ⇒ r$: $t ∧ ¬ r ⇒ ¬ q$ $⇐ ⟨ \text{Monotony of ⇒ in ...
0
votes
1answer
18 views

Questions about expressing each of the following statements in formal language and negating each of them respectively

I am trying to express the following statements in formal language and negating each of them. The following is my attempted solution. The universe of each statements is the set of real numbers and ...
0
votes
1answer
34 views

Transition from Upper Bound definition for Sets to Sequences using Logical transitions & Set-Builder notation

Upper bound definition for sets: $ M \in \mathbb{R} $ is an upper bound of set $ A $ if $ \forall \alpha\in A. \alpha \leq M$ Upper bound definition for sequences: $ M \in \mathbb{R} $ is an upper ...
0
votes
0answers
25 views

“The maximum of empty set is less than 1”

Is this statement true because the empty set has no maximum element or false because there isn't a specific element you can say is the maximum of the empty set that is less than 1.
0
votes
0answers
30 views

Proof that set $\{0, 1\}^{*}$ of all bit strings are countable? [duplicate]

I can't seem to solve this question, I found similar questions, but I wouldn't consider them exactly the same. Struggle to understand what the asterix means in this situation?
0
votes
1answer
43 views

The difference between validity and entailment in first order logic

I'm a newbie to logic so please forgive me if this is a basic question. I've searched the web and stack exchange but can't seem to find an answer. The book I'm reading on predicate logic (forallx) ...
1
vote
1answer
24 views

Question of finding the weakest proposition

could you help me solve this question? We consider three propositions, $P,Q,R$. We want to find the $R$ that satisfies the following conditions: a) $P\implies R$ , b) $(Q\land R) \implies P$ c) $¬(R\...
4
votes
1answer
83 views

Gödel's Incompleness Theorems and the “Minds vs. Machines” conundrum

As a part of my self-learning about Gödel's Incompleness Theorems, I try to dive a little bit into their different interpretations and (possible) philosophical implications. One that immediately ...
0
votes
0answers
59 views

Is there a notion of “product” that fits this description?

So I want to take an algebraic structure $A$ (given as a set and a function, maybe some relations eventually) and I want to make sure it is (countably) infinite. If it's already infinite, we do ...
1
vote
1answer
76 views

Let $A$ and $B$ be two sets. Then, prove that $A - B = A$ iff $B - A = B$

Can someone help me with this question? Question: Let $A$ and $B$ be two sets. Then, prove that $$A - B = A \Longleftrightarrow B - A = B$$
0
votes
1answer
31 views

Suppose that $\Sigma \vdash \exists x \theta$. Do we then have that $\Sigma \vdash \theta$?

This is a problem from A Friendly Introduction to Mathematical Logic by Christopher Leary and Lars Kristiansen which is in Page number 65. Here's my attempt: Consider a structure $\mathfrak{U}$ and ...
0
votes
1answer
28 views

FOL proofs with IP rule [closed]

What should I do after line 12? Since line 10 is not an assumption I cannot use $\rightarrow I$ rule here
0
votes
2answers
25 views

Counterexample? Equality holds in the Cauchy-Schwarz Inequality iff $\textbf{x} = \alpha\textbf{y}$ for some $\alpha \in \mathbb{R}$

I found this way of expressing that equality holds in Cauchy Schwarz inequality iff $\textbf{x},\textbf{y}$ and are linearly dependent in a book (as an exercise), but I think it is wrong, so there's a ...
2
votes
0answers
34 views

Knowing the answer of $Ax_1=a$ and $Bx_2=b$, can we say something about the solution of $(A+B)x_3=a+b$?

given symmetric invertible matrices $A, B \in \mathbb{R}^{n \times n}$ and vectors $a, b \in \mathbb{R}^n$. Assume we know the solution of $Ax_1=a$ and $Bx_2=b$ and $A+B$ is an invertible matrix. Are ...
-2
votes
0answers
30 views

Mathematical logic Hilbert style proof

Given $~\Gamma , A \wedge B \vdash \textrm{False}~$, show that $~\Gamma, A \vdash \neg B~$
-2
votes
0answers
16 views

proof using axioms derivation in mathematical logic [closed]

prove that $ A \vee \neg B , C \vee B |- A \vee C$ How to prove this axiomatically, hypothesis is clear consists of two formulas. Not sure how to arrive at the result using only axioms
1
vote
0answers
23 views

LTL formula proof for $X (\varphi U \psi) \Leftrightarrow (X \varphi) U (X \psi)$

First of, I know that on Wikipedia there are formulas for this. My question: Is my proof sufficient, if the necessary background knowledge can be expected in a reader? Question: is the following path ...
1
vote
2answers
68 views

strict order property

I wanted to prove that the theory of ordered abelian group has a strict order property. I know by the theory of Kikyo and Shellah we have: a theory is unstable iff it has SOP or NIP and by the : https:...
2
votes
1answer
26 views

What is the Turing degree of truth in the second-order theory of real numbers?

Let $X$ be the set of Godel numbers of sentences in the second-order language of ordered fields which are true in $\mathbb{R}$. Then my question is, what is the Turing degree of $X$? In particular, ...
0
votes
1answer
15 views

Removing Implication in the Conversion of WFF to Clausal Form

I understand the conversion algorithm, my concern is regarding the first step of 'Removing Implication'. Example: In the following figure when one removes implication, the negation comes before ...
0
votes
2answers
33 views

How do you inductively prove a conditional?

I'm very lost here. I thought I understood inductive proofs, but then I was hit with this: 'Prove by induction that if n≥4, then n!≥2^n.' How should I approach solving this?
0
votes
1answer
20 views

What is the difference between WFF and FOPL

I have been studying Artificial Intelligence lately and am a bit confused about First Order Predicate Logic and Well-formed Formulas. What is the exact difference between the two or how are the two ...
2
votes
1answer
56 views

Missing a logic argument

I have to prove $$(q ⇒ s ∨ p) ∧ (s ⇒ ¬ t) ∧ (t ∧ p ⇒ r) ⇒ (t ∧ ¬ r ⇒ ¬ q)$$ Proof: Assuming $q ⇒ s ∨ p$, $s ⇒ ¬ t$, $t ∧ p ⇒ r$ are true: $$q ⇒ s ∨ p$$ $$= ⟨ \text{Contraposition with } p, q ≔ q, s ...
0
votes
1answer
21 views

What is the complexity of this formula?

Keeping in mind the classification of (arithmetical) formulas in the arithmetical hierarchy, and given decidable predicates $P(x)$ and $Q(a,b,c)$, what is the complexity of $\forall x P(x) \wedge \...
-1
votes
0answers
78 views

Determine all number of marbles for which the first player wins

Consider the two-player game that consists of a single bowl of $n$ marbles. The players alternate turns. During each turn, a player can remove $2^k$ marbles, for any $k \ge 0$ of his or her choice. ...
0
votes
2answers
47 views

Unless in a Logic Problem

This is a problem from Kenneth H. Rosen's Discrete mathematics and its applications: Translate the given statement into propositional logic using the propositions provided. You cannot edit a protected ...
0
votes
2answers
47 views

GRE logic problem

So I am confused on the negation of the following: Let $f,g$ be continuous on the reals. Negate the statement: For each $x \in \mathbb{R}$ there exists a $y \in \mathbb{R}$ such that if $f(x)>0$, ...
0
votes
0answers
29 views

Supplementary Video Courses For Proofs

I have a quick question for you today. I just started reading Daniel J. Velleman's How To Prove It (second edition) and I'm having a bit of a tough time on getting through the problems. I am stuck on ...
2
votes
3answers
87 views

Why, when we impose restrictions such as the ones of our physical world, new properties arise? [closed]

Unfortunately I am not and expert mathematician nor a philosopher so I don't have the right words to phrase the concept, but the following example should be able to make the question clear: Take the ...
0
votes
0answers
26 views

If $\phi$ is a propositional consequence of $\{ \gamma_1,\ldots, \gamma_n\}$ then $\Sigma \vdash ((\gamma_1\wedge\ldots\wedge\gamma_n)\to\phi)$

I am reading A Friendly Introduction to Mathematical Logic by Christopher Leary and Lars Kristiansen. This is what I want to prove (and this is not in the textbook): Let $\mathcal{L}$ be first order ...
-1
votes
0answers
24 views

Hilbert style proofs for $ A \vee A \vee $ False $ \vdash B \rightarrow A $ [closed]

Solve this problem by using Hilbert style proof: $ A \vee A \vee $ False $ \vdash B \rightarrow A $ I am following George Tourlakis, Mathematical Logic (2008) Book But not sure how to proceed. ...
-2
votes
1answer
25 views

Pls help me with this logic exercises [closed]

Can someone help me with these 2 excercises please Let P and Q be two propositions. Show that P ↔ Q ⇒ P → Q. Let A, B be two sets. Prove the following: B − (B − A) = A if and only if A ⊂ B

1
2 3 4 5
458