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
48 views

What questions or areas in the foundations of mathematics remain active research fields?

By foundations of mathematics I am referring to the mathematical, logical, and philosophical foundations of the subject. I'm interested in seeing which of these have active research going on within ...
1
vote
2answers
941 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
1
vote
1answer
45 views

What is the name of a “basis” in Boolean algebras

So, a basis in linear algebra is the smallest set which generates a particular vector space. (More formally, a subset of the vector space which is linearly independent and spans the vector space) Is ...
0
votes
1answer
42 views

Which rules of inference does Suppes use?

I'm reading Axiomatic Set Theory by Suppes, and I'm having a bit of trouble understanding which rules of inference (logical system) he is using, here's an example (capital letters are used for sets): ...
3
votes
0answers
67 views

Are all statements about math inherently formal? Can one do math without formal logic? [duplicate]

Are all people who do mathematics applying (whether they know it or not) formal logic? Does every statement someone may make about math, at its core, a formal statement in mathematical logic? ...
5
votes
0answers
28 views

Difference between a variable and an indeterminate

What are the differences and common points between a variable and an indeterminate ? Is an indeterminate also a variable ? Thank you EDIT : I am not trying to solve anything in particular, it was ...
0
votes
1answer
44 views
2
votes
1answer
44 views

Characterizing coding with automorphisms

I am attempting the following exercise from chapter 5 of Van den Dries' notes "Introduction to Model-Theoretic Stability". I suspect the exercise shouldn't be too difficult but I've become pretty ...
0
votes
1answer
26 views

Alternate form of Modus tollens applicable?

The definition states that not(q) p--> q ---------- not(p) Is the following form is also true? ...
3
votes
1answer
57 views

Can multiplication and division be treated as logical operations?

