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

Awodey's Category Theory Exercise 9.9.2

I am having problems with this question in Awodey's Category Theory book p.248: Show that every monoid M admits a surjection from a free monoid $F(X) → M$, by considering the counit of the free ...
2
votes
1answer
44 views

Functor between ordered sets.

(a) Let $f : K \rightarrow L$ be a map of sets, and denote by $f^* : \mathscr{P}(L) \rightarrow \mathscr{P}(K)$ the map sending a subset $S$ of $L$ to its inverse image $f^{-1 }[S] \subseteq K$. ...
3
votes
2answers
38 views

Multiple possible interpretation for negation of a statement

For the statement below: One of my two cars was stolen. What is the negation? For me, it seems like there are two ways of interpreting this. First, if we interpret the statement as: $N = $ ...
0
votes
1answer
25 views

Definition of variables in propositional calculus

Let $\tilde P$ be a first order algebra, and consider the definitions below: I'm confused about the very last thing: what $y\not\in V(c)$ means. $c$ has a free variable, so what does it mean to say ...
1
vote
0answers
21 views

If $T$ is a set, $P(x)$ denotes x is a hard worker and $D(x)$ denotes that $x$ is a worker, how to translate the following to English sentence?

So $T$ is a set of workers and materials in a tower, $P(x)$ denotes that $x$ is a hard worker and $D(x)$ denotes that $x$ is a worker $\forall x \in T: [D(x) \rightarrow [\exists y \in T: P(y)]]$ ...
3
votes
1answer
28 views

What is a “prime implicent”?

What is a "prime implicent"? I guess it's also the "prime implicant". The wiki page is too hard for me to understand. Can someone explain it in simpler terms?
1
vote
0answers
34 views

Translate from logical expression to regular expression

I have a type of exercise in which I want to translate a formal logical expression to regular expression. Now my question is, is there a set of rules which I can learn so I will be able to do this ...
0
votes
1answer
33 views

Extension of a theory vs conservative extension

I'm not sure whether I get the difference between extension $T'$ of some theory $T$ and conservative extension $T''$ of this theory. Extension $T'$ of $T$: Language $L\{P\}$ and it's theory $T$ ...
1
vote
1answer
32 views

Logic - Proving or disproving a formula is satisfiable

