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)

1
vote
1answer
50 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$. ...
0
votes
1answer
61 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 ...
0
votes
0answers
22 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
47 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
38 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
24 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
24 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)) ??
0
votes
0answers
17 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
0answers
32 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
44 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 ...
1
vote
1answer
108 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
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 ...
0
votes
1answer
11 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 ...
0
votes
2answers
45 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
1answer
43 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 ...
1
vote
1answer
37 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)$, ...
8
votes
1answer
358 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
2answers
61 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 ...
2
votes
3answers
40 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\}$. ...
4
votes
1answer
140 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
1answer
28 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
32 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
27 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
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 ...
0
votes
1answer
23 views

Equivalence infinite Spectrum problem and finite spectrum problem

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
0
votes
1answer
43 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 ...
-2
votes
2answers
56 views

How do I prove\disprove the following logical statement?

I saw this statement in one of my logic books and I was curious how to proof/disproof it? Let $S_1$ and $S_2$ be sets of propositions. If $S_1$ is satisfied and $S_2$ is satisfied then $S_1 \cup ...
12
votes
1answer
270 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
0
votes
0answers
20 views

$\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?

Let P be some statement. Is my negation correct? $\neg (\forall x\in\mathbb{Z}\forall i\geq 0: P)=\exists x\in\mathbb{Z}\exists i\geq 0: \neg P$?
0
votes
1answer
37 views

Number of steps

In a shopping complex Sunita walks down an escalator moving down from the first to ground floor in 30 sec taking 6 steps for every 5 sec. On reaching the ground floor she realizes she has to go back ...
0
votes
1answer
24 views

Proof for association law?

I am new in logic and I getting a little bit confused with maths. Can I do something like this following the Associative Law? $$(p ∨ ¬r) ∨ (r ∨ ¬p) ≡ (p ∨ ¬p) ∨ (r ∨ ¬r)$$ Thank you in advance for ...
0
votes
2answers
26 views

help on simplifying boolean algebra

I need t show the the terms on the left simplify to the ones on the right $$(X+Y).(X'+Z)= X.Z+X'.Y$$ My attempt: I went with $$XX'+XZ+YX'+YZ= 0 +XZ+YX'+YZ$$ But I'm stumped beyond ...
1
vote
2answers
42 views

How to define the functions and relations for a logical model?

In model theory one has to define functions and relations on a set for the function and relation symbols of the logical theory. My questions are: What kind of operations are allowed to define ...
0
votes
0answers
37 views

Is there any way to retain Russell's original proof of induction in Appendix B of PM 1925?

Recently I was reading this question again and the following question occurred to me, Can there be some new interpretation of the system of PM $1925$ so that Russell's proof of $^\ast89.16$ is not ...
0
votes
2answers
39 views

How do you prove this logical equivalence?

$\\ (\exists! x:P(x)) \leftrightarrow ((\forall x:P(x) \rightarrow Q(x))\leftrightarrow(\exists x:P(x) \land Q(x)))$ If there's only one $x$ for which $P(x)$, then saying "all $x$ for which $P(x)$, ...
1
vote
1answer
30 views

Hilbert style proof of double negation introduction and reductio ab adsurdum

I'm trying to prove: $\phi\to\neg\neg\phi$ $(\neg\phi\to\neg\psi)\to((\neg\phi\to\psi)\to\phi)$ Using these axioms with modus ponens and the deduction theorem: A1: $\phi\to(\psi\to\phi)$ A2: ...
1
vote
2answers
41 views

Not very sure about this contraposition…open and closed sets

I have this lemma that states, Let $X$ be a topological space and $A \subseteq X$. Then, $A$ is open in $X$ if and only if $\forall x \in A$, there is a neighborhood of $x$ that is contained in ...
0
votes
1answer
42 views

Is T an infinity spectrum whenever T is a spectrum?

Definitions: For a given first order sentence $\phi$ define $\text{spectrum}(\phi)$ to be the set of all cardinalities of the finite models of $\phi$. A set $S\subseteq\mathbb N_+$ is said to be a ...
1
vote
1answer
47 views

Infinite Spectrum Problem

Let us work in a class theory like NBG. For a given first order sentence $\phi$ define $\infty\text{-spectrum}(\phi)$ to be the class of all cardinal numbers $\kappa$ for which there is a model $M$ ...
3
votes
1answer
38 views

Prove that in every WFF, there is a logical connective between every two atoms.

First, I have defined a well-formed formula as such: 1) Each atom is a WFF. 2) If φ is a WFF, so is ¬φ 3) If φ and ψ are WFFs, if ∗ is a binary connected (i.e., ∨,∧,→), then (φ∗ψ) is a WFF. What ...
0
votes
1answer
73 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
1answer
24 views

List of primes and compactness

I'm working on the following problem: Let $p_0,p_1,...$ be a list of the prime numbers in increasing order. Show that for any set $X\subseteq\mathbb{N}$, there is a model of Th($\mathbb{N})$ which ...
2
votes
1answer
39 views

Show that for propositional logic $\vdash_i \neg \varphi \Leftrightarrow \vdash_c \neg \varphi$.

As the title says, where $\vdash_i$ is derivations in Intuitionistic logic and $\vdash_c$ is derivations in Classical logic. I am allowed to use a corollary that states that $\vdash_i \varphi ...
-1
votes
2answers
81 views

What number(s) is unequal to itself [closed]

Is there any number that does not equal itself (satisfies $x-x\neq0$)? I've seen the question ...
4
votes
2answers
71 views

Trouble with “only if”

This is from pg. 45 of Discrete Mathematics with Applications by Epp: I'm having trouble understanding the last sentence. If we say that $p$ is John breaking the world's record and $q$ is John ...
1
vote
2answers
61 views

Is $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ a tautology?

Is this proposition a tautology? $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with ...
1
vote
1answer
51 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) ...
0
votes
4answers
50 views

Negation with De Morgan’s law

I'm having a hard time getting my head around transformation proofs. There is one particular example demonstration in the material I'm studying which I can't make sense of From this ¬ (¬ (¬ p) ∨ ¬ ...
0
votes
1answer
25 views

Logic Integer Proof with Common Divisors

Let $n, m ∈ Z$ (integer set) , $(n, m) = 1$. Suppose that $d$ is a positive divisor of $mn$. Show that there exist positive integers $d_1$ and $d_2$ such that $d =$ $d_1$$d_2$ where $d_2$ ...