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

learn more… | top users | synonyms (1)

2
votes
3answers
68 views

If true for the general element, then true for all. What's this?

In mathematics often (always) one proves that a property is true for the general element of a set. From that, one can say that that property is true for all the elements of that set. Is that a ...
1
vote
1answer
140 views

Reference request basic logic/model theory

I'm taking a knowledge representation class and need more perspective on basic model theory. We're currently using Levesque and Brachman. Specifically, a question on the midterm was something like, ...
4
votes
1answer
50 views

Show functionally completeness property for propositional logic

Let $n>0, n\in \mathbb{Z}$ and let t,f denote true and false. For every function $$g:\{t,f \}^n \to \{t,f\} $$ There is a propositional forumala $B$, using only the connectives ...
1
vote
3answers
167 views

Proof of the Principle of mathematical Induction [duplicate]

We always use the Principe of Mathematical induction and we have two versions of it. I myself have been using it for many years. But it just came to my mind that I have never seen a proof of the ...
3
votes
4answers
122 views

How to show that something is not logically entailed?

I was just thinking about entailment and would like to know if you can show that something is NOT entailed by the premises. I know that to show $A, A → B \vdash B$, I could just provide a proof ...
1
vote
3answers
105 views

Where to put the “such that”, given multiple quantifier

Personally, I would put the "such that" (i.e. the symbol $:$ or $|$) behind any quantification. That is given an assertion $A(x,y)$, I'd write $$ \forall x\in X\exists y\in Y:A(x,y)\\ \exists x\in ...
4
votes
5answers
159 views

semantics(truth) vs formal system?

my first question is can we just define semantics in logic and not define a formal system ? why do we need a formal system to prove a proposition when for example we know the proposition is true ? ...
2
votes
3answers
63 views

What does 'any' mean in predicate calculus

I need to translate an English sentence into a well-formed predicate calculus formula. The sentence starts off as: Any tiger who chases every creature also chases itself. Does 'any' translate ...
2
votes
2answers
99 views

The existence of conjunctive/disjunctive normal forms?

I am studying propositional logic/calculus and I am currently learning about normal forms. The algorithm to construct a conjunctive/disjunctive normal form from any given formula is straightforward. I ...
2
votes
2answers
86 views

Syntax of an epsilon delta proof/why is this version incorrect [duplicate]

So we have the regular $\delta$-$\epsilon$ definition of continuity as: (1) For all $\epsilon>0$, there exists a $\delta>0$ such that, if $|x-a|<\delta$, then $|f(x)-f(a)|<\epsilon$. My ...
1
vote
1answer
37 views

proof checking - power set and family set

Decide if it is true that $P(A) \subseteq P(B) \implies \bigcup A \subseteq \bigcup B $ where $P(A), P(B)$ are power set and $A,B$ are family of sets My proof: Let $x \in P(A)$ then we have ...
1
vote
1answer
40 views

Generic in Boolean-Valued-Models

Let $M$ be a transitive $\in$-interpretation of a extension $T$ of $ZF$ in $ZF$,and let $B$ such that $$T\vdash B\in M\wedge B\text{ is a complete Boolean algebra}$$ Then, using the fact that any set ...
3
votes
1answer
77 views

Bases of complex vector spaces and the axiom of choice

In Zermelo-Fraenkel set theory $ZF$ consider the following statement defined for every field $K$: $B_K$ : Every vector space over $K$ has a basis. It is well-known that $AC \Rightarrow \forall K ...
0
votes
3answers
94 views

Recommendation on Quine's text

I'm planning to study logic seriously and I think Quine's style is fine to me so i'm going to read his book. There are two famous books by him. Namely, "Methods of logic" and "Mathematical logic". I ...
0
votes
1answer
81 views

Problem in solving a logical Equivalence

Prove or disprove the following equivalence: $$ ∀x Px \wedge ∀x Qx \Leftrightarrow ∀x ∃y ( Px \vee Qy ) $$ I've tried it, but I do not know how to solve logical equivalences involving quantifiers.
4
votes
1answer
228 views

Propositions logic and problem solving

How can a question of this nature be approached: Two avid game players Alice and Bob play three different games. They are very competitive and so would do anything within the rules of the game to ...
3
votes
1answer
88 views

What is a list of book that i need to read as a prerequisite before start reading “lectures of logic and set theory vol.1 by George Tourlakas”?

What is a list of formal textbook that i need to impose myself to read as a prerequisite before start reading a book called lectures of logic and set theory vol.1 by George Tourlakas? That book is ...
0
votes
1answer
37 views

How does the following example prove that this set of axioms for a probability field is consistent?

This is froms Kolmogorovs Foundations of probability theory. He gives the following five axioms. Let $E $ be a set and $\mathcal F $ be a set of subsets of $E $. I $\mathcal F $ is closed under ...
0
votes
1answer
55 views

Cardinality of the set of non isomorphic structures of fixed cardinality

Let $L$, be a language and $\alpha$ be a cardinal; let $\Gamma:= \{\text{set of non isomorphic $L$ structures, having cardinality $\alpha$}\}$. Prove that $\operatorname{Card}(\Gamma)\leq ...
1
vote
1answer
53 views

Set theory, operation with products, union and intersection

