Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

-1
votes
0answers
10 views

primitive recursive function and simultaneous recursion

i think: We can apply simultaneous recursion with more than two functions, defining each of then at n + 1 in terms of the values at n. We can also define simultaneous recursion for functions on an ...
2
votes
1answer
25 views

How to rewrite and simplify sequence of negative words?

What's the general method or algorithm or procedure, for longer sentences replete with them? I bold them below. I ask this here because I venture that if I rewrite these sentences with prepositional ...
1
vote
3answers
44 views

Logically proving that the smallest factor of an integer is prime

I argued it as follows, let $p, q, r$ and $s$ be predicates $p$: "$m$ is divisible by $k$" $q$: "$k$ is divisible by $n$ ($n < k$ and $m$ is divisible by $n$) " $r$: " $k$ is the smallest factor ...
0
votes
0answers
19 views

A question about an special kind of proof [on hold]

Is there some proof method in which I can prove the existence of a mathematical object? How can I prove a conjecture that it is an existence statement of a mathematical object? Which are the ...
4
votes
1answer
51 views

The “converse” of $P\rightarrow(Q\rightarrow R)$

As everyone know, even when reading mathematics books, a paragraph written in natural language contains much more information than just its purely logical translation. For my next tutor session, I am ...
4
votes
2answers
49 views

What is a finitary proof?

I started reading "mathematical logic", by J.R.Shoenfield, but I cannot quite understand a sentence in the very first chapter: Proofs which deal with concrete objects in a constructive manner are ...
1
vote
1answer
49 views

Natural deduction, from premise $\lnot p \lor \lnot q$ to conclusion : $\lnot(p \land q)$

What's the natural deduction of this exercise? Premise: $\lnot p \lor \lnot q$ Conclusion: $\lnot(p\land q)$ I must have something like the following, but I do not know how to start.
-2
votes
2answers
60 views

Creating Truth tables [on hold]

What is the truth table for the logical expression? $$ (p \land (p \to q) \land r) \to ((p \lor q) \to r) $$ Frankly, I'm lost.
0
votes
1answer
48 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
-1
votes
0answers
37 views

f(x)= {$ \uparrow$ when $x \in K$, 2 when otherwise } is partial recursive? [on hold]

Recently i learned some material on partially recursive topic. Partially computable functions are also called partial recursive, and computable functions, i.e., functions that are both total and ...
0
votes
1answer
57 views

Why is $x\mapsto x$-th prime number a partial recursive function?

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive. In computability ...
0
votes
2answers
89 views

Is the formula $ \forall x (A(x) \to B(x)) \to ( \exists x A(X) \vee \exists x B(X)) $ logically valid [on hold]

Recently I studing on logic. I try to solve some first order formula that not valid. Why the following first order formula is not logically valid? every expert would please help me? 1- $ \forall x ...
3
votes
3answers
73 views

Deriving $A \rightarrow ( B \rightarrow C ) \rightarrow ( ( A \rightarrow B ) \rightarrow ( A \rightarrow C ) )$ in the sequent calculus

I need to prove the following theorem: $A\to (B\to C) \to ((A\to B) \to (A\to C))$ using the sequent calculus method. Using the rules: $$ G, A \Rightarrow B,D \over G \Rightarrow A \to B , D ...
0
votes
1answer
51 views

Undecidability of First Order Logic [on hold]

friends! I read in Ebraham's Outline of Logic that first order logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. It is undecidable ...
0
votes
1answer
27 views

What does it mean for a model to have 'the less cardinal possible'?.

