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)

0
votes
0answers
30 views

Guess my number game (Plus Minus)

There is a number guessing game played by two players. The rules and procedures are the following: Let's say that we are playing the game with 4 digits. This is not fixed and not a strict rule of the ...
1
vote
0answers
15 views

Resolution method: example

Now i study resolution method over first order logic in university but i can't feel power of this method. Can anyone give such statement that would be at least some nontrivial and interesting and at ...
0
votes
2answers
14 views

Number of truth tables for a 2 letter formula

I am reading a book called "The Haskell Road to Logic, Maths and Programming" A question in the book is: "How many truth tables are there for 2-letter formula's" The answer in the answer sheet is: ...
-2
votes
4answers
41 views

Expressing “there is exactly one” [duplicate]

I'm trying to express $∃!x : (P(x))$ in a different way. i want to know how to express it with the other quantifiers. Here is what I have tried: $∃!x(P(x)) = ∃x : (P(x) \wedge ∀y, y≠x (\neg P(y)))$ ...
3
votes
1answer
16 views

Why does every complete theory have joint embedding property?

I came across a sentence in page 196 Chang & Keisler's model theory book that I don't understand. It says: Every complete theory has the joint embedding property. Def. A theory $T$ has joint ...
1
vote
0answers
21 views

Applications of the Axiom of Regularity to non-set-theoretical Mathematics [duplicate]

In the beginning of my mathematics studies at university, we have learnt that nearly all of ordinary mathematics not dealing with proper classes can be formalized within ZFC, which is a famous ...
2
votes
2answers
23 views

Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) ...
0
votes
2answers
35 views

Why do some literals disappear when passing from CNF to DNF

$(p \Rightarrow q) \land (q \Rightarrow r) \land \neg(r \Rightarrow p)$ According to wolframalfa the result is $\neg p \land r$. Could you tell me how did this happen? where did $q$ disappear and ...
0
votes
1answer
49 views

How to construct an injection $A\to B$?

We consider functions $A\to B$. Let $f$ be such a function $A\to B$. Furthermore, suppose that every function $A\to B$ is not surjective. How to construct an injection $A\to B$? I have the ...
1
vote
1answer
46 views

Non-principal ultrafilters on a set [duplicate]

Let $X$ be a set. If $X$ is finite then all ultrafilters on $X$ are principal, i.e. have the form $\{A \subseteq X : x \in A\}$ for some $x\in X$. But now suppose $X$ is infinite, say $X=\mathbb N$. ...
-3
votes
1answer
34 views

how a irrational number having infinite terms can be represented with certain distance on number line? [on hold]

I think that nothing is irrational if it is represented on number line for ex:the value of root2 is 1.41421.............it increase with every new number as 1.41 is grater than 1.4 but we can ...
0
votes
1answer
51 views

Does a $\Pi_2^0$ sentence becomes equivalent to a $\Pi_1^0$ sentence after it has been proven?

I heard that the P vs NP question is equivalent to a $\Pi_2^0$ sentence, and that the Riemann hypothesis is equivalent to a $\Pi_1^0$ sentence. Many known mathematical theorems state that some ...
0
votes
0answers
16 views

Kinds of logic and constraint programming

I am currently solving combinatorial optimisation problems using integer linear programs (ILP), and I would like to try something different (constraint satisfaction, logic programming, ...). I tried ...
1
vote
1answer
34 views

For a compact logic, strong completeness follows from weak completeness

I have heard it said from reputable sources that one of the differences between a compact and a non-compact logic is that in a compact logic, strong completeness follows from weak completeness. ...
0
votes
1answer
53 views

What does Elim $\land$ actually eliminate

Say I were to have the premise $$P \land \sim Q \implies R$$ And I were to apply the Elim $\land$ inference rule, would the result of that lead to just P, or can the elim be simply applied to the $P ...
-3
votes
0answers
24 views

Combinatorics and Factorials. [on hold]

An urn contains 7 red, 8 yellow and 13 green balls; another urn contains 9 red, 4 yellow and 6 green balls. We pick a ball from each and record the colors. How many pairs (one ball from each urn) have ...
0
votes
1answer
35 views

Translate “If I would not exist if I will travel back in time, then I will not travel back in time” into predicate logic.

"If I would not exist if I will travel back in time, then I will not travel back in time" Translating the conditionals using ⊃ and 'I do not exist' as 'I am not something', find a tautologous form ...
0
votes
1answer
18 views

