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.

learn more… | top users | synonyms (1)

1
vote
3answers
13 views

$A \subseteq X$ and $B \subseteq Y$, show that $(X \times Y) \setminus (A \times B) = (X \setminus A) \times (Y \setminus B)$ is not always true.

I want to prove that $(X \times Y) \setminus (A \times B) = (X \setminus A) \times (Y \setminus B)$ with $A \subseteq X$ and $B \subseteq Y$ is not always true. However, I have difficulties to ...
0
votes
3answers
18 views

Examples of automorphisms on structures

For some structure $(M,I)$ with $M$ a set and $I$ the interpretation of the constants, functions, and predicates, what is an example of a such a structure such that for each $a$ of $M$ there are only ...
2
votes
2answers
40 views

Prove $\lnot \lnot B$

Prove: $\lnot \lnot B$ from $\lnot \lnot A \implies \lnot \lnot B, \lnot(A \implies B) $ I cant use excluded middle: $B \lor \lnot B$ So I choose $\lnot B$ as hypothesis and will try to get $B$ ...
2
votes
1answer
73 views

Existence of model implies consistency in Cohen's book

On page $13$ of his book Set Theory and the Continuum Hypothesis Paul Cohen writes: The point of these definitions is the following obvious fact: THEOREM $1$. ... If a set of statements $S$ ...
1
vote
3answers
31 views

Predicate logic translation $\exists y \exists x \neg P(x,y)$

Let P be the predicate P(x,y) "x owns y" where x represents people; y represents objects. $$\exists y \exists x \neg P(x,y)$$ I am trying to convert the above statement into plain english, for some ...
3
votes
1answer
40 views

Why is a not-not-p invalid in a logical clause?

I have an assignment and it states that while $(p \vee q) \vee \lnot r$ is valid, $(p \vee q) \vee \lnot(\lnot r)$ is invalid in a logical clause, but I don't see why. A clause is described as being ...
0
votes
5answers
33 views

How do I validate/prove the following statement using a proof?

How do I validate/prove the following statement using a proof? if x^2 is irrational, then x is irrational. The number y = π^2 is irrational. Therefore, the number x = π is irrational
-1
votes
0answers
19 views

What is the proof order? [duplicate]

The proof below has been scrambled. Please put it back in the correct order. Claim: For all n ≥ 9, if n is a perfect square, then n-1 is not prime. Since (n-1) is the product of 2 integers greater ...
0
votes
2answers
42 views

What is the right order?

The proof below has been scrambled. Please put it back in the correct order. Claim: For all $n ≥ 9$, if $n$ is a perfect square, then $n-1$ is not prime. Since $(n-1)$ is the product of 2 integers ...
1
vote
1answer
38 views

The truth set of the formula $\{x\mid x\subset A\}$

I have an assignment where I have to work with power sets (I think): Let $\mathcal{P}(A)$ denote the set $\{ x ~|~ x \subseteq A \}$. And the I have 2 questions: Is the set $\mathcal{P}(A)$ a ...
0
votes
3answers
35 views

Determine the valid arguments by using proofs

Determine whether these are valid arguments: a) “If x^2 is irrational, then x is irrational. Therefore, if x is irrational, it follows that x^2 is irrational.” b) “if x^2 is irrational, then x is ...
0
votes
1answer
42 views

Mathematical Expressions: Proofs

Prove or disprove the claim, and prove or disprove the converse: Claim 1: ∀n ∈ ℕ, (Ǝk ∈ ℕ, n = 5k + 2) ⇒ (Ǝj ∈ ℕ, n^2 = 5j + 4) Claim 2: ...
1
vote
1answer
25 views

How to prove the validity of this argument?

I have an assignment where I have to prove the validity of a statement, but I am not sure about what I am doing. This is the assignment: Is the statement $(A \wedge B \wedge C) \to D$ a valid ...
0
votes
0answers
19 views

A symbolic logic problem generator, or at least a huge ready-made collection?

I am an amateur student of formal logic, and I was wondering other Gensler's LogiCola program, is there anything out there that produces logic proof problems? For example, the LogiCola program I am ...
1
vote
0answers
27 views

