Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
3answers
41 views

Help with proposition whether it's true or false

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why?
0
votes
2answers
37 views

Simple rewrite of a question to mathematical form

Simple rewrite of a question For all real numbers x with $x^2-3 x+2\leq 0$, $1\leq x\leq 2$ I am trying to put this into a better form, Could someone give me feedback : stands for: "Such that" ...
0
votes
3answers
37 views

Extended Socratic Syllogisms?

I'm not entirely sure where I might ask this, but there is a logic tag, so I guess this fits the budget. I am taking an introductory course on logic, mainly revolving around Syllogisms, or a logical ...
2
votes
1answer
37 views

Flattening quantification over relations

I already asked this question in stack overflow here and somebody suggested to post it here. I repeat the question again: I have a Relation f defined as $f: A \to B × C$. I would like to write a ...
-2
votes
2answers
37 views

Proof of a Proposition in Logic

Is it possible to prove the proposition if $P \land Q \Rightarrow R$ then $P \land R \Rightarrow \lnot Q $ or in other words ($P \land Q \Rightarrow R) \Rightarrow (P \land R \Rightarrow \lnot Q ...
2
votes
1answer
32 views

Consistency vs Inconsistency in a set of sentences: which is more common

I'm curious whether there is any research in the "probability" that a set of sentences in a first-order logic is consistent. Obviously, there are an infinite number of inconsistent sets and an ...
2
votes
1answer
41 views

Is this an upper bound or lower bound?

I came across a probability distribution function in my work, it is however difficult to find in closed form, therefore I am looking to either upper bound or lower bound it. Assuming $a,b,T$ are ...
3
votes
1answer
47 views

Proving $P$ by proving $\neg Q$ and knowing $P\lor Q$

This may sound silly. I used to remember studying this in physics class and I thought of asking it in physics.stackexchange and then later I decided to ask it here itself. Let's say, under some ...
2
votes
0answers
41 views

Extension of theory

There are two languages $L_1=\{+\}$ with equation, where nonlogical symbol is binary function. There are formulas: $$φ≡∃n∀x(n+x=x)∧∃n∀x(x+n=x)$$ $$ψ≡∃n∀x(n+x=x∧x+n=x)$$ There are theories $T_1={φ}$, ...
3
votes
0answers
29 views

Logics for resource control over time

I'm studying proof theory and I've seen that linear logic can be used as a "way" to control resources usage, since by the propositions-as-types it is equivalent to the linear lambda calculus. Is ...
0
votes
2answers
24 views

Propositional formula, consisting of $p, q, r$ is true iff only one of them is true

I have some difficulties in building a formula $\phi(p, q, r)$, which is true iff only one of the variables is true. I suppose that it's reasonably to start trying, using the truth table, but ...
0
votes
1answer
19 views

infinite mape is $k-$colourable if and only if each finite subset of the map is $k-$colourable

Prove: An infinite map is $k-$colourable if and only if each finite subset of the map is $k-$colourable . How to use compactness theorem at this problem? And the compactness theorem says that ...
2
votes
0answers
28 views

$A\cong B$ then $Th(A)=Th(B)$

question: $A\cong B$ then $Th(A)=Th(B)$ answer: $\phi \in Th(A)$ then $A\vDash \phi$ and $A\cong B$ so we have $B\vDash \phi$ then $\phi \in Th(B)$ and $Th(A)\subseteq Th(B)$ and we could prove ...
0
votes
1answer
35 views

show that if $\mathfrak{A}$ and $\mathfrak{B}$ are $L-$structure such that $\mathfrak{A}\cong \mathfrak{B}$ then $\mathfrak{A}\equiv \mathfrak{B}$ [on hold]

show that if $\mathfrak{A}$ and $\mathfrak{B}$ are $L-$structure such that $\mathfrak{A}\cong \mathfrak{B}$ then $\mathfrak{A}\equiv \mathfrak{B}$ answer:$\mathfrak{A}\equiv \mathfrak{B}$ so ...
1
vote
1answer
38 views

is this formula provable in predicate logic? ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1))

"Can you prove ⊢ (∀x)(∀y)(f(x1) = y1 → ((∀z)g(z) = f(x1) ≡ (∀z)g(z) = y1)) in predicate logic? explain." I'm saying no, but I'm not sure why. Is it because it's not a tautology? and how would Godel's ...
0
votes
1answer
54 views

Where does this definition for the free variables of a formula come from?

I am doing some reading about this and I have come across the definition of a free variable. The free variables of a formula, $F V (\varphi)$, are defined by induction on the structure of $\varphi$: ...
1
vote
1answer
58 views

