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
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 ...
2
votes
0answers
21 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
1answer
83 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 ...
0
votes
1answer
18 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 ...
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 ...
3
votes
3answers
110 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 ...
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
vote
1answer
51 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 ...
0
votes
2answers
22 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 ...
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
0answers
27 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 ...
1
vote
8answers
583 views

Are the real numbers really uncountable?

Consider the following statement Every real number must have a definition in order to be discussed. What this statement doesn't specify is how that loose-specific that definition is. Some examples ...
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
33 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 ...
2
votes
2answers
43 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)) \\ ...
1
vote
1answer
69 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
5answers
110 views

Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...
0
votes
1answer
42 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$: ...
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
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
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 ...
-1
votes
0answers
31 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 ...
6
votes
3answers
10k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
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 ...
0
votes
0answers
22 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 ...
4
votes
0answers
76 views

Is there a mistake in the SEP article about Godel's Incompleteness theorems?

The second supplement to the Stanford Encyclopaedia of Philosophy article about Gödel's incompleteness theorems concerns the proof of the diagonal lemma. The author refers to a substitution function ...
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 } ...
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 ...
0
votes
0answers
24 views

Are these two sentences semantically equivalent? [closed]

Suppose the atomic formulas that I've used in this question {P,Q,R} are true. '$P\rightarrow Q$' and '$R$' Given the valuation, those sentences have the same truth values, are they semantically ...
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
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: ...
0
votes
2answers
198 views

Prove/Disprove: For any sets A and B, $(A \cup B)^c = A^c \cap B^c$

After drawing a diagram of this statement, I believe it to be false. However, I'm having trouble approaching how to disprove this. Do I try to prove the negation? Or what else can I do?
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
3answers
288 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: For any relations $R,S$ and $T$ of $\mathcal{T}$, the relations ...
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 ...
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 ...
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.
-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.
2
votes
2answers
96 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
36 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
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 ...
3
votes
1answer
75 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
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 ...
2
votes
2answers
177 views

Are non-standard models always not well-founded?

Are non-standard models of ZF set theory by definition always not well-founded? And it seems it is, because it must be. But then, Wikipedia says that when there is a set that is a standard model of ...
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
43 views

Find some complete theory $U \supseteq T$

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
0
votes
1answer
36 views

Does theory have uncountably many pairwise non-isomorphic models?

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
1
vote
1answer
56 views

Does theory have the smallest model

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
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
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 ...