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)

1
vote
4answers
55 views

Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
1
vote
1answer
17 views

Show that a sequence of elements each realizing an isolated type over the previous realizes an isolated type

I'm trying to prove the following result which seems correct to me, but I'm not sure how to proceed. The proposition is: Let $M$ be a structure, $A\subseteq M$, $(a_1,\dots,a_n)$ be a sequence ...
1
vote
1answer
26 views

Logical form of a set-theoretic statement.

From Velleman's 'How to Prove it' book, there is one statement - written below - of which I don't know how to write the logical form of, and I'm wondering if somebody could write it out. The ...
1
vote
1answer
26 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is define, and its truth values are given by the following table \begin{array}{c|ccc} ...
-2
votes
1answer
34 views

Propositional-Calculus/ Set Theory Proof using Identities [on hold]

$$(\sim P\,\lor \sim Q)\equiv (Q\to (\sim P\,\lor\sim Q))\land ((\sim P\,\lor \sim Q)\to Q) $$ Can someone demonstrate the identity proof here? I've been trying to figure this out, but with no ...
0
votes
1answer
26 views

Translate the following into predicate calculus. State assumed universe of discourse

This is my first assignment on these, so I would greatly appreciate your help. Translate the following into predicate calculus. For each answer, also state the assumed universe of discourse. ...
3
votes
0answers
27 views

Group orderable iff all its finitely-generated subgroups are orderable

I want to proof this specifically using the Compactness Theorem from propositional logic (this is an exercise from Model Theory, Hodges). $G$ orderable means there is a total ordering s. t. $g\leq h$ ...
0
votes
1answer
36 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
0
votes
1answer
11 views

Minimal Model, from formula

{p2 ^ p3 -> p1, p3 ^ p4 -> p2, .... p9 ^ p10 -> p8} Find the minimal model. My professor told me the answer is the empty set, but aren't these minimal models too?: {p1}, {p2}, {p3}, {p4}, {p5}, ...
2
votes
1answer
35 views

Proof using formal deduction, how to introduce a conclusion?

Prove that $(E \land G) \lor ( G \rightarrow F )$ is formally deducible from $(E \lor F)$ where: "$\land$" means AND "$\lor$" means OR "$\rightarrow$" denotes an implication This is what I have ...
3
votes
1answer
31 views

N body computer

Which mathematical questions can be answered with an n-body computer? An n-body computer is an arrangement of n-bodies moving under mutual gravitation that is prepared in an initial state to answer a ...
0
votes
0answers
12 views

Find a formula of predicate logic for not decreasing and increasing sequences

