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)

0
votes
2answers
17 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
22 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
28 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 ...
2
votes
0answers
28 views

Logic problem: “John's safe's passcode'” question from earlier, with more detail [on hold]

The answer and explanations have already been given at its original post (on Facebook) but I'd like to confirm that it is indeed solvable since there are still some parts I don't quite understand. ...
0
votes
2answers
28 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
32 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
25 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
28 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
37 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
16 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
22 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
19 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
31 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 ...
17
votes
5answers
900 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
26 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
23 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 ...
0
votes
1answer
16 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
27 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
70 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
40 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
943 views

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

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
21 views

Significance of rules of inference [on hold]

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
20 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
52 views

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

Prove that if $k$ is any odd integer and $m$ is any even integer, then, $k^2 + m^2$ is odd.
3
votes
2answers
41 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
17 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 [on hold]

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
77 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
33 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
106 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
32 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
41 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
34 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
49 views

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

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
26 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
45 views

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

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 ...
1
vote
1answer
13 views

Can this Boolean expression be simplified any further using the commutative law?

$AB' + B'A + CDE + C'DE + EC'D$ Since $AB' = B'A$: $AB' + CDE + C'DE + EC'D$ Since $C'DE = EC'D$: $AB' + CDE + C'DE$Is this as far as it can be simplified according to commutative law?
3
votes
1answer
80 views

Gödel's Completeness Theorem

A famous paper by Leon Henkin ("Completeness in the theory of types") begins as follows: "The first order functional calculus was proved complete by Gödel in 1930. Roughly speaking, this proof ...
0
votes
2answers
34 views

Can a negation have an inverse?

I have started a middle/highschool level geometry text. The text is warming me up for proofs by going through basic logic, which was introduced alongside Euler diagrams. I am given the following ...
1
vote
1answer
41 views

Every infinite recursive set has a recursively enumerable subset which is not recursive.

Is the above statement true? If so, how do I go about proving it? Another thing: Given two recursively enumerable sets $Q_1$,$Q_2$, I want to prove that $Q_1\backslash Q_2$ isn't necessarily ...
-4
votes
0answers
16 views

Writing formal logical language [on hold]

Translate the following assertions into a suitable formal logical language: If we leave the window open, the water will get in, but only if it rains. If we leave the window open and it rains, ...
1
vote
2answers
29 views

Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent.

I am new in Discrete Math so that I am still not familiar with Logical Equivalent rules. 1) Show that ¬p ∨ (r →¬q) and ¬p ∨¬q ∨¬r are equivalent. My Try: ¬p ∨ (r →¬q) $\equiv$ ¬p ∨ (¬r∨ q) ...
0
votes
1answer
46 views

Propositional function and Rule of Inference

I'm reading Cohen's 'Set theory and Continuum Hypothesis'. In the book, propositional function is defined as follows: If $A$ is a variable letter then $A$ is a propositional function. If $A$ and $B$ ...
0
votes
1answer
35 views

Discrete math: Simplified the following english sentence?

Simplified the following english sentence? It is not the case that overnight lows are not in the 60s or the furnace is running. What I tried is ignore the exactly meaning in the real life. So I took ...
0
votes
1answer
24 views

Propositional Logic with Two Statements

I am given two statements. Letting $s(x)$ denote "$x$ is a car" and $h(x)$ denote "$x$ is manual" I have to formalise the following statements: "Some car is manual" Which I think can be denoted ...
3
votes
1answer
54 views

Is negation introduction derivable in the natural deduction system of intuitionistic propositional logic?

If I have a natural deduction system for intuitionistic propositional logic, is it possible to derive the following rule? $$\frac{\Gamma \vdash \phi \Rightarrow \psi \quad \Gamma \vdash \phi ...
0
votes
2answers
42 views

(Enumerable) set of natural numbers might not be effectively enumerable

It is well known that a set of natural numbers, although trivially enumerable, might not be effectively enumerable. I am trying to understand this fact intuitively. What is the decisive element in the ...
1
vote
1answer
65 views

If a formula $φ$ contains at most one occurrence of any sentence letter, then $φ$ is not a tautology.

If a formula $φ$ contains at most one occurrence of any sentence letter, then $φ$ is not a tautology. The only connectives in my system are $→$ and $¬$. I think I should attempt this by induction on ...