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

learn more… | top users | synonyms (1)

4
votes
2answers
70 views

Non existence of Prime models

Let $L$ be a countable language. Let $T$ be a complete $L$ theory. We know that if $T$ is small, then there is a prime model of the theory. But $\text{Th}(\mathbb{N},+,\times,0,1)$ is not small but it ...
0
votes
0answers
13 views

Show that if X implies Y is valid, then X is unsatisfiable or Y is valid

How can I show that if X and Y are two formulas with no propositional variables in common, and (X ⇒ Y) is valid, then either X is unsatisfiable or Y is valid (or both). I know that (X ⇒ Y) is false ...
0
votes
0answers
32 views

Every Logical Expression is either a Tautology or Contradiction

The question ask if the above claim is True or False. if true I Must prove that and give a counter example if it is false. I prefer the claim to be false. since looking at every logical expression ...
0
votes
1answer
26 views

Showing a relation is primitive recursive, recursive, or semirecursive.

I am not sure what strategy to use to I should use to show this is primitive recursive. I believe I am to show all three cases: primitive recursive, recursive, and semi-recursive. The diagonal of ...
0
votes
2answers
17 views

Building a truth table for the following expression, confused on comma's within the expression.

{A $\rightarrow$ B, (C $\rightarrow$ A $\lor$ B), C} $\models$ B I'm confused on the commas and what their meaning is here. In my truth table, am I to OR them all together?
1
vote
1answer
30 views

Does False Entail True, and Vice Versa?

I have these two statements: False $\models$ True Reads as : False logicially entails True if all models that evaluate False to True also evaluate True to True. True $\models$ False Reads as : ...
2
votes
3answers
58 views

About definition of model

In Model theory, the definition of a model is a set. Can it be a proper class? ZFC has a model and maybe some models is a proper class. Definition of a model needs to include a proper class. Is it ...
0
votes
0answers
83 views

Gödel's incompleteness theorem applys to ZFC theory

When I assume ZFC's consistency, it is impossible to prove ZFC's consistency in itself from Gödel's incompleteness theorem 2. If ZFC's consistency have done, its proof need to be done in stronger ...
2
votes
0answers
82 views

How can I understand about ZFC and Gödel's Completeness theorem [closed]

English 1 ZFC could be formulated as First order logic. 2 Gödel's Completeness theorem is a theorem within ZFC. 3 I think a lot of books about set theory is implicitly assuming Gödel's ...
1
vote
1answer
86 views

What book on Set Theory is best to understand motivation for axiomatization?

I am Master of Science in ICT, and I had always been in loved in math. On University we haven't been doing any Foundational Mathematics, the closest being Automata Theory and mention of Church-Turing ...
0
votes
2answers
55 views

Differentiating between standard and non-standard interpretations of 'less than' relation

Take a relation $R$. In Structure $A$, $R$ is interpreted as the 'less than' relation (for natural numbers). In $B$, $R$ is interpreted as a relation (for natural numbers) where $R(a,b)$ holds if and ...
-1
votes
1answer
26 views

Determine whether or not( (x+y+z)==(p+q+r) and E1==E2 and (x!=p or y!=q or z!=r))

there are two number E1 and E2 $$E1=Ax + By + Cz \quad\mbox{and}\quad E2=Ap + Bq + Cr$$ Value of $A,B,C$ are different and positive integers. Value of $x,y,z,p,q,r$ may be same and they are ...
0
votes
1answer
23 views

reduce (p v ~q) ^ (~p v ~r) using equivalences

can the law of distribution be used in the following way: $$(p\vee \neg q)\wedge (\neg p\vee \neg r)$$ $$(p\vee \neg p)\wedge(\neg q\vee \neg r)$$ $$\top\wedge (\neg q \vee \neg r)$$ True
0
votes
1answer
35 views

show ((p → q) ^ (r → s) ^ (p v r )) → (q v s) is a tautology

