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)

2
votes
1answer
1k views

re-writing a $\min(X,Y)$ function linearly for LP problem

I am trying to formulate an LP problem. In the problem I have a $\min(X,Y)$ that I would like to formulate linearly as a set of constraints. For example, replacing $\min(X,Y)$ with some variable ...
1
vote
1answer
851 views

Structural Induction — Logic

I have to prove the replacement lemma by structural induction. We define the logical complexity of a formula as follows: Let $\varphi$ be a formula. If $\varphi \in \left\{t, f\right\} \cup IV$ ...
2
votes
2answers
295 views

Lowenheim-Skolem theorem and first-order model

In Wikipedia, it says that a nonstandard model of natural numbers is not first-order. But, from the Lowenheim-Skolem theorem, I don't see anything that points to this conclusion. Can anyone show me ...
10
votes
1answer
443 views

Finding Expressively Adequate truth Functions

I was wondering if someone could help me count the total number of Truth Functions of 3 variables, that can generate all the possible truth functions.. I got 56 but I'm not sure of the answer. EDIT: ...
4
votes
2answers
723 views

First order logic - why do we need function symbols?

Using function symbols in first order logic forces us to define "terms" inductively, which makes many proofs longer and much more tedious. Of course, function symbols simplify matters when trying to ...
4
votes
0answers
192 views

Starting my nephew out on the journey to higher mathematics.

My nephew is 8 years old and shows great promise as a student. Sadly, as most of you know most programs in secondary education don't offer any foundational courses for higher mathematics. What ...
3
votes
3answers
470 views

Sheffer stroke the most important advance in logic?

I think I once read, or heard, that Bertrand Russell once said that the discovery that all logical operators are expressible in terms of the Sheffer stroke was the most significant advance in logic ...
5
votes
3answers
341 views

Compactness theorem for propositional calculus - nice uses?

The compactness theorem for propositional calculus states that a set of propositional sentences has a model (satisfying assignment) if and only if every finite subset of it has a model. I'm looking ...
4
votes
1answer
130 views

Generic reals in forcing iterations

Suppose that $(\mathbb{P}_{\alpha}, \underset{\sim}{\mathbb{Q_{\alpha}}} : \alpha<\beta)$ is a forcing iteration, and that for each $\alpha$, there is a name $\underset{\sim}{\eta_{\alpha}}$ for ...
3
votes
1answer
149 views

A Formal and Precise treatment of Simplification?

I am looking to gain a deeper understanding of, and increase my own skill in "Mathematical Simplification". But I've been finding the concept overly vague and haven't been able to find any good ...
8
votes
2answers
564 views

Gromov-Hausdorff distance and the “set of all sets”

If $X$ and $Y$ are compact metric spaces, then the Gromov-Hausdorff distance, $d_{GH}(X,Y)$, describes how far $X$ and $Y$ are from being isometric. In the Wikipedia article on Gromov-Hausdorff ...
2
votes
3answers
175 views

Why $\bar{A}A+\bar{A}B\Rightarrow B$?

