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)

2
votes
2answers
143 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
vote
2answers
226 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
41 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 ...
2
votes
2answers
83 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
188 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. ...
1
vote
2answers
48 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$?
1
vote
2answers
102 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
66 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
62 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
1answer
266 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 ...
2
votes
1answer
73 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
81 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
153 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 ...
6
votes
1answer
103 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 ...
6
votes
1answer
336 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
89 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
89 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
39 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
79 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
108 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
60 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
39 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
60 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) ...
1
vote
1answer
76 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, ...
0
votes
1answer
78 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 ~ ...
2
votes
2answers
613 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 ...
0
votes
1answer
39 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
116 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
219 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
66 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
53 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
749 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)$ ...
15
votes
2answers
271 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 ...
2
votes
0answers
59 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
112 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
55 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 ...
1
vote
2answers
190 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 ...
4
votes
1answer
199 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
71 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
111 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
82 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))$.
5
votes
1answer
380 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
27 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
85 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
2answers
171 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
64 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 ...
2
votes
1answer
112 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 ...
0
votes
1answer
51 views

proving{$\neg(\forall x)\alpha \rightarrow \alpha$}$\models$$(\forall x)\alpha$

prove {$\neg(\forall x)\alpha \rightarrow \alpha$}$\vdash\space(\forall x)\alpha$ Im not sure what is the convention, so to be clear I am talking about proving the formula from the seven axiom ...
6
votes
3answers
381 views

Is the pseudomenon a statement?

I'm asking this because I'm teaching a class on paradoxes for kids, and I realized I have no idea what the answer to this question is. It is a research question in the pedagogical sense, I suppose. ...
1
vote
2answers
308 views

An Uncountable language , A Model of $\mathbb{N}$, A Problem.

Edit 1: I messed up my original question, but Arthur Fischer answered my question anyway. Edit 2: We can actually restrict $L$ to the language in arithmetic with the prdicate $P_{\mathbb{P}}$. ...