I want to find out if the formula $\{p\implies(q\land r),(p\lor r)\implies q,\neg r\}$ is satisfiable. (meanings each clause is satisfiable. there is an $\land$ between the clauses. The problem is ...
0
votes
1answer
34 views

Verification of Lindenbaum's Lemma proof for the Mendelson system and a question of maximally consistent sets.

In this proof I will use Mendelson's axiom system (the one in this book). Question 1: Could someone check my work? I feel some parts are a bit hard to see/read, but I think the general idea ...
29
votes
11answers
5k views

Is $[p \land (p \to q)] \to q$ a tautology?

I am new to discrete mathematics, and I am trying to simplify this statement. I'm using a chart of logical equivalences, but I can't seem to find anything that really helps reduce this. Which of ...
1
vote
0answers
37 views

Checking if $p$ tautologically implies $q$

What is the difference between $p\Rightarrow q$ and $p\to q$? Is $p\to q$ a necessary and sufficient condition for checking $p\Rightarrow q$ is a tautology? Are there alternative approaches?
1
vote
3answers
78 views

Propositional Logic- Prove sentences (a) and (b) entail (c)

I'm given three sentences: (a) If Frodo destroys the ring, then the world will be saved. (b) Gollum stole the ring from Frodo or Frodo destroyed the ring. (c) The world will be saved or Gollum stole ...
0
votes
1answer
17 views

Reducing propositional logic statements

I am having some trouble with reducing some propositional logic statements. The first one is as follows: $\neg(P \lor Q) \lor \neg (P \lor \neg Q)$. I used deMorgan's law to change this to: ...
4
votes
4answers
7k views

What is the name of the logical puzzle, where one always lies and another always tells the truth?

So i was solving exercises in propositional logic lately and stumbled upon a puzzle, that goes like this: Each inhabitant of a remote village always tells the truth or always lies. A villager will ...
0
votes
1answer
47 views

writing a formal proof

If B is a statement form involving only negation, conjunction and disjunction, and B' results from B by replacing each conjunction by a disjunction and each disjunction by a conjunction, show that B ...
1
vote
1answer
61 views

Is the definition of recursive function unchanged if we restrict substitution to binary composition?

When defining recursive functions, are the following two statements equivalent?$$f:\mathbb{N}^n\rightarrow\mathbb{N}^m, g:\mathbb{N}^m\rightarrow\mathbb{N}^k \text{ recursive}\implies g\circ f \text{ ...
1
vote
1answer
39 views

Have some trouble proving $(1-x)^n \geq 1-nx$

Here is the question: Prove that $(1-x)^n \geq 1-nx,~\forall n\in\mathbb{N}~and~x\in(0,1)$. My proof by induction: Base Case: when $n=1$, $(1-x)^1\geq 1-1\cdot x$ Induction Hypothesis: $\forall i \in ...
0
votes
2answers
60 views

In the structure $\langle \mathbb{Q}, < \rangle$ which of the ZF axioms hold?

In the structure $\langle \mathbb{Q}, < \rangle$ which of the following axioms hold? How about when we use the weak versions of the axioms (all $\leftrightarrow$ replaced with $\rightarrow$ )? ...
1
vote
2answers
57 views

What is L-implication?

So I'm reading The GUHA Method of Automatic Hypothesis Determination by P. Hajek, and he talks about something called "L-implication". Forgive the stupid question, but what does that mean? I'm not a ...
0
votes
1answer
35 views

Prove that if an existential formula A is satisfiable in a countable structure, then it's valid

Question Prove that if an existential formula A is satisfiable in EVERY countable structure, then it's valid. Proof: My proof is that $B=\lnot A$ is universal so if B is not satisfiable in any ...
1
vote
0answers
22 views

Question in regards to representing propositons with P/~P

In a standard Frege-System does it break any rules to have 'P' stand for, say "Smith is not president"? Is it mandatory that such a statement be represented by '~P', or can it indeed be represented ...
1
vote
2answers
47 views

Can't find a theory which meets conditions

I'm trying to solve this problem. There is a language $L = \{f\}$ with equality (we can use '$=$'), where $f$ is a unary function. Our goal is to decide and prove, whether there is a theory $T$, ...
3
votes
2answers
90 views

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$ Here, a set of formulas is inconsistent means they syntactically imply some formula as well as its negation. ...
0
votes
1answer
64 views

Proof in Propositional Logic of Peirce's Law

How can I proove in Propositional Logic (using only the basic axioms of P.L. and not a valuation function like it's used in Propositional Calculus) that : $\vdash$ ((($\phi$ $\to$ $\psi$ )$\to$ ...
4
votes
1answer
155 views

Can't EF game theory be applied to finite languages WITH function symbols?

Let $\mathcal{M}$ and $\mathcal{N}$ be two structures in a language $\mathcal{L}$. We define the finite determined game $G_n(\mathcal{M},\mathcal{N})$ as a game with $n$ rounds where in each round ...
22
votes
10answers
15k views

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

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
4
votes
3answers
203 views

Vacuous Truth and Universal Conditional Statements

Sometime after I began studying conditional statements, I started having difficulty understanding vacuous truth. For instance, the fact that for any set $A$ we have $\emptyset\subset A$ is commonly ...
0
votes
2answers
46 views

Proving that if $\Gamma \cup \{\gamma\}$ is inconsistent, then $\Gamma\vdash \neg\gamma$.

Definition Let $\gamma\in \text{Form}$. A proof of $\gamma$ is a sequence of formulas $\phi_1,\phi_2,...,\phi_n=\gamma$ where each $\phi_i$ is an instance of an axiom or was obtained by modus ponens ...
0
votes
1answer
943 views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
53
votes
12answers
6k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
2
votes
2answers
60 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let ...
26
votes
2answers
2k views

When writing proofs, is logical notation a crutch?

I'm near the end of Velleman's How to Prove It, self-studying and learning a lot about proofs. This book teaches you how to express ideas rigorously in logic notation, prove the theorem logically, and ...
0
votes
0answers
20 views

Example CNF for FOL

I don't understand this example: $\forall x [\forall y\ Animal(y)\Rightarrow Loves(x,y)] \Rightarrow [\exists\ y Loves(y,x)] \\$. After, I must eliminate biconditionals and implications. In the ...
1
vote
1answer
338 views

Understand Logarithm of Bar values manipulation step.

Currently I am learning Logarithm , but I can't understand the manipulation of the following Highlighted step how it comes How the result come after after ...
7
votes
0answers
111 views

What can the reals of an inner model be?

This is probably a silly question. Call a set of reals $X$ a constructibility ideal (in analogy with a Turing ideal) if $X$ is closed under effective join $r\oplus s: n\mapsto 2^{r(n)}3^{s(n)}$ and ...
3
votes
1answer
102 views

$\sqrt{x}$ is a constant function?

I just "proved" something ridiculous and can't find the fault in my logic. It's probably something really simple and obvious that I'm just overlooking, or maybe not because none of my friends can find ...
0
votes
1answer
52 views

Proof of the deduction theorem explanation

I'm reading through this proof of the deduction theorem, and there are a few things I don't understand. The basic idea is to show that if $\Gamma\cup \{A\}\vdash B$, then we have a proof of $B$ with ...
5
votes
3answers
466 views

Why is it impossible to define multiplication in Presburger arithmetic?

Peano arithmetic defines multiplication recursivly as: $$\begin{gather}a\cdot0=a\\a\cdot S(b)=a+(a\cdot b)\end{gather}$$ Why is this not possible in Presburger arithmetic?
0
votes
3answers
648 views

Find first term and common difference of Arithmetic Sequence, given two other terms

The 7th and 11th terms of an arithmetic sequence are 7b + 5c and 11b + 9c respectively. Given these i want to find the first term (term when n = 0) and the common difference. I tried a lot of ...
0
votes
2answers
68 views

Proof by contradiction in predicate logic

So we are given the following to prove, only by proof by contradiction $\forall x(Q(x)\to P(y)) \vDash \forall xQ(x)\to P(y)$ Now the first thing that comes to mind in predicate logic when i am on a ...
0
votes
2answers
52 views

For all $x$ and some of $y$

Prove that this works for all $x$ and and only some $y$ $$\sqrt{(x-1)^2-(y+2)^2}=0.$$ This is as far as I got so far Difference of squares: $\sqrt{(x-1-y-2)(x-1+y+2)}=0$ ...
0
votes
2answers
45 views

Is it false or it cannot be proven to be true

On a re-reading of D.J.Vellemann's book - "How to prove it" (2nd edition, pg. 69), it reads It should be clear that if $A =\varnothing$, then $\exists x \in A P(x)$ will be false no matter what ...
1
vote
1answer
23 views

How to find a formula that is true for the given model in the First Order Logic?

I think I might get lost in the definitions. I am not sure if this is the right way to deal with models and formulas in the First Order Logic. I am not looking for the solution for this particular ...
0
votes
0answers
48 views

Mr.Smith commute word problem. Solved through logic, where is the argument unsound?

Mr. Smith commutes to the city regularly and invariably takes the same train home which arrives at the his home station at 5 pm. At this time, his chauffeur always just arrives, promptly picks him up ...
0
votes
1answer
23 views

Logical translation with possibly one or two premises

I'm trying to translate an argument into sentential logic. It's of the form $$\text{sentence }1:\text{ } p\\\text{sentence }2: \text{ If so, then } q$$ What I want to know is, do I translate this as a ...
1
vote
1answer
33 views

How to draw a triangle on a sphere surface where each angle has 90°?

The problem statement says this: Explain how to draw a triangle, on a sphere surface, where each of its angles 90 degrees. In this right triangle, do the hypotenuse and the sides (adjacent and ...
0
votes
1answer
29 views

Proving that a certain function is not recursive

Consider the set $R_0=\{+,\cdot,I_<\}$, where $I_<$ is the characteristic function of the 2-ary relation $<$, and for every n let $R_{n+1}=\{p^n_1,...,p^n_n\}\cup R_n\cup C_n$, where ...
0
votes
1answer
19 views

Why these propositional statements are (basically) identical?

I have this two statements: $A$ if and only if $B$. (Not $A$) if and only if (not $B$). One of requests is to determine when these statements are true. Here is what I done: Then, it is also ...
1
vote
1answer
24 views

If a set $S$ is inconsistent, does $S\vdash \alpha$ for all $\alpha$ in this system?

Let $S$ be an inconsistent set of propositional formulas. If our system consists of the axioms: \begin{align} AX1&\quad (P\implies (Q \implies P))\\ AX2&\quad (((P\implies(Q\implies ...