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)

0
votes
1answer
35 views

Why are conjunctions used with existentially quantified sentences? [closed]

Why can we not use implication with existentially quantified sentences? Why can we only use conjunction?
1
vote
0answers
71 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
37 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
71 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
332 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
57 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
187 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
37 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
40 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
28 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
27 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
39 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
26 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
53 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 ...
-3
votes
0answers
33 views

Classification of Abstract Elementary Classes/Shelah/2 volume book [closed]

Is there someone around with whom I can consult the 2 volume book by Shelah on Classification of Abstract Elementary Classes? He should have, in particular, at his disposal the second volume, since it ...
0
votes
1answer
58 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
26 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
44 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
353 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
24 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
37 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
61 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
160 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
60 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
28 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 ...
3
votes
1answer
71 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
18 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
62 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
104 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
25 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$: ...
0
votes
1answer
58 views

Proof strategy for simple proofs.

I'm currently in a discrete mathematics course and I'm having quite a bit of trouble with the idea of proofs. From what I understand the one I've been stuck on is also rather simple but to me it's ...
-1
votes
1answer
31 views

company as none-binary tree [closed]

Company's structure is depicted as none-binary tree where each node represents an employee. Root of the tree is CEO of the company and every node that has children is their supervisor. When assigning ...
2
votes
1answer
64 views

How to rewrite a theorem in symbolic logic?

I'm currently working on some discrete mathematics work and I've encountered a question I'm not sure how to answer exactly. Precisely, I'm trying to translate or re-write a division algorithm into ...
2
votes
1answer
61 views

Computable function with noncomputable set of fixed points

I'm looking for a computable function $f: \mathbb{N} \to \mathbb{N}$ such that the set of fixed points $\mathcal{F}_f = \{ e \in \mathbb{N} \mid f(e) \sim e \} = \{e \in \mathbb{N} \mid \forall x \in ...
0
votes
0answers
22 views

Determining if a logical statement is false?

I'm currently working on some simple existential and universal quantification questions as a brush up for a discrete mathematics course and I'm having a bit of trouble remembering the method used to ...