I was reading the following from a book of probability theory: A contradiction $\bar{A}A$ implies all propositions, true and false. (Given any two propostions $A$ and $B$, we have ...
2
votes
1answer
627 views

Question about the proof of consistency iff satisfiability of a theory

In pretty much any Model Theory or Logic textbook you will find the following claim, where $T$ is a theory (a set of $\mathsf{L}$-sentences), $T$ is consistent if and only if $T$ is satisfiable. ...
2
votes
2answers
680 views

Infinite Disjunctions and Conjunctions

While doing work on propositional logic (namely, proving the Generalized De Morgan's Laws), I found myself wondering why precisely an infinite conjunction or disjunction are not permitted, due to the ...
2
votes
1answer
222 views

Independence results in first-order PA and second-order PA

There are statements $\varphi$ that are independent of first-order Peano Axioms. Are these statements also independent of second-order Peano Axioms? I'm reading Wikipedia articles around ...
3
votes
1answer
93 views

combinatory basis for head reduction

Consider combinatory calculi that don't have tail reduction. So there may be combinators $x$, $y$ and $z$ such that $y\to z$ but $xy\nrightarrow xz$. We can still write every combinator as a ...
2
votes
1answer
116 views

First order logic with N quantifiers - the number of members in the domain matters for validity/consistency in this situation?

Would a proposition of first-order logic, with N quantifiers, always held the same logical status (of consistency or validity) no matter if the domain has N members, or N + x members? [x being a ...
0
votes
2answers
285 views

Predicate Logic Problem

Given the following predicates: Truck(X): X is a truck Person(X): X is a person IsBlue(X): X is of blue color Like(X,Y): X likes Y Expensive(X): X is expensive Write following statement in ...
3
votes
1answer
122 views

Potentially stupid question about the Boolean Satisfaction Problem

So I recently learned about the boolean satisfaction problem in an article that linked it to super mario brothers. Anyways, I was wondering why you can't solve the problem in the following way. ...
-1
votes
1answer
96 views

Meaning of a Logical Operator

Is it possible to know what those operator mean if they must be involved in this logicical condition? What is all the possible meaning of those two symbol if you don't know the symbol's meaning ...
0
votes
3answers
161 views

Equivalent formula - how do I go from $\neg (P \wedge \neg Q) \vee (\neg P \wedge Q)$ to $\neg P \vee Q$?

This is item "c" of question 11 from section 1.2 in Daniel J. Velleman's "How to Prove It - A Structured Approach" (great book). The question asks that I find a simpler formula equivalent to $\neg (P ...
1
vote
2answers
148 views

Propositional Logic by Resolution Problem

I'm lost on this example problem. My professor did not explain it very well and the book is no help either. Any help would be appreciated. Here goes: For each of the following cases, you are given ...
1
vote
1answer
176 views

Primitive Recursion Question

I am having trouble understanding the definition of primitive recursion. I would like to have clarification of the definition with simple applications of the definition with examples. The definition ...
0
votes
1answer
131 views

Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$

Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...
2
votes
1answer
253 views

How to write a first order formula with unspecific parameter

Excuse me for the awkward wording. I'm new to logic. What I really mean is this: Consider the number theory that spawns from the structure $N=\{\mathbb{N},+,\cdot\}$ (equipped with the usual ...
2
votes
4answers
145 views

All naturals are T-finite, all finite sets are T-finite

In Jech's Set Theory, there is defined T-finite, where a set $S$ is T-finite if every non-empty $X\subseteq\mathcal{P}(S)$ has $\subseteq$-maximal element. [ie. there is $u\in X$ s.t. there is no ...
2
votes
2answers
100 views

Proving the free occurrence of a variable is primitive recursive

Show that FreeOcc$(m,n,i)$, which holds when $m$ is the godel number of a wff $\varphi$ and the $i^{th}$ symbol of $\varphi$ is a free occurrence of the variable $x_{n}$, is primitive recursive. ...
0
votes
1answer
176 views

Propositional calculus and preferences.

Propositional logic is able to represent the phrase "If every individual prefer any alternative x to alternative y..."? Namely, is the propositional logic able to manage the concept of "preference"?
5
votes
3answers
472 views

How should I understand “$A$ unless $B$”?

The statement is from the book Linear Integral Equations by Rainer Kress: A compact operator cannot have a bounded inverse unless its range has finite dimension. Here are my questions: How ...
12
votes
6answers
641 views

When does the set enter set theory?

I wonder about the foundations of set theory and my question can be stated in some related forms: If we base Zermelo–Fraenkel set theory on first order logic, does that mean first order logic is not ...
2
votes
2answers
276 views

the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
0
votes
2answers
98 views

How to do decide a necessary truth for greater formulae complexity than $\Delta_{0}$

How does one determine if a sentence in predicate logic is a theorem? That is to say, for sentences with a greater complexity hierarchy than $\Delta_{0}$, what general methods can I use to decide if a ...
11
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
0
votes
3answers
128 views

In which of following stuctures is valid implication $x\cdot y=1\implies x=1$?

In which of following stuctures is valid implication $x\cdot y=1\implies x=1$? a) $(\mathbb{N}, *)$ b) $(\mathbb{Z}, *)$ c) $(\mathbb{Q}, *)$ d) $(\mathbb{C}, *)$ Solution is ...
7
votes
2answers
245 views