There is a language $L = \{+, s\}$ with "=" + is func symbol behaving like this $(a_0, a_1, ....) + (b_0, b_1,...) = (a_0+ b_0, a_1 + b_1,...)$ s - shifts sequence to the left, i.e $s((a_0, ...
3
votes
0answers
39 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
0
votes
1answer
37 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ [duplicate]

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
0
votes
1answer
47 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) ...
1
vote
1answer
37 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...
1
vote
2answers
36 views

Recall that $ p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this be used as an explanation for how to use proof by contradiction.

Recall that $p \rightarrow \sim q$ is equivalent to $p \land \sim q$, how can this equivalence be used as an explanation for how to use proof by contradiction. I'm having a hard time answering this ...
1
vote
3answers
52 views

How to prove that $A⊆B$ means that $A∪B=B$ [duplicate]

How does one prove that $A⊆B$ means that $A∪B=B$ ? I can understand it in my head but I don't know how you'd put down in logic notation.
0
votes
2answers
36 views

How can I express the NOT in terms of AND, XOR, XNOR [duplicate]

I need to figure out how to express the NOT operator in terms of the operators AND, XOR, XNOR. I need to show that this set is functionally complete, which I'm trying to do by showing that I can ...
0
votes
1answer
13 views

Simplify Conjunctive Normal Form?

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying: (P or Q) and P and (Q or R) and (P or notP or R) and ...
1
vote
1answer
21 views

How can I show that an argument or proposition is valid through logic proof sequence?

I know the logic of proof sequence as I solved many proof problems, I now have one that has been taken my attention for a couple of days and as easy as it may look, I don't seem able to simplify the ...
2
votes
1answer
62 views

Different axiomatizations of set equality

I've seen two definitions (or axioms?) of set equality: $a=b \Leftrightarrow (\forall x : x \in a \Leftrightarrow x \in b)$ $a=b \Leftrightarrow (\forall x : a \in x \Leftrightarrow b \in x)$ That ...
-1
votes
0answers
36 views

Peano Arithmetic and Riemann Hypothesis.

I recently learnt from an MO post that, if the negation of the Riemann Hypothesis is not provable in Peano arirhmetic, then the Riemann Hypothesis is true. But is there any reference of this result ? ...
-1
votes
0answers
38 views

Question regarding tautologies [on hold]

Argue that the collection of tautologies is closed under conjunction, disjunction, implication, and the biconditional.
1
vote
0answers
21 views

How can we prove a statement is provable?

Given a concrete mathematical statement, such as BSD conjecture(https://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture), do we know if it is provable?
1
vote
2answers
49 views

Existance of an (in)finite theory having infinite model

Please help me to study the following simple cases: Let $P$ be a binary predicate symbol. I am trying to find out, if there exists a satisfiable $T$ having infinite models only, for the following ...
0
votes
1answer
18 views

Translation of arguments into symbolic logic

If all men were good, there would be no wars. Some men are not good. Therefore, there will be wars. *I am confused on what sign to use on the some part
0
votes
1answer
23 views

Binary to Gray code using XOR boolean expressions

I have a question which asks to design a circuit to convert from binary to gray code, using a boolean expression. Now I understand you have to use XOR to achieve this. And I understand that XOR ...
1
vote
4answers
35 views

How can this inverse of conditional statement be equivalent?

"A positive integer is a prime only if it has no divisors other than one and itself." The inverse of this conditional statement is : " A positive integer is not prime if it has divisors other than one ...
0
votes
1answer
47 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
1
vote
0answers
16 views

How to solve this equation using semantic equivlence

Hi I am trying to workout the solution to this propositional logic formula using the below semantic equivalence formula but I am stuck. Could someone please help me out. These are the rules ...
0
votes
1answer
60 views

Is it possible to create a software to find formal proofs?

Let's say I have a Hilbert style system, with a few axioms and rules of inference, and I want to find a proof for some formula $\varphi$, is it possible to create an algorithm that would find a proof ...
0
votes
3answers
40 views

How would I translate this sentence into a predicate formula

A dragon is green if at least one of its parents is green I have ∀X⋅dragon(X) ∧ green (X) ⇒ ∃Y⋅childOf(Y,X)∧green(X) Is this correct?
0
votes
1answer
25 views

natural deduction problem using the connective not

I am having problems understanding how the connective not works in natural deduction. We were given the below example but I cannot workout how the lecturer got the values in table. If someone could ...
1
vote
1answer
14 views

Translate quantification into English and give the truth value

The problem is: $\exists x \in \mathbb{R} (x^3 = -1)$ I understand the following: $\exists x$ = There exists an $x$ $\in$ = shows the element before it is a member of a set after it $\mathbb{R}$ = ...
0
votes
2answers
33 views

Find all models of given theory

$\def\imp{\Rightarrow}$I have a theory $T=\{p \imp \neg q, \neg q, r \imp q, r \imp \neg p\}$ over $P=\{p, q, r\}$ I need to find all models of theory $T$. My question is whether I could use any ...
0
votes
1answer
28 views

number of ways of arranging balls so that there are exactly two pairs of green balls

There are $5$ identical red balls and $6$ identical green balls. In how manys we can arrange them so that there are exactly two pairs of green balls. Let red balls be $R,R,R,R,R$ and green be ...
0
votes
1answer
32 views

If a is odd, how do I prove that 3a is also odd?

I know that if something is odd then $\exists k \in \mathbb{Z}: a = 2k + 1$. But what I get is: $n = 2k + 1$ $3n = 3(2k+1)$ $3n = 6k + 3 $ But i can't factor 6k + 3 to give me 2k + 1 ! Any ...
0
votes
2answers
29 views

Triangle Inequality?

I'm having trouble proving the following claim: $\forall a, b, c \in \mathbb{R}_+: T(a, b, c) \Rightarrow [|a − b| < c$ and $|b − c| < a$ and $|a − c| < b]$ Where $T(a, b, c)$ is a ...
0
votes
0answers
46 views

Reference request for a very particular problem solving skill

I want to start with an apology for a very verbose description of my question but if there is a way to cut it down, please let know and I will do so right away. I have been trying to get better at ...
0
votes
2answers
32 views

Discrete Math: Determining if Argument is Valid

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
1
vote
2answers
31 views

Does a statement need to be a biconditional statement to prove by the contrapositive

I am trying to write a proof and was wondering if a then b, the converse if b then a might not be true. This leads me to wonder if the statement needs to be an if and only if statement if it can be ...
1
vote
1answer
40 views

Tautological Proof Help

I've been having some trouble with proving or disproving tautologies. I am very new to proofs and am hoping I am on the right track. The question asks to show that: If ψ → φ is a ...
0
votes
1answer
22 views

Determining if Argument is Valid via Short-Cut Method

I understand there are two ways to determine validity of an argument. The first way is to construct a truth table and if the statement consisting of the premises combined together implying the ...
0
votes
1answer
26 views

How to use natural deduction for introducing implication

I am doing some propositional logic and we learned about the natural deduction rule. Everything was going fine until the rule of introducing implication arose. I am slightly confused as to how it ...
0
votes
0answers
20 views

Are these two formulas theorems in the mendelson system of prop. calc? [on hold]

Are $$((a\rightarrow b)\rightarrow (\neg\neg a \rightarrow \neg \neg b))$$ and $$((a\rightarrow \neg b) \rightarrow (\neg \neg a \rightarrow \neg b))$$ theorems in the mendelson system? I really ...
1
vote
1answer
36 views

Help understanding a particular proof of the compactness theorem for Propositional Calculus.

I've reading through this proof, I don't understand the last part: the claim $\tau \models \Sigma$. Note: I'll use $AP(\varphi)$ and $\text{Var}(\varphi)$ interchangeably, to mean the variables that ...
37
votes
6answers
2k views

Proving the existence of a proof without actually giving a proof

In some areas of mathematics it is everyday practice to prove the existence of things by entirely non-constructive arguments that say nothing about the object in question other than it exists, e.g. ...
0
votes
2answers
28 views

Logical Implication on set of statements

All birds are animals. All animals are four legged. Implications a. All animals which are four legged are birds. b. All birds are four legged c. Some birds are four legged d. ...
1
vote
2answers
28 views

How can I negate this conditional statement? [on hold]

The conditional statement is: If today is February 1, then tomorrow is Ground Hog's Day. I need to negate this but I am confused. Would it just be If today is not February 1, then tomorrow is not ...