I've encountered this question, and I'm not sure if my interpretation is right because if it is, seems like there would be very trivial models (and there would no problem at all). Ex 1: $\{\forall x ...
3
votes
1answer
48 views

How can I imagine a model of $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$?

Gödel's second incompleteness theorem states that if $\mathsf{ZF-Inf}$ is consistent, then $\mathsf{ZF-Inf} \nvdash \mathsf{Con(ZF-Inf)}$. Moreover, if $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$ ...
0
votes
0answers
18 views

What is difference between logical implication and conditional statements? [duplicate]

I want to know that what is Logical implication? Is it meant by converse, inverse and contraposition? Is this logical implication is same as conditional statement? Hey i m a new user on this site. ...
-1
votes
1answer
44 views

increasing computation function relation with recursive [on hold]

i read this post: A is recursive iff A is the range of an increasing function which is recursive I read in this tutorial: http://www.comp.nus.edu.sg/~fstephan/recursiontheory-pstopdf.pdf that the ...
1
vote
1answer
35 views

Incompleteness theorem and regarding consistency of theory $T$

By Godel's incompleteness theorems, a formula expressing consistency of a theory that can contain Peano arithmetic cannot be derived or contained from/in the theory. Godel's completeness theorem ...
0
votes
1answer
55 views

Godel's completeness theorem and formula that states consistency of ZF

Godel's completeness theorem, in original formulation, says that every logically valid statement/formula has finite deduction of a formula. Now then there is Godel's incompleteness theorem. Would this ...
2
votes
1answer
28 views

Does introduction and elimination rule for an operator determine uniquely its truth table?

My question is regarding the inference of a truth table for an operator given how it behaves according to introduction and elimination. This follows from an exercise I read, and it got me thinking if ...
1
vote
0answers
48 views

Are there axiomatizations of first order logic or set theory defined in first order logic or set theory?

There are several axiomatizations for number theory, group theory, and other theories represented in first order logic. Further, these theories are also representable in set theory such as $\sf ZFC$ ...
0
votes
0answers
124 views

range of one increasing computation function?

We know that that the range of any recursive partial function is recursively enumerable. Also we know the fact: Set A is recursive if and only if it is range of some increasing section partial ...
0
votes
1answer
40 views

Problems On Many-one Reducible [on hold]

In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. ...
1
vote
1answer
57 views

How can $A \supset B$ be a synonymous of $A \Rightarrow B$? [duplicate]

From time to time, although not so commonly, I see $A \supset B$ written with seemingly the same meaning as $A \Rightarrow B$. Ex. in Constructive Type Theory and Interactive Theorem Proving, on page ...
-1
votes
1answer
48 views

Recursively enumerable language [on hold]

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively ...
1
vote
1answer
31 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
0
votes
0answers
44 views

Power of 3 Elimination Tournament Seeding

Most tournaments are $1$-on-$1$. They use seeding system where $1$ v $16$, $2$ v $15$... $1$ v $16$ $8$ v $9$ $5$ v $12$ $4$ v $13$ $6$ v $11$ $3$ v $14$ $7$ v $10$ $2$ v $15$ is correct assignment ...
28
votes
5answers
2k views

Examples of “Non-Logical Theorems” Proven by Logic

I am still an undergraduate student, and so perhaps I just haven't seen enough of the mathematical world. Question: What are some examples of mathematical logic solving open problem outside of ...
1
vote
2answers
47 views

Prove or disprove the syntactic consequence.

Consider $\forall x(Px\implies Qx)$. Which of the following are syntactic consequence of the former?: (i)$\forall xPx $, (ii) $\exists x Px$, (iii) $\exists x (Px\wedge Qx)$, (iv) $\neg\exists x ...
0
votes
0answers
106 views

Is there a reasonably strong foundation for mathematics that can prove its on consistency?

Ever since I have read about both Gödel's incompleteness theorem(s?), which I believe roughly means: "A system at least as strong as Peano arithmetic cannot prove its own consistency." and learned ...
2
votes
1answer
29 views

Two-place position predicate problem

I see this sentence in one Logic Note Tutorial. What arguments are involved in any situation is determined by the meaning of the predicate. Sleeping can only involve one argument, whereas placing ...
-1
votes
1answer
48 views

Logic Substitution Problem

I see this formula on Logic Text Book, I take a picture and insert it here in order to one expert help me and correct the error. t is a term and $\varphi$ is a formula. I think one of ...
1
vote
0answers
58 views

How do I read a ⊢ ab in mathematical logic?

I'm beginning to read the interesting Introduction to Mathematical Logic, by Detlovs and Podnieks, but I'm having some troubles with a few simple concepts. In an early paragraph, the following theory ...
2
votes
1answer
61 views

Relations between Theories and Categories

I'm just toying around with some thoughts, trying to grock some concepts: It seems that every formal theory induces a locally small category via interpretations: its objects are structures that ...
3
votes
2answers
65 views

Types versus kinds and sorts

In the context of logic, especially Higher‑Order‑Logic and Calculus‑of‑Construction, what is a kind and how does it relates to and differs from a type? My raw guess if that a kind is the higher level ...
-1
votes
1answer
33 views

Set of Logical Result Problem [on hold]

If we have a set of predicate formulas $A$, and there is an algorithm such that for every predicate formula $X$, (with input $X$), output YES iff $X \in A$. My question is about set of logical result ...
0
votes
2answers
70 views

Well Formed Expression (Polish Notation)

In Kunen's book Foundation of Mathematics the definition of a well formed expression (wfe) of a lexicon for Polish notation $\langle W, \alpha \rangle$ ($W$ is a set and $\alpha:W\to\omega$ is a ...
2
votes
0answers
35 views

Showing non-independence of a statement with respect to an axiomatic system

Is it possible to show that either a statement or its negation is non-independent of say, ZFC, without actually proving or disproving said statements? The reason I ask is because I've read of proofs ...
1
vote
2answers
31 views

Definition and decidability of bounded quantifiers

Consider quantifier-free formulas $P(x,y) = Q(x,y)$ of Peano arithmetic. Consider $P(x,y),Q(x,y)$ to be terms composed of variables $x,y, \operatorname{succ}, +, \times$. Note that these are ...
0
votes
2answers
57 views

Clever Substitution Notation for Logic Formulae

Assume I have a first order- ($\mathsf{FO}$-) formula $ \varphi(x)$ with free variable $x$ and bounded variables $x',x''$. Then, $\varphi(x) \in \mathsf{FO}^3$ since it has $3$ distinct variables. ...
2
votes
2answers
35 views

Reducing $ab' + cb + ac$ to $ab' + cb$

Boolean expressions $I = ab' + cb + ac$ and $J = ab' + cb$ have the same truth table. Then why expression $I$ can't be reduced to expression $J$?
0
votes
2answers
86 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
3
votes
1answer
46 views

A question about second-order logic and inaccessible cardinals.

Let $\kappa$ denote an inaccessible cardinal, and suppose $T \in V_\kappa$ is a second-order theory. Now consider some mathematical structure $X \in V_\kappa$. Then I think it is clear that $X \models ...
1
vote
1answer
52 views

Comprehension and Impredicativity

Wang and McNaughton (Les Systemes Axiomatiques de la Theorie des Ensembles, 1953) discuss briefly the topic of impredicativity in chapter 2 (titled 'Type Theory') of the above mentioned book, but I'm ...
2
votes
1answer
142 views

Why do some universities offer mathematical logic in different departments? [on hold]

I'm thinking of pursuing mathematical logic after my undergraduate work and I have noticed that some universities offer mathematical logic in their philosophy department while others offer it in their ...
0
votes
1answer
80 views

question about Herbert B. Enderton's book : A mathematical introduction to logic

I hope someone can help me. My question arises on page 114 of the second edition of the book. Here the notion of 'prime formula' is introduced to enable one to view a formula as a formula of ...
0
votes
1answer
41 views

Time and work aptitude problem for CAT preparation [closed]

$A$ can do a job in $10$ days, $B$ in $12$ days and $C$ in $15$ days. They all start working together but $A$ leaves after $2$ days and $B$ leaves $3$ days before the job is completed (i.e. $C$ works ...
2
votes
1answer
43 views

If a version of GCH holds for Chang's $\kappa$-constructibility, does a version of GCH hold for $L_{\infty}$?

In C.C. Chang's paper "Sets Constructible Using $L_{\kappa \kappa}$" one can "deduce a version of the GCH, theorem VI [(iv)--my comment], assuming that all sets are $\kappa$-constructible." Now ...
0
votes
1answer
62 views

Is this theorem about soundness or completeness?

$\def\True{\top}\def\False{\bot}$ In Kaye's math logic, $X$ is a set of propositional letters, and $BT(X)$ is the set of Boolean terms over $X$. There is a theorem about its valuation on the binary ...