Questions tagged [logic]
Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).
27,497
questions
0
votes
0
answers
26
views
Basic proof verification
Let $\alpha \in X$. I want to prove following statement
$$
\text{Condition } A(\alpha) \text{ is satisfied} \iff \text{Condition } B \text{ is satisified}.
$$
First I assume that $\alpha \in X$ and ...
- 27
0
votes
1
answer
83
views
Fundamental axioms of logic used to interpret most of modern mathematics [duplicate]
so i'm going through Terrence Tao's analysis 1 and he has a clear emphasis on rigor, however its kind of a contradiction when he didn't even go over the basics of mathematical logic.
A mathematical ...
- 53.7k
-1
votes
0
answers
19
views
Distance, speed and time word problem. Calculate Time
A Business owner Alex, got a call for an urgent business meeting and he had to drive through a road which did not have network coverage. He immediately left in his Car driving at constant speed of 87 ...
0
votes
1
answer
50
views
What are the consequences of negating the Godel sentence in a formal system? [duplicate]
What is wrong with the following argument?
Let $F = T + ¬G_T$, where $T$ is an effectively generated formal system and $G_T$ is its Godel sentence.
Then, it is possible to prove within $F$ the First ...
- 39.2k
2
votes
0
answers
90
views
Please criticize my attempted proof of a simple set theory lemma.
I am reading Terrence Tao's analysis 1 and am new to writing proofs. I'm currently financially unstable and have no one to talk about math's with, so any criticm would help me so much.
In his book, I ...
- 21
-3
votes
0
answers
23
views
Problem about the Zhegalkin polynomial [closed]
Let the Zhegalkin polynomial for function 𝑓 consist of those and only those monomials that are not included in the polynomial for function 𝑔. How different can the functions 𝑓 and 𝑔 be? (Write the ...
7
votes
6
answers
9k
views
Help to understand material implication [closed]
This question comes from from my algebra paper:
$(p \rightarrow q)$ is logically equivalent to ... (then four options are given).
The module states that the correct option is $(\sim p \lor q)$. ...
- 908
1
vote
3
answers
93
views
How does propositional logic address the situation where the statement $(p \Rightarrow q)$ is false?
I was exploring the inferences drawn from the truth values of $p$, $q$, and $(p \Rightarrow q)$. The truth table of material implication is:
$$\begin{array}{|c|c|c|}
\hline
p&q&p\Rightarrow q\\...
- 5,536
-2
votes
0
answers
33
views
set theoretical language [closed]
Can someone please translate the following English sentence into set-theoretical language
"For every set having at least one element, there is a set whose elements are the elements and only the ...
- 101
2
votes
1
answer
109
views
Is my notation correct?
$\{x : x \le 75, \in \mathbb{Z}_+ \cup \{0\}\}$
Is this notation correct? I'm going for positive integers less than or equal to $75$ including $0$.
- 2,910
3
votes
1
answer
120
views
Proof of Peano existence theorem in ZF without mathematical logic
There is a proof of Peano existence theorem in ZF.
Peano existence theorem:
For any open $D \subseteq \mathbb{R}^2$, continuous $f:D \to \mathbb{R}$ and initial condition $\langle t_0,x_0\rangle \in ...
- 40k
2
votes
0
answers
21
views
Prove which of the extended dense linear order models are atomic and saturated
Let ${\sf DLO}$ be the theory of dense linear orders without endpoints. Let $c_i$, for $i \in \mathbb N$, be new constant symbols, and let ${\sf DLO}'={\sf DLO}\cup \{ c_i < c_{i+1} \mid i \in \...
- 153
1
vote
1
answer
68
views
Expand a model to have a well ordering. Prove that the set of all definable elements over a subset $X$ is the universe of an elementary substructure
Let $\mathcal A$ be an $\mathcal L$-structure, let $\dot{\triangleleft}$ be a new binary predicate symbol, let $\triangleleft$ be a wellordering of $A$, and let ${\mathcal A}^*$ be the expansion of $\...
- 10.1k
7
votes
4
answers
1k
views
How can I prove this statement about subsets?
Let $A$, $B$, $C$ be sets. Prove that if $A \subseteq C$ and $B \subseteq C$ then $A \cup B \subseteq C$.
This is an exercise in mathematical logic.
My attempt to progress forward: This statement ...
- 14.9k
1
vote
1
answer
46
views
Can this disjunction be eliminated?
This is a question about classical propositional logic.
Definitions: If there is a proof from $\alpha$ to $\beta$, we'll write $\alpha \vdash \beta$. We'll say that $\alpha$ is equivalent to $\beta$ ...
- 756
0
votes
0
answers
33
views
Show restriction of isomorphism is isomorphism (libkin lemma 4.8)
Assume that $h:N_r(a) \rightarrow N_r(b)$, ie h is an isomorphism between the neighborhoods of r-distance (where distance is in the Gaifmann graph) induced by the tuples $a,b$ in structures A, B resp. ...
- 444
0
votes
3
answers
147
views
What does it mean to assume an axiom is “true” in mathematics? [duplicate]
I honestly don’t even know what “true” means anymore :(.
Is mathematics typographical?
Are we just saying a string of symbols is “true” to kickstart our theory?
- 98.1k
2
votes
0
answers
40
views
$\models P \wedge Q \iff \neg ( \neg P \vee \neg Q )$ is a valid argument
I have to show that $\models (P \wedge Q) \iff \neg ( \neg P \vee \neg Q )$ is a valid argument.
However, I have no idea how to interpret a $\models$ symbol WITHOUT a LHS. I have always seen it like ...
- 64.9k
1
vote
1
answer
2k
views
*Language, Proof, and Logic* Fitch Proof Exercise 6.16
This is the last proof I need to finish. I've really been struggling with this one even though it seems so simple. Instructions say use Tarski's world if the sentences are consistent (they aren't), or ...
CommunityBot
- 1
0
votes
1
answer
1k
views
The axiom systems of predicate logic
I'm writing an article about logic for absolute dummies, so I want to make everything crystal clear; now I'm going to discuss predicate logic. After Googling, I found there are mainly 2 slightly ...
CommunityBot
- 1
43
votes
2
answers
1k
views
When are two proofs "the same"?
Often, we find different proofs for certain theorems that, on the surface, seem to be very different but actually use the same fundamental ideas. For example, the topological proof of the infinitude ...
- 516
0
votes
2
answers
116
views
Aid for logical puzzle [duplicate]
I am looking for some help to solve this logical puzzle. The problem I am asked to solve is:
"You’re a famous detective and you’re trying to solve a second murder. You know that the murderer was ...
- 199
3
votes
1
answer
56
views
$tp^\mathbb{Q}(a/\mathbb N) = tp^\mathbb{Q}(b/\mathbb N)$ iff there is an automorphism $\sigma$ of $\mathbb Q$ fixing $\mathbb N$ and $\sigma(a)=b$
If $a, b \in \mathbb Q$, then $\text{tp}^{\mathbb Q}(a/\mathbb N) = \text{tp}^{\mathbb Q}(b/\mathbb N)$ if and only if there is an automorphism $\sigma$ of $\mathbb Q$ fixing $\mathbb N$ pointwise ...
- 29.4k
0
votes
1
answer
65
views
$\varphi$ is quantifier free sentence, $T$ a theory, $\vec{c} \not\in T$. $T \vdash \varphi(\vec{c})$ implies $T \vdash \forall x \varphi(\vec{x})$?
Let $\varphi$ be a quantifier free sentence and $T$ is a theory such that $\vec{c} \not\in T$. I am trying to see why the following is true: $T \vdash \varphi(\vec{c})$ implies $T \vdash \forall x \...
- 93k
2
votes
2
answers
125
views
Meaning of "theorem of a system"
The following excerpt is from page 357 of Logic: The Laws of Truth by Nicholas Smith:
Given a system of proof - say, the tree method for GPLI - we call propositions that can be proven using that ...
- 93k
6
votes
1
answer
746
views
Is there a formula in FOL that is only satisfiable in an infinite domain
Is it possible to construct a formula or set of formulas using only equality that are satisfiable only in an infinite domain? I have seen such formulas but they all use a relation like greater than or ...
- 3,352
3
votes
1
answer
81
views
Question about logic and proving negation statements
I am currently taking an introduction to real analysis course, and I was having trouble on knowing when I can prove the negation of a statement.
I was answering this question
If $f'(x) \neq 0$, then $...
- 3,528
1
vote
1
answer
66
views
Axiomatic proof in modal system $⊢_{K5} □(□p → p)$
I’m having a hard time proving $⊢_{K5} □(□p → p)$. Proving validity in Euclidean frames.in this from axiom 5 is valid $◇p → □◇p$
I’m able to derive
$□p → □(□p → p)$
I,m also able to derive from Axiom ...
- 993
2
votes
0
answers
30
views
Count the number of non-isomorphic models for a theory $T$ describing infinitely branching equivalence classes, each class infinite
Let $T$ be a theory in a language $\mathcal L = \{E_i(x,y) \mid i \in \omega \}$ expressing the following:
(1) $E_i$ is an equivalence relation with each equivalence class infinite, for each $i \in \...
- 9,897
1
vote
0
answers
112
views
What are examples of models for which the Continuum Hypothesis is true/false?
I'm not a set theorist so pardon my improper language. I'm trying to make sense of the unprovability of the Continuum Hypothesis. What I've come to understand is this: since set theory is broad and ...
- 56.7k
0
votes
1
answer
53
views
Why is the cardinality of a first-order language max{$\aleph_0, k$}?
My understanding is that the cardinality is given by the cardinality of equivalence classes of formulae under the equivalence relation of being variants of each other i.e. identical up to uniform ...
- 152
-2
votes
1
answer
64
views
Confusion about mathematical definitions
Definition 1: Let $A={[a_{ij}]}_{m\times n}$ and $B={[b_{ij}]}_{m\times n}$. We define
$$A+B:={[a_{ij}+b_{ij}]}_{m\times n}$$
My problem: Which of the following mathematical notations below is ...
- 53.7k
1
vote
1
answer
66
views
Defining fundamental sequence in advance
My question is about large countable ordinal numbers and their fundamental sequence.
It looks as our knowledge of large countable ordinal number theory grows,
brand-new fundamental sequence for brand-...
- 26.7k
0
votes
0
answers
15
views
Do sole sufficient operators have to abbreviate existing functions?
I'm thinking about this question about modal logic.
I'm wondering whether a sole sufficient operator needs to be an abbreviation of existing functions or not.
More concretely, consider an equational ...
- 10.1k
-1
votes
0
answers
14
views
When there is no ost general unifier [closed]
I'm having a hard time to understand the unification algorithm properly. Why are these two problems:
P(x , h(b), h(x)) and P(f(g(y)), y, h(f(g(h(a)))))
P(f(g(x)), g(b), h(x)) and P(f(y), y, h(c))
...
- 1
0
votes
0
answers
50
views
Substitution lemma for many-sorted logic interpretation in a topos
Goldblatt's "Topoi" suggests the following exercise (16.3.2). Let $\varphi$ be some formula of some many-sorted language, and let $u$ be some term of the same sort as some free variable $v_i$...
- 1,771
3
votes
2
answers
157
views
You forgot whether the logic class is at 11 or 12. Your friend knows which but sometimes lies. What should you ask them?
In "Mathematical Logic" by Chiswell and Hodges, there is the following exercise (3.5.3):
You forgot whether the logic class is at 11 or 12. Your friend certainly knows which; but sometimes ...
- 31
0
votes
1
answer
225
views
Can axioms be proven?
In this answer by Henning Makholm, he states that the following statement can be proven in Peano Arithmetic:
$$
\forall x:\forall y:x\cdot S(y)=(x\cdot y)+x \, .
$$
The proof is very simple—since the ...
- 18.8k
0
votes
1
answer
57
views
Is the axiom of foundation/axiom of regularity relatively consistent with ZFC?
Wikipedia says that the axiom of regularity is relatively consistent with the rest of ZF. Is the same true if we adjoin choice, i.e. is ZFC + regularity relatively consistent with ZFC?
- 56.7k
0
votes
1
answer
68
views
first order language of "sets"
There is a list of variables symbols in the first order language (with "$=$") for sets
There is a list of logical operator symbols
There is a list of grouping symbols
There is a binary ...
- 53.7k
0
votes
2
answers
110
views
Understanding Quantifiers with Propositions
I learned that
$$p(x): (x-2)(x-1)=0$$
$$q(x): x=2 \lor x=1$$
$p(x) \implies q(x)$ is true.
But how do you use quantifiers in this proposition?
Is it
$$(\forall x)[p(x) \implies q(x)]$$
or
$$(\exists x)...
- 1,415
0
votes
1
answer
61
views
Why can't I prove the opposite expression the same way? [duplicate]
There's explanation in Tarski's book about belonging of the null class to every other class.
It goes like this:
“If x belongs to the null class, then x belongs to K. Whatever object we substitute here ...
- 98.1k
1
vote
0
answers
137
views
Can someone explain how they derive a consequence from the axion of choice
To give you guys the context: This isn’t for anything specifically, however, I hear the phrase such and such “…then we invoke the axiom of choice…” or something like, “…but by the axiom of choice, we ...
- 56.7k
2
votes
4
answers
401
views
Need help with natural deduction logic proof (Chiswell/Hodge exercise 2.6.2d)
in Chiswell/Hodge exercisee 2.6.2d it asks for the proof of $\{\lnot(\phi\leftrightarrow\psi)\}\vdash((\lnot\phi)\leftrightarrow\psi)$. I've managed to produce half the proof, but I'm unable to ...
2
votes
1
answer
64
views
How to prove the tautology for the inference rule of hypothetical syllogism using a chain of logical identities?
Let $p$, $q$, and $r$ be any propositions. Then, using a chain of logical equivalences, how to establish the following logical identity?
$$
\big( (p \rightarrow q) \land (q \rightarrow r) \big) \...
- 53.7k
-2
votes
0
answers
30
views
ab≤0if and only if(a≤0 and b≥0) or (a≥0 and b≤0) [closed]
Here is the statement:
$ab≤0$ if and only if $(a≤0$ and $b≥0)$ or $(a≥0$ and $b≤0)$
Is this true or false with justification?
1
vote
5
answers
300
views
Vacuous falsehood - does it exist, and are there examples?
I've ben struggling with the concept of vacuous truth, as used (1) in proving implications, (2) as base cases for induction proofs.
To help me understand, it would be useful to understand if the ...
- 4,225
5
votes
1
answer
301
views
Does the term "free" in "free ultrafilter" have a meaning related to category theory?
I know that free ultrafilters are defined in contrast to principal/fixed ultrafilters. Nonetheless, is there some categorical way to view the use of the word "free" here (e.g. some pair of ...
- 159k
-1
votes
1
answer
38
views
The Laws of Boolean Algebra [closed]
Can someone expand or illustrate how this logic applies. $$\bar AB+A=B+A,$$
how does $\bar A$ disappear?
- 498
0
votes
0
answers
59
views
Theorem derivations in truth functional logic - How do I formally prove $(\neg P \to Q) \to (P \lor Q)$ [closed]
$\forall x~(\lnot F(x)\to G(x))\to\forall x~(F(x)\vee G(x))$
I understand that $[\forall x~(\lnot F(x)\to G(x))]$ and $[\forall x~(F(x)\lor G(x))]$ are semantically the same, but I can't figure out ...
- 152