Questions about 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)

0
votes
1answer
53 views

Is formula satisfiable using resolution

When I use the resolution "tree" to determine whether formula is satisfiable, it gives me wrong result: Can you find my mistake and explain how is it done right? Grant
1
vote
1answer
142 views

Questions on Basic Terminology in Mathematical Logic

As a beginner, I'm overwhelmed by the usage of terminology , such as theory, model, interpretation, structure et al, which are omnipresent in Mathematical logic. Here's my understanding about them: ...
1
vote
2answers
302 views

What is the cardinality of the countable ordinals?

Every countable ordinal $\alpha$ can be written uniquely in Cantor canonical form as a finite arithmetical expression, say $C(\alpha)$. We thus have the 1-1 correspondence between the countable ...
5
votes
1answer
315 views

Compactness theorem and Tychonoff theorem

This thread has it compactness theorem can be derived from Tychonoff theorem. I'm interested in how this can be done, but got stuck. Here's how far I understand: Following the version of campactness ...
1
vote
3answers
991 views

Double implication

The present question is about a double implication. I have the following implications: $(a)\implies (b)\implies ((c)$ or $(a))$ Can I deduce that $(b)\implies(a)$ only?
2
votes
1answer
78 views

Pullback of an empty family

As I understand it, in the category of sets, there is no morphism $\{1\}\rightarrow\emptyset$. On the other hand, is one permitted to say sentences like the following? "Consider the empty family ...
3
votes
2answers
122 views

Assigning attributes to elements of a empty set

I was wondering if one could assign random attributes to the elements empty sets, even contradictions. Because there are no elements, I can say something like: $\forall x \in \emptyset.P(x) \land ...
0
votes
1answer
116 views

Understanding entailment

I am trying to understand the concept of entailment when used within the context of inductive logic programming. Could somebody explain this to me? In other words: if A entails B, this means that B ...
8
votes
3answers
2k views

Proof of the Compactness Theorem for Propositional Logic

I have a problem understanding the proof for the compactness theorem for propositional logic in my logic course. The compactness theorem states that there is a model for an infinite set $S$ of ...
5
votes
1answer
250 views

Absoluteness of $ \text{Con}(\mathsf{ZFC}) $ for Transitive Models of $ \mathsf{ZFC} $.

Is $ \text{Con}(\mathsf{ZFC}) $ absolute for transitive models of $ \mathsf{ZFC} $? It appears that $ \text{Con}(\mathsf{ZFC}) $ is a statement only about logical syntax. Taking any $ \in $-sentence $ ...
15
votes
6answers
2k views

Book on the Rigorous Foundations of Mathematics- Logic and Set Theory

I am asking for a book that develops the foundations of mathematics, up to the basic analysis (functions, real numbers etc.) in a very rigorous way, similar to Hilbert's program. Having read this ...
2
votes
1answer
46 views

If every assignment that models $F$ also models $G$, does it mean that $F=G$?

$G$ and $F$ are formulas, If every assignment that models $G$ also models $F$, does it mean that $F=G$? The question may be silly, but I'm not sure if there's some obscure scenario where $F\neq G$.
0
votes
1answer
60 views

How to determine the logical converse of of a result

I want to determine the logical converse of this result. I am confused. The complex number $s=α+iβ$ is a solution of $f(s)=0$ and $α=1$ if and only if $g(s)≠0,h(s)=u(s)$ and $d(s)=v(s)$. Here the ...
2
votes
1answer
60 views

Possible typo in Just/Weese's set theory

In Just Weese on page 197 there are the following corollaries: Regarding Corollary 24: Is this a typo and should say "$CON(ZF) \not\rightarrow CON(ZF + \exists \text{ "a strongly ...
4
votes
1answer
105 views

Connection between dual space V* and negation P^c

Notice the following similarity between the vector space dual and negation in propositional logic: $$ V^* \equiv V \rightarrow F $$ $$ P^c \equiv P \rightarrow \bot $$ Is there some general notion ...
2
votes
1answer
138 views

Understanding the model-theoretic proof of Hilbert's Nullstellensatz

The proof I am talking about goes like this: Given $k$ algebraically closed and $(f_1,..,f_k)=I\neq (1)$ an ideal in $A=k[x_1,..,x_n]$, let $m$ be a maximal ideal with $I\subseteq m$ and observe that ...
9
votes
6answers
610 views

