Questions about 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.

learn more… | top users | synonyms (1)

0
votes
1answer
44 views

Propositional Logic meta-variable notation abuse

When defining Formation Sequence, van Dalen (4th edition page 9) says: A sequence $(\varphi_0,\varphi_1,...,\varphi_n)$ is called a formation sequence of $\varphi$ if $\varphi_n=\varphi$ and: ...
0
votes
2answers
47 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: ¬(P ∨ Q) ∨ (¬P ∨ Q) The result: ¬P ∨ Q The objective is to simplify. I'm stuck at (¬P ∧ ¬Q) ∨ ¬P ∨ Q I could make the distributive, ...
2
votes
3answers
49 views

Discrete math - conjunction or disjunction in this case?

Teacher asks students if they did the homework on their own (everyone either did it on their own or copied it). He gets the following answers: Andy: Everyone didn't do their homework on ...
0
votes
1answer
29 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: $$ \lnot \lnot P \land \lnot(\lnot\lnot Q \lor\lnot P) $$ The result: $$ P \land \lnot Q $$ The objective is to ...
2
votes
2answers
74 views

A fragment of Exercise 1.3.4 in _Shorter Model Theory_ by Hodges

The following is what I believe is necessary to solve Exercise 1.3.4 in Shorter Model Theory by Hodges. Given two structure $\mathcal {A, B}$ of the same signature $\tau$, a set $S$ of generators of ...
5
votes
1answer
60 views

O-minimal Theories with Non-Dense Order Type

In this paper, Knight, Pillay, and Steinhorn prove that for any O-minimal structure $\mathfrak{A}$, in which the underlying order types is dense, and if $\mathfrak{B} \equiv \mathfrak{A}$, then ...
1
vote
1answer
29 views

Strange Absorption Behavior in Discrete Math

I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example: ...
0
votes
1answer
34 views

Natural Deduction for sets

I'm a student of logic and I have a question, want to prove The Following sets by natual deduction, but do not know how to proceed. $$\begin{align} a) A \cap (B \cup C) ≡ (A \cap B) \cup (A \cap C) ...
0
votes
1answer
131 views

Discrete Math Formula Equivalence Proof

How can I prove that the following two statements are equivalent, using Formula Equivalence laws? f(x) and (g(x) and h(x)) (f(x) and g(x)) and (f(x) and h(x)) I ...
2
votes
1answer
112 views

Why is Skolem normal form equisatisfiable while the second order form equivalent?

I asked in another question when is it appropriate to de-Skolemize a statement. The answer, I'm not sure I'm satisfied with yet, relies on a second order logical equivelance, but Skolem normal form ...
-1
votes
2answers
23 views

Boolean Simplification of a large problem

I am unsure where to even start on this problem. My intuition that what ever can be done to the original problem can be done over and over to simplify the whole thing. Please help with some guidance. ...
1
vote
1answer
27 views

Boolean Simplification of $ (a+b) \cdot (a \cdot c + a \cdot \overline{c}) + a \cdot b + b $

Below is my simplification, but my truth tables don't line up, but I can't find my error. $ (a+b) \cdot (a \cdot c + a \cdot \overline{c}) + a \cdot b + b $ $ (a+b) \cdot a \cdot (c + \overline{c}) ...
0
votes
1answer
48 views

Universe of discourse in $A \subseteq B$

In the following logical analysis: $A \subseteq B $ $\forall x(x \in A \implies x \in B)$ Is the universe of discourse for the above logical form is A since the ...
2
votes
2answers
107 views

The truth table shows the following statement is a tautology, but it doesn't make sense.

the truth table of the sentence $$(p \rightarrow q) \vee (q \rightarrow p)$$ is \begin{array}{ c c l } p & q & (p \rightarrow q) \vee (q \rightarrow p) \\ \hline T & T & \, ...
1
vote
1answer
66 views

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3.

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3. My only idea is to assume the opposite, make some needed arrangement, and to show that changing the ...
1
vote
2answers
44 views

Boolean Simplification of $(\overline{a+b+c})+a\cdot(b+ \overline{c})$

I'm lost, when checking my answer via truth tables, my simplified form does not match the original equation. My work, with reasoning step by step is below. Can you help me figure out where I'm wrong, ...
1
vote
2answers
53 views

prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table

I need to prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table. Please help me to solve it.
0
votes
1answer
43 views

Clarification regarding bound variables and quantifiers

I have been working on one of the problem like this: $ x \in \wp(A \cap B) $ $ x \subseteq (A \cap B) $ $ \forall y (y \in x \implies y \in (A \cap B)) $ $ \forall y (y \in x \implies y \in A ...
2
votes
4answers
68 views

Natural Deduction for Sentence Logic sets

well hello, I'm trying to prove by natural deduction the following sets of laws, but I have some doubts I know I am not doing the right way. $$\begin{align} a) A \cup B = B \cup A \end{align}$$ ...
5
votes
3answers
76 views

Name for introducing negation with quantifiers

The rewriting of $\varphi\to \psi$ into the logically equivalent $\neg \psi\to\neg \varphi$ is called contraposition. Is there a similar word for rewriting $\forall x.\varphi$ into $\neg\exists ...
-1
votes
1answer
48 views

how to define good language for the theory of vector space? [duplicate]

what would be a good language for the theory of vector space?There are two different varieties of objects , scalars and vectors.
4
votes
2answers
64 views

When is de-Skolemizing statements appropriate?

In first order logic we often convert prenex normal form statements to Skolem normal form statements to eliminate the existential quantifier: $\exists$x$\forall$y$\exists$z$\phi$(x,y,z) becomes ...
0
votes
1answer
40 views

show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent [duplicate]

without using the truth table: Show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent.
1
vote
2answers
70 views

Prove $\;\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor q \lor r$ without use of a truth table.

Without using the truth table, I need to prove: $$\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor r \lor q$$ Up until now, we've been using truth-tables to ...
1
vote
1answer
44 views

Second order universal quantifier elimination restriction

Dirk van Dalen in his Logic and Structure gives following universal elimination rule: from $\forall_{X^n} \phi$ infer $\phi^*$ where $\phi^*$ is $\phi$ in which every occurence of $X^n(t_1, ..., ...
1
vote
2answers
87 views

How can we explain the discrepancy between $\rightarrow$ (IF-THEN) and $\setminus$ (A-BUT-NOT-B)?

Let $\mathbb{B} = \{0,1\}$ denote the Boolean domain, ordered in the usual way. Then $\mathbb{B}$ is a lattice. It has a join operation $\vee$ that coincides with "OR," a meet operation $\wedge$ that ...
5
votes
3answers
89 views

Involution on Cantor space with exactly one fixed point

Let $X=\{0,1\}^{\mathbb{N}}$ be the Cantor space. What is an example of a continuous map $\sigma : X \to X$ with $\sigma^2=\mathrm{id}$ and $\# \{x \in X : \sigma(x)=x\} = 1$? This has to exist, ...
0
votes
4answers
56 views

Solving $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

I have been solving this problem from Velleman's How to prove book: $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$ This is my ...
2
votes
2answers
39 views

Building logical connectives only with $\neg$ and $\to$

We want to show that the only connectives that are absolutely necessary are $\neg$ and $\to$. Meaning we can construct all the others with them. Given $A_1, A_2 \in \mathcal{L_0}$, the set of ...
0
votes
1answer
39 views

First-Order Logic: If $\mathcal{N}\models\phi$ for every $\mathcal{N}$, then $\mathcal{M} \cong \mathcal{N}$.

Given that the alphabet $\mathcal{A}$ is finite and that $\mathcal{M}$ is a finite $\mathcal{L}_A$ structure, prove that there is an $\mathcal{L}_A$-sentence $\phi$ such that for every ...
0
votes
2answers
41 views

Characterizing the collection of automorphisms on $\mathbb{Z}$ with a binary relation.

How can one characterize the collection of automorphisms of integers $\mathbb{Z}$ with the binary relation "$<$"? Or "$>$"? "$=$"? How can we acquire the collection of automorphisms?
27
votes
3answers
1k views

Murder at Hilbert's Hotel!

I'm sorry if this is a duplicate in any way. I doubt it's an original question. Due to my ignorance, it's difficult for me to search for appropriate things. Motivation. This question is inspired by ...
2
votes
1answer
50 views

Two questions about the empty type

I have two questions regarding the empty type, $0$, in Martin-Löf type theory: I was reading that, in intuitionistic logic, one has $\neg\neg\neg P\rightarrow \neg P$. This amounts to finding a ...
1
vote
2answers
104 views

Proof Explanation (Zorn's Lemma)

1.13 Theorem The following statements are equivalent: (a) (The Axiom of Choice) Them exists a choice function for every. of sets. (b) (The Well-Ordering Principle) Every set can be ...
3
votes
2answers
78 views

Formal theories dealing with non-commutattive and non-transitive notion of equality

This question is inspired by a philosophical discussion which I don't want to bother you with. As far as I know when we use (or define) the statement "$x$ is equal to $y$" in logic and ordinary ...
1
vote
3answers
85 views
2
votes
2answers
160 views

Proving tautology

Trying to prove if this statement is a tautology: $\neg (p\to q) \to p$ I can simplify the left hand side $\neg (p\to q)$ to $p\land \neg q$, but once I get there I'm stuck.
1
vote
1answer
232 views

How to solve this knights and knaves problem using CNF?

There are 5 natives A-E, each is either a knight or knave. Let a be the statement “A is a knight” and ¬a be “A is a knave”. Same format for the other four natives. Let T be “tautology” and F be ...
0
votes
1answer
150 views

Trouble understanding case analysis (proof by cases)

I've got a discrete math test coming up, and I've been studying religiously for the past week. Proof styles still frighten me though, I find it hard to wrap my head around them. Right now I am ...
0
votes
0answers
35 views

How Do I Show that Condensed Derivable Rules of Inference Yield the Same Formula as Using Condendensed Detachment Multiple Times?

If we look at condensed detachment of two formulas $\alpha$ and $\beta$, we can see that D$\alpha$.$\beta$, where $\alpha$ has form C$\alpha$$_a$$\alpha$$_b$ is equivalent to using the rule ...
0
votes
3answers
90 views

How can I prove that (B and (A implies B)) is equivalent to B?

I was given a couple of proofs to work out like the one stated in my question. While I have successfully managed to prove all the others, this one has me stumped: Show that (B and (A implies B)) is ...
0
votes
1answer
78 views

Set of all perfect squares

I have been going through Velleman's How to prove book and they have explained the set of all perfect squares using this set: $S = \{ n^2 | n \in N\}$ Then it is ...
0
votes
1answer
32 views

Bounded quantifier and it's meaning

It's explained in Velleman's how to prove book that $\exists x \in AP(x)$ means that there is at least one value of x in the set A such that P(x) is true. Then ...
4
votes
1answer
50 views

Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$

Let $\Gamma$ be a set of formulas and $\phi$ be a formula. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$. This seemed pretty obvious but I wanted ...
0
votes
1answer
51 views

Understanding a weird notation when proving a theorem

I'm reading a paper that's trying to prove a theorem. However there is a weird notation that I couldn't understand. First they present the theorem and then they present two claims. In the first claim ...
7
votes
1answer
272 views

Why wouldn't someone accept Gentzen's consistency proof?

Reading the consistency section of the Peano Axioms wikipedia page, I came across this sentence: The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, ...
1
vote
1answer
188 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
2
votes
1answer
52 views

what is the negation of ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN).

what is the negation of ∀x∀y(xy ∈ nN) =⇒ (x ∈ nN ∨ y ∈ nN). Is this correct? if the negation of p=>q is p∧~q then the answer is ∀x∀y(xy ∈ nN) ∧ ~(x ∈ nN ∨ y ∈ nN) = ∀x∀y(xy ∈ nN) ∧ ~(x ∈ nN ∨ y ∈ ...
0
votes
2answers
35 views

Logic : unsatisfiable set

It is obvious that for a set $\Phi$ of well-formed formulas, if $\Phi\cup\left\{\alpha\right\}$ is unsatisfiable and $\Phi\cup\left\{\left(\neg\alpha\right)\right\}$ is unsatisfiable, then $\Phi$ ...
0
votes
1answer
50 views

Propositional formulas, truth assignments proof

Exhibit a propositional formula $\phi$ using only the logical connectives $\neg$ and $\to$ and using all three propositional symbols $A_1,A_2,A_3$ such that for any $\nu$, $\bar{\nu}(\phi)= T \iff \nu ...