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.
3
votes
5answers
362 views
How to interpret material conditional and explain it to freshmen?
After studying mathematics for some time, I am still confused.
The material conditional “$\rightarrow$” is a logical connective in classical logic. In mathematical texts one often encounters the ...
3
votes
3answers
95 views
Alternate proofs (other than diagonalization and topological nested sets) for uncountability of the reals?
I recently started studying set theory and am having quite a bit of difficulty accepting Cantor's diagonal proof for the uncountability of the reals. I also saw a topological proof via nested sets for ...
0
votes
2answers
51 views
How to present a three-valued logic function as a polynomial?
How to present a three-valued logic function as a polynomial?
Having only the truth table. For example:
Perhaps this is due to Zhegalkin polynomial in binary logic. But I do not quite understand ...
2
votes
1answer
33 views
simple proof for logical formula
I am stuck in this proof, I am given:
$$A\setminus(B\setminus(C\setminus D)) = (A\cup C)\setminus (B\cup D)$$.
I did this, but cannot come to solution where i can say, this is true or not.
...
2
votes
3answers
81 views
If $\newcommand\PA{\mathrm{PA}}\newcommand\Con{\operatorname{Con}}\Con(\PA)$, then $\Con(\PA+\Con(\PA))$?
Assume that $\PA$ is consistent.
Then we know that $\PA$ cannot prove $\Con(\PA)$. I was wondering. Can $\PA$ prove that $$\Con(\PA) \Rightarrow \Con(\PA + \Con(\PA))?$$
0
votes
1answer
58 views
what is a closure (hull) operator?
Just that. what is a closure operator?
reading the wiki wasn't enough and i would like to know more.
I'd be happy if someone shared examples of closure operators so that i may further understand ...
0
votes
1answer
169 views
Godel number and expressibility [duplicate]
how to show that these properties of strings of symbols are expressible:
1) being a term,
2) being a formula
3) being a sentence
4) being a proof in PA
and where a property (i.e., predicate) P of ...
11
votes
3answers
170 views
What is necessary to exchange messages between aliens? [closed]
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
2
votes
1answer
68 views
Materials for studying logic
I am looking for study and beginner material to study mathematical logic. I understand that it is a very broad topic but I would like to know what the best path there is to learning mathematical ...
3
votes
2answers
80 views
(Logic) Formally writing a rational number in logic
How do I "formally write" a rational number $a_i$ in a logic formula?
For example, I was taught that $x^2$ should be formally written as $F_\times(x_1,x_1)$, $1$ should be formally written as $c_1$, ...
0
votes
2answers
70 views
How to show that the property of being algebraically closed is reflected by elementary extensions?
May I ask how to show that the property of being algebraically closed is reflected by elementary extensions?
The reason that I want to show that is to prove the following:
Prove:
If ...
4
votes
1answer
76 views
Which logic is stronger? SOL or $\frak{L}_{\infty,\infty}$?
Both second-order logic($\mathsf{SOL}$) and infinitary first-order logic $\frak{L}_{\infty,\infty}$ are proper extensions of first-order logic($\mathsf{FOL}$), that is, are extensions of a ...
9
votes
5answers
402 views
Why König's lemma isn't “obvious”?
I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof?
It seems somewhat obvious, but I ...
3
votes
2answers
80 views
What counts as a standard model of arithmetic?
In my research so far, I've found that the canonical standard model of arithmetic is $\mathbb{N}$ under the addition and multiplication operations. However, I've been unable to find much on any other ...
2
votes
2answers
91 views
Why are the two versions of Gödel Completeness theorem equivalent?
There're two versions of Gödel Completeness theorem:
If $\Gamma \vDash \phi$, then $\Gamma \vdash \phi$.
Any consistent set of fomulas is satisfiable.
I've seen a proof of the second version ...
5
votes
3answers
318 views
Gödel's Paradox — Every set of formulas is consistent
I am sure I have made a gross misunderstanding of Gödel's completeness theorems, as to me, it seems to follow that all sets of formulas are consistent.
Let $\Gamma$ be a set of formulas.
If ...
1
vote
1answer
37 views
Less absorption in Minimal Logic?
I just wonder whether the following is not derivable in Minimal Logic:
$$ \bot \dashv\vdash \bot \land A \hspace{3em}\mbox{/* not derivable */ }$$
I read this that although Minimal Logic attaches ...
2
votes
3answers
51 views
Use rules of inference to show
Premises:
$p \land \lnot s$
$q \to (r \to s)$
Conclusion:
$(p \to q) \to \lnot r$
Use rules of inference to show the above argument is valid.
I only manage to get $(p \to q) \to (p \land ...
5
votes
0answers
75 views
Model theory in terms of type spaces/Lindenbaum algebras
Are there any good references that go into some detail of known 'translations' between properties of the type space of a model and the model theoretic properties of the model? All I seem to find are ...
6
votes
1answer
115 views
What are the formal properties of Godel numbering that are required to make it 'work'?
Godel numbering assigns a number to every formula. It appears to me that any encoding will do. However its also apparent, though I'm not sure how, that certain properties of the encoding used in Godel ...
1
vote
4answers
73 views
A structure elementarily equivalent to $(\mathbb{N},0,\operatorname{S},<,+,\cdot)$
Given $\mathfrak{R} = (\mathbb{N},0,\operatorname{S},<,+,\cdot)$, Let $$\Sigma = \{ 0 < c, \operatorname{S}{0} < c, \operatorname{S}\operatorname{S}{0} < c, \ldots\}$$
By compactness ...
3
votes
3answers
90 views
How to logically analyze the statement: “Nobody in the calculus class is smarter than everybody in the discrete math class.”
I am self-studying Daniel Velleman's "How to Prove It."
In the exercises for section 2.1, for question # 1b, I got a different answer than he did (his answer is in the back of the book).
I think ...
1
vote
0answers
53 views
Equivalence of two very specific propositional calculi
Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes:
P1: $A\rightarrow . B\rightarrow A$
P2: $(A\rightarrow . B\rightarrow ...
1
vote
2answers
60 views
taking the contrapositive of this statement?
Statement: If every right triangle has angle defect equal to zero then the angle defect of every triangle is equal to zero
Taking the contrapositive do i have this correct? : There exists at least ...
1
vote
1answer
30 views
Provably finite sets in constructivist logic
I was reading about Diaconescu's theorem and began with the following statement: If for a given proposition $P$ we let $U=\lbrace x \in \lbrace 0,1 \rbrace : (x=0) \lor P \rbrace$, then $U$ is not ...
1
vote
1answer
64 views
Polygon made up of 12 unit sticks with an area limit
A polygon is made up of 12 unit sticks and its area is 3 units^2. Find as many such polygons as possible. Note that a side of the polygon could be made up of more than 1 stick but a stick could not be ...
4
votes
1answer
55 views
Derive the box from a set of FOL clauses
S = {{P(x,y), P(f(y),z), Q(x,y)}, {~P(y, a), Q(y, x)}, {R(h(x), x), ~Q(x, a)},
{~R(x, y), ~R(h(z), y), ~Q(z, u)}}
For each resolution step specify the ...
6
votes
1answer
124 views
Is there more than one Rosser sentence?
Let $T$ be a recursively axiomatized consistent extension of PA (if you're so inclined you can replace PA everywhere with Robinson's Q). Let $\mathrm{bws}_T(p,\varphi)$ be the proof predicate, ...
1
vote
2answers
61 views
Language, set and sentential calculus
I'm trying to learn sentential calculus now and I'm very confused with the following thing.
In many books on logic I've found out that before working with sentential calculus itself we need the ...
10
votes
5answers
722 views
Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?
For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements.
My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
22
votes
7answers
1k views
Does mathematics require axioms?
I just read this whole article:
http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf
which is also discussed over here:
Infinite sets don't exist!?
However, the paragraph which I found most ...
2
votes
1answer
108 views
Resolution rule in propositional calculus
I was thinking about a reverse case of validity of resolution rule and had a question about it.
Basically, let me state resolution rule first.
Suppose $C_1$ and $C_2$ are clauses such that a ...
5
votes
1answer
57 views
$T\vDash\psi$ equivalences
$T\vDash\psi$ means $T$ satifies $\psi$ from Tarski's definition of truth, it simply means that the sentence $\psi$ is valid in $M$. I call a sentence $\psi $ universally if it is valid in every ...
5
votes
1answer
64 views
Semi-formal language - Universe has at least three elements
First of all I would like to construct a semi formal sentence, such that the universum has at least three elements. My attempt:
$$\exists x\exists y\exists z (x\not=y\wedge y\not=z\wedge x\not=z)$$
...
1
vote
1answer
172 views
Bijection and Natural elements
I'm trying to establish that the set of $L_{PA}$ terms and $p$ an element of the $N[x_1,\ldots,x_n]$ where $N$ = naturals, for some $n$ in the Naturals are in a bijection.
Well, the $L_{PA}$ terms ...
1
vote
3answers
48 views
How to show that a theory T union a sentence $\varphi$ is consistent.
In a substep of a proof, I have a sentence $\varphi$ such that $\varphi\notin T$ and $(\neg\varphi)\notin T$. ($T$ is a consistent theory)
Information about $T$: $T$ is a consistent theory of a first ...
1
vote
2answers
42 views
Logic question linking $\omega$-categoricalness to completeness
Please check my attempted "answer" below. Any corrections are gladly welcomed!
I am stuck with this problem:
Assume that $T$ is a consistent theory of a first order language ...
3
votes
0answers
66 views
Difference between elementary submodel and elementary substructure
This is a really "elementary" question, forgive the pun.
What is the difference between an elementary submodel and an elementary substructure (in first-order Logic)?
Sincere thanks for help.
0
votes
1answer
41 views
Question on the use of induction in the Electronic Mail Game
In Rubinstein's Electronic Mail Game, Player I and Player II's strategies take the form as $s_i : \mathbb{N} \to \{A,B\}$, $(i =1,2)$.
Rubinstein shows that the pair of constant functions, $s_1(t_1) ...
2
votes
1answer
58 views
Logic Coin Game
2 people are playing a game with coins. First, 10 coins are put in a circular form. Then, the players take turns removing 1 coin or 2 coins that are together at each turn. The player who takes the ...
1
vote
1answer
135 views
Expressibility and numbering
A predicate $P$ is expressible (in PA) if there exists a formula $\phi(x_1,\ldots, x_n)$ of $L_A$ such that for all $m_1,\ldots, m_n$ elements of $\mathbb{N}$, we have that $P(m_1,\ldots, m_n)$ holds ...
1
vote
1answer
152 views
Second incompleteness and Model theorey
If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
9
votes
4answers
313 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 ...
0
votes
1answer
137 views
Logic Puzzle from “101 Puzzles in Thought and Logic”
The following is a puzzle from "101 Puzzles in Thought and Logic"
By C R Wylie, Jr.
Jane, Janice, Jack ,Jasper and Jim are the names of five high schools chums. Their last names in one order or ...
0
votes
1answer
41 views
Entailment of a negative case
The lecture notes for my logic course say that the statement
If $\Gamma\models\neg\phi[\tau]$ for some ground term $\tau$, then
$\Gamma\not\models\forall x.\phi[x]$
is false. But I don't see ...
5
votes
1answer
80 views
Basic question about encoding ZFC into PA
1) Are ZFC and PA arithmetic mutually interpretable if we extend PA to PA+A , where A is the set formulas of PA that result from the translation of the axioms of ZFC (or any large cardinal axioms ...
2
votes
3answers
68 views
Prove By Mathematical Induction
Prove $(n!)^{4}\le2^{n(n+1)}$ for $n = 0, 1, 2, 3,...$
Base Step: $(0!)^{4} = 1 \le 2^{0(0+1)} = 1$
IH: Assume that $(k!)^{4} \le 2^{k(k+1)}$ for some $k\in\mathbb N$.
Induction Step: Show ...
3
votes
1answer
45 views
Elementary existence proof in first order logic
Please forgive my dullness but I just don't know how to - formally - show that
$$\lbrace \forall x\ \phi(x), \exists x\ x = x \rbrace \vdash \exists x\ \phi(x)$$
for an arbitrary formula $\phi(x)$.
...
0
votes
1answer
197 views
How to write an equivalent statement?
What is a good equivalent statement to : If the garden is not watered every day, the flowers wilt.
Using the Morgan's Laws
0
votes
1answer
30 views
Logic automorphism question about $(\mathbb{R},0,1,+,\cdot,<)$.
I am stuck on the following question:
Let $\mathcal{A}=\{c_0,c_1,F_+,F_\times,P_<\}$. Let $\mathcal{R}=(\mathbb{R},0,1,+,\cdot,<)$ be the structure of $\mathcal{L}_\mathcal{A}$ with universe ...