What syntax exists for higher order logic?

I know this is sort of a broad question, but I'm having trouble getting a handle on the syntax for higher order logic, when going from first order logic. Basically I want to be able to do resolution ...
3
votes
1answer
39 views

Existence of two unrelated pairs in a constrained relation

Given two sets $S, T$ and a relation defined by a set of pairs $R \subset S \times T$, such that: $$ \exists \, s_1, s_2 \in S : s_1 \neq s_2 \\ \exists \, t_1, t_2 \in T : t_1 \neq t_2 \\ ...
1
vote
2answers
96 views

Prove $( \lnot C \implies \lnot B) \implies (B \implies C)$ without the Deduction Theorem

The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using ...
0
votes
0answers
33 views

Boolean algebra and boolean subalgebra

I have to prove that set of all dividers of number 210 with appropriate operations forms a Boolean algebra. And describe these operations and create a Hasse diagram. In the secondd part I have to ...
3
votes
2answers
51 views

Proof, is $\lnot p \land \lnot q \vdash p \iff q$?

I have derived the proof to some extent, mentioned below:- $$\begin{array}{rll} 1. &\lnot p \land \lnot q &\text{Premise} \\ 2. &\lnot p ...
2
votes
1answer
38 views

What does not having a first-order frame imply for models?

There are formulas in modal logic which which do not have a first-order frame condition, as stated here (Non-Sahlqvist formulas, Wikipedia). An example is the McKinsey formula for $p$: ...
-1
votes
0answers
32 views

Predicate calculus using inference rule

I am unable to solve the following propositional logic: \forall x : T \dot P(x) \land Q(x) <=> (\forall x : T \dot P(x)) ^ (\forall x : T \dot Q(x)) I need ...
1
vote
1answer
32 views

Mathematical Group for describing the domain of mathematical process

I am trying to follow discussions regarding provability and paradoxes, particularly in the domains of logic and set theory. It is my belief that there is an assumption that any question expressable in ...
3
votes
3answers
84 views

Is there a concise way to notate 'There are exactly 482 x, such that Px…' in logical notation?

My prof has taught us that we can express the proposition $⟦$there are exactly two entities characterized by $P$$⟧$ thus: That proposition looks verbose, despite the fact that it references just ...
0
votes
0answers
23 views

Example of the formula of the arithmetic language [duplicate]

There is arithmetic language $L=\{0, S, +, \cdot\}$ and its standard implementation $N$. Support of implementation is set {0,1,2...}. Could somebody help me to find example of formula $\varphi(x)$ of ...
3
votes
1answer
89 views

A conservative extension

There are two languages $L_1 = \{+\}$, $L_2 = \{\cdot\}$, $L_3 = \{+, \cdot\}$ with equation, where both nonlogical symbols are binary functions. There are formulas: $$\varphi \equiv \exists n ...
2
votes
0answers
37 views

Are tautologies and contradictions analogous to universal sets and empty sets, respectively?

Already read: $\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable? I am learning logic for the first time, about six months after finishing my undergraduate degree. I ...
2
votes
1answer
44 views

How can you negate this sentence?

Suppose claim $P$ is "I know that I don't know you". My gut feeling says "I don't know that I don't know you". One set of lecture notes I have says I need to negate everything in the sentence in a ...
2
votes
3answers
37 views

Proving if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$

This is one of the problem I have been solving in Velleman's How to prove book: Prove that if $A \subseteq B$ and $A \nsubseteq C$ then $B \nsubseteq C$ This is my solution: Suppose $A ...
1
vote
1answer
35 views

Translating an English statement to its logical equivalent

Translate the sentence to its logical equivalent: There are at least three people who are TA’s and have not taken the class The domain is the set X. You may use the functions S(x), meaning that “x ...
-2
votes
0answers
30 views

Which of these arguments are not identical in N? [closed]

$$A) p(x): x+2=5, q(x): x=3$$ $$B) p(x):(x-1)/3=x, q(x): x-1=3x$$ $$C) p(x): x^2-16=0, q(x): (x-4)(x+4)=0$$ $$D) p(x): x^2-4=0, q(x): x=2$$ I think they are all correct.
0
votes
2answers
69 views

Which of these arguments is wrong? [on hold]

a) $x\cdot y=0$ $\implies$ $x=0$ or $y=0$ b) $x=3$ $\implies$ $x^2=9$ c) $x^2<x$ $\implies$ $x<1$ d) $x>1$ $\implies$ $\frac{1}{x}<1$ I think they are all correct.
3
votes
1answer
42 views

