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.
1
vote
1answer
13 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 ...
0
votes
1answer
22 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 ...
2
votes
1answer
49 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
40 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 ...
1
vote
1answer
29 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 ...
12
votes
2answers
140 views
+50
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
3answers
44 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 ...
1
vote
0answers
41 views
+50
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 ...
2
votes
1answer
34 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 ...
4
votes
1answer
43 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
4answers
119 views
Proving that for any sets $A,B,C$, and $D$, if $(A\times B)\cap (C\times D)=\emptyset $, then $A \cap C = \emptyset $ or $B \cap D = \emptyset $
I'm trying to prove that for any sets $A$, $B$, $C$, and $D$, if the Cartesian product of $A$ and $B$ is disjoint with the Cartesian product of $C$ and $D$, then either $A$ and $C$ are disjoint or $B$ ...
4
votes
1answer
46 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) ...
2
votes
5answers
135 views
How to show $A-B \subseteq C \Rightarrow A\cup B \subseteq B\cup C$?
I really need help with this logical proof.
Show that $A-B \subseteq C \Rightarrow A\cup B \subseteq B\cup C$.
Please show the steps to the solution. Thank you!
4
votes
1answer
84 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 ...
4
votes
2answers
86 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 ...