I have tried the following but then got stuck: I apply the implication rule to the first two elements: ((~p v q) ^ (~r v s) ^ (p v r)) -> (q v s) Then again to the entire equation: ~((~p v q) ^ ...
0
votes
1answer
62 views

Formal deduction proof of predicates

I am trying to proof equality is transitive, that is, $\emptyset \vdash \forall x \forall y \forall z ((x=y) \land (y=z) \to(x=z))$ using formal deduction (17 rules) and also other rules (ex. To ...
1
vote
4answers
40 views

Show that the intersection of any two intervals is an interval

So i've come across this question, with a follow up question of showing that the union of any two intervals need not be an interval. I don't see how this could possibly be the case. The general ...
3
votes
2answers
53 views

The textbook's way of deriving a natural deduction proof of $\vdash((\phi\leftrightarrow\psi)\leftrightarrow\phi)$ feels wrong.

The problem is "Show that if we have a derivation $D$ of $\psi$ with no undischarged assumptions, then we can use it to construct, for any statement $\phi$, a derivation of ...
0
votes
1answer
43 views

Truth table for logically equivalent questions

I am a bit confused about this truth table that I have copied down during my lessons. The question is Use a truth table to determine whether the statement (P→Q)∧(Q→P) is logically equivalent to ...
0
votes
1answer
15 views

How do I derive a proper natural deduction proof for $\{(\phi\leftrightarrow(\psi\leftrightarrow\psi))\}\vdash\phi$?

I tried to derive a natural deduction proof for the sequent as below, but it feels wrong. Below is the latex code. How should I prove this correctly? ...
0
votes
0answers
102 views

What kind of Properties are Allowed in the Schema of Comprehension?

Studying an introduction to set theory, we were presented with several axioms as the Axiom Schema of Comprehension and the Axiom of Infinity. This last aximom allows the definition of the inductive ...
37
votes
3answers
4k views

Can proof by contradiction 'fail'?

I am familiar with the mechanism of proof by contradiction: we want to prove $P$, so we assume $¬P$ and prove that this is false; hence $P$ must be true. I have the following devil's advocate ...
0
votes
1answer
27 views

Construct an injective function $f:[a,b]\times[c,d]\rightarrow\mathbb{R}$ for some $a,b,c,d\in\mathbb{R}$

Let $a,b,c,d\in\mathbb{R}$ such that $a<b$ and $c<d$ be given. Construct an injective function $f:[a,b]\times[c,d]\rightarrow\mathbb{R}$. My intuition is to construct a function ...
0
votes
0answers
13 views

(Complexity) Subset of set of premises and the entailment problem

I've a finite set of propositional formulas $\Gamma$ and a logical conclusion $\psi$ over variables $X$. The following decision problem arises: Does a cosistent subset $\Gamma' \subseteq \Gamma$ exist ...
0
votes
0answers
62 views

What does superscript false mean?

I was reading a blog post and found a logic statement that read as so: $ k^⊥ → k$ Do anyone know what is mean by this statement? (I read it here: ...
-1
votes
1answer
23 views

Proof using mathematical induction

This sum appears to be proved by using mathematical induction. As usual it it's easy for n=1 but i can't prove that for n=k+1. Help me
0
votes
0answers
13 views

Prove that there is a syntactic equivalence for a formula with repeated occurrences of a quantifier

A formula $A$ has repeated occurrences of a bound variable $x$, if $Qx$ appears more than once in the sub-formulas of $A$. Here $Q \in \{∀,∃\}$. Prove that there exists a formula $B$ which has no ...
1
vote
2answers
41 views

Does defining a type of mathematical object require defining a binary relation of “equality”?

I'm trying to determine whether defining a type of mathematical object requires us to know what we mean by another object being "equal" to it. For example, when we define a type of object like set, ...
5
votes
0answers
97 views
+50

Injections between distinct models of the simply typed lambda calculus

Let a model of the simply typed lambda calculus be a Cartesian-closed functor from $C_T$ to Set, where $C_T$ is a free CCC (as in e.g. this reference, p. 83.) The simple case of one or two primitive ...
2
votes
2answers
27 views

Predicate Logic: Distinguishing structures in the first-order language having only multiplication

I am attempting to distinguish the below structures under the multiplication function. As of right now I have determined the following: <N, ⋅>|= ∃z∀x∀y ((x-x=z)∩(y-y=z)) (xy ≥ z) ...
1
vote
1answer
51 views

HPC: Prove that $\vdash A\to \lnot\lnot A$

Prove that $\vdash A\to \lnot\lnot A$ By Deduction Rule we know that it is sufficient to show that ${A}\vdash \lnot\lnot A$ I am also familiar with the formula: $\lnot A \vdash (A\to B)$. So if ...
0
votes
1answer
31 views

what is prove the method in reversing the operation symbol in DeMorgan's law?

For instance, Taking the second DeMorgan's law of set, which we mostly prove as: (A U B)' = A' ∩ B' ...
2
votes
2answers
79 views

Valid inference in first-order predicate logic

I should prove for the following premises and conclusion if the inference/conclusion is valid by using general resolution for clauses. The conclusion is valid if it is possible to derivate a ...
1
vote
2answers
44 views

Modus Tollens Proof

I came across the following proof in the book Logic, by Paul Tomassi: (P & Q) → ~R : R → (P → ~Q) According to the author, the proof should be a simple application of modus tollens. The following ...
1
vote
0answers
16 views

Prove that $\{Tri, \lnot \}$ is not functional complete

Let the function $Tri(p,q,r)$ which returns $t$ if and only if at least 2 out of 3 input variables are $t$. Prove that $\{Tri, \lnot\}$ is not functional complete. I'd be glad for help, because ...
0
votes
2answers
19 views

Proof by Contrapositive (with 'and' statement)

I just wanted to make sure that my logic here is not faulty. Up till now I've generally avoided contraposition proofs and worked only with contradiction (since we may rephrase the former in terms of ...
3
votes
2answers
59 views

How is “$A$ generalizes $B$” formally defined?

This might look a bit silly but I was trying to find if there is specific symbol/formalization in logic to describe "$A$ generalizes $B$". At first I though simply about using implication, because it ...
0
votes
1answer
73 views

Developments from Charles Peirce's logic diagrams?

These last weeks I have been revisiting Charles Sanders Peirce's logical or thought diagrams (what he called, alpha, beta and gamma diagramms) and I found many of them highly interesting. Some ...
3
votes
3answers
125 views

Proofs of the form $(P\lor\neg P)\implies Q$

Suppose I have a statement $S$ along with two contidtional proofs: A proof that the Riemann hypothesis implies $S$, and Another proof that the negation of the Riemann hypothesis also implies $S$. ...
2
votes
1answer
26 views

property about truth tables

Is the question "show that any truth table is same as the truth table for some wff built from $\neg,\implies,\iff$ only" the same as asking show that any wff is logically equivalent to some wff built ...
1
vote
1answer
33 views

Prove/Disprove a claim in logic

Prove/Disprove: $A, B$ are two formulas without common variables (meaning, $p$ is a variable of $A$ iff $p$ isn't variable of $B$, and vice-versa) and $\vDash A\to B$. Then, at least one of the ...
1
vote
1answer
25 views

Weighted average of multiple weighted factors

Lets say a factory machine runs as follows: Day 1: $3$ widgets per minute $\times 1000$ minutes $\times 1$ kg per widget $= 3000$ kg. Day 2: $5$ widgets per minute $\times 800$ minutes $\times 1.5$ ...
0
votes
0answers
34 views

I want clear a point about definitions. [duplicate]

I want know wether "defnitions" are if and only if. For example if a set satsfies all four group axioms we say it is group but then we go other way also. thank you.
0
votes
1answer
27 views

Prove/Disprove the logical implication

Let $$(p\land q)\to r, d\to p, d\to \lnot r \implies \vDash \lnot q$$ Disproving: we choose $d=f$. Therefore, $p=f, r=t$. Hence, since $(p\land q)\to r = t$ then it must be that $(p\land q)=t$. ...
0
votes
0answers
19 views

A logic circuit simplification and boolean algebra question

Here is my logic circuit Hey guys, I have a question that I'm working on for 2 days but I couldnt find a way out. The question is : Determine a boolean function F(x,y,z) and reduce F using boolean ...
0
votes
1answer
31 views

If $f_1, f_2, f_3,\ldots$ is the Fibonacci sequence proof $f_1^2 + f_2^ 2 + \cdots + f_n^2 = f_n f_{n+1}$. [duplicate]

I'm assuming this is using strong induction/ regular induction. However, besides the "base case" I'm really confused with the inductive steps in my notes. The inductive steps in my notes use the ...
0
votes
1answer
19 views

How do I prove that $(A \times B) \times C \sim A \times (B \times C)$?

I am trying to prove that $(A \times B) \times C \sim A \times (B \times C)$ but I am stuck. First I defined a function from $f:(A \times B) \times C \rightarrow A \times (B \times C)$, so I defined ...
1
vote
2answers
26 views

Simple existence proofs without bounds

Which is/are the most simple proof/s of an existential statement like $$ \exists x P(x) $$ or $$ \forall x \exists y P(x,y) $$ where the variables rage over the integers, such that the proof doesn't ...
0
votes
1answer
20 views

Why is “necessary p” true in a world when there is no world accessible from it?

So my question is situated in modal logic and everything is defined as usual. I'm reading volume 2 of logic, language, and meaning and on page 24 it says: $V_{M,w_3}(\square p)= 1$ So the valuation ...
0
votes
3answers
73 views

How does logic and elementary set theory work together to prove $A \cup \varnothing = A$?

In How do I prove $A \cup\varnothing = A$ and $A \cap\varnothing = \varnothing$ A proof was given reproduced here: Prove: $A \cup \varnothing = A$ Let $a\in A\cup \varnothing$. Then $a\in A$ or ...
0
votes
1answer
32 views

Trouble solving lambda calculus example

Let $M \equiv \lambda xy.y(xx)$, then what is $MM(\lambda z.M)$. I tried and i got a recursion, but I know the answer should be M. Thanks in advance.