A few of my friends and I were playing around with math (more specifically, why (-1)(-1)=1) and we figured out that multiplication (with regards to signs) was an "nxor" operation (I.E. If we treat "1" ...
1
vote
2answers
31 views

First order structures for Posets

Im tackling this question: So Im ok with part (a) For part (b) I came up with $\sigma_n :=\exists x_1 \exists x_2 ... \exists x_n \Bigg(\bigwedge_{i\neq j}\Big(\neg (x_i\leq x_j)\wedge \neg ...
0
votes
2answers
38 views

Why does a finite set having a model imply that the set is consistent [closed]

Assuming the soundness theorem to be true, can someone explain why if we assume $\Sigma$ has a model $M$. Then $\Sigma$ is consistent ?
0
votes
2answers
23 views

Rectified prenex form conversion algorithm inconsistencies

I've looked at these two different RPF conversion algorithms where the first step of each, say 1 and 1', states: 1.Remove all “$\to$”s using the fact that $\alpha\to\beta ≡ \neg\alpha\lor\beta.$ ...
0
votes
1answer
37 views

Resolution Proof Understanding

If we have a clause like $$(x,y)$$ and $$(x,\neg y)$$ we can derive empty clause but why do we derive the empty clause and not the empty set? When would we derive the empty set? My question is ...
-1
votes
1answer
46 views

Least ordinal $\beta$ such that it is provable that $2^{\aleph_0} \leq \aleph_{\aleph_\beta}$

What is the east ordinal $\beta$ such that it is provable in $\mathsf{ZFC}$ that $2^{\aleph_0} \leq \aleph_{\aleph_\beta}$?
1
vote
0answers
24 views

(Semi-)decidable sets and infinite sets

I’m confused about the notion of (semi-)decidable sets in the context of transition systems. Suppose we have some transition relation $\rightarrow$ over some infinite set of states $\Sigma$. Let’s ...
1
vote
1answer
76 views

Has it been proved that ∨ ∧ ¬ ⇒ ⇔ ∀ ∃ and predicates are enough to express all known mathematics?

I frequently encounter this statement in math books: "All of known mathematics can be expressed in terms of elementary predicates, logical connectives, and quantifiers."
1
vote
1answer
27 views

Primitive recursive functions definition (understanding “composition” and “primitive recursion”)

$\newcommand{\N}{\Bbb{N}}$ I am trying to understand the concept of primitive recursive functions, using the definition in the Open Logic Text (Definition 14.3): The set of primitive recursive ...
1
vote
1answer
47 views

Weak Representability and Derivability Condition 1

Can someone point out the error in the following reasoning? Let K be an axiomatizable, consistent extension of Peano Arithmetic. Let P' denote the Gödel number for P. K is axiomatizable, thus ...
-1
votes
1answer
15 views

How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
7
votes
1answer
147 views

Gödel's ontological proof and “modal collapses”

Recent findings on Gödel's ontological argument allowed to ultimately establish a couple of things: Gödel's original axiomata are inconsistent Scott's variation instead is consistent Scott's axioms ...
0
votes
1answer
1k views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
5
votes
1answer
58 views

If two posets have same dense open sets, are they equivalent as notions of forcing?

Suppose that $\mathbb{P}_0=(P,\leq_0)$ and $\mathbb{P}_1=(P,\leq_1)$ are partial orderings (in the weak sense, i.e., reflexive and transitive relations) on the same underlying set $P$, and such that ...
5
votes
1answer
85 views

Statements independent of ZF that quantify over the real numbers

(This question is a bit vague, because I probably haven't aquired all the logical tools needed to express it in a more concise way) I've seen a few examples of statements in set theory that can ...
3
votes
1answer
51 views

Does the theory of equivalence relations have quantifier elimination?

I am aware that the theory of equivalence relations with infinitely many classes, all of which infinite, has quantifier elimination, as can be seen from the answer to this question. However, does the ...
0
votes
1answer
29 views

If $\text{“}x^2>0\text{”}$ and $\text{“}x>0 \text{”}$, write a translation for $\text{“}$ $x^2>0$ whenever $x>0$ $\text{”}$?

I'm reading Rosser's: Logic for Mathematicians. In the first chapter, he asks to translate some sentences to It's logical form. There is this exercise: If $\text{"P"}$ and $\text{"Q"}$ are ...
0
votes
0answers
24 views

Should the truth values of all sentences $Q$ equivalent to the fixed sentence $P$ be the same?

This might be silly, but I'd like to be sure about it. Suppose I'm making an application of a kind of logic, say mathematical logic on certain objects. And then there is one sentence: $P \to Q$. ...
1
vote
1answer
29 views

Converses of statements

Does this statement have a converse? Denote by $A_2$ the circumcenter of $\triangle{B_1C_1D_1}$, and define $B_2, C_2,D_2$ in an analogous way. Show that the quadrilateral $A_2B_2C_2D_2$ is similar ...
0
votes
1answer
46 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 ...
3
votes
3answers
136 views

In which order should I learn the foundations of mathematics? [closed]

I know from Wikipedia that those are the four pillars of the foundations of mathematics: Proof theory Aximatic Set theory Model Theory Recursion Theory and I want to learn all of them, the problem ...
0
votes
0answers
22 views

Can epsilon induction be derived from the transitive closure induction?

I was wondering (and could not seem to prove or disprove) if epsilon-induction could be derived from the transitive closure operator for binary relations. The induction of the transitive closure ...
1
vote
2answers
60 views

Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite

I got the following exercise: Prove that, for any sentence A of the predicate calculus with identity, at least one of spectrum(A) and spectrum(¬ A) is cofinite. I already tried to prove this ...
0
votes
0answers
27 views

First Order Logic Tableau Multiple Universal Identifiers

I've been looking into tableau lately and I have come across multiple Universal Identifiers which I am not used to. How do I approach these to validate/invalidate with these identifiers and provide an ...
1
vote
1answer
46 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. ...
1
vote
1answer
34 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
16 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: ...
-1
votes
4answers
45 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)))$ ...
6
votes
1answer
42 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
24 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
47 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
42 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
58 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
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
0answers
21 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 ...
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
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)) ??
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
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)) ...