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)

1
vote
0answers
62 views

Why is $\mathsf{Type} : \mathsf{Type}$ a contradiction?

In reading this cstheory.se question and this stackoverflow question, they mention that $\mathsf{Type}: \mathsf{Type}$ is inconsistent. I also understand that Coq has an infinite hierarchy of Types. ...
-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 ...
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 ...
0
votes
1answer
55 views

Boolean formulas over omega automata

I've been reading on omega automata(automata on infinite words) and stumbled upon a definition involving logic which caught me off guard. For example, on Buchi automata the definition I originally ...
-1
votes
0answers
92 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 ...
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 ...
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) ...
3
votes
2answers
59 views

Proving $Y$ such that $Y \cap B = \emptyset$

I have been solving this problem from Velleman's How to prove book: Suppose $B \subseteq A$ and define a relation $R$ on $\mathcal{P}(A)$ as follows: ...
0
votes
2answers
21 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 ...
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 ...
0
votes
1answer
31 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) && ...
1
vote
2answers
54 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 ...
6
votes
1answer
86 views

Do all logics have formula syntax specified by context-free grammar?

I think propositional logic formulas syntax could be specified by context-free grammar with production rule below, where $A$ generates a finite string of $a_0, a_1$ stands for an atomic formula ...
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 ...
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
3answers
45 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
2answers
67 views

Is the following a correct logical proof?

A → (F ∧ P) ~A → (S ∧ R) ~R ∴ P     assume ~P         assume A         F ∧ P ...
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
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)]$ ...
0
votes
1answer
67 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
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 ...
1
vote
1answer
78 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) ...
2
votes
2answers
58 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 ...
0
votes
1answer
52 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$? ...
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
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 ...
2
votes
2answers
51 views

The generalized Axiom of Dependent Choice (DC) - is this a valid generalization?

After studying the axiom of dependent choice, I tried to think of a possible generalization of the axiom that would work in a similar way on infinite uncountable sets: by replacing the binary relation ...
2
votes
1answer
82 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 ...
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 ...
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
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 ...
3
votes
1answer
53 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 ...
2
votes
1answer
52 views

Local isomorphism question in logics

The definition of a local isomorphism between structures: a local isomorphism between structures $\mathcal{A}$ and $\mathcal{B}$ over an alphabet $L$ is a finite relation $$\{ ...
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
111 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, ...
1
vote
0answers
41 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
69 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 ...
1
vote
3answers
27 views

Converting a statement

This is from "How to Prove It: A Structured Approach" by Daniel J. Velleman. In the selected exercise the goal was to negate the statement, but I'm more interested in its form. The statement is: ...
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
3answers
31 views

Difference between these two logical expression

I am trying to solve the following problem: Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate “x has asked y a question,” where ...
-1
votes
1answer
30 views

Find logical errors in the proof

I'm finding it really hard to find the logical errors in this proof. I'm still new at this and trying to learn it. Claim: for all $n$ is in set $\mathbb{N}$(Natural numbers), if $2n+1$ is a ...
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 ...
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 ...
2
votes
1answer
50 views

Integer programming: if a or b then a, b, and c

I'm writing a mixed integer programming (MIP) constraint where my $\color{blue}{\texttt{binary variables}}$ are $a, b,$ and $c$ to meet the following condition: $$ (a \lor b) \to (a \land b \land c)$$ ...
4
votes
1answer
46 views

“There are exactly two values of $x$ for which $P(x)$ is true” formula using logical symbols

Assuming $P(x)$ is true. The statement: "There are exactly two values of $x$ for which $P(x)$ is true" can be rewritten using logical symbols as follows: $$\exists x \exists y[(P(x) \wedge P(y) ...
1
vote
1answer
62 views

Are the logical [equivalence] laws sound and adequate without de Morgan's law?

I need to say whether the system of logical laws made of: Double negation Commutative Associative Distributive Idempotent Implication Contradiction de Morgans Absorption Equivalence is sound and ...