Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
1answer
37 views

Please help me solve this tautological proof

I'm studying for an upcoming exam and have run across this tautological proof: $(R\to Q)\to ((J\land\neg K)\to [(J\equiv Q)\lor(K\equiv R)])$ To start this one off, I decided to create two ...
7
votes
1answer
251 views

Understanding the proof of “$\sqrt{2}$ is irrational” by contradiction.

I have some difficulties in understanding the proof of "$\sqrt{2}$is irrational" by contradiction. I am reading it in 10th class(in India) Mathematics book( available online, here ) This is the ...
-2
votes
1answer
41 views

Logic: Conditional Proof

$(G\land H)\to (J\equiv L)$ $(G\equiv H)$ $(H\land\neg L)\lor(H\land K)$ | $J\to K$ I am trying to use a conditional proof to solve this one. So I'm assuming J is true and using that to prove ...
1
vote
1answer
69 views

Proof that using only logical form is valid?

I'm studying logic. One of the fundamental things that I find everywhere is the claim and I'm quoting wikipedia: "The concept of logical form is central to logic, it being held that the validity ...
11
votes
9answers
8k views

If yesterday were tomorrow, then today would be Friday.

(S) If yesterday were tomorrow, then today would be Friday. Question: What day is today? This seems to be an old puzzle, and depending on the interpretations, the answers are Wednesday or ...
0
votes
0answers
21 views

Finding average as well as impact of quantity

I am new to this site, I am basically a developer and stuck at a logical mathematics portion. I have polarity of people sending email, so suppose p1 sent mail and mathematical polarity came out to be ...
-1
votes
0answers
94 views

Is there a universal way to define cartesian product with arbitrary many terms?

Suppose we are working with some set theory where primitives are sets and membership. Starting from that, we can give a prescription to define what it means to be an ordered pairs $(a,b)$. This allows ...
-1
votes
0answers
28 views

Proving conditionals

Let's take a conditional $P\Rightarrow Q$, then its truth table P | Q | P⇒Q | ------------- T | T | T | T | F | F | F | T | T | F | F | T | So in ...
1
vote
1answer
27 views

The logical structure of a certain proof.

Let $x,y,z$ be real numbers with $0<x<y<z<1$. Prove that at least two of the numbers $x,y,z$ are within $\frac{1}{2}$ unit from one another. The proof I'm referring to is this ...
1
vote
3answers
27 views

logic distributivity with only conjunction (or disjunction)

Hi I read real analysis book, but some part strikes me weird.. so far I knew that $$((p\wedge q)\wedge r) \Leftrightarrow (p\wedge (q\wedge r))$$ but the textbook said that $$((p\wedge q)\wedge r) ...
2
votes
1answer
35 views

Logic question requiring axiom of choice

Predicting Real Numbers Regarding the above question, the solutions require creating classes of sequences with representative sequences. How are those sequences constructed? How is it possible to ...
0
votes
2answers
22 views

Translate usual sentence into logical proposition

Let $x$ is the notation of an element of argument domain. Now $Ax$ and $Mx$ is predicate for the sentence that "$x$ is an American", and "x is a man", respectively. I want to symbolize the sentence ...
1
vote
2answers
55 views

Looking for a Great book on Proving, on Mathematical Logic in general

I'm looking for a good/great book on Mathematics. More specifically one that focuses on how I should go about to prove various things, e.g. given equations what are the methods I can use in order to ...
2
votes
2answers
64 views

Why is it false that empty set is not bounded?

'A set S is bounded' is defined by $\exists M >0, \forall x \in S : |x| \leq M$. I know that proof that empty set is bounded. $$\forall x \in \varnothing \Rightarrow \exists M >0, \forall x ...
3
votes
2answers
67 views

Is the following a correct logical proof?

A → (F ∧ P) ~A → (S ∧ R) ~R ∴ P     assume ~P         assume A         F ∧ P ...
0
votes
1answer
32 views

Analyze the logical forms of the following statements?

Analyze the logical forms of the following statements: 3 is a common divisor of 6, 9, and 15. Is my solution correct? Let f(x) stand for 3 is a common divisor of x f(6) && f(9) && ...
0
votes
3answers
46 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 ...
3
votes
1answer
72 views

Is this a typo in Jech's Set Theory?

In Jech's Set Theory, p. 603 in the chapter about Proper Forcing, the proof of Theorem 31.7. In the second but last paragraph, the proof says By Theorem 8.27 (Menas), $\lbrace M \cap \lambda ...
1
vote
1answer
80 views

