Tagged Questions
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.
0
votes
1answer
17 views
Prove or disprove $ \exists x \in S [ p(x) \land q(x)] \iff [\exists x \in S p(x)] \land [\exists x \in S q(x)] $
I proved it as follows. Can anybody tell me if it is correct or wrong?
Assume $ \exists x \in S [ p(x) \land q(x)] $ ,
Let $ x_0 \in S, st [ p(x_0) \land q(x_0)]$
$p(x_0)$ and $ q(x_0) $
Let x ...
1
vote
3answers
60 views
Can a statement in FOL be equivalent to two separate independent statements?
This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
0
votes
0answers
16 views
Model-theory : questions regarding back-and-forth sets
See my previous post for the basic definitions from Jouko Väänänen, Models and Games (2011), page 54-on.
See page 64 for :
Definition 5.14 Suppose $\mathcal A$ and $\mathcal B$ are ...
2
votes
2answers
34 views
'Algebraic' way to prove the boolean identity $a + \overline{a}*b = a + b$
For me, it is pretty clear that $a + \overline{a}*b = a + b$, because the first $a$ in the or will make sure that if the second term must be 'evaluated', $a$ will ...
1
vote
2answers
32 views
implication versus conjunction correctness in FOL?
I've just started learning FOL and I'm really confused about whether to use conjunction or implications. For example, if I want to represent
...
2
votes
1answer
31 views
Is there a phrase to describe those objects of $\mathbf{C}$ that can be expressed as quotients of the algebra freely generated by $X$?
Let $\mathbf{C}$ denote the category of models of an algebraic theory in $\mathbf{Set}.$ Now suppose $X$ is an object of $\mathbf{Set}$. Is there a traditional phrase used to describe those objects of ...
1
vote
1answer
35 views
Model-theory : questions regarding partial isomorphism
I'm having problems with the first pages of Bruno Poizat, A Course in Model: Theory An Introduction to Contemporary Mathematical Logic (ed or 1985), specifically with local isomorphism and back- and ...
0
votes
1answer
36 views
Decidability…
I'm confused about what my book is saying here. It's a bit long so I have an image of it here (if that's okay?)
https://docs.google.com/document/d/1ssy3P06dqSAhREuRbr9PNj6CYYe4_HdcITg1X4kx8PM/edit
...
1
vote
1answer
24 views
What techniques are there to search for first order sentence equivalence?
Suppose we have a first order sentences $\phi$, $\psi$, and $\chi$ such that:
$\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$)
And $\phi$ and $\chi$ are known or fixed. How can we search for a ...
0
votes
1answer
47 views
proof without using pigeonhole principle [on hold]
Suppose there are 25 marbles of four colours. Prove that out of those 25, there is a group of at least 6 marbles of the same colour, without using the Pigeonhole principle.
Thanks!
1
vote
0answers
43 views
What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization?
I am in possession of a book, which, inspired by Russell's Principia Mathematica (PM) and logical positivism, attempts to formalize a specific domain by determining axioms and deducing theorems from ...
6
votes
1answer
121 views
Gödel's way of teaching non-standard models to Takeuti.
In Memoirs of a Proof Theorist, Gaisi Takeuti relates how Gödel taught him about nonstandard models in an "interesting" way:
It went as follows. Let T be a theory with a nonstandard model.
By ...
2
votes
2answers
39 views
$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))$ What does it mean?
$(\forall x\in S)P(x)\equiv \forall x(x\in S\Rightarrow P(x))\\(\exists x\in S)P(x)\equiv \exists x(x\in S\wedge P(x))$
What I think it means:
1) For all $x$ in $S$, $P(x)$ holds true = for all $x$, ...
1
vote
1answer
30 views
From statement to logic
I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian):
Martha is not a singer, and she doesn't play violin or flute, but not ...
2
votes
4answers
430 views
What is the truth table for demorgan's law?
From Demorgan's law:
$(A \cup B)^c = A^c \cap B^c$
I constructed the truth table as follows:
$$\begin{array}{cccccc|cc}
x\in A & x \in B & x \notin A & x \notin B & x \in A^c ...
0
votes
2answers
47 views
Finding boolean/logical expressions for truth table + explanation [on hold]
I'm having very hard time finding boolean expressions from truth tables. I've also tried many tricks but still can't get through...think you guys can help me with this??...you'll be doing this lil ...
0
votes
1answer
18 views
Simplification of a Disjunctive Normal Form Logic Equation
So I'm fairly new to logic equations and I've been given a pretty big logic equation to simplify and just need a bump in the right direction to figure out where to go. I've been told it's going to be ...
-3
votes
2answers
51 views
check the formulas for satisfiability and validity [on hold]
Could perhaps somebody explain me how to define if a formula is valid, satisfiable, or not satisfiable if
...
0
votes
1answer
50 views
particular property and completeness?
I was puzzeling with the almost standard definition of completeness:
In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula ...
5
votes
0answers
144 views
What is semantics of “type”? Do “types” of “type theory” semantically differ from “set” of set theory?
"To be of a (certain type)" is a fundamental relationship for ontology and the computer science "ontologies" are in the core of Semantic Web (which is my interest). But I did not encounter a ...
4
votes
1answer
81 views
+100
Simplifying a categorical proof of constructive dilemma
In axiomatic propositional calculus the following axiom schema captures constructive dilemma:
$\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$
\begin{equation}
(a \lif c) \lif ((b \lif c) ...
1
vote
0answers
46 views
Divisibility is not definable over $\mathbb{N}$ with coprimality relation
I am asked to show that the divisibility relation "|" is not definable over $(\mathbb{N},\perp)$, where "$\perp$" is the coprimality relation.
I am pretty sure that I should use the following:
...
-1
votes
0answers
25 views
Complete to make the statement true [on hold]
The __ is the negation of the conditional
The __ is the negation of the inverse
1
vote
1answer
61 views
Show that if $L$ is countable and contains a two-place predicate symbol, there are $2^{2^{\aleph_0}}$ classes of $L$-structures closed under $\equiv$
We say that a class of structures $K$ is closed under elementary equivalence ($\equiv$) if for all $A, B$, if $A \in K$ and $A \equiv B$, then $B \in K$. How to show that if $L$ (as a set of specific ...
1
vote
1answer
43 views
Completeness theorem for intuitionistic logic
Reading from Wikipedia about intuitionistic logic, I am guessing that there is a formal proof system for intuitionistic logic. (Note: My knowledge of intuitionistic logic is almost nil). My ...
1
vote
2answers
36 views
Abelian/Isomorphic logic statement
I don't understand this logic statement. I don't think the context helps at all but I thought i'd include it anyway.
$G$ is abelian and $H$ is not abelian, then $G\ncong H$, is the same as:
$G$ ...
0
votes
2answers
30 views
Showing that $A \cap X = A$ for all $A$ if and only if $X = S$.
I have the following task:
Let $S$ be a nonempty set. All capital letters will denote
subsets of $S$. Show that $A \cap X = A$ for all $A$ if and only if $X = S$.
This does not seem to true. ...
1
vote
1answer
22 views
Propositional calculus , axiom scheme independence proof
I am studying mathematical logic from Mendelson's "Introduction to mathematical logic" and have difficulty understanding the intuition behind his proof of independence of axiom schemes introduced for ...
1
vote
2answers
45 views
Derivation of Null Quantification in Logic?
I was reading page 10-8 of this: https://faculty.washington.edu/smcohen/120/Chapter10.pdf
and I was wondering if the distributive qualities could be derived, e.g. $\forall x (P \lor Q(x)) ...
0
votes
0answers
17 views
Can a non-cyclic infinite proof tree with always-reachable provable nodes be used to construct a proof?
Suppose that I have a finite number of basic elements x,y,z ... and a finite number of operators +, * ... Terms X,Y,Z ... are created by combining basic elements and operators. For example, x+y, and ...
1
vote
1answer
25 views
Rules of inference: The Rules of Disjunctive Syllogism and Double Negation
I have a question about the use of Double Negation in relation to this problem I found in my textbook examples.
Problem:
$\;¬(r \land t) \lor u$
$\;r \land t$
Therefore, $u$.
In my textbook it ...
1
vote
1answer
31 views
Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate?
Can a predicate in logic operate on something undefined ? Is $P(x)$ true or false for $x$ undefined, where $P$ is a predicate ?
To be more concrete:
Is $x \le 5$ true or false for $x$ undefined ?
...
-1
votes
1answer
69 views
Mathematical Logic Problems [on hold]
True or false(and why): If T is a set of logical sentences which is
logically contingent and T' so that T' $\subset$ T, then
T' is also logically contingent
Prove that $$\phi \lor \psi, \lnot \phi ...
0
votes
1answer
49 views
Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ elementarily nonequivalent structures for $L$?
Let $L$ be a set of specific symbols and $\operatorname{Form}(S)$ be the set of all first-order formulas over $L$. Why are there $\leq$ $2^{\operatorname{card}(\operatorname{Form}(L))}$ ...
1
vote
1answer
79 views
Arrows-only implication & disjunction in $\mathbf{Set}.$
Just before the truth-arrows in a topos subsection of Goldblatt's "Topoi: A Categorial Analysis of logic," descriptions of the truth functions $\Rightarrow$ and $\smallsmile$ are given in ...
0
votes
2answers
55 views
Ordinal existence
Is there any ordinal $\alpha$ such that $\omega ^ {\omega ^ \alpha} = \alpha$?
Could you please suggest me how to even try to solve this?
2
votes
1answer
21 views
Proposition Question
I am trying to translate this into propositional symbols but (for me) it's so complicated. Can someone help me figure this out.
"If it rains then I will carry a sharp object and I will start laughing ...
2
votes
1answer
54 views
How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?
I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...
0
votes
0answers
52 views
I there a rigorous, mathematical, approach to definitions (denotations)?
In mathematical logic, a definition is treated as an abbreviation - a denotation which simplifies the discourse making it shorter. This is so much so that in a formal theory or a logic we can do ...
0
votes
1answer
37 views
How to prove this expression in mathematical logic
How to prove that the problem is a tautology, using only replacement by equivalence(s) (1. negation, 2. distribution, 3. de Morgan's laws, 4. $x\leftrightarrow y\equiv(x\rightarrow ...
1
vote
1answer
41 views
Provide the Proof for $\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$
Provide the Proof for $$\forall x\,\bigl ( P(x) \land Q(x)\bigr ) \leftrightarrow \forall x \,P(x) \land \forall x\, Q(x)$$
This is all i got so far:
Assume $\forall x \,\bigl( P(x) \land Q(x) ...
2
votes
2answers
31 views
Logic question for a program I'm designing
I'm developing an application in ASP.NET with C# and i'm trying to figure out the best way to implement a logic statement that will stop the system from allowing another reservation to be taken if the ...
0
votes
2answers
61 views
How to express $\lnot (a < b < 0)$ or the contrapositive of this statement?
I can't seem to get the negation, $\lnot (a < b < 0)$, right.
I thought I could break it into 3 parts: a < b, a < 0, b < 0, but that leaves me with a > b or a > 0 or b > 0 (greater or ...
0
votes
1answer
33 views
A Logical Equivalence?
Is $\exists y \forall x (P(y) \ \wedge (P(x) \Rightarrow (x=y)))$ the same as $\exists x \forall (y\neq x) (\neg P(y) \wedge P(x))$? I think they are, but I can't think of a way to transform from one ...
2
votes
0answers
44 views
If $\mathbb{Z}$ satisfies an identity $\eta$, then every **commutative** ring satisfies $\eta$? And related questions.
Assume all rings have unity and that ring homomorphisms preserve unity.
Now by general principles, if every free object in the category of rings satisfies an identity $\eta$, then every object in the ...
1
vote
1answer
42 views
“If… then” equivalence [duplicate]
This website states that the equivalent statement to if A then B is if NOT B then NOT A
This doesn't make sense.
I also am a ...
0
votes
1answer
75 views
Can variables of quantification be repeated?
For example, is the following valid?
$\forall x \forall x \alpha$
Is so, then how is it evaluated user the basic semantic definition?
5
votes
1answer
23 views
same variable bound by different quantifiers
In studying first-order logic, I have come across this sentence:
$\exists x\, P(x)\land\exists x\, R(x)$
If there is some $x$ such that $P(x)$, and there is some $y$ such that $R(y)$, is this ...
2
votes
1answer
98 views
Cardinalities of Collections of Models
Let $T$ be a complete theory in a countable language (with only infinite models). Recall the spectrum function: $I(\aleph_\alpha,T)=$ the number of non-isomorphic models of $T$ of cardinality ...
0
votes
0answers
44 views
Two conditions, necessary and sufficient conditions.
I am currently studying for a test for a scholarship, in such a test, the following question appears (The part that I'm having trouble with in is in bold):
For each of $A$ ~ $D$ in the following ...
