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
2answers
89 views
Does $\Sigma_1 \cup \Pi_1$ generate the complete first order theory of arithmetic?
If a set $T$ of sentences in the language of arithmetic
is deductively closed under the usual inference rules of first order logic, and
includes all true $\Sigma_1$ sentences and all true $\Pi_1$ ...
2
votes
2answers
36 views
Translate the following sentences into predicate logic language.
Translate the following sentences into predicate logic language. Use
the following translation key:
a ~ Anne
b ~ Bob
M(x) ~ x is male
G(x,y) ~ x is married to y
C(x,y) ~ ...
6
votes
4answers
105 views
Second order logic question.
I'm reading Michael Potter's book "Set Theory and its Philosophy" and where he's explaining why he chose to use first-order predicate calculus with identity instead of second order logic to reason ...
2
votes
2answers
36 views
How to prove that $x\epsilon\cap_{i \in I}(A_i\cup B_i)$ $\neq$ $x \in (\cap_{i \in I}A_i)\cup(\cap_{i \in I}B_i)$
I can make sense of why these two equations are not equivalent intuitively but I cannot prove them on paper.
For $x\in\cap_{i \in I}(A_i\cup B_i)$ I end up with:
$\forall(i \in I \rightarrow (x \in ...
2
votes
3answers
77 views
Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$
The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if
$$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$
and it is antireflexive if
$$\forall a\in ...
1
vote
0answers
26 views
Definable with parameters (Example)
Throughout my course in Logic, I have not yet encountered a set that is definable with parameters.
(Most of the examples are definable without parameters)
Is there a simple example of a set that is ...
3
votes
1answer
45 views
construction set of natural number logic
I identify the natural number $0$ with the empty set $\emptyset$, $1$ with $S(0)$, $2$ with $S(1)$, etc, etc.
The axiom of infinity says $\exists x (\emptyset\in x\wedge \forall z\in x\space ...
2
votes
1answer
54 views
Axiom schema of specification - Existence of intersection and set difference
I want to prove existence of intersection $x\cap y=\{z\in x| z\in y\}$ and set difference $x\setminus y=\{z\in x| \neg z\in y\}$using an axiom schema of specification.
My first thought was to use ...
1
vote
1answer
31 views
Are these two statements(theorems) equivalent?
I am given this theorem:
Let $H$ be a check matrix for a linear code $C$. Then $C$ has minimum
distance $d$ iff. there exists a set of $d$, but no set of $d-1$, linearly dependent columns
in ...
2
votes
1answer
72 views
Derivation of deMorgans using basic inference rules.
Using only the ten primitive inference rules how do you derive:
$$ \lnot (A \land B) $$
from
$$(\lnot A \lor \lnot B)$$
The basic rules are 5 (one for each connective) In and Out or Add and ...
1
vote
1answer
43 views
In Fitch, is a symbol not in a specified language automatically free?
In Fitch proofs where no language has been specified, we (at least seem to) treat lines that have the form
$$p(x)$$
to mean that $x$ "can be anything". That is they are equivalent to
$$\forall ...
2
votes
2answers
44 views
How Can I Get This Quantification Deduction?
This is a question in my logic class.
Premises:
$(\exists x)(Px \land Lxa)$
$(y)(Py \supset Lay)$
$(x)(y)[(Lxa \land Lay) \supset Lxy]$
Deduce:
$(\exists x)[Px \land (y)(Py \supset Lxy)]$
So ...
1
vote
3answers
55 views
Prove that Statements forms are tautologies
Given variable statement forms $A$ and $B$. How to prove that if $(A\land B)$ is a tautology then $A$ and $B$ are tautologies too?.
Mi approach would be a proof by contradiction, something like: If ...
4
votes
1answer
55 views
distribution of categorical product (conjunction) over coproduct (disjunction)
In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$:
Assume $(A \lor B) ...
4
votes
2answers
107 views
Is there a sentence in the language of $\mathrm{PA}$ asserting that $\mathrm{PA}$ is sound?
We often write $\mathrm{Con}(\mathrm{PA})$ for the sentence (in the language of $\mathrm{PA}$) asserting that $\mathrm{PA}$ is consistent. Is there a sentence $\mathrm{Sou}(\mathrm{PA})$ (in the ...
5
votes
1answer
54 views
Inherited topology of logical Stone's spaces.
I'm asking here if the following construction is of any interest. I can not find any reference for that kind of thing, so either the subject is completely trivial, either I just don't have the correct ...
1
vote
2answers
52 views
Probe logical equivalence
a. $\quad\quad p \rightarrow q\;\equiv\;-p ∨ q$
b. $\quad -(p \land q)\;\equiv\; -p \lor -q$
Can these be proven without truth tables?
0
votes
1answer
74 views
$\neg (p\rightarrow q)$ as an implication
obviously $a\equiv\neg (p \rightarrow q)=p\land\neg q$.
But, I was wondering what is the simplest\shortest sentence (other than $a$ of course), which contains 1 or more implication connectives ...
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 ...
1
vote
2answers
60 views
how to prove: $A=B$ iff $A\bigtriangleup B \subseteq C$
I am given this: $A=B$ iff $A\bigtriangleup B \subseteq C$. And $A\bigtriangleup B :=(A\setminus B)\cup(B\setminus A)$.
I dont know how to prove this and I dont know where to start.
please give me ...
2
votes
1answer
56 views
reverse direction of modus ponens
Let $\mathit{pvbl}$ is a formalized provability predicate.
If a sentence $X$ is decidable, then following is correct?
$$ \left(\mathit{pvbl}(X) \to \mathit{pvbl}(Y) \right) \implies \mathit{pvbl}(X ...
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))?$$
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 ...
4
votes
1answer
106 views
Tricks for Constructing Hilbert-Style Proofs
Several times in my studies, I've come across Hilbert-style proof systems for various systems of logic, and when an author says, "Theorem: $\varphi$ is provable in system $\cal H$," or "Theorem: the ...
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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
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
1answer
74 views
Degree structure of $1$-Generic Set
We can construct a $1$-generic set $A\leq_{T}\emptyset'$, using an $\emptyset'$-oracle and finite extension construction as in the Kleene-Post theorem to meet all jump requirements. How can I show ...
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 ...
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 ...
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 ...
14
votes
2answers
192 views
Is there a “tree-like” proof of compactness theorem in the case of uncountably many variables?
I like proofs using trees and König's lemma, since they are very visual.
One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, ...
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 ...
5
votes
2answers
127 views
The Axiom of Choice and definability
I've seen a lot of relations between the notion of the existence of a definable set with a given property and the necessity of AC is proving that there is a set with the property. For example:
Under ...
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, ...
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 ...
