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
1answer
22 views

Mathematical XOR

I'm having some trouble understanding XOR in mathematical terms. I'm familiar with XOR in logical terms, meaning $A \oplus B$ meaning mutual exclusiveness, and I can easily write out the truth table ...
1
vote
0answers
15 views

Infinite strings and infinite theorems - Is there a theory on these stuffs?

I can have an alphabet $\mathcal{A}$, a set of axioms $\mathcal{X}$ which are finite strings of $\mathcal{A}$ and a set of rules $\mathcal{R}$. Every finite strings produced by applying a finite ...
0
votes
1answer
13 views

Proof Explanation: Existence of “fg-chains” Axiom of Choice implies Zorn's Lemma

I would be very glad if someone could explain the validity of a passage of this paper to me. In the proof of Lemma 3.3, "Fundamental Lemma", the notion of "fg-chains" is introduced and later on, we ...
0
votes
0answers
12 views

How to prove unicity in a disjunction of $n$ propositions

Let's suppose I have the propositions $\varphi_1, \varphi_2,...,\varphi_n$ and I want to prove that there happens exactly one of them. How do you do it? To do it the hard way I guess we first need to ...
2
votes
1answer
28 views

Undecidability and truth

Are there undecidable problems for which a single truth exists? For example, the question about parallels is not decidable from Euclid axioms. But multiple answers are valid and give different kinds ...
1
vote
3answers
17 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
24 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
46 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
95 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
35 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
45 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
34 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
40 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
36 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
43 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
26 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
56 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
32 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
29 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
82 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
54 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
19 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
27 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
34 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
50 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
64 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
39 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
84 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
45 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 ...