1
vote
1answer
69 views

Need help with a fundamental theorem of finite arithmetic

An amateur mathematician, I am working with a finite set $N$, elements $0, m\in N$ and partial function $S$ on $N$ such that the following Peano-like relations hold. ($0$ is the first element of $N$. ...
0
votes
1answer
38 views

Formal statement of the well-ordering theorem

Out of interest, how would you write the well-ordering theorem in pure set-theoretic language?
0
votes
2answers
45 views

Suppose $A, B$, and C are sets. Prove that $C\subset A\Delta B \Leftrightarrow C \subset A \cup B$ and $A \cap B \cap C = \emptyset $

The problem statement is in the title. I'm proving a problem in class and I need to show the above containment. I've drawn some Venn diagrams to make sure the containment makes sense, and it does to ...
0
votes
1answer
30 views

Can all cardinal numbers be represented by an ordinal numbers, assuming choice?

Can all cardinal numbers be represented by ordinal numbers, assuming AC? (ZF+AC) If or if not, what would be the proof?
2
votes
1answer
96 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
2
votes
5answers
79 views

Question about definition of binary relation

Wikipedia says: Set Theory begins with a fundamental binary relation between and object $o$ and a set $A$. If $o$ is a member of $A$, write $o \in A $. I thought that a binary relation is a ...
2
votes
1answer
35 views

choosing elements from the set of sequences in ZFC

In my previous question, I asked about infinite-length formula in ZFC. But I am still confused over following: Suppose you want to build a function from a set of sequences to a set that chooses $n$th ...
4
votes
2answers
174 views

Is infinite-length formula allowed in ZFC?

I am curious whether infinite-length formulas are allowed in ZFC. If it is not, then how does it express the case where infinite number of terms (in ordinary mathematics) are being handled? (Like ...
1
vote
1answer
40 views

Subtraction of elements from $\mathbb Z$

Let $M_n$ be the set of integers which are integer multiples of $n$. If $\mathbb N = {1,2,3...}$ What would $$ \mathbb Z - \bigcup_{n\in\mathbb N}M_{2n+1} $$ be? I know that $M_{2n+1}$ represents ...
0
votes
2answers
30 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
0
votes
1answer
30 views

Can an element hood test be converted into an existential statement?

I'm just curious whether it makes sense to convert a statement of the form: $$ y\in \{x\in A : \phi(x) \} \;\; \text{into the form} \;\; \exists x(\,...) $$ It's just that in the book I'm reading the ...
3
votes
2answers
83 views

De Morgan's laws in logic and set theory

In logic De Morgan's law means $\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B$ In set theory De Morgan's law means $(A \cap B)^C = A^C \cup B^C$ I'm surprised that the same idea is true in ...
0
votes
1answer
42 views

Analogue of Russell's paradox

Using ZF set theory (without the axiom of foundation), is $$ \{z: \neg(\exists u_1,...,u_n)((z \in u_1)\land (u_1 \in u_2) \land ... \land (u_n \in z))\}$$ A set for any n? This is an analogue of ...
2
votes
4answers
94 views

Convincing proofs, proofs by contradiction and countability

Disclaimer: I have a (modest) background in mathematical physics, not logic, so I know very little of the latter. Although when I understood Cantor's argument for the first time (from one of Martin ...
0
votes
1answer
56 views

Countable and Uncountable sets

Is $\mathbb{N}\cup\{a\}$, for some $a\not\in\mathbb{N}$ countable or uncountable? $\mathbf{Attempt: }$ It is true that a set is countable if there exists an injective function $f : S → N$ from $S$ to ...
0
votes
3answers
59 views

How did I solve this problem?

While writing a SQL query I had to solve a problem I'd never dealt with before. It was trivial, but I cannot explain the solution without drawing lines on paper or making examples with actual numbers ...
-4
votes
1answer
101 views

What's the difference between relations, functions, and operations?

My understanding is vague: operations is a subclass of functions, functions is a subclass of relations. operations and functions can form terms but not formulas, relations can form formulas but not ...
1
vote
2answers
58 views

Sigma hierarchy of logical formulae

In some papers on mathematical logic I've found references to hierarchy like $\Sigma_1^0$-sentence and so on. What does it mean? What is $\Sigma_n^m$, what is $n$ and $m$ here?
1
vote
2answers
67 views

A quick question about a logical negation

I just want to make sure I'm negating the following logical statement correctly (for a contradiction proof): For every set $A$, there exists a well ordered set $V$ such that there exists no ...
2
votes
1answer
37 views

Every truth function of the inderterminates X and Y is an iterated composition of negations and disjunctions.

I'm reading K.T.Leung and Doris L.C.Chen's Elementary set theory.I can't solve exercise 10: Prove that every truth function of the inderterminates X and Y is an iterated composition of negations and ...
2
votes
0answers
25 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models ...
1
vote
1answer
40 views

Prove $A $ \ $B $ = $A \cap B^c $

I see the use of $A $ \ $B $ = $A \cap B^c $ being used in bigger problems but how do you prove this? Is the proof as simple as: $A $ \ $B $ $\iff$ $ x \in (A \setminus B) \iff x\in A \cap ...
4
votes
1answer
120 views

Can one define $\langle x,y\rangle$ in $P(C)$?

I study at course Foundations of Mathematics the below definitions and lemma: $\langle x,y\rangle:=\{\{x\},\{x,y\}\}$ (from Kuratowski 1921) $\langle x,y\rangle:=\{\{\{x\},\varnothing\}\{\{y\}\}\}$ ...
0
votes
3answers
70 views

Prove $A \cup A' = U$ and$ A \cap A' = \emptyset$

Prove $A \cup A' = U$ and $A \cap A' = \emptyset$ $A \cup A' = U$ set union definition with negation on the second $A$. $[x: x \in A \lor x \notin A]$ This means that x is in $A$ or x is not in ...
1
vote
1answer
135 views

Recommendation on a rigorous and deep introductory logic textbook

In this post, I don't mean any word by its somewhat "mathematical or logical" meaning but just "literally". It's been three years since I started "formal" mathematics, and now I'm familiar with set ...
1
vote
2answers
87 views

Prove $A+(B+C) = (A+B) +C$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the following statement: f.$A+(B+C) = (A+B) +C$ We need to ...
0
votes
1answer
31 views

Can the sheffer stroke do the work normally done with sets?

It seems to me that the sufficiency-necessity relation is effectively the same as the set-member relation. Using a concrete examples to make the point: A rain drop ⊃ a bit of water A rain drop → ...
0
votes
3answers
121 views

Prove $A + (B+C) =B+(A+C) = C+ (A+B)$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove the following statement $A + (B+C) = B+(A+C) = C+ (A+B)$ ...
0
votes
3answers
87 views

Proving $A \cap C = B \cap C$, but $ A \neq B$

Let $A,B,C$ be sets. Identify a condition such that $A \cap C = B \cap C$ together with your condition implies $A=B$. Prove this implication. Show that your condition is necessary by finding an ...
1
vote
2answers
132 views

Prove $A+B= A \cup B$ if and only if $A \cap B = \emptyset$ using the definition of $A+B$

Let $A$ and $B$ be sets. Define the symmetric difference of $A$ and $B$, written $A+B$, by $A+B=(A \cup B) \backslash (A \cap B)$. Prove $A+B= A \cup B$ if and only if $A \cap B = \emptyset$. My ...
1
vote
5answers
55 views

Prove that $A \ne B$ is equivalent to the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$

Prove that $A \ne B$ is equivalent to the logical statement $(\exists x)[x \in A \land x \notin B] \lor (\exists x)[x \in B \land x \notin A]$. Given: P: $A \ne B$ is equivalent Q: the logical ...
1
vote
6answers
79 views

Prove the following statement: If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set.

If $E$ is an empty set and $A \subseteq E$, then $A$ is an empty set. Edit: Thanks for the \emptyset Latex command. Given: P: $E$ is an empty set and $A \subseteq E$ Q: $A$ is an empty set. We ...
3
votes
1answer
56 views

Prove the following statement: If A is any set, then $A \subseteq A$

I'm doing some practice problems and I'm wondering if I got this right. I think this is a very short proof, but I'm not sure. Given: P: A is any set Q: $A \subseteq A$ We have a $P \rightarrow Q$ ...
1
vote
3answers
57 views

Understanding the union operation

Suppose we have: $A = \{(x,v,w):x+v=w\}$ $B = \{(x,v):x=v\}$ $C = \{(w,u):\exists x 2x=w\}$ Can we say that $C = A \cup B$?
1
vote
2answers
44 views

What makes a condition unary vs. n-ary (n>1)?

For any two disjoint sets $A$ and $B$, a set $W$ is a connection of $A$ with $B$ if $Z\in W\implies (\exists x\in A)(\exists y\in B)[Z=\{x,y\}]$ $(\forall x\in A)(\exists !y\in B)[\{x,y\}\in W]$ ...
2
votes
5answers
221 views

Logic and set theory textbook for high school

Do you have any advice for a textbook or a book for high schools students which completely adresses basics of logic (proposition, implication, and, or, quantifiers) and set theory (intersection, ...
3
votes
3answers
73 views

Disproving $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$

Let $A,B,C$ be any sets. Tell if $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$ is true or false. I tried to prove by absurd. Suppose $A \subset B \wedge B ...
7
votes
2answers
164 views

Plausibility argument for Zorn's Lemma

In "Mathematical Physics" by Robert Geroch, the following 'plausibility argument' is given for Zorn's Lemma [If every totally ordered subset of a partially ordered set $S$ is bounded above, $S$ has a ...
1
vote
2answers
41 views

Statements about attributes of given function.

Let $HF(0) = \emptyset$. $HF(n+1) = P_\omega(HF(n))$, where $P_\omega(A)$ - set of all finite subsets of $A$, and $HF = \displaystyle\bigcup_{n\subset\omega}HF(n)$. Are those statements true? ...
1
vote
2answers
75 views

Book suggestion on set theory/logic

Can anyone recommend good books/tutorials on set theory/logic with simple explanations for a person with no math background(nothing beyonds arithmetic and basic algebra back in school) ?
0
votes
1answer
63 views

Proving that an infinite set is uncountable.

I've been doing some practice questions for my course and I found the following question quite difficult to understand. Prove that the following set is uncountable $B_\infty = \{ s \in B : s ...
1
vote
2answers
50 views

Can I do this? $A^c - B^c$

If not how can I work with it? (A and B are sets) $A^c - B^c$ I am trying to simlify the above... $= (B-A) - (A-B) $ $= 2B - 2A $ $= B-A$ Is it safe to say that $A^c = B - A$? Furthermore is my ...
0
votes
1answer
49 views

Cardinality of the set of all well formed formula in propositional logic?

Here's the simple grammar for propositional logic I'm using: For all $n \in \mathbb{N}$, $P_n$ is a WFF (Well formed formula). If $\phi$ and $\psi$ are WFF's then $(\phi \rightarrow \psi)$ is a WFF. ...
0
votes
0answers
34 views

Disproving a proof about the explosion principle for sets of sentences

Imagine that someone were to try to prove that every sentence is a consequence of an inconsistent set of sentences in the following way. Suppose that Γ is inconsistent. Then for some ϕ ∈ S, ϕ & −ϕ ...
2
votes
3answers
77 views

First order logic. Describe that a set has more than 2 elements.

I would like to describe that a set has at least 3 elements using first order logic, would this be a valid way to do that? $\forall x\exists y\exists z(\neg(x=y)\wedge\neg(x=z)\wedge\neg(y=z))$ I ...
0
votes
1answer
41 views

prove two different forms of the same uniqueness theorem are logically equivalent

One may take either of the statements below as a definition of $(\exists!x)(P_x)$, where $P_x$ is a predicate concerning the set $x$. Prove that they are logically equivalent. $$ (\exists x)(P_x) ...
2
votes
4answers
161 views

Does cardinality really have something to do with the number of elements in a infinite set?

I've seen some videos and read some texts (non-rigorous ones) that explained the concept of cardinality, and sometimes I see someone asking if there are more numbers between the reals in $[0,1]$ then ...
5
votes
1answer
54 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
5
votes
4answers
113 views

Why use the biconditional in the Axiom of Extensionality

I'm studying the Axiom of Extensionality in the following form: $$ \forall a \forall b[\forall x(x\in a\leftrightarrow x\in b)\rightarrow a=b] $$ (where quantification of a,b is restricted to sets ...
2
votes
1answer
69 views

Generalized distributive laws proof feedback

I'm currently learning proofs and elementary set theory. I would like to have feedback on my proof since I'm self-studying. Are some part superfluous or unclear? My proof goes as follows: I will ...