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
4answers
78 views
Writing an expression using logic
Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table:
$$\begin{array}{ccc|c}
P&Q&R&???\\ \hline
T&T&T&F\\
T&T&F&T\\
...
2
votes
1answer
50 views
Declarative statements
Is there some branch of mathematics that works with truth bearing statements instead of variables, and defines operations between them?
Basically I am looking for some well known system that defines ...
1
vote
1answer
43 views
CNF/ Create a cnf variable from some forumals of CNF
I have the next CNF: $(A \lor C) \land (B \lor C)$
and also: $(D \lor E) \land (F \lor G)$
Now, I want to be sure that only one of the CNF is true.
Meaning, I want to declare two new variable, T ...
10
votes
2answers
76 views
Growth-rate vs totality
How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
2
votes
1answer
94 views
$xy$ itself square in this particular logic
I would like to know the solution or procedure to find the exact analysis/solution of one of my observation. let $x = a^2$ and $y = b^2$, then can we express $xy$ (concatenation of $x$ and $y$) as ...
14
votes
3answers
395 views
What is dual to “There exists unique?”
I know that "for all" $(\forall)$ and "there exists" $(\exists)$ are dual, in the sense that $$\neg \forall \neg = \exists,\quad \neg \exists \neg = \forall$$
What is dual to "there exists unique"? ...
52
votes
9answers
3k views
How far can one get in analysis without leaving $\mathbb{Q}$?
Suppose you're trying to teach analysis to a stubborn algebraist who refuses to acknowledge the existence of any characteristic $0$ field other than $\mathbb{Q}$. How ugly are things going to get for ...
0
votes
3answers
70 views
what is the relation between not A and everything but A
I am examining Bayes' Theorem, and wondering about the alternative interpretations of ~A, as being:
not A, ¬ A
everything but A, ∀-A
And how this will affect the use of probabilities.
...
4
votes
0answers
63 views
Axiom of Choice-esque argument to show that a proof of a statement exists without actually giving a proof
What if the set of all well-formed statements in ZFC formed a kind of pseudo-category where a morphism f between objects A, B represented a formal proof that A implied B? What if that category could ...
3
votes
0answers
84 views
An Axiomatic Treatment of Mathematics from First Principles to the Major Subjects?
I'm looking for a book - more likely, books - that could take me from the axioms of mathematical logic up to the major subjects of mathematics, like analysis, algebra, geometry, etc.
For example, a ...
2
votes
2answers
61 views
Are these propositions equivalent?
Statement 1: Maria will find job if she learns mathematics.
Statement 2: Maria will find a job unless she does not learn
mathematics.
I know the answer is probably that these are same, but ...
4
votes
1answer
55 views
Special undecidability situation
Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). Can one construct two
statements $\phi_1$ and $\phi_2$ such that
$$
ZFC' \vdash ((ZFC \vdash \phi_1) \ \text{or} \ (ZFC \vdash \phi_2))
$$
...
20
votes
4answers
539 views
Is $\mathbb{N}$ impossible to pin down?
I don't know if this is appropriate for math.stackexchange, or whether philosophy.stackexchange would have been a better bet, but I'll post it here because the content is somewhat technical.
In ZFC, ...
3
votes
1answer
126 views
Why every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$
Let $\mathbb{Q}$ be the set of rational numbers. Show that every member of ${}^{*}\mathbb{R}$ is infinitely close to some member of ${}^{*}\mathbb{Q}$.
This is an exercise on page 180, A ...
3
votes
1answer
36 views
Boolean Algebra Transform
I am revisiting Boolean algebra after a long while.
Can somebody help show me how to simplify the LHS to get the RHS?
$$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
5
votes
2answers
84 views
Does this qualify as a statement?
Is this a statement?
All positive integers with negative squares are prime.
What do we need to qualify as such?
4
votes
6answers
93 views
Symmetric, non-reflexive relation
I'm looking for an example of a mathematical relation that is symmetric but not reflexive. A standard non-mathematical example is siblinghood.
2
votes
3answers
77 views
Logic Negation Symbols
$\def\nn{\mathord{\sim}}$
This is a rather simple question but I can't find an exact answer on it.
In examples, I've seen $\nn$ and $\lnot$. These fall under ‘negation’. If they both fall under ...
1
vote
2answers
39 views
Can the results of an problem invalidate the process and therefore themselves?
For example, suppose that to solve an equation, one must divide both sides by x, and it is later discovered that x = 0 (and zero was a permissible value in the original equation). What would this mean ...
1
vote
1answer
79 views
Is it interesting to consider satisfiability modulo theory in the context of modal logic?
Recently lot of work has been done considering satisfiability of formulas in
specific theory (array theory, bit-vector theory).
But I did not find any results about satisfiability modulo theory in ...
2
votes
1answer
60 views
Are the following two first-order logic statements correct?
I am doing questions to revise for an exam.
Here is the question:
Convert "Elder gods do not like Hello Kitty" to first-order logic.
Here is the answer they give:
...
4
votes
4answers
112 views
the role of logic in math and education
My question is somewhat related to this discussion:
Is Mathematics one big tautology?
I have a computer science background and I have always approached math from the logic point of view ...
4
votes
1answer
84 views
The manuscript Summa Logicae (William of Ockham)
The Summa Logicae (Latin, in English it's the Sum of Logic) is a textbook on logic by William of Ockham. There are articles about the Summa Logicae in Wikipedia and in Logicmuseum.
It was published ...
0
votes
1answer
54 views
How to prove $∀x ∀y (P(x) → Q(y)) ↔ (∃x P(x) → ∀y Q(y))$ using Fitch Intro and Elim rules
$∀x ∀y (P(x) → Q(y)) ↔ (∃x P(x) → ∀y Q(y))$
We are only permitted to use Intro and Elim rules, and I am stuck on how to even begin this proof. Any help would be appreciated. Thanks!
2
votes
1answer
52 views
How to calculate the “difference between X and Y”
I feel like this is the silliest question ever, so I apologize in advance!
a statement reads:
Z is the difference between X and Y.
Which of these is true?
Z = X - Y
Z = Y - X
Z = |X - Y|
I want ...
1
vote
2answers
52 views
formalized provability predicate and implication relation
$\DeclareMathOperator{\pvbl}{pvbl}$ Let $\pvbl$ be the formalized provability predicate.
Sentences $A$, $B$, $C$, $D$ have the following relation.
$\pvbl ( A \rightarrow B)$
$\pvbl ( C \rightarrow ...
9
votes
2answers
405 views
9 pirates have to divide 1000 coins…
A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.
Arriving on a deserted island, they now have to split up the ...
3
votes
1answer
45 views
Determine whether two primitive recursive functions are equal
Is there an algorithm to determine whether two primitive recursive functions are equal (as mathematical functions)?
2
votes
2answers
61 views
Prove that $(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$.
Logically, the following proposition makes sense:
$(S \cap T = \varnothing) \land (S \cup T = T) \rightarrow S = \varnothing$
Or, in english, if sets $S$ and $T$ share no elements, and the union of ...
0
votes
1answer
79 views
Herbrand Logic-Fitch System
Given $$\forall x.(p(x) \implies q(x))\quad and \quad p(a)$$ use the Fitch system to prove q(a)
I have started:
$$\\$$
$$1) \forall X.(p(X) \implies q(X)) \qquad (Premise)$$
$$2) p(a) \qquad ...
3
votes
1answer
58 views
Extending the recursive functions to higher classes in the aritmetical hierarchy
It is an important theorem that the recursive functions are exactly those which are definable by $\Delta^0_1$ formulas.
We have just finished the part about incompleteness in a course I'm TA'ing, and ...
1
vote
3answers
149 views
Is there more than one inconsistent theory?
For a given language, is there more than one inconsistent theory? My intuition told me no, but I'm not sure.
1
vote
1answer
44 views
Simple logic equivalence incorrect
I am having some problems negating a rather simple logical statement. I am currently taking a introduction course, so please bear with me if my question is silly.
I am supposed to turn this:
$$ ...
1
vote
1answer
74 views
Logical correlation from Oedipus myth
My girlfriend likes the myths and she found an MIT article about Oedipus myth which is looks interesting for her. She showed me, but for me it is looks like no correlation between the logical ...
3
votes
1answer
98 views
Equivalence of first-order formulas
The following are elementary truths for arbitrary formulas $\phi, \psi$ of first-order logic in which all variables but $x$ are bound:
$\vdash \forall x \phi(x) \wedge \forall x \psi(x) ...
4
votes
0answers
61 views
Infinite “String” of Implication Statements
This question is inspired by the conversations at
Does this require transfinite induction?
First of all, does an infinite string of implication statements have a conclusion? I don't think so, but I ...
2
votes
2answers
106 views
Every sentence in propositional logic can be written in Conjunctive Normal Form
While reading through Artificial Intelligence - A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following ...
1
vote
3answers
65 views
How can I use a truth table to show that this is a tautology?
How can I show that this is a tautology by using a truth table?
$(p∨q)∧(¬p∨r)\to(q∨r)$
I know how to do it by logical equivalences, but now I have to use a truth table.
Never done it before so I dont ...
6
votes
2answers
237 views
How to formalize this paradox?
A friend gave me this problem (in the "blue box")
An interesting fact about the number $2$.
How many times the number $2$ appears in this text?
It appears $2$ times.
Well I see the ...
3
votes
2answers
95 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
45 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
111 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
40 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
80 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
27 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
49 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
58 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
32 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
48 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 ...