Difference between model and interpretation

In the book Mathematical Logic by J. Shoenfield, the author uses the concept of a interpretation of set theory to proof consistency results, while the other texts on set theory (e.g. Kunen and Jech) ...
0
votes
1answer
40 views

(Sphere Lemma) Hanf locality Lemma and locally threshold testability

I am reading the proof of Hanf's Sphere Locality lemma for (finite or infinite structures but with bounded degree), and I'm trying to understand the details of the proof! I'm confused with the ...
1
vote
2answers
71 views

Language structure of $\mathbb{R}$ and $L_{\mathbb{R}}$

Ok, so, I'm reading up on some first order logic and am now studying languages and structures. If we define the language $L:= \{0,1,+,\cdot\}$, with $0,1$ the constants and $+, \cdot$ the $2$- place ...
1
vote
0answers
30 views

Does Temporal Logic have undecidable propositions?

In order to avoid being too broad or ill defined let me preface by stating that by a proposition in temporal logic I mean a proposition which uses modal operators (until,next,...). In atemporal logic ...
0
votes
1answer
70 views

Conditional Definition Rule(Theory of Definitions)

I am reading Patrick Suppes' "Axiomatic Set Theory". It defines "Conditional definitions of operations" as follows: An implication P is introducing a new operation symbol O is a conditional ...
2
votes
1answer
38 views

Is there a summary of all rules for each type of logic?

I am learning about rules in logic and type systems and am having to piece together fragments of them from different articles and books, which makes it difficult to see the subtle differences in each ...
1
vote
1answer
31 views

Is ths FOL structure necessarily infinite?

Follow up to question: Formula that's only satisfiable in infinite structures Suppose we have predicates $D$ and $R$ such that : $\exists x: D(x)$ $\forall x:[D(x) \implies \neg R(x,x)]$ ...
2
votes
2answers
60 views

Prove that $\exists z \in \mathbb R\forall x \in \mathbb R^+[\exists y \in \mathbb R(y-x=y/x) \iff x \neq z]$

This is Velleman's exercise 3.4.13: Prove that $\exists z \in \mathbb R\forall x \in \mathbb R^+[\exists y \in \mathbb R(y-x=y/x) \iff x \neq z]$. I am am stuck on that one. Seems like I am ...
5
votes
1answer
378 views

What are some examples of applications of König's lemma?

König's lemma states that given an infinite tree, an infinite path exists, where of course by tree we mean a full binary tree. I found some examples in Logical Labyrinths by Smullyan where he ...
2
votes
1answer
126 views

The largest tile in 2048, groups of 3 variant?

Question closed on SO for being too mathematical, I've re-asked it here. Following the rules of the, as http://arxiv.org/pdf/1501.03837v1.pdf puts it, "slide and merge" game 2048, canonically ...
3
votes
3answers
73 views

On an axiomatic definition of $P\Rightarrow Q$

One thing that often confuses beginners in logic is that $P\Rightarrow Q$ is TRUE when $P$ is FALSE, whatever Q is. One (weak) reason is that we are mostly interested in the case where $P$ is ...
3
votes
1answer
58 views

Proofs as implication and proving implications

I am working through a textbook, on my own, having to do with logic and mathematical proofs, and I have a question about a problem I just completed. Here's the problem: "Suppose $P \to (Q \to ...
3
votes
2answers
58 views

What does it mean to say that a given theory is weak or strong?

In logic (and in mathematical logic) I wondered what does it mean to say that a given theory is weak or strong? To be specific, I am just interested in arithmetics. Thanks!
2
votes
1answer
83 views

What is a Primitive Atomic Formula?

I am reading "Axiomatic Set Theory" by Patrick Suppes and he defines a primitive atomic formula as follows: A primitive atomic is an expression of the form ($v\in w$ ), or of the form ($v=w$) where v ...
0
votes
1answer
53 views

Expression of theorem by $p\Rightarrow q$ [closed]

$\sqrt 2$ is irrational. Is it true that i express this theorem in this way?: If $\sqrt 2$ is a real number, then it is irrational. Is there any better way to express this theorem by $p\Rightarrow q$? ...
0
votes
1answer
53 views

Can Incompleteness be Computable?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
0
votes
2answers
65 views

Proof for $\forall x A \Leftrightarrow \neg \exists x \neg A$