I need to show the following using logical connectives: $B\setminus (B \setminus A)=A \cap B $ $(A \setminus B)\cup(B\setminus A)=(A \cup B)\setminus(A \cap B)$ $(A\times B\setminus C )=(A\times ...
1
vote
2answers
68 views

logical associative expressiveness with no negation operator

Let's suppose we can only use $\wedge$ and $\vee$ operators (we have no negation operator), and by default we have associativity to the left. Is this subset of logic as expressive as the one with the ...
2
votes
1answer
298 views

Translate the following argument into propositional logic, and then assess it for validity.

This is question 9 from exercise 6.5.1 in Smith and Cusbert's Logic: The Drill. It wants a translation and test of validity for the following: Catch Billy a fish, and you will feed him for a ...
0
votes
1answer
182 views

What is the formal way to define “class” in ZFC?

Unlike axiomatic systems deal with classes such as NBG, the term "class" is not a word in ZFC. How do I formally treat classes? Here is an example of what I'm exactly talking about. Example ...
1
vote
1answer
108 views

There are any known example of independence proofs about independence result?

(This question is inspired by deleted question, and the questioner who write the deleted question wrote new question.) It is well-known that consistency of "ZF + DC + every set of reals are Lebesgue ...
4
votes
4answers
758 views

Which texts do you recommend to study universal algebra and lattice theory?

As I'm planning to study some algebraic logic (a lot of!), I found that some knowledge of universal algebra, lattice theory and boolean algebras is a must. I wonder if you have any recommendation to ...
3
votes
1answer
42 views

Suppose a $\in \mathbb{Z}$. $a^{2}|a$ if and only if $a \in \{-1,0,1\}$

Suppose a $\in \mathbb{Z}$. Then $a^{2}|a$ if and only if $a \in \{-1,0,1\}$ So, I have started and this is what I have so far: Case 1: If $a^{2}|a$, then $a \in \{-1,0,1\}$. For the sake of ...
4
votes
2answers
74 views

Can this expression $(\neg B \land \neg D) \lor (\neg A \land B \land C) \lor (A \land C \land D)$ be further simplified?

I have assignment for computer architecture where I have to simplify a big boolean function: f(a, b, c, d) = a'b'c'd + a'bcd' + abcd + a'bcd + a'b'cd' + ab'cd' + ab'c'd' + ab'cd + a'b'c'd' ...
0
votes
2answers
76 views

How to prove $p \vee q \vdash \neg(\neg p \wedge \neg q)$?

I'm trying to complete a list of exercises but this question I still can not solve. Somebody could help me? updated: this is my conclusion 1 - $p\vee q$ Premise 2 - p Assume 3 - $\neg p\wedge\neg q$ ...
0
votes
0answers
50 views

What's the difference between a costant $k$ and $arity = 0$?

What kind of mathematical entities can have $arity = 0$ without being a constant ? Or there is a concept that generalize the concept of constant and I can't see it ? Background: I am having some ...
1
vote
2answers
123 views

Proving the non-derivability of formula using the of the kripke model

I try proving the non-derivability of $(p\to q) \to \lnot p \lor q$, using the of the kripke model. I tried using different combinations of $Wi$, but I get fail.
1
vote
1answer
31 views

How can I further simplify this $A$ + $\neg A B$?

I know there's a rule to simplify this formula $A$ + $\neg A B$, but I am not seeing it. Can someone tell me the name and how to do it?
0
votes
1answer
56 views

Show that $(A \oplus B) \oplus B = A$

I having some trouble proving $(A \oplus B)\oplus B = A$, I understand the truth table logic but can someone example to me in theory what the equation mean in set theory?
1
vote
1answer
121 views

How to better understand “ x occurs free in a wff ” in first order logic?

On page 121 of Herbert Enderton's A Mathematical Introduction to Logic, the author gives a proof of the following example : If x does not occur free in $\alpha$, then $$ \vdash ( \alpha \rightarrow ...
3
votes
2answers
179 views

Different models of ZF disagree on equality of explicit recursively enumerable sets

Assuming that ZF is consistent, are there two recursively enumerable sets defined by explicit enumerators that are the same in one model of ZF+Con(ZF) but different in another model of ZF+Con(ZF)? If ...
0
votes
1answer
42 views

Beautiful logical minimum construction

On a circle after equal intervals 25 points are located. On every point is a policeman. All policemen are numbered (from 1 to 25) in some way. Now they have to move to some other points through this ...
2
votes
1answer
105 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
36 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
40 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 ...
1
vote
0answers
42 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 ...
3
votes
2answers
73 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
30 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
47 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
73 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$ ...
1
vote
1answer
170 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
70 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
57 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
47 views

How do I prove the following statement?

How do I prove the following statement? If $x^2$ is irrational, then $x$ is irrational. The number $y = π^2$ is irrational. Therefore, the number $x = π$ is irrational
0
votes
2answers
66 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 ...
3
votes
2answers
86 views

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

I have an assignment where I have to work with power sets: Let $\mathcal{P}(A)$ denote the set $\{ x ~|~ x \subseteq A \}$. And I have 2 questions: Is the set $\mathcal{P}(A)$ a truth set ...
-1
votes
3answers
82 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, ...