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

Largest number definable in $n$ symbols [closed]

Let $f(n)$ be the largest number definable using $n$ characters including spaces, in PA or some formal system. Then we can define $g(n)$ to be the largest number definable using n characters ...
3
votes
2answers
60 views

How to prove that $(p\rightarrow q)\wedge(p\rightarrow r)$ and $p\rightarrow (q \wedge r)$ are logically equivalent?

I am trying to prove that $(p\rightarrow q)\wedge (p\rightarrow r) = p\rightarrow (q \wedge r)$. This is my approach: $(p\rightarrow q)\wedge(p\rightarrow r) = (-p \vee q) \wedge (-p \vee r)$ = ${[...
1
vote
1answer
50 views

Are equality and non-equality mutually dependent?

Is there any type of objects or ideas for which asking about their equality makes sense, but asking about non-equality doesn't? (or vice versa) Intuitively, "not equal" is a negation of "equal", so ...
5
votes
2answers
83 views

Formal systems in which $\forall x \in \mathbb{R}(x \neq 0 \rightarrow x^{-1} \neq 0)$ is true, but the contrapositive is disallowed.

Question. Are there any formal systems out there for which $$\forall x \in \mathbb{R}(x \neq 0 \rightarrow x^{-1} \neq 0)$$ is true, but the contrapositive $$\forall x \in \mathbb{R}(x^{-1} =...
0
votes
1answer
67 views

Can we take definability and existence as primitive notions of a theory?

One of my friend tries to develop an alternative viewpoint of Set Theory. For this he has taken the terms binary relation, set, existence and definability as primitive notions of his Set Theory. After ...
1
vote
2answers
49 views

How does the axiom schema of replacement work?

According to this website, the first partion of this axiom schema is Let $P(y,z)$ be a propositional function, which determines a function. That is, we have $∀y(∃x:(∀z:(P(y,z)⟺(x=z))))$. ...
-2
votes
0answers
17 views

Existence Theorem of Natural Recursion & Mutual Recursion

$f: A -> R$ $f(a)=$ $1. basecase$ $2. g(...h(first loa) f(rest loa))$ Exist a function $F: N-> R$ Q: Is there any theorem that says the existence of this relation? More complicated version ...
-4
votes
1answer
113 views

Are Godel's incompleteness theorems proven non-trivial?

Does somebody have a deep enough understanding of Godel's incompleteness theorem to confirm that the unprovable statements in some language $F$ are necessarily not just: The axioms themselves (...
1
vote
0answers
78 views

easy proof of the completeness theorem [closed]

The completeness theorem of first-order logic states: If $\Phi\models\phi$, then $\Phi\vdash\phi$. Assume that I have a calculus $\vdash$ in mind for which I want to prove this completeness theorem. ...
2
votes
1answer
49 views

Function $F(n)=n+n$ is not $\Delta_0$

Define $F(n)=n+n$, for $n<\omega$, and $F(n)=0$, for $n\not\in\omega$. I have to show that this is not a $\Delta_0$-function but it's the composition of two $\Delta_0$-functions. I have one hint; ...
2
votes
1answer
47 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
0
votes
2answers
43 views

Why is this counter-example valid?

I don't understand why the counter example of the following argument is valid: $\forall x\exists y(Ax\iff By)$ $\exists xBx \land \exists x\sim Bx $ $\forall x(Ax \to \sim Cx) $ ...
1
vote
2answers
89 views

When does circular reasoning go wrong?

Consider the following erroneous usage of L'hopital's rule: $$\lim_{h \to 0} \frac{f(x+h) - f(x)}{h} = \lim_{h \to 0} \frac{D_h(f(x+h) - f(x))}{D_h(h)} = \lim_{h \to 0} \frac{f'(x+h)}{1} = f'(x) \...
1
vote
1answer
46 views

Second Order Arithmetic

Since second order arithmetic is finitely axiomatazible why do not work with it, and insted we prefer first order Peano Axioms that include induction scheme?
0
votes
1answer
42 views

Express statement with predicates and quantifiers.

Ex: A student must take at least $60$ course hours, or at least $45$ course hours and write a masters thesis, and receive a grade no lower than a B in all required courses, to receive a masters degree....
-1
votes
1answer
31 views

Express the statement using predicates and quantifiers.

Ex: A passenger on an airline qualifies as a frequent flier if the passenger flies more than $25,000$ miles in one year or takes more than $25$ flights during that year. I started and made up these ...
2
votes
1answer
20 views

Use truth tables to show logical equivilance

Q: Show using truth tables that $\lnot(p \to q)$ and $(p \land q)$ are logically equivalent. So I thought that the negation of $(p \to q)$ was $(p \land \lnot q)$ so not sure if "logically equivalent"...
0
votes
1answer
45 views

Herband model for a forumla

I need to find a Herband model for the formula $Pc \land \forall x (\exists y (Px \leftrightarrow \neg Py))$, where $c$ is a constant and $P$ is a unary relation. I've already read the theory but ...
0
votes
1answer
38 views

Prove a relation is primitive recursive, x is prime?

Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive? Hello, $x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (...
4
votes
4answers
194 views

Calculus of Natural Deduction That Works for Empty Structures

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\Gamma$ is a set of formulas and $\phi$ a ...
-3
votes
1answer
70 views

A philosophical question on probability theory [closed]

This question is philosophical in nature. The example is taken from theology, but one may invent more examples, including these more scientific than mine. Nevertheless it is a valid mathematical issue....
1
vote
2answers
26 views

Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this ...
0
votes
2answers
37 views

About a proof of the Adequacy of Natural Deduction for Propositional Logic

In Mathematical Logic by Chiswell and Hodges, section 3.10 page 89 proves the following theorem: Theorem 3.10.1 (Adequacy of Natural Deduction for Propositional Logic) Let $\Gamma$ be a set ...
1
vote
1answer
34 views

Every intersection of a finite number of open subsets is also open

Edit: former solution was deleted Assume $$\bigcap_i \Bbb C \setminus A_i \neq \emptyset, i = 1, ..., n.$$ Thus $$\exists x \in \bigcap_i \Bbb C \setminus A_i,$$ and therefore $$\exists x \in \...
0
votes
0answers
44 views

What rules should I use to rewrite equations?

For a homework assignment I have to prove the following: Using: \begin{align} &[A_1]\quad \text{found} = (∃k : 0 \le k \lt i : b[k])\\ & [A2] \quad0 \le i \le N\\ &[A3]\quad i < N \\ &...
2
votes
2answers
33 views

Write the contrapositive of an if-then statement

$\forall a, a' \in A,$ if $f(a)=f(a'),$ then $a=a'$ Here is my attempt: $\exists a, a' \in A,$ if $\sim (a=a')$, then $\sim (f(a)=f(a'))$ Did I attempt to do this correctly? I based this on the ...
0
votes
1answer
24 views

Find weights and threshold of function

I have been tasked with finding if a a function can be represented through threshold logic, and if that is the case to find the associated weights and threshold. The function is: $$ f = x_7 + x_6 \...
1
vote
4answers
95 views

natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then ...
0
votes
0answers
10 views

scotts theorem and other representation theorems for order aggreeing qualitative quantitative probability measures

Scotts theorem and other theorems give conditions under which a qualitative ordering (>= for at least as probable than) which satisfies certain constraints (total pre-order, finite cancellation axioms ...
1
vote
1answer
73 views

Prove the formula is a contadiction

For every $A$ in Propositional calculus and for every $\rho$ we define: $$A^\rho = \begin{cases} A & \text{if $[|A|]_\rho = true$} \\ \lnot A & \text{if $[|A|]_\rho = false$} ...
3
votes
1answer
91 views

Formalizing splitting into cases

Let $x$ denote a fixed but arbitrary real, and suppose we're trying to solve an equation like $$(x^2-1)^2 = 1.$$ The 'high school' approach is to just shuffle the functions on one side onto the other ...
4
votes
1answer
58 views

Simple model of (propositional) intuitionistic logic to recognize valid formulas

I noticed that when I want to know (or rather see/understand) whether some classical tautology is valid intuitionistically, I first try to replace each propositional variable by a finite union of open ...
2
votes
1answer
27 views

Logical consequence problem

$P=(\forall x)(\exists y) GTOE(x,y)$ $Q=(\exists y)(\forall x) GTOE(x,y)$ And I want to know whether Q is an logical consequence of P. I know P is a logical consequence of Q. But I cannot identify ...
1
vote
4answers
114 views

A tough logic puzzle

I took a course on logic a few semesters ago so am having trouble remembering certian concepts. I came across another problem in one of my classes yesterday and am not sure how to solve it exactly. ...
2
votes
3answers
124 views

Is “all swans are white” equivalent to “if it is not white, then it is not a swan”?

More formally, is "All As are Bs" equivalent to "if it is not a B, then it is not an A"?
1
vote
1answer
29 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
0
votes
4answers
88 views

why is $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$

I'm having a hard time wrapping my head around why $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$
0
votes
0answers
22 views

Composition of substitutions of SLD tree

I found a question on my university past paper and it asked to get the SLD tree from a computation rule using some rules and facts. However I obtained the answer and to complete the question I have to ...
0
votes
0answers
8 views

Complexity class for subsumption for $\mathcal{AL}(\circ, ^{-})$

According to Baader et al's Description Logic Handbook, subsumption for $\mathcal{AL}(\circ)$ and $\mathcal{AL}(^{-})$ is in $\mathrm{P}$. However, I am not sure what complexity class subsumption for $...
0
votes
1answer
47 views

Are there any examples of consistent proper axiomatic extensions of classical logic?

By a proper axiomatic extension, I mean a logic with the same set of well formed formulas as classical logic, but with the set of theorems of the logic a proper superset of the theorems of classical ...
1
vote
0answers
51 views

Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
1
vote
1answer
34 views

Notation matter concerning 'or'-elimination

I have to show that $\{(\phi\lor\psi),(\lnot\phi)\}\vdash\psi$ using the following natural deduction rule: I don't know which of these is correct in term of notation: Could you please tell me? ...
4
votes
1answer
86 views

what mathematical theorem is this

Reading Gödel, Escher, Bach by Douglas R. Hofstadter, at p. 552, Achilles asks the Crab to play this piece: ∀a:∃b:∃c:<~∃d:∃e:<(SSd * SSe) = b ν (SSd * SSe) = c> ^ (a+a)=(b+c)> And it seems ...
2
votes
3answers
86 views

What does a period in between quantifiers mean?

I'm currently reading the notes (rather a book) of an MIT preliminary math course for discrete mathematics. In section on page 39, some ZFC axioms are written and roughly explained. For example, the "...
0
votes
1answer
26 views

Prove tautology using truth trees

Hi there I have to prove some tautologies using truth trees. I am doing this by negating the expresion and then trying to find contradictions on every branch. But I can't achieve this. I can't find ...
0
votes
1answer
79 views

Is there any System that's not logicist?

I have this assignment about different types of formal logic systems, like Lewis S5, Fuzzy Logic and some others, but now they ask me to search for any non logicist system, but I've search a lot and ...
8
votes
1answer
735 views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
1
vote
0answers
113 views

Green eyes/Common Knowledge problem proof verification

I was trying to solve the common knowledge problem, but am not sure if my proof is accurate. Here is a rough statement of the problem : 'An island consists of $k$ people with green eyes, all ...
1
vote
2answers
56 views

A question regarding contrapositive for implications

I am slightly confused about the negation for an implication after encountering two questions as follows: "Let P be the statement: If 3 is even, then 6 is even or divisible by 5. Write the negation ...
1
vote
2answers
38 views

Every finite subset of $\Gamma$ is consistent implies $\Gamma$ is consistent

Thm: If every finite subset of $\Gamma$ is consistent then $\Gamma$ is consistent. My notes claims that it can be implied from compactness of $\vdash$. Meaning: If $\Gamma \vdash A$ then there's a ...