Mathematical expressions: Proving logic statements

For $x \in \mathbb R$, define the floor function by: $$\lfloor x\rfloor \in \mathbb Z ~~\land~~ \lfloor x \rfloor \le x ~~\land~~ (\forall z \in \mathbb Z ~:~ z \le x \Rightarrow z \le \lfloor ...
1
vote
2answers
48 views

Proving logic statements

For x ∈ ℝ, define by: ⌊x⌋ ∈ ℤ ∧ ⌊x⌋ ≤ x ∧ (∀z ∈ ℤ, z ≤ x ⇒ z ≤ ⌊x⌋). Use this definition to prove or disprove the following with a structured proof technique: ∀x ∈ ℝ, ∀y ∈ ℝ, x > y ⇒ ⌊x⌋ ≥ ⌊y⌋. ...
1
vote
2answers
31 views

Proving $\forall x (A\to B) \to(A \to \forall x B):x\notin \mbox{free}(A)$ in a Hilbert system where it is not an axiom

I have no idea whether this question is way too specific or whether something similar has already been asked (we still need to work out a way to search for formulas I guess). Anyways here I go: I ...
0
votes
2answers
33 views

For any set of formulas in propositional logic, there is an equivalent and independent set

A set of formulas is independent if no proper subset is logically equivalent to it. Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.
0
votes
0answers
16 views

finite state machine rows and columns

Knowing that the FSM has 23 states, 4 input bits, and 3 output bits, how do you calculate how many rows and columns will be needed to represent the truth table? I know that the answer is 512 rows and ...
2
votes
1answer
28 views

Show that $(\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A)$.

Let $A, B,$ and $C$ be sets. Show that: $$ (\overline A ∪ B) ∩ (\overline C - A) = (\overline C - A) $$ I’ve simplified to the following: $$ (\overline A ∪ B) ∩ (\overline{C \cup A}) = ...
3
votes
3answers
81 views

Formal notion of computational content

In constructive mathematics we often hear expressions such as "extracting computational content from proofs", "the constructivity of mathematics lies in its computational content", "realizability ...
0
votes
0answers
8 views

how to do that function $n \rightarrow h(f(n),g(n))$ is URM [on hold]

if $f:N\rightarrow N$ ,$g:N\rightarrow N$ , $h:N^{2}\rightarrow N$ are URM computable then so is the function $n \rightarrow h(f(n),g(n))$.
3
votes
3answers
53 views

High school geometry proofs and first order logic?

I am a student of logic who recently came across two column geometry proofs which seem to be the bane of many a high-school student. My main question though, is that is there any way of doing these ...
1
vote
1answer
18 views

Boolean Logic Converting DNF to CNF

I'm confused on how to convert DNF to CNF. On the answer sheet my teacher gave me, she just convert it right away with no explanation. So my teacher convert $F: (A \wedge \neg B) \vee (B \wedge D)$ ...
0
votes
1answer
41 views

Any substructure of $(\mathbb{N}; 0, 1, +, \cdot)$ is itself

Consider a substructure $\mathcal{M} \subseteq \mathcal{N} = (\mathbb{N}; 0, 1, +, \cdot)$. Prove that $\mathcal{M} = \mathcal{N}$. EDIT: This result seems intuitively easy, but I'm having trouble ...
2
votes
4answers
26 views

Question About Notation Nested Quantifiers.

It's a pretty simple question on nested quantifiers but I didn't see anything about it on my Textbook or on Google so I wanted to give this a shot. So let's say you have $P(x)$ and $P(y)$ and you ...
1
vote
1answer
20 views

Distribute ANDs over ORs in this sentence

Can someone explain how we turn the sentence $$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because ...
1
vote
3answers
42 views

Reverse of Deduction Theorem

Why is it "easy to see" that if $S \vdash (A\to B)$ then $S \cup\{A\} \vdash B$?
0
votes
2answers
23 views

how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$ I tried doing it with a truth ...
2
votes
3answers
37 views

Is this formula satisfiable?

I am confused whether or not my explanation for whether or not this formula is satisfiable is correct. Note that the question state it should be Brief and it should not be necessary to write down a ...
-4
votes
1answer
21 views

what can be considered the winning points? [on hold]

2 people play a matchstick game. When it is your turn you can remove 1, 2 or 5 matches from the pile. You lose if you can not make a move. Develop a winning strategy for this game.
1
vote
2answers
32 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
1
vote
2answers
47 views

Is it true that if not $\alpha \vDash D$ implies $\alpha \vDash \neg D$?

If it is not true that $\alpha \vDash D$, with $D$ arbitrary formula, is it true that $\alpha \vDash \neg D$? I think that this assertion is false, but I cannot find counterexamples. Thanks in ...
3
votes
0answers
63 views

Intuition for the choice of background (set) theory

Problem From the formalist point of view, any mathematical statement should ultimately be an assertion about the derivability of a certain formula in a certain formal system, call it the background ...
0
votes
1answer
8 views

Write Propostion using Quantifier

Write the proposition “Every pair of strangers has a common friend” using connectives and quantifiers. Use F(x, y) for “x is friends with y.” (Two people are strangers if they are not friends.) My ...
5
votes
1answer
38 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
1
vote
1answer
35 views

Proof of Soundness Lemma

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$ We are given the hint to ...
1
vote
1answer
18 views

Inference Lemma Proof?

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$. Proof: Let $\langle ...
2
votes
2answers
83 views

Beautiful combinatorial painting problem

Mark paints squares of a white $10 \times 10$ board. He can either paints some vertical row of squares blue or some horizontal row red.(Every row is painted at most once). If blue paint is put on ...
1
vote
1answer
40 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
55 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...
1
vote
1answer
48 views

Prove: $\{α_1,…,α_n\} ⊨ α$ iff $\{α_1,…,α_{n−1}\} ⊨ (α_n→α)$.

Recently began my second logic course and have been surprised at how very, very different it is from the first one. My main struggle is that we have to prove things all the time, and I've never learnt ...
1
vote
2answers
38 views

What are the rules for negating quantifiers in propositional logic in general, is the “NOT” distributive?

I was wondering what the general rules for negating quantifiers was. I was reading that they follow this rule holds: $$NOT(\forall x. P(x)) \iff \exists x. NOT(P(x))$$ Which makes sense to me. ...
3
votes
2answers
43 views

Why does changing the order of quantifiers in Goldbach's conjecture changes its meaning and truth value?

Goldbach's conjecture in English reads: “Every even integer greater than 2 is the sum of two primes.” Which can be written in terms of quantifiers as: $$\forall n \in Even. \exists p \in ...
1
vote
2answers
26 views

What operation is done first in the following exercise…

Here I have such an exercise: I have to simplify the form of the following expression:$$(p\lor \lnot q)\land(\lnot p \lor q )\lor (p \lor \lnot r)\lor \lnot q$$. I know how to simplify it, but what ...
0
votes
0answers
13 views

Conditional Probability Semantics

I am studying conditional probability, and have a question on the semantics of a problem. I have the following belief network: ...
2
votes
1answer
44 views

Convert one proof into another

For a long time I have been investigating this question on my own, but it seems impenetrable. The question is this: To find a method whereby it becomes possible to convert proof A into proof B, where ...
0
votes
0answers
20 views

how to describe an $\mathcal{L}-$model that has its univers $R$? [on hold]

this language consisting of one constant , synbole , one 3-ary function symbole and one binary relation symbole :$\mathcal{L}$ is $\{\flat \; \natural \; \sharp\}$. how to describe an ...
0
votes
0answers
18 views

Translating sentences into sentential calculus [closed]

William Shakespeare was William Shakespeare if and only if he wasn’t Francis Bacon.
0
votes
2answers
58 views

Show that the following statement is a theorem.

Suppose h is not a counting number and h is greater than 1, then there is a counting number n such that h is between n and n + 1. I am working through "Creative Mathematics" by H.S. Wall. The book ...