Questions about logic and 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
1answer
61 views

Write the proposition in words - $\urcorner\left(\forall x P\left(x\right)\right)$

Hi here is the problem and my answer attempt. $\urcorner\left(\forall x P\left(x\right)\right)$ Let P(x) denote, "x is taking a math science course". Domain is the set of all students. Write the ...
1
vote
1answer
35 views

Are these two statements logically equivalent?

Are the statements $D \Rightarrow H \vee S$ and $(D \Rightarrow H) \vee (D \Rightarrow S)$ logically equivalent?
2
votes
1answer
99 views

Why don't we use Presburger's arithmetic instead of Peano's arithmetic?

I was reading about quantifier elimination and discovered the Presburger Arithmetic, the article mentions two points about it: It is decidable, complete and consistent. It omits multiplication ...
3
votes
1answer
32 views

prove that $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ leads to $\Sigma \vdash \phi_1 \wedge \phi_2$.

I try to prove that if $\Sigma \vdash \phi_1$ and $\Sigma \vdash \phi_2$ then $\Sigma \vdash \phi_1 \wedge \phi_2$. Notice that, the ONLY rule of inference of the system is modes ponens and the set ...
0
votes
1answer
42 views

prove this theorem $\vdash (\exists x_i (A\to B)\to (A\to \exists x_i B))$

Here is my thought to prove the theorem we should get $\{\exists x_i (A \to B), A\} \vdash \exists x_i B $ then, I don't know how to process...
0
votes
2answers
50 views

Discrete Math - Determine if the argument is valid

Can you guys please check my work and syntax. Question: Determine if the argument is valid. p $\rightarrow $ q $\underline{\urcorner{q}}$ $\therefore \urcorner$p Answer: T $\rightarrow $ T ...
0
votes
1answer
29 views

Discrete Math - Determine truth value of each proposition

If 3 + 5 < 2, then 1 + 3 $\neq $ 4 Can someone kindly check my work? Let p: 3 + 5 < 2 and q: 1 + 3 $\neq $ 4 (3 + 5) < 2 $\rightarrow$ (1 + 3) $\neq$ 4 8 < 2 $\rightarrow $ 4 $\neq $ ...
0
votes
0answers
81 views

Truth Tables in Real Life

Are truth tables something that can be used in real life, or are they merely something that philosophers would have used? And by real life I mean outside of mathematics. I already know that we use ...
1
vote
0answers
39 views

predicate logic question about finding satisfied formula

Let $f,g$ be binary function symbols, $P$ a binary predicate symbol, $c,d$ constant symbols and let $\mathcal{L} := \{f,g;P;c,d\}$. Consider $\mathcal{R}:=\langle\mathbb{R};+,\cdot;<;0,1\rangle$ as ...
1
vote
2answers
75 views

What are some applications of model theory?

In an attempt to "broaden my horizons", I am taking a class on model theory, which follows this book: http://u.math.biu.ac.il/~dahari/download/Mathematical%20Logic/Elad%2022.pdf Skimming through the ...
1
vote
1answer
36 views

predicate logic proof about not free variable

