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)

0
votes
2answers
20 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
23 views

Extension of theory

There are two languages $L_1=\{+\}$, $L_2=\{⋅\}$ with equation, where both nonlogical symbols are binary functions. There are formulas: $$φ≡∃n∀x(n+x=x)∧∃n∀x(x+n=x)$$ $$ψ≡∃n∀x(n+x=x∧x+n=x)$$ There are ...
3
votes
0answers
23 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
23 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
32 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
35 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
45 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
52 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
0answers
32 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 \\ ...
0
votes
2answers
88 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
32 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
37 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
83 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
84 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
34 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? [on hold]

$$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
59 views

Which of these arguments is wrong?

a) $x*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
40 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
30 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
111 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
70 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. \ ...
2
votes
2answers
44 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
172 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 ...
0
votes
1answer
27 views

Getting sum of products from products of sum

I need to write the following Boolean expression in the form of sum of products $F(A,B,C,D)= (A+B+C+D)(A'+B'+C+D')(A'+C)(A+D)(B+C+D)$ I just want to know how to deal with the missing letters. Is $ ...
0
votes
0answers
23 views

For what terms t does the evaluation of the goal p(t) terminate

Consider the following logic program: p(b) :- p(b). p(X) :- r(b). p(a) :- p(a). r(Y). For what terms t does the evaluation of the goal p(t) terminate and which ...
-1
votes
1answer
53 views

Proving a Tautology Formally [closed]

I wish to prove: $(\neg p\leftrightarrow q)\leftrightarrow\neg(p\leftrightarrow q)$
0
votes
2answers
26 views

Does $r \implies \neg q$, $q$ give $\neg r$?

In resolution, if we have a premise such as $r \implies \neg q$ and we know that $q$ is true, can we infer $\neg r$? If yes what is the rule called
1
vote
1answer
28 views

How would one derive conclusions from this?

Using only the 18 rules of inference without CP or IP derive the conclusion (x)(Ax ⊃ Bx) (x)(Bx ⊃ Cx) / (x)(Ax ⊃ Cx) As well as when using an Existential Quantifier (x)(Bx ⊃ Cx) (∃x)(Ax & ...
1
vote
1answer
27 views

Using CP prove the truth of a tautology

Having trouble figuring out this tautology using CP and the rules of infrence [P ⊃ (Q ⊃ R)] ≡ [Q ⊃ (P ⊃ R)]
2
votes
0answers
61 views

“constructible but not definable”

T. Jech in his monograph Ch. 18, p. 301 writes "... the set T is constructible, but not definable in L." My guess is that this means that T (a subset of, say, some ordinal) is definable in some ...