Combinatorial Problem about putting foxes in a $n\times n$ table

Let $n$ be an integer with $n\geq 2$. $k$ foxes are put into $n \times n$ table, and each $1 \times 1$ square has at most $1$ fox. They are put in such a way that each $2 \times 2$ table has exactly ...
0
votes
1answer
37 views

Silly Question on Excluded Middle

This is perhaps a silly question, but here it is. As I understand, the law of excluded middle is Aristotelian, and is typically written $P \vee \neg P$, or in vernacular that a given statement is true ...
2
votes
1answer
41 views

For any propostional sentences $a,b,c$, if $a\models (b\wedge c)$, then $a\models b$ and $a\models c$

I'm having a hard time dealing with the $\models$ symbol. I don't really know how to reason through or manipulate these equations to prove why or why not the result holds. Another similar question is: ...
2
votes
0answers
31 views

Predicate Logic Interpretation/Modelling help

I'm having trouble creating models for predicate logic statements. I am going to give an example, I hope you guys can help me out. $$\forall x(P(x) \text{^} Q(x,a) \to Q(x,b) )$$ Let $M_1$ be the ...
2
votes
2answers
97 views

Is “It is raining or it is not raining.” a tautology?

Is the following proposition a tautology: "It is raining or it is not raining." I is obviously always true, so one thinks that it should be a tautology. However, i thought a tautology has free ...
0
votes
1answer
25 views

Question on Logic in translation

let $P,P'$ two affine subspace of $R^{3}$ have we equality between this two statement $$\exists\ u_{0}\in R^{3}\ \mbox{such that } t_{u_0}(P)=P'$$ $$\exists B,A\in PP' \mbox{such that } ...
3
votes
1answer
43 views

Model of Robinson Arithmetic but not Peano Arithmetic

I am curious how can structure of with linear successor function that do not admin induction looks like. In other words I would like to see structure of Peano Arithmetic without induction. I believe ...
3
votes
1answer
76 views

The Lowenheim-Skolem theorem does not hold for $\mathfrak{L}_{II}$.

In "Mathematical Logic" second edition written by H-D Ebbinghaus, J.Flum and W.Thomas, in chapter 9 "Extensions of First-Order Logic", page 140, in the prooof of theorem 1.5 (The Lowenheim-Skolem ...
3
votes
3answers
113 views

If $B$ is a model for the set of positive consequences of $\Gamma$, then there's $A \subseteq B$ such that $A \models \Gamma$

I'm working through Chang & Keisler again and got stuck on the following exercise (1.2.14) about propositional logic. First, consider a set $\mathscr{S}$ of sentence symbols of arbitrary ...
1
vote
1answer
71 views

Easy question on Logic and Modes Ponens

I got confused with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ 3. \ ...
3
votes
2answers
46 views

Super Simple question on Logic and Modus Ponens

I am totally mixed up with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ ...
0
votes
1answer
23 views

de morgan's law for greater and less than

Suppose that we let $!$ mean not (negation) and let $a,z,p$ be integer variables. We have the expression. $$! ( (a>7) \& (z<=p) ) $$ and we can solve it by De Morgan's laws to yield: ...
0
votes
1answer
38 views

two place predicate logic

Im trying to prove following,as lecturer did not have time to go through the proof on the lecture, I wonder how to solve at least the first statement $$(\forall x)(\forall y)L(x, y) ≡ (\forall ...
0
votes
0answers
25 views

Notation for selectors

I hope there is some agreed notation for this. The idea is very similar to DOM (or CSS) selectors, but on mathematical (or logical) formulas. I'll explain this with an example. Imagine I have some ...
2
votes
4answers
175 views

The Order of Mixed Quantifiers

How can we derive the implication: $$ ∃y∀xP(x,y) \implies ∀x∃yP(x,y) $$ In other words, when quantifiers in the same sentence are of the same type (all universal or all existential), the order in ...
0
votes
1answer
30 views

Skolem Function and one Exam Challenge [closed]

we know if P implies Q (and show it by $P \Longrightarrow Q$ ), The Predicate Q is weaker than P. i want to check it which of the following is weaker than others? F1 is a Skolem function and F2 is a ...
0
votes
1answer
30 views

How would you solve these similar logic problems?

I'm not sure how to derive the conclusion from this problem (x)(Ax ⊃ Bx) Am & An / Bm & Bn As well as a similar problem with a disjunction instead of a conjunction (x)(Ax ⊃ Bx) Am v ...