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
vote
0answers
18 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 ...
1
vote
0answers
66 views

Why do some universities offer mathematical logic in different departments?

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

question about Herbert B.C. 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
36 views

Time and work aptitude problem for CAT preparation [on hold]

$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 ...
1
vote
1answer
25 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
58 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 ...
0
votes
2answers
43 views

A consistent set of formulas

In a logic system, a set $\Sigma$ of formulas is said to be inconsistent if $\Sigma \vdash \bot$, and consistent otherwise. Does it mean that $\Sigma$ is consistent if and only if $\Sigma \vdash ...
5
votes
1answer
61 views

Example of first order logic without equality.

Most logic texts say that = is a special symbol which is always part of our language. It is my understanding, though, that it is perfectly acceptable to consider = to be an ordinary binary relation ...
5
votes
1answer
208 views

Can the proof of fixed point theorems ever be constructive?

Overall, Brouwer fixed point theorem and Kakutani fixed theorem are non-constructive. Is there any established paper that demonstrates that there exists constructive proofs that do exactly what these ...
1
vote
1answer
52 views

Can universal instantiation be used more than once?

I'm trying to follow a proof in a logic text and it seems like the author used universal instantiation twice to reach the needed result. I was under the impression that you could only use UI one time ...
2
votes
3answers
54 views

Is there no propositional letter in first order logic?

In Kaye's math logic book, in propositional logic, there is a set of propositional letters, but there is no symbols for formulas or sentences in first order logic. Does the book miss it? Strangely, ...
1
vote
1answer
29 views

Relative Interpretations alla Kunen

at the moment I try to figure out some details of Kunen's "Relative Interpretation" Definition (within the 2013 Edition of his "Set Theory", p. 99 to 100): Definition If $\Lambda$ is some axioms ...
4
votes
1answer
55 views

Decision and the Uncountable Spectrum

In 2000, Hart, Hrushovski, and Laskowski classified all complete first order theories in a countable language up to their uncountable spectra. However, does this also imply that given a $any$ ...
1
vote
1answer
57 views

separating propositons with commas?

From Kaye's Mathematics Logic, about notation for propositional logic: Another place where we relax notation is in the notation on the left hand side of a turnstile symbol $\vdash$. Instead of ...
0
votes
2answers
33 views

Let Alphabet have only one unary function of symbol f. Prove that every term must have 3K+1 symbols for some k≥0.

I believe in order to solve this question, I have to perform induction on the complexity of terms. But I'm not sure how to begin.
0
votes
1answer
30 views

Language and interpretation.

Let $L$ be $\{c_1,c_2,P^1,R^2\}$ and consider the interpretation $M_I=<M,0,1,\{0,1\},\{<0,1>,<1,1>\}>$ for $M=\{0,1,2\}$. I have a few questions regarding how the determine if a ...
1
vote
2answers
32 views

What is a well built formula?

I am just beginning with Propositional Logic, and trying to understand few concepts: Well-built formula. If $3 + 2 = x$ , $\sqrt{5} − 3 > 2$, $x^2 + 2x − 1 = 0$ are atoms, then: $$((3 + 2 = x) ...
0
votes
0answers
21 views

proof of quantifier elimination in theory of real closed field/reals and existential quantifier over atomic formula

Standard proof of quantifier elimination for theory of real closed field/reals uses induction, as in Wikipedia article (http://en.wikipedia.org/wiki/Quantifier_elimination#Basic_ideas). However, it ...
1
vote
1answer
53 views

Are algebraic structures required to satisfy axioms?

Is it a requirement for algebraic structures, when studying universal algebra, to satisfy axioms? The reason I ask is because algebraic structures are only defined by a underlying set, a signature, ...
-9
votes
0answers
69 views

Logic Predicate Problem again [duplicate]

it dosent has any answer related to question on Primitive Recursive Predicate Problem if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? ...
-2
votes
0answers
33 views

Question and Recursive Predicate Problem [duplicate]

i get trouble with 2011 midterm exam question. if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? anyone could describe it for me? 1) $P(x) ...
-2
votes
0answers
31 views

primitive recursive predicate challenge [duplicate]

I see this question as a nice challenge on logic. Primitive Recursive Predicate Problem if P(x) and Q(x) be a primitive recursive predicate. which of the following is not a primitive recursive? ...
0
votes
0answers
36 views

simple exercise in Cylindric algebra

I am trying to gain a better understanding of cylindric algebra, so I made up this example. Given a general rule that someone's father's father is his/her grandfather: $\forall_X ~ \forall_Y ~ ...
1
vote
2answers
42 views

statements, propositions, formulas, and wffs

In a logic system, are statements, propositions, formulas, and wffs the same concepts? Do they all mean the elements in the formal language of the system, which are not terms? Are they either ...
-4
votes
1answer
54 views

Index Set & R.E Set & Primitive R.E [on hold]

I ran into a problem with 2011 midterm exam question on Theory of Computation course. i see it without any definition and detail. Suppose A is an index set (type of $R_\Gamma$ ) which is non trivial ...
0
votes
1answer
29 views

How to express the following meaning?

$\tan(\theta)$ is changing with $x_i,x_j,y_i$ and $y_j$ , how to express it in the above expression? should I use $\tan(\theta)_z$? thanks.
2
votes
3answers
73 views

How to express the meaning I mention in one formula?

There are two points: $(x_1,y_1),(x_2,y_2)$, if $|y_2-y_1|>|x_2-x_1|$ then $\tan(A)=\frac{|y_2-y_1|}{|x_2-x_1|}$ else if $|y_2-y_1|<|x_2-x_1|$ then $\tan(A)=\frac{|x_2-x_1|}{|y_2-y_1|}$ My ...
5
votes
1answer
67 views

Is there a formal way to describe classical logic as a reflective subcategory of constructive logic?

Working informally, we can take any proof $P$ in constructive (or intuitionistic) logic and turn it into a classical proof $cP$ by 'copying' it, since all the rules of constructive logic reappear in ...
1
vote
2answers
62 views

Represent “No naive is bad” using the first order logic.

How can I represent the following sentence using the first order logic? "No naive is bad" I had thought: $$\neg Naive(x)\vee Bad(x)$$
2
votes
1answer
36 views

Is this a valid natural deduction?

I'm trying to prove that $\{(p_1\implies p_2),p_1,(p_2\implies p_3)\}\vdash (p_3\vee p_5)$ which seems easy, but I'm unsure about a step in the way. I did: $1.\ p_1\implies p_2 \text{ (Pre)}\\2.\ ...
1
vote
1answer
31 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)$ ...
11
votes
0answers
156 views