I try to proof, that $\forall x A(x) \Leftrightarrow \neg \exists x \neg A(x)$ I know how to prove, that $\forall x A(x) \Rightarrow \exists xA(x)$, but I don't understand how to get negation.
2
votes
2answers
56 views

Logical Formulation of the Ending of “Ode on a Grecian Urn” by John Keats [closed]

Thanks very much in advance to anyone who can help me on this problem. Here is the well-known conclusion of "Ode on a Grecian Urn" by John Keats: "Beauty is truth, truth beauty,"—that is all / Ye ...
1
vote
1answer
47 views

How to **formally** prove that $(\exists!x)(A(x))\iff(\exists x)(A(x)\wedge(\forall y)(A(x)\wedge A(y)\implies x=y)$

$$(\exists!x)(A(x))\iff(\exists x)(A(x)\wedge(\forall y)(A(x)\wedge A(y))\implies x=y)$$ This is extremely intuitive, there is only one $x$ that satisfies the property $A$ if and only if there exists ...
1
vote
3answers
243 views

Is there any commonality between Math induction and Logic induction?

Logic induction is reasoning by probability. Math induction seems to be related to just Natural numbers and used to prove a statement for every natural number. From these definitions there is no ...
1
vote
1answer
467 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
1answer
31 views

Is this proof using only modus ponens correct?

The mouse is either quick or slow. If it is quick, it will escape the cat. If it is slow, it will take the cheese. If it takes the cheese, it will not escape the cat. A = “the mouse is slow” B = ...
7
votes
2answers
113 views

First-order definition of nonnegative in integers

Given the structure $(\mathbb Z,+,-,\times,0,1)$, what's the easiest way to write "$x\ge0$" in that structure? I know that this works: $$\exists a\exists b\exists c\exists d,a^2+b^2+c^2+d^2=x$$ ...
1
vote
1answer
28 views

How can the composition inference rule be used to prove the correctness of a program split in two segments?

So the basic setup is you have a program segment S and it is split into two segments S1 and S2. You know for a fact S1 is partially correct with respect to initial assertion p and final assertion q, ...
3
votes
3answers
78 views

Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$

Suppose $\mathcal{F}$ and $\mathcal{G}$ are families of sets. Prove that if $\mathcal{F} \subseteq \mathcal{G}$ then $\cup\mathcal{F} \subseteq \cup\mathcal{G}$ My attempt: Given $\mathcal{F} ...
1
vote
1answer
52 views

A mistaken proof of consistent choice?

Given a set of sets ${\cal A} = \{S_i\mid i\in {\cal B}\}$ and a binary relation $Con$ on $\bigcup {\cal A}$, a $Con$-choice on $\{S_i\mid {i\in F}\}, F\subseteq {\cal B},$ is a function $\epsilon\in ...
2
votes
1answer
39 views

Rigor of this direct justification of mathematical induction

Proofs of a mathematical statement or theorem can have different levels of rigor and I have a question about this. In the method of mathematical induction, there are statements numbered with 1, 2, 3 ...
0
votes
2answers
85 views

Show that $A \lor B ⊢ B \lor A$

Prove the following derivability claim using only our primitive rules: $A \lor B ⊢ B \lor A$ I know this can be attributed to the commutative property, but I'm not exactly sure how to prove this ...
1
vote
1answer
35 views

Express $V(\diamond \alpha)$ set theoretically in terms of $V(\alpha)$

I am reading Modal Logic. While going through the basics of the subject I am having problem in a place. Please help me. Say we are dealing with a frame $(W,R)$ and defined a model $M$ using a ...
1
vote
0answers
42 views

Is $\exists x(P(x)\rightarrow\forall y P(y))$ a tautology? [duplicate]

This is from the book by D.J. Velleman-"How to prove it?" Sec 3.5 Excercise 31: Prove $\exists x(P(x)\rightarrow\forall y P(y))$ Suppose the universe of discourse is set of all men. Let statement ...
0
votes
2answers
70 views

Does my insurance company commit Gambler's Fallacy, or do I?

I would not be able to put this into symbols, but I ask here because I think it's the correct place to ask. Would the chance of my parked car getting damaged (bumped or scraped) by other cars parking ...
0
votes
1answer
19 views

Propositional Logic - Conditional Proof

I'm confused doing one problem. The problem is to show that $$(P\vee Q \implies R) \implies (P\wedge Q \implies R)$$ using Rule C.P. What I have done so far: Assumed antecedent of the conclusion as ...