The question is Prove that $\vdash (\forall x_i(A\to B)\to(\exists x_i A\to B)$ for any formulas A, B provided that the variable $x_i$ does not occur free in B. Can someone help me sketch this ...
7
votes
1answer
338 views

A gameshow logic puzzle

A friend posed this puzzle to me a few months ago, and it has tortured me ever since. The puzzle goes something like this: Suppose you're on a gameshow, and there are three doors: two doors have a ...
5
votes
0answers
58 views

Iterated ultrapowers with arbitrary measures are well-founded

An iterated ultrapower of an inner model $M$ is a sequence $\langle M_\gamma:\gamma\leq\lambda\rangle$ such that $M_0=M$, $M_{\gamma+1}$ is a class of $M_{\gamma}$ using a measure in this model, and ...
0
votes
1answer
61 views

How can I represent a question in first-order logic?

How can I represent a question such as: Which colour turns into white when it is under the sun? in first-order logic? I think that if it was the following sentence: There is a colour that ...
5
votes
4answers
191 views

How can we say two algebraic expressions are “equal” if one is undefined at certain points and the other isn't?

I'm trying to understand why it is that we can say $\frac{x^2-1}{x-1} = \frac{(x-1)(x+1)}{(x-1)} = x+1$ but then have it also be the case that the two functions $f(x) = \frac{x^2-1}{x-1}$ and ...
0
votes
0answers
50 views

Let $T=\{17\}, U=\{6\}, V=\{24\}$ and $W=\{2,3,7,26\}$. In which of these four different universes is the statement true?

sLet $T=\{17\}, U=\{6\}, V=\{24\}$ and $W=\{2,3,7,26\}$. In which of these four different universes is the statement true? a) $(\exists x)(x\,odd\implies x>8)$ b) $(\exists x)(x\, odd\wedge ...
1
vote
1answer
42 views

Is it possible to characterize the theory of Integral domains with first-order logic alone ?

Is it possible to characterize general ring theory with first-order logic alone ? Is it possible to do so for the theory of Integral domains ?
2
votes
1answer
33 views

Partial truth table and proving or disproving tautology

Let $p,q$ be elementry statements and $\alpha,\beta,\gamma$ be statements. (sorry if this is the wrong translation). Prove/disprove: is $p,q\Rightarrow \gamma$ tautology? is ...
1
vote
0answers
28 views

Principal Ultrafilter implies Isomorphic Ultraproduct

Let $\mathfrak{F}=\{X\subseteq \mathbb {N} \mid 17\in X \}$ (Note that $\mathfrak {F}$ is principal ultrafilter) and: Let $\mathfrak{N}$ be the standard model for arithmatic and ...
2
votes
2answers
40 views

Associativity and De Morgan's for more than 2 literals

Do logical operators have meaning when used with more than 2 literals "associatively", e.g.: $(A \land B \land C)$? I.e., are statements such as $(A \land B \land C)$ meaningful, as opposed to $((A ...
0
votes
0answers
18 views

Least finite linear orders with same theory in monadic second order logic.

Today I want to ask a relaxed version of my last question. So if somebody finds a solution to that question he will immediately get a solution for this question here. Question. Let $m<\omega$ ...
1
vote
1answer
27 views

Question about equivalencies when using the existential quantifier

I'm currently in a boolean algebra class, and we are asked if the statement: $$ \exists xM(x) \wedge \exists xD(x) $$ is a proposition. Although I know that it is a proposition, I was wondering if ...
1
vote
2answers
54 views

Help understanding what is asked of me

Is there a "min(a,b)" in math I do not know about? PLEASE DO NOT ANSWER THE QUESTION. I just need to know about "min" and what it stands for so I can figure out the question. Question: Use a ...
0
votes
1answer
61 views

Foundations of math and primitive terms leading to Russells paradox

If the statement "Is an element of" is a primitive term (is not defined/you cant determine its truth) then how do you determine the truth of statements such as "If $x$ is in $S$, then $x$ has property ...
1
vote
1answer
29 views

Logically determining the validity of a statement

I'm having some trouble determining if the following statement may be considered valid. if the apples are on sale, I will buy the apples. the apples are not on sale. ∴ I will not buy the apples. ...
1
vote
1answer
45 views

What is a principal formula??

I am studying structural proof theory by Sara Negri, but I am having a problem, I can't understand what a principal formula is ? When she wants to prove a lemma or a theorem, she divides it into two ...
3
votes
2answers
357 views

Prove that a statement or its negation follows from ZFC

There are several problems which have been shown to be unprovable in ZFC. Has there ever been a case of the opposite? That is, has it ever been proven for some statement $\varphi$ that $\text{ZFC} ...
1
vote
3answers
55 views

Proof by contradiction in Discrete Mathematics

Ok, so my college book is the worst book ever and I can only survive from this site and youtube. Could someone please explain the answer below? I really do not understand the answer and to me there is ...
2
votes
0answers
25 views

What strongly normalizing lambda calculi exist that can be integrated with/as logic?

If I'm trying to implement a logical system for deduction based on propositional reasoning, I can start with predicates and quantifiers and functions to obtain first order logic. I can further extend ...
8
votes
2answers
1k views

Why is there this strange contradiction between the language of logic and that of set theory?

In standard probability theory events are represented by sets consisting of elementary events. Consider two events for which (as sets) $A \subset B$. If an elementary event $x \in A$ takes places then ...
1
vote
4answers
38 views

Using proof by contraposition to show that if $n\in\mathbb Z$ and $3n+2$ is even, then $n$ is even

I have my answer below but there is one step that I am not understanding...and maybe my brain is just not trained to understand it. Prove that if $n$ is an integer and $3n+2$ is even, then $n$ is ...
2
votes
0answers
62 views

$\overline{\mathbb Q}$ and $\mathbb C$ same first order theory

How do you show that $\overline{\mathbb Q}$ (the algebraic closure of $\mathbb Q$) and $\mathbb C$ have the same first order theory over the signature $(0,1,+,\cdot)$?
-2
votes
1answer
42 views

Nullary Arithmetic Product (at Wiki)

In Nullary Arithmetic Product at Wiki, we are given a sequence of numbers $a_1, a_2, a_3\ldots$ The product of the first $m$ elements of this sequence is given there by $P_m=a_m \cdot P_{m-1}$ ...
7
votes
1answer
162 views

$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large) There are $N$ perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the ...
1
vote
2answers
36 views

Basis for infinite-dimensional vector spaces

Let $V$ be a vector space over a field $D$, and $U \subseteq V$ a subset. Prove that the following are equivalent: For each $v \in V - \{0\}$ there exist unique $n \in \mathbb{N}$ and $u_1,...,u_n ...
-5
votes
1answer
47 views

Real in Mathematics Vs Real in Philosophy [closed]

Real is being really analyzed. The two subjects--Mathematics and Philosophy use the term Real. Is there any difference between these two Reals? How can we show their difference using Mathematical ...
2
votes
0answers
62 views

Seeking Feedback on my solution: Maximum area of a triangle inside a rectangle.

I was solving problem 3.3.16 from Paul Zeitz's book "The Art and Craft of Problem Solving." The problem reads Inside a 1 x 1 square, 101 points are placed.Show that some three of them form a ...
1
vote
1answer
39 views

How to proove the following general form of proof

Suppose I have a statement $p(m,n)$ where $m,n \in \mathbb{N}$ that I want to proove. Suppose I have proofs of the following: $p(1,n)$ true for all $n \in \mathbb{N}$. $p(m,1)$ true for all $m \in ...
0
votes
1answer
38 views

natural numbers, square roots, modell

My task is to formulate the statement: "There exists a third root, which is the product of two square roots" in the model $(\mathbb{N}, +,\cdot,=,<)$ Therefore I have to model this: ...
0
votes
2answers
29 views

Logical disjunction truth table

The truth table for a logical disjunction shows that there is only one situation where the result can be false, being when both statements are false. As long as one statement is true, the result is ...
4
votes
1answer
76 views

What's the difference between “unprovable” and “undecidable”?

It seems to me that there is a difference between an unprovable sentence, and an undecidable sentence, but sometimes I have the impression that some authors use the terms interchangeably. In my ...
1
vote
3answers
111 views

Handling division by zero axiomatically

Suppose we define the multiplicative inverse function on real numbers as follows: $\forall{x \in \mathbb{R}}(x \neq 0 \implies x \times \frac{1}{x} = 1) $. Consider this truth table. \begin{array} ...
2
votes
1answer
50 views

Recursively enumerable sets are domain of partial recursive functions

My definition of recursively enumerable set is that it is the language recognized by some Turing machine. I want to show that this definition is equivalent to "a r.e. set is the domain of some ...
2
votes
2answers
62 views

Notation or verbiage for the opposite of 'iff'? [duplicate]

Given the statement $X \implies Y$ and $Y \implies X$, we have the common notation $X \iff Y$. Ok so is there an opposite of this concept? Suppose I have $X$ doesn't imply $Y$, nor does $Y$ imply ...
2
votes
1answer
22 views

Negation of Compound-Statements

If I have the following statements p: It is cold outside q: It is snowing p∧q = It is cold outside, and it is snowing. p∨q = It is either cold outside or it is snowing. If I were to negate p∧q ...
0
votes
1answer
65 views

First Order Logic prove there exists a Model that has an infinite member

I'm doing some extra self-exercises on first order logic (I'm taking the course through open university) and I've come across this question: Let there be a language $L = \{ +, \cdot, 0, 1, < ...
1
vote
2answers
64 views

Why cant AND and NOT represented only with IMPLICATION?

Can someone please explain why can't I use only implication to represent AND and NOT with proof as well? I know that I can represent OR simply by using implication. Was thinking if I could find ...
2
votes
3answers
109 views

Is empty set element of every set if it is subset of every set?

This problem is from Discrete Mathematics and its Applications My question is on 9b. I know that the sign represents an element is a member of. (from book) I know that the O with a slash across ...
1
vote
2answers
26 views

Confused on Conditional Statements

Write these propositions using $p$ and $q$ and logical connectives (inclduing negations) $p$: You drive over $65$ miles per hour. $q$: You get a speeding ticket You will get a speeding ticket if ...
1
vote
3answers
82 views

What’s wrong with this proof that $5$ is prime?

I’m reading How To Prove It and I’m confused as to how the proof of “$x$ is prime” is correct. I've written proof given below and also my conclusion after substituting in values for $x$, $y$ and $z$: ...