Books in foundations of mathematical logic

I'm a civil engineer that spends all of its free time (with the permission of my wife and my two children) studying set theory and mathematical logic. For instance, I've read and enjoyed "Axiomatic ...
1
vote
1answer
243 views

Programming related calculus & math symbols and questions

I am reading a textbook for my next semester just for fun. I didn't study so hard during the high school so I have missed out many vital information. Questions: 1) What is λ -calculus and λ (in ...
6
votes
3answers
701 views

How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that $\{\lnot, \# \}$ is not complete. A set of connective symbols is complete, if every function $G : \{F, T\}^n ...
4
votes
3answers
343 views

Expressing a first order logic sentence that requires counting

Given the set $ R(x,t)= \{ (a, 1), (b, 1), (c, 1), (a, 2), (b, 2) \}$. How can I express with a first-order logic sentence "if for $t$ the amount of tuples $(x, t)$ is equal to $d$, then for $t+1$ the ...
56
votes
3answers
14k views

Proof by contradiction vs Prove the contrapositive

What is the difference between a "proof by contradiction" and "proving the contrapositive"? Intuitive, it feels like doing the exact same thing. And when I compare an exercise, one person proves by ...
0
votes
4answers
418 views

A logic puzzle from TES: Arena

Its nice when games have riddles hidden in them. While playing TES:Arena, I came across an unusual logical puzzle: There are 3 cells. If Cell 3 holds worthless brass, Cell 2 holds the gold key. If ...
22
votes
6answers
1k views

Axiomatic characterization of the rational numbers

We have the well-known Peano axioms for the natural numbers and the real numbers can be characterized by demanding them to be a Dedekind-complete, totally ordered field (or some variation of this). ...
3
votes
2answers
228 views

What area of mathematics is this problem asking about?

A colleague posted this on a whiteboard (as a brain-teaser I guess): A $\rightarrow$ B; B $\rightarrow$ C; AD $\rightarrow$ E; BE $\rightarrow$ C; BF $\rightarrow$ D; AC $\rightarrow$ F What is ...
1
vote
2answers
158 views

Express each of these sentences in terms of $Q(x, y)$, quantifiers, and logical connectives,

Let Q(x,y) be the statement “x has been a contestant on quiz show y”, where the domain of x is the set of students and the domain for y consists of all quiz shows. For each of the English sentences ...
0
votes
1answer
414 views

Write statements using quantifiers

I want to know how to properly write below statements using quantifiers and simple relations ($\in, =, <, \leq, |$): Between any 2 rational numbers exists number different than these 2. Every ...
9
votes
4answers
495 views

How to introduce advanced set-theoretical objects to philosophy students?

First, I apologize if MSE is a bad fit for this question. I'm going to give a course as the last course of "elementary set theory" (the previous courses were not given by me). I planed to introduce ...
5
votes
1answer
126 views

How to multiply out a statement form?

I got this form: (not M or V) and (A or not M) and (not B or M) and (B or V) and (A or not V) and (not A or B) Or: $$(\neg M\vee V) \wedge (A\vee\neg M) \wedge (\neg B \vee M) \wedge (B\vee ...
1
vote
2answers
237 views

Gödel's Incompleteness Theorem — meta-reasoning “loophole”?

Gödel's Theorem says that I can construct a mathematical statement like "f(x1,x2,...,x_n)=0 has no integer solution", where it is impossible (in a certain system of axioms) to formally prove that it's ...
2
votes
1answer
199 views

Can we prove the completeness of FOL based on forcing?

In David Marker's Model Theory, there is a exercise said " we can view a countable Henkin construction as a forcing construction ". But in the book the Henkin construction is used to prove the ...
3
votes
4answers
150 views

Why is this statement able to be resolved as true with “if”?

Why is (a) true if (if) is put in there?
3
votes
2answers
240 views

Goodstein's theorem without transfinite induction

Is it possible to prove Goodstein's theorem without transfinite induction? Is there such a proof?
3
votes
1answer
144 views

How to prove correctness of CNF transformation?

Let $f$ be a propositional formula in negative normal form. It holds: Applying the rules $$A\lor(B\land C)\to(A\lor V)\land(A\lor C)$$ and $$(B\land C)\lor A\to(B\lor A)\land(C\lor A)$$ as many ...
5
votes
1answer
359 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
1
vote
2answers
299 views

Question on independent equivalent set

On Page 28, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Say that a set $\Sigma_1$ of wffs(short for well-formed formulas) is equivalent to a set $\Sigma_2$ of wffs iff for any ...
4
votes
3answers
114 views

How does this textbook go from this step to the next in proving this?

Here's the picture of the question: How does it go from p v ~q to ~p -> ~q?
2
votes
1answer
97 views

Find the representation in Peano system

It's known that all recursive functions are representable in Peano arithmetic. I am trying to find representation of subtraction function $f(x,y)= \left\{\begin{matrix} x-y &if& x>y\\ 0 ...
2
votes
2answers
513 views

Rewriting Conditionals In Their Well Known Form

The question is, "Write each of these statements in the form “if p, then q” in English. [Hint:Refer to the list of common ways to express conditional statements.] a) It snows whenever the wind ...
0
votes
1answer
33 views

Add open $wf.$ to consistent first order system

I've trying to solve this for a while. Problem Let $L$ be a first order language with the predicate symbol $p$. Let S be the extension obtained by adding to $K_L$ the open $wf. p(x, y)$. Is S ...
1
vote
1answer
127 views

Logic about systems?

In Godel's Incompleteness Theorem, his theorem is about a system of logic. Where can I find more about this study, especially the notation? EDIT I mean logic about systems in general. I worded the ...
2
votes
2answers
118 views

Logic Notation question (specifically about logical equivalences)

$$\text{Equivalence}$$ $p \land T \equiv p\tag{Identity law 1}$ $$p\lor F \equiv p\tag {Identity law 2}$$ $$p\lor T \equiv T\tag{Domination law 1}$$ $$p\land F \equiv F\tag{Domination law 2}$$ ...
3
votes
1answer
96 views

Is the validity of the Skolemization of a sentence A infers the validity of A?

I have a claim I need to prove or disprove. Let Sk(A) be the Skolemization of A (A is a sentence). If Sk(A) is valid then A is also valid. In other exercise I was asked if A is valid then Sk(A) is ...
3
votes
3answers
203 views

Is every model of PA well-ordered?

Assume first-order Peano arithmetic is consistent and $N$ is its model, we know that every subset of $N$ contains a minimal element. It's a second-order property so I am not sure if it hold in ...
1
vote
2answers
55 views

Satisfaction in models of non-sentences?

I know the definitions for satisfaction of a sentence in a model but if there are free variables in a formula does that mean that it isn't true or false? (as determined by the model)Thanks
4
votes
2answers
256 views

Paper cube from 13 squares?

Can someone describe the steps to make a paper cube from a sheet of cardbord with squares (3x5) - the second and forth squares from the second row are removed. The sheet looks like this (black boxes ...
3
votes
2answers
4k views

What is the difference between an axiom and a postulate?

I here about axioms is set theory and postulates in geometry, but they seem like the same thing. Do the mean the same thing but then are used in different instances or what? Is one word more ...
12
votes
3answers
564 views

Does every complete theory admit quantifier elimination?

Does every complete theory admit quantifier elimination? I know that at least in some simple cases the reverse is true; such as some reducts of number theory.Thanks
4
votes
1answer
93 views

Show that the theory of the $Th(\mathbb N)$ in first order logic with the finiteness quantifier is categorical

Suppose that a finiteness quantifier $\mathbf Fx$ is added to first order logic. Its semantics are: $\mathbf Fx\Phi(x)$ is true in a model just in case there a finitely many things in the domain of ...
8
votes
3answers
218 views

How to deduce that something does not follow?

Assume I have formulas $H$, $P$ and $Q$. Assume further that I can show in classical logic that $P$ follows from $H$: $$H \vdash P$$ And that the negation of $Q$ follows from $H$: $$H \vdash \neg ...
0
votes
2answers
158 views

Show that there is a hyperreal number system of the same size as the real numbers?

The hyperreal number system is defined as one that contains the real numbers, satisfies the first order properties of real numbers, and contain infinitesimals. It can't be as simple as stating the ...