Counting Possible Ways to Score in a Basketball Game

In a basketball game, a goal is worth 1,2, or 3 points. Given the score n of a team at the end of the game, we are interested in the possible ways the score n can be achieved. Write a function ...
0
votes
2answers
20 views

How can I write a DNF to CNF form?

How can I have write (p∧q) ∨ (¬p ∧ ¬q), which is the equivalent for (p<->q), in conjunctive normal form (CNF)? In general, am I allowed to do (p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q)) ??
4
votes
1answer
1k views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...
0
votes
0answers
13 views

Showing that $(p(x)\rightarrow q(x)) \leftrightarrow (\neg q(x) \rightarrow \neg p(x))$ is a valid $\mathcal{L}$-formula

If $\mathcal{L}=\{p,q\}$ with $p,q \in \mathcal{P}_1$, would showing that $(p(x)\rightarrow q(x))$ and $(\neg q(x) \rightarrow \neg p(x))$ have the same truth table prove that $(p(x)\rightarrow q(x)) ...
1
vote
1answer
49 views

Hilbert style proof for $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) \right) $

How can I proof that the following formula is a tautology by using Hilbert calculus? $ \left( \left( A\rightarrow \left( A\wedge \neg A\right) \right) \rightarrow \left( A\rightarrow A \right) ...
1
vote
2answers
126 views

First Order Logic vs First Order Theory

What is the difference between a First Order Logic and a First Order Theory. Can anybody please describe what each one precisely (formally) is? For a bit more elaboration on the question, I think ...
5
votes
4answers
7k views

What is the difference between an axiom and a postulate?

I hear about axioms in set theory and postulates in geometry, but they seem like the same thing. Do they mean the same thing but then are used in different instances or what? Is one word more ...
-2
votes
0answers
30 views

what is the logic box proof for $(\neg A \vee B) \vee (B \implies A)$ [on hold]

I understand that classical contradiction is needed but just cant manage to get a complete answer question: $((\neg A) \vee B) \vee (B \implies A )$
9
votes
1answer
144 views

Is there a way to tell how many different ways you can prove a theorem?

Consider the question. Given the nature of a sentence $S$, it there any way to tell how many different ways you can prove this sentence? Proofs are not distinct if we have a situation such as: $P ...
0
votes
1answer
10 views

2-Sat to Implication Graph

I have a set of clauses $$(x,y),(x,z),(y,z),(\neg x, \neg y), (\neg x , \neg z), ( \neg y, \neg z)$$ I drew the implication graph and have no bad loop but the answer says there is a bad loop. My ...
2
votes
1answer
40 views

Determining whether a truth function can be defined in terms of another

Given an $n$-ary truth function $f$ and $m$-ary truth function $g$, is there a way to determine whether $g$ can be defined in terms of $f$? In other words, is there a systematic procedure that can ...
12
votes
4answers
420 views

Can unprovability unprovable? Is there an $\omega$-fold unprovability?

I was just thinking about unprovability. I just wanted to know if it is possible to make a concrete boundary between provable problems and unprovable problems in a certain axiomatic system. We know ...
1
vote
0answers
29 views

How many valuation are there for a set of atoms?

I'm studying propositional logic. On my notebook I wrote: Theorem: If v is a function from ATOMS (set of atoms) into $\{0,1\}$ then exists a unique valuation $[[*]]_v$ such that $[[\psi]]_v=v(\psi)$ ...
-2
votes
1answer
52 views

A clown, a robot, a cowboy, and a mathematician are traveling through the woods when they come to a river they need to cross. [on hold]

A clown, a robot, a cowboy, and a mathematician are traveling through the woods when they come to a river they need to cross. There is a boat at shore that can only hold two people or one robot. ...
0
votes
1answer
71 views

What kind of proof is this?

Let's say that we want to prove that object A is blue. Is the following reasoning true? First assume that $A$ is indeed blue. Then, use other axioms to show that depending on a control parameter ...
0
votes
0answers
32 views

a problem about truth in first order logic [on hold]

Suppose that $L$ is a first order language with no function symbol,constant and $=$ & $A=\forall x_1 \ldots x_n \exists y_1 \ldots y_m B$, $B$ has no quantifier.prove that $\models A$ if and only ...
0
votes
0answers
24 views

logical consequence [on hold]

I have been asked to prove the following formula related to Logical Consequence. I have searched through the math stackexchange site, but I havent really found anything that fits what I am looking ...
4
votes
2answers
75 views

Ultraproduct of a metric space

I am currently trying to understand "Curvature bounded below: a definition a la Berg--Nikolaev" by Nina Lebedeva and Anton Petrunin. They start with a complete, intrinsic metric and space $X$ and say ...
0
votes
2answers
40 views

A better general definition of a predicate

What's a better definition for (an interpretation of) a predicate in general (i.e. non-theory-specifically): ...
1
vote
2answers
57 views

Is $(\neg q \rightarrow \neg p) \rightarrow (p \rightarrow q)$ equivalent to $p \vee \neg p$ in intuitionistic logic?

I've heard mathematicians say that contrapositive arguments are usually preferable to proofs by contradiction, so I was curious if this was based on logical reasons (i.e. that $(\neg q \rightarrow ...
1
vote
1answer
35 views

Do all fields have a total cyclic order?

It is well known the finite commutative rings, $Z/nZ$, are not discretely ordered rings. The axiom $\forall x \forall y \forall z((0<z \land x<y) \rightarrow (x*z < y*z))$ is false for the ...
7
votes
1answer
93 views

Members of $\Sigma^1_4$ sets

I'm pretty sure this is an easy descriptive set theory question that I'm just blanking on. Is it consistent with large cardinals - say, with a measurable - that every (nonempty) $\Sigma^1_4$ class ...
8
votes
1answer
292 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
1
vote
1answer
33 views

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$

True or False: $\exists x(P(x)\lor Q(x))\equiv \exists xP(x)\lor \exists yQ(y)$ My intuition tells me yes, these two things are equivalent. Assume the first, take some $x_0$ s.t. $P(x)\lor Q(x)$, ...
2
votes
0answers
48 views

Is there a standard name for using a function application, rather than a variable, as a summation index, as in $\sum_{f(x)}$?

I am trying to find out whether there is a standard notion of generalizing indexing such as $\sum_i$ to function applications as in $\sum_{f(x)}$. Intuitively, the latter means "iterating over all ...
4
votes
1answer
134 views

$\vDash \varphi$ iff $\| \varphi \|_A =1$ for every boolean valued structure $A$

In the book Axiomatic Set Theory (Takeuti, G; Zaring, W.M. - 1973) the theorem 6.4 states that if $\varphi$ is a closed formula of a given language then it is satisfied in every boolean valued ...
2
votes
3answers
38 views

What is the logic underlying this proof?

Proposition: A metric space $X$ is connected if, and only if, every continuous function $f:X\to (\{0,1\},d_D)$ is a constant function, where $d_D$ is the discrete metric on the set $\{0,1\}$. ...
2
votes
1answer
23 views

Spectrum of a set of first order formulas

Let ψ be a first order formula. Wikipedia defines the spectrum of the formula ψ as follows: The spectrum of ψ is the set of natural numbers n such that there is a finite model for ψ with n elements. ...
1
vote
0answers
26 views

Unprovable identity over the integers

I was thinking about Tarski's problem, and was wondering what happens if we have a theory $T$ with two sorts $N,Z$ with intended interpretations $\def\nn{\mathbb{N}}$$\def\zz{\mathbb{Z}}$$\nn,\zz$ ...
0
votes
1answer
13 views

Reducing a Boolean function

I have the following boolean function: f(x,y,z) = xyz + xyz' + xy'z + x'yz + xy'z' I could reduce it to the following: f(x,y,z) = xy + xy'z + x'yz + xy'z Im not sure what to do next, i know it can ...
1
vote
1answer
26 views

Converting ∃ to ∀ and vice versa

I'm having some trouble getting my head around the conversion of quantifiers. For instance, I know that $\forall x \,F \,\equiv\, \neg\exists x \, \neg F$ and conversely. $\exists x \,F \,\equiv\, ...
0
votes
1answer
41 views

In sequent calculus, what's going on with sequents with multiple formulae in the succedent?

The sequent proof systems I learned only allowed one formula on the right hand side of the sequent, and $\phi_1, \ldots, \phi_n \Rightarrow \psi$ (or ... $\vdash \psi$) is understood as saying that ...
0
votes
1answer
29 views

Proving a conclusion (Logic)

I had a question on how to prove a conclusion with a series of premises using deduction. From a statement such as the one below: If you eat carefully then you will have a healthy digestive system. If ...