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)

2
votes
1answer
65 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 ...
0
votes
0answers
38 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 [closed]

Argue that the collection of tautologies is closed under conjunction, disjunction, implication, and the biconditional.
1
vote
0answers
22 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
52 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
1
vote
4answers
36 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
2answers
60 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
62 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
41 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
29 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
15 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
47 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
33 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
23 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
27 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? [closed]

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
37 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 ...
45
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
29 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
29 views

How can I negate this conditional statement? [closed]

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 ...
0
votes
1answer
17 views

Direct proofs involving disjunctions

I've just started a logic and proof class, and I'm confused about what we learned. Given a proof of the form $$(P \lor Q) \rightarrow R$$ why is it true that you only have to show $$P \rightarrow R$$ ...
0
votes
3answers
30 views

Help with logical quantifiers

Let $L(x,x)$ be "$x$ loves $y$". Then is the statement: "Nobody loves everybody" equivalent to $$∀x ∀y \overline{L(x,y)} $$
2
votes
3answers
71 views

Trying to prove for all integers: $n \ge 1 \implies \frac{2n+1}{2n+2} \ge \frac{\sqrt{n}}{\sqrt{n+1}}$

Been racking my brain on this one.. I've tried some things but not sure if it flows logically: $\forall x \in \mathbb{Z}: n \ge 1$ $n+2 \ge 1$ $2n+2 \ge n+1$ $\frac{2n+1}{2n+2} \ge ...
1
vote
1answer
43 views

Why doesn't Cantor's diagonalization work on integers? [duplicate]

Why can't you use Cantor's diagonalization argument to prove that the integers are countably infinite? i.e. 1: 12345.... 2: 42345.... 3: 56903... 4: 46234... 5: 23421... etc. Then we could ...
5
votes
1answer
1k views

Which is the most powerful language, set theory or category theory? [closed]

As far as I know, mathematics is written based on a language which can be for example set theory or category theory. My concern is about the power of these languages. How can we realize which language ...
-1
votes
0answers
22 views

Significance of rules of inference [closed]

I was just wondering about the significance of the rules of inference and about Modus Tollens and Modeus Ponens when validity of expressions like p=>q can be checked by checking if p->q or ~p+q is ...
0
votes
2answers
22 views

Can I do universal instantiation on this predicate?

Can I do universal instantiation on the following predicate : $ \forall x\;S(x)\; \lor\; \forall x\;L(x)$ become $S(c)\lor L(c)$ or is it has to be $\forall x\; ((S(x) \lor L(x))$ to be able to do ...
-1
votes
3answers
59 views

Showing $k^2 + m^2$ is odd when $k$ is odd and $m$ is even [closed]

Prove that if $k$ is any odd integer and $m$ is any even integer, then, $k^2 + m^2$ is odd.
3
votes
2answers
42 views

$ x \ge 0\text{ and } y \ge 0 \implies \frac{x+y}{2} \ge \sqrt{xy} $ [duplicate]

The above applies $\forall x,y \in \mathbb{R}$ I've tried: $x + y \ge 0$ $$x + y \ge x$$ $$ (x + y)^2 \ge 2xy$$ $$\frac{(x + y)^2}{2} \ge xy$$ But the closest I get is $\dfrac{x+y}{\sqrt{2}} \ge ...
1
vote
1answer
18 views

Do the inputs to a boolean-function need to be boolean variables?

That is, say we had the following: define a set, $A$, as: $A = \{x,y,z\}$ If we had a function which only takes the elements of $A$ as its inputs, and returns "true" if $x$ is an input and false if ...
0
votes
0answers
18 views

canonical to algebraic form with don't cares [closed]

How do I transform the canonical form of a logic expression to its algebraical equivalent? For example: $$ f(a,b,c) = \sum \{3,7\} = \not abc + abc $$ But what would it look like for: $$ ...
5
votes
2answers
80 views

Is there a first order formula $\varphi[x]$ in $(\mathbb Q, +, \cdot, 0)$ such that $x≥0$ iff $\varphi[x]$?

In the first-order language $\mathscr L$ having $(+, \cdot, 0)$ as signature, it is easy to define a formula $\phi[x]$, namely $\exists y \; x = y^2$, satisfying : $$\text{for all } x \in \Bbb R, ...
3
votes
1answer
36 views

Deducing the compactness theorem from the completeness theorem (in first order logic)

Given that $\Sigma\vdash\phi \Leftrightarrow \Sigma\vDash\phi$, I want to prove: $\Sigma \text{ satisfiable} \Leftrightarrow \text{ every finite subset of } \Sigma \text{ is satisfiable}$. I will ...
1
vote
3answers
121 views

Book on foundational reasoning of standard arithmetics “curriculum”

I am interested in a book that is about arithmetics but the presentation is not just the known to all formulas but the foundational logic behind it. The closest example I can think about is the way ...
0
votes
2answers
24 views

Changing (enlarging) the domain in a Quantified statement

I would like to ask the following. If we have the proposition $$\forall x\in\mathbb{R}^{+}(x^2>0)$$ and we wish to use as a domain the $$\mathbb{R}$$ instead. Is it correct that it will translate ...
1
vote
3answers
35 views

Use logic quantifiers to write…

Use logical quantifiers to write: "Everybody loves somebody sometimes" (Where U=all people) I came up with this but not sure how to type symbols in here. $$\forall x \in U\,: \exists y\in U: x \text{ ...
2
votes
1answer
43 views

algebraic closure is the intersection of all elementary sub-models of the monster

This is a question from an exercise in model theory. Let T be a complete theory, $ \mathfrak{C} $ monster model of T (a $ \kappa $ saturated model of cardinality $ \kappa $ for some large $ \kappa $) ...
0
votes
1answer
37 views

Reasoning ( CSIR NET December 2015)

This question was asked in CSIR NET December 2015. I could not solve this question.Although I know the answer that CSIR posted in their answer key, which is 2. But I cannot understand how 2 is the ...
0
votes
1answer
24 views

Proof of equivalence theorem using equational calculus

I have to show the following theorem: $p\vee \neg p \equiv ((p \vee q)\wedge \neg (\neg p \wedge (\neg q \vee \neg r)))\vee (\neg p \wedge \neg q) \vee (\neg p \wedge\neg r)$ I have proved $((p ...
-3
votes
1answer
50 views

How to prove that $x \leq y$ if $x,y$ are real numbers and $c>0$. (Hint: Use the contrapositive.) [closed]

How to prove that: Let $x$ and $y$ be real numbers such that $x \leq y + c$ for every $c > 0$. Prove that $x \leq y$. (Hint: Use the contrapositive.) I am doing homework on Real Analysis and ...
1
vote
1answer
27 views

How to read predicate formulas

I have just started learning about predicate logic and am having some trouble in figuring out how to actually read the formula as as a sentence. ...
1
vote
1answer
47 views

“If A, then B” True or False? A giraffe with wings is a butterfly. [closed]

HINT: Rewrite the sentence in if-then form. My rewritten sentence: If a giraffe has wings, then it is a butterfly. I know that "if A, then B" is TRUE unless you can find a situation where A (A ...