Consistency of PA: why other proofs?

Completeness theorem affirms that a formal first order system is consistent iff it has a model. The FOL number theory(PA) or First Order Arithmetic has a model, which is the natural numbers structure. ...
10
votes
3answers
1k views

How to prove an axiom system is consistent?

I would like to know whether systems capable of proving other systems consistent, use any methods fundamentally different then 'Add 'T is consistent' as axiom, then T is consistent, QED'. How does ...
9
votes
5answers
397 views

How do we know that we'll never prove a contradiction in Math

I know that we can prove a contradiction in naive set theory. Let D be a set of all sets that don't contain itself. Say D does not contain D. Then D contains D. That means D contains itself. A ...
0
votes
2answers
111 views

Impredicative Comprehension about classes?

The Predicative Comprehension in NBG is $\exists X\forall y(y\in X \iff \phi)$, where $\phi$ is a formula where no bound class variables occur. A possible quantification over classes (I know this is ...
5
votes
1answer
559 views

Mendelson's Logic book “cheats” in the propositional calculus?

In Mendelson's book ("Introduction to mathematical logic") he defines truth values for sentences in the propositional calculus using truth tables. However, it seems to me he assumes implicitly that ...
35
votes
5answers
2k views

Does “This is a lie” prove the insufficiency of binary logic?

If "This is a lie" were a true statement, its fulfilled claim of being a lie implies it can't be true, leading to a contradiction. If it were false, it could not be a lie and thus had to be true, ...
1
vote
0answers
90 views

Proving that a formula cannot be proven (has no formal proof) in a given deduction system

In my homework I was asked to prove that a deduction system for modal logic with $\rightarrow$, $\neg$ and $\square$, with 4 axioms and 2 inference rules (MP and a $\square$-generalization rule), is ...
2
votes
3answers
244 views

A question about a certain way to define mathematical objects

It is common in mathematics to see definitions of the following form: we begin with a certain object $A$. we perform some construction depending on a choice of some parameter $\lambda\in\Lambda$ for ...
1
vote
2answers
128 views

Triangle Requirements based of triangle Inequality

In a Geometry course we are dealing with triangle inequality and two statements arose: "For any triangle, any side is smaller the the sum of the others." and "For any triangle, the largest side is ...
4
votes
1answer
201 views

Proof with axiom of choice implies proof without?

Is there a theorem that guarantees the existence of a proof not using AC given there is a proof using AC, at least under some circumstances? What is its name (if there is one) and its most general ...
1
vote
1answer
203 views

Understanding HORNSAT… all variables true?

I'm trying to understand the problem of HORNSAT: given a set of Horn clauses, is there a satisfying assignment. A Horn clause has the form $(x_1 \wedge x_2 \wedge \cdots x_k) \rightarrow v $ where all ...
5
votes
1answer
333 views

completeness of the theory of real numbers

The theory of natural numbers (such as Peano axioms) is incomplete due to Gödel's incompleteness theorem. But, I heard that the theory of real numbers is complete (edit: not in the sense of ...
1
vote
1answer
801 views

Right and Left arrow notation in proof.

I'm studying vector spaces and I'm reading a proof where the authour uses the symbols $$(\Rightarrow)$$ and $$(\Leftarrow)$$ when proving a theorem. He doesn't use them in context, but rather ...
0
votes
1answer
189 views

How to compare quantities in first order logic?

Say: $x_i$ are members of a set (e.g. nodes of a graph) and there is a quantity $V(x_i)$ associated with each (e.g degree of the node) Let's say $Q(x_i,x_j)$ denotes the equality $V(x_i) = V(x_j)$ ...
4
votes
2answers
253 views

In modal logic, is $\lnot\square P\equiv\lozenge\lnot P$?

"Possibly" and "necessarily" seem very much like "exists" and "for-all", but does the following hold true: $\neg \square P \equiv \lozenge \neg P$ in the same way as $\neg\forall P \equiv \exists\neg ...
5
votes
4answers
405 views

How to start with automated theorem proving?

I'm interested in this question, but I'm not going to list my knowledge/demands but rather gear it to more general purpose; so the first thing concerns the prerequisites, i.e. How much ...