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
1answer
53 views

Can one use the Hilbert-Ackermann Consistency Theorem to prove the consistency of $PRA$?

In his textbook Mathematical Logic, Shoenfield states the Hilbert-Ackermann Consistency Theorem as follows: "Consistency Theorem (Hilbert-Ackermann): An open theory $T$ is inconsistent iff there is ...
0
votes
2answers
44 views

Can we say in first order logic the following: Every person who loves everyone is good?

I have just started to learn the first order logic. I have learned that one can use predicated to specify relations between specific objects (or entities). For example: $LocatedIn(Berlin, Germany)$ ...
3
votes
1answer
58 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
2
votes
1answer
26 views

Direct constuction of nonlow noncomplete c.e. sets

How can one construct a noncomplete nonlow c.e. set? (Background: I've been trying to construct, as an exercise, a nonlow low$_2$ set, but I do not know what kind of requirement is adequate for ...
9
votes
0answers
156 views
+50

An exercise in Fine Structure of constructible universe concerning projectum patterns

This question assumes some familiarity with Jensen's fine structure analysis of the constructible universe L (https://en.wikipedia.org/wiki/Jensen_hierarchy, ...
0
votes
1answer
20 views

Need some assistance converting to conjunctive normal form

I've been asked to convert a couple formulas to CNF. I've tried them several times but I always get stuck at the same point. They are as follows: $(P \to (Q \to R)) \to (P \to (R \to Q))$ $ ...
0
votes
0answers
36 views

Proof that the inverse limit of an inverse system is equal to another set

I'm trying to to learn model theory and so working with some basic examples. Consider the following: Let $D$ be finite subsets of $\mathbb{Q}$ with the ordering given by the subset relation. Let ...
-1
votes
1answer
34 views

prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$

I'm just starting out in natural deduction. So I have a question now how to prove the following. Prove that $\vdash (P \Rightarrow Q) \lor (Q \Rightarrow P)$ I'm finding this rather difficult cause, ...
0
votes
2answers
60 views

Natural deduction, Proof $\vdash$ $P\Rightarrow(Q\Rightarrow P)$

So I have a question regarding natural deduction, are we allowed to "copy" our previous assumption inside a new assumption. I will use an example to illustrate. $\vdash$ $P\Rightarrow(Q\Rightarrow ...
1
vote
0answers
48 views

Theories of Arbitrary Morley Rank

Suppose that you have a language $L$. I can show that theories like DLO, or any unstable theory for that matter, has Morley Rank $\infty$. I can also show that $REI_\alpha$ has Morley rank $\infty$, ...
0
votes
1answer
72 views

translate sentences using predicate logic and universal quantifiers

ok so I think I understand of them, but correct my answers if I am wrong.. Any pet either loves itself(a) or some person(b). my answer: ∀ x Pet(x) --> (Love(x,a) V Love(x, b)) Dogs will eat ...
0
votes
2answers
67 views

Can anything be the logical consequence of an always false statement? For eg: $p \wedge \neg p$

$p \wedge \neg p$ is never true, does that mean that any statement can be it's logical consequence?
2
votes
0answers
41 views

Relationship between intuitionistic logic and infinite dimensional vector spaces.

Some time ago, I've heard that there was a relationship between intuitionistic logic and infinite dimensional vector spaces. More precisely, the fact that $\neg \neg \phi \to \phi$ may not be "true" ...
0
votes
1answer
33 views

What will be the value of this term in a Herbrand structure?

I have a problem for my logical programming class. I have a structure H, which is a Herbrand structure and v is the evaluation ...
0
votes
1answer
44 views

Confused about proof by contradition

In proof by contradiction, I can understand how it works when the hypothesis leads to a clearly false proposition. e.g., if we want to prove $P$, we assume $\neg P$ and show that $\neg P \implies ... ...
0
votes
2answers
46 views

Proving double inequality by cases

I am puzzled by an exercise in Vellemen's How To Prove It, here is the exercise: Prove that for all real numbers $a$ and $b$, $|a| \le b$ iff $-b \le a \le b $. There is actually no official ...
0
votes
1answer
92 views

Proving by induction that a balanced strings of parentheses has equally many opening and closing parentheses

In computer science, a string is a finite sequence of characters. For strings $A$ and $B$, we express $AB$ as $A$ followed by $B$. A balanced string of parentheses is a string of open and closed ...
0
votes
1answer
35 views

How to solve this propositional logic propblems using the following rules.

Okay so I have the following problem, which I need to solve without using truth tables. This is the formula p ∧ (¬p ∨ q) ≡ p ∧ q and these are the semantic ...
1
vote
2answers
39 views

how to prove the following formula true using semantic equivalences

Hi I am trying to prove the following the formula and this is what I have so far false ∨ p ≡ p This is what I have do so far ...
1
vote
2answers
33 views

Why a truncated table for logic implication $(p\wedge q) \implies p$ verification?

The book Discrete Mathematics by Kenneth A. Ross says: "Let's verify the logic implication $(p\wedge q) \implies p$. For that, we need to consider only just the case when $p\wedge q$ is true; i.e., ...
0
votes
2answers
23 views

Correlation, dependence and the statement “Correlation does not imply Causation”

If we have two non-zero correlated random variables then they are dependent. Why then do we have the saying "Correlation does not imply Causation". A change in one variable may not cause exactly the ...
1
vote
1answer
17 views

What is the negation of the statement $S\cup T$ is a subring?

I am trying to prove the statement $S\cup T$ is a subring implies $S\subseteq T$ or $T\subseteq S$. What is the contrapositive of this statement? Thanks
0
votes
1answer
27 views

Predicate and Propositional function?

What's the difference between a predicate and a propositional function, both in mathematical aspect and logical aspect? I also see some texts in wikipedia, which made me confused. "Later Russell ...
0
votes
1answer
29 views

Proving inadequacy given a set of connectives

Let $\oplus$ be a binary connective defined by the truth table: $\begin{array} {|r|r|} \hline p &q & p \oplus q\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ ...
1
vote
3answers
72 views

Are “formulas” in Axioms of ZFC indefinite?

There is the Separation Schema in Axioms of ZFC. Where do "formulas" in this axiom comes from?Are they indefinite and is ZFC actually something like "ZFC(X)" where X is a variable which denotes a ...
0
votes
2answers
27 views

How can I prove the following formula using semantic equivalences

Hi I am trying to prove the following formula using semantic equivalences $$(p \land q) \to r \;\equiv\; p \to (q \to r )$$ I am thinking maybe to use the implication rule but I am note sure.
0
votes
0answers
7 views

Express in LTL the following properties (we assume a path s0; s1; : : :)

i. If A occurs at least twice, then A occurs in nitely often. ii. A holds at all states s3k and does not hold at all states s3k+1, s3k+2, where k =0; 1; : : : iii. If A holds at a state si, then B ...
1
vote
3answers
47 views

Verify if Propositions hold or not

I want to show wether or not these two propositions hold or not. The first one is that $$\forall x\exists y(xy>0\implies y>0)$$ For this one I noticed that hen $y=0$ it doesn’t hold. But I’m ...
0
votes
0answers
13 views

Find algebraic normal form that's derived from 2 other ANF

I have to find the ANF of a function $h$ where $h = f \star g$ where $x \star y := x \wedge \neg y$. $f$ and $g$ are given functions. They are $f(x, y, z) = y \oplus x \oplus xy \oplus zy \oplus zx ...
1
vote
1answer
26 views

Is this formula in normal form prenex $(\forall x)(\exists y)(P(x) \land (\exists z)Q(y, z))$?

In my course notes, this $(\forall x)(\exists)z(P(x) \land (\exists z)Q(y, z))$ formula is said to be in normal form prenex. But, shouldn't al cuantors be in the ...
1
vote
1answer
46 views

Are the ordered field axioms consistent?

Today in class a student asked to the professor "Are the ordered field axioms consistent?" And my prof replied something along the lines of "Yes, as we have a model of them: $\Bbb R$, this ...
0
votes
0answers
26 views

Construct a proof showing the argument is valid (Logic)

I am having some trouble with this problem. I think maybe more guidance or suggestion on rules to use would help. For each of the following arguments, either show that it is valid by giving a proof, ...
0
votes
1answer
48 views

Tarski's semantic conception of truth and logic

Tarski's semantic conception of truth states: $X$ is true iff p (where $p$ is a sentence, and $X$ is the name of the sentence $p$ to which the truth predicate applies). However, in logic, to express ...
3
votes
0answers
32 views

Negating a predicate with a biconditional

Negate the following statement and make the negation appear immediately before the predicates $$ \forall x \forall y(Q(x,y) \leftrightarrow Q(y,x)) $$ I did the following steps: $$ \neg(\forall x ...
1
vote
1answer
39 views

Proof of Why or Why Not some equivalence holds

How do I prove that this equivalence $$\lnot\exists x\,\forall y\,(P(x)\Rightarrow\lnot Q(x,y))\equiv \forall x\,\exists y\,(P(x)\land Q(x,y))$$ holds or not? I remember that $A\implies B\equiv\lnot ...
0
votes
1answer
37 views

Implication and the equal sign?

My question is best stated as an example: $\int_{c_0}^{c_1} g(x)dx = G(c_1)-G(c_0)$, therefore $\int_{c_0}^{c_1} g(x)dx \implies G(c_1)-G(c_0)$ From the two statements above, can we always conclude ...
2
votes
3answers
69 views

Some hints for “If a prime $p = n^2+5$, then $p\equiv 1\mod 10$ or $p\equiv 9\mod 10$”

I tried to prove this question by first considering the possible last digit of $p$ when $p=n^2+5$, but that reasoning got me nowhere. Then I tried to prove it by contrapositive, and however I just ...
6
votes
1answer
135 views

Do mathematical objects have underlying types?

I came upon this issue while I was trying to think about what "type" of object is $\mathbb R^n$ - is it a set, a vector space, an inner product space, an affine space, a metric space? Perhaps the ...
0
votes
2answers
52 views

Quantifier notation: $\forall n \implies \cdot$ versus $\forall n, \cdot$

I'm not sure which of the following two notations is the correct one (or, are both correct?). I've seen both being used by different professors. $\forall \varepsilon > 0\ \exists \bar n \colon ...
0
votes
2answers
26 views

I cannot figure out what this question means with the semantic turnstile

Hi I have recently started studying propositional logic and am finally understanding the truth tables and how to use them. I came across this formula which is confusing me. Use truth tables to ...
0
votes
1answer
24 views

Misunderstanding the concept of semantic consequence

In my course notes I have a statement like this one: Let $F_1, ..., F_n \in FOL$. We say that $F$ is a semantic consequence from $F_1, ..., F_n$ and we denote that by $F_1, ..., F_n \vDash F$ if ...
3
votes
1answer
44 views

If $F : \mathbf{C} \to \mathbf{D}$ is an equivalence, does $\alpha_{GD} = G(\beta_D)$ hold in general?

Let $F : \mathbf{C} \rightleftarrows \mathbf{D} : G$ be an equivalence with natural isos $\alpha : 1_\mathbf{C} \to GF$ and $\beta : 1_\mathbf{D} \to FG$ witnessing the referred equivalence. I wonder ...
1
vote
2answers
50 views

Transitivity in Logic

I was reading the work of Marvin Minsky on What makes Mathematics hard to learn? and in the "Bringing Mathematics to Life" chapter there is a question on Logic, here it is: If most A’s are B’s, ...
0
votes
1answer
26 views

Boolean logic gate implementation

how many minimum number of nand gate is required to implement f=A+B'C ? please give a diagram so i can understand... In general what is strategy to implement logic with minimum number of nand gate?
0
votes
1answer
32 views

DNF simplification

I am currently learning about propositions and logical equivalences in a mathematics course I'm taking at university. I'm having trouble understanding how to simplify DNF Formulas. I was given a truth ...
1
vote
2answers
30 views

Implication as defined in mathematical logic [duplicate]

If we can take the truth of an implication to mean the validity of reasoning, then that would mean that all reasoning that begins with false premises is valid reasoning. Are there no counterexamples ...
2
votes
1answer
19 views

What is “determined form” of a predicate?

So I'm still reading The GUHA Method of Automatic Hypothesis Determination by P. Hajek, and there he uses a phrase: set of predicates with a determined form I have no idea what determined form ...
0
votes
1answer
31 views

Propositional Equivalence

Are the following two propositions equivalent? p IMPLIES (q IMPLIES r) p IMPLIES (q AND r) From what I can tell, using the logical equivalences, this should be false, correct? p ...
0
votes
1answer
67 views

Why can we prove things via the contrapositive, contradiction, etc.?

I don't understand why we can use things as the contrapositive, reductio, etc. when we look to prove some statement. If we look at this from something like axiomatic propositional logic we can say ...
0
votes
0answers
15 views

Some LTL and CTL inequivalencies

I'm trying to find some examples in which a certain LTL-formula is valid and another (very similar) CTL-formula is not valid. I found most of them, but I'm not sure about my results because I'm not ...