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 ...
17
votes
5answers
891 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
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 ...
1
vote
2answers
45 views

Proof for ∨ distributing over →

I'm am stuggling to prove the following: x ∨ ( y → z ) ≡ ( x ∨ y ) → ( x ∨ z ) After making a truth table, I know that disjunction distributes over implication but I am failing to prove the above ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
5
votes
2answers
84 views

Is there a symbol for ‘equal if defined’

Can anybody recommend a symbol for ‘equal if defined’ as an asymmetric concept? In contexts where one might write down notation for an undefined quantity (such as $1/x$ when $x$ might be $0$), ...
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
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 ...
0
votes
1answer
30 views

choose from implication and logical and in write assertions in first-order logic

I am a student and I get confused in translating some sentence to logic assertion. For example: Joe does not have a lawyer, i.e. is not a customer of any lawyer. The right way to translate is: "For ...
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 ...
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 ...
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$$ ...
5
votes
2answers
6k views

What is the difference between an axiom and a postulate?

I hear about axioms in set theory and postulates in geometry, but they seem like the same thing. Do they mean the same thing but then are used in different instances or what? Is one word more ...
4
votes
5answers
531 views

Is the propositional set countably infinite?

Recently I'm learning logic. Here is the definition from the book "Logic For Computer Science": A countable set $PS$ of proposition symbols: $p_0,p_1,\dots$ The set $\text{Prop}$. propositions is the ...
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)} $$
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
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
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 ...
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, ...
0
votes
1answer
81 views

Modal Logic backward looking modality

For an exercise in Modal Logic I have to solve the next problem, can someone please help? Use generated submodels to show that the backward looking modality (that is, P of the basic temporal ...
8
votes
6answers
4k views

How do the Properties of Relations work?

This is simply not clicking for me. I'm currently learning math during the summer vacation and I'm on the chapter for relations and functions. There are five properties for a relation: Reflexive - ...
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
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
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 ...
6
votes
0answers
114 views
+50

An exercise in Fine Structure of constructible universe concerning projectum patterns

This question assumes some familiarity with Jensen's fine structure analysis of the constructible universe L (https://en.wikipedia.org/wiki/Jensen_hierarchy, ...
-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 ...
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: $$ ...
1
vote
1answer
36 views

Logic - Is it safe to state the following?

say that ∀x∃y in all possible integers (negative integers, 0 and positive integers) is x*y = x is it safe to say that ∃y∀x is also true. If not can someone explain why its not true. The way I'm ...
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 ...
3
votes
1answer
63 views

Is $\exists x \in A ~:~ P(x)$ the same as $\exists x ~:~ x \in A \implies P(x)$

If we wish to convert a statement of the form $\exists x \in A ~:~ P(x)$ into the form of an implication, would the correct conversion be $$\exists x ~:~ x \in A \implies P(x)$$ Thanks
51
votes
19answers
6k views

In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: $$\begin{array}{|c|c|c|} ...
0
votes
1answer
53 views

Finding a truth function

I wanted to find a truth function $f$ if it exists that make the formula below true: $((p\to \lnot(q \oplus \lnot p)) \to (\lnot r \oplus (q \to p)))$ Where the $\oplus$ operator is defined as: ...
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 ...
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
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 ...
2
votes
1answer
60 views

How to convert to disjunctive normal form?

The formula is: $\lnot((s \lor \lnot p) \land (q \land r))$ and what I've done so far is this: $\lnot(s\lor\lnot p) \lor\lnot(q\land r) $ $(\lnot s\land p) \lor (\lnot q\lor\lnot r)$ After this ...
2
votes
2answers
126 views

Proof of $\exists x(P(x) \Rightarrow \forall y P(y))$

Exercise 31 of chapter 3.5 in How To Prove It by Velleman is proving this statement: $\exists x(P(x) \Rightarrow \forall y P(y))$. (Note: The proof shouldn't be formal, but in the "usual" ...
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?
0
votes
1answer
33 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 ...