The (un)decidability of Robinson-Arithmetic-without-Multiplication?

Take our old friend Robinson Arithmetic, and cut it down to a theory of successor and addition. To spell that out (just to ensure that we are singing from the same hymn sheet), take the first-order ...
0
votes
0answers
43 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
2
votes
1answer
38 views

Relations and functions with valence 0

From http://en.wikipedia.org/wiki/First-order_logic#Non-logical_symbols Relations of valence 0 can be identified with propositional variables. For example, P, which can stand for any ...
1
vote
1answer
46 views

Can True and False be represented without quantifies?

From http://en.wikipedia.org/wiki/First-order_logic#Logical_symbols Sometimes the truth constants T, Vpq, or ⊤, for "true" and F, Opq, or ⊥, for "false" are included. Without any such logical ...
0
votes
2answers
46 views

Are variables logical or non-logical symbols in a logic system?

Are variables logical or non-logical symbols in a logic system? I understand constants are 0-ary logical operation symbols. I think variables are non-logical symbols. But here are two contrary ...
3
votes
1answer
99 views

What does “calculus” mean?

"calculus" and "formal system" From http://en.wikipedia.org/wiki/Propositional_calculus#Terminology a calculus is a formal system that consists of a set of syntactic expressions ...
0
votes
1answer
65 views

How do I notate that $1/2$ children do not exist

Suppose that, the average person has $2$ $1/2$ children. only whole children exist It should be straightforward to notate: If an average person exists, then that person has two $1/2$ children ...
0
votes
3answers
81 views

Are axioms assumed to be true in a formal system?

In a logical system, there is assignment of truth values to the sentences in the language, and axioms are assigned the true value. A logical system is a formal system. In a formal system, there is ...
0
votes
2answers
66 views

Logic Inference Challenge [closed]

I read some logic course recently, would you please anyone say my inference is True? $\forall x S(x) \to \exists y(R(y)) \Rightarrow \forall x \exists y(S(x) \to R(y))$.
4
votes
1answer
85 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
0
votes
3answers
25 views

Can the proof for the following 4 cases be simplified to 2 cases?

Let $X$ and $Y$ be finite and disjoint sets. Suppose we are required to prove the following: $|X|\ge 0 \text{ and } |Y|\ge 0 \Rightarrow Q $ where $Q$ is some statement. Therefore, I know I need to ...
1
vote
1answer
48 views

Zorn's lemma and maximal ideals

Let's consider two statements: Zorn's lemma and theorem about existence of maximal ideals in commutative ring with $1$. It's easy to prove that Zorn's lemma implies existence of maximal ideals. I ...
1
vote
1answer
53 views

How to prove theorems using axioms and lemmas [closed]

How do I prove the following? Theorem L 10. $(\sim B \implies \sim A) \implies (A \implies B)$ Theorem L 11. $\sim \sim B \implies B$ Theorem L 12. $B \implies \sim \sim B$ We are actually ...
-1
votes
1answer
49 views

Logic Inference Problem [closed]

I read that the inference below is false, but I think it's true. Would you explain it to me please? $\forall x \exists y(S(x)\to R(x,y)) \Rightarrow \forall x(S(x) \to \exists y R(x,y))$.
1
vote
2answers
130 views

Mathematical statements that cannot be proved or disproved [on hold]

I've recently been reading about the continuum hypothesis and am fascinated by the fact that it cannot be proved or disproved, despite the fact that the statement itself is either true or false. What ...
1
vote
1answer
27 views

Transform a k-CNF formulae to conjunctions of boolean literals

The question comes from Mehryar Mohri's Foundations of Machine Learning. In Example 2.5 the book transform a $k$-CNF formula to conjunctions of boolean literals, but I can't understand the trick in ...
2
votes
0answers
62 views

Can we always give a direct proof? [duplicate]

This is something I was wondering about for quite a while. Is it possible to construct a statement that can only be proven by using 'proof by contradicition' or contraposition? Or to put it ...
-1
votes
1answer
67 views

Logic Challenging Question

I see this statement on the book: Assuming a set $\Sigma = \{ φ_1, φ_2, \ldots \}$, for each valuation v, we have n such that $v(\varphi_n)=1$. in this case we have n, such that: $\vDash \varphi_1 ...
2
votes
1answer
80 views

Expressibility of Gödel's Incompleteness Theorem

Can Gödel's Incompleteness Theorem be expressed as a formal sentence in ZFC and be proven formally or is it inherently meta-mathematical? (Note: I am referring to the theorem itself, not the ...