0
votes
1answer
61 views

Prove the reflexivity of $\subseteq$.

My professor gave me a list of exercises, I've been able to figure out what mechanism I should exploit to prove them, but I'd like to know if it's good. Until now we've been taught a little logic and ...
2
votes
2answers
34 views

Composition of injections (proof)

I'm trying to prove that composition of injections is an injection. I want to know if this is a good proof: Composition of injections is an injection. Let $f:S_1\rightarrow S_2$ and ...
4
votes
6answers
1k views

In a class of 65, there are twice as many maths students as biology students.

I have a task: In a class of 65, there are twice as many maths students as biology students. If 12 biology students do not take maths and 15 students take neither of these subjects, how many students ...
1
vote
2answers
32 views

Proof on limit superior and limit inferior of a set

I understand the result intuitively but how can I prove this? For a given integral $n \ge 1$, let $A_n = \left\{\frac mn \mid m \in \mathbb Z\right\}$. Show that $\varlimsup_{n\to\infty} A_n = ...
0
votes
2answers
21 views

Fine partitions

I am tasked with the following: Give four different partitions $\Pi_1,\Pi_2,\Pi_3,\Pi_4$ of the set $\Bbb N$ with $\Pi_i$ Finer that $\Pi_{i+1}$ for $i =1,2,3$ I think that partition by 8, 4,2 ...
2
votes
2answers
42 views

Proving existence of surjective $f:\mathbb{N} \rightarrow A$ implies $A$ is at most countable.

Definition of "at most countable" used: A set $A$ is at most countable iff it's finite or there exists a bijection $f:\mathbb{N} \rightarrow A$. Problem: I want to prove that if there exists a ...
4
votes
1answer
38 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
2
votes
0answers
14 views

Set with relative complement forms partition

Prove that if $S$ is a set and $ \emptyset \subsetneq A \subsetneq S $ then $\Pi = \{A , S-A \}$ is a partition of $S$. Proposed Solution: Since $ A \subsetneq S$ , we have $S - A \neq ...
0
votes
2answers
30 views

Subsets and Cardinality

I'm confused on if I should count a subset as one element or if I should count all the elements of that subset when computing cardinality. Example: Given the set $A = \{1,2,3,\{4,5,6\}\}$ does $A$ ...
3
votes
1answer
85 views

Does $f^{-1}(Y)$ make sense if $Y$ is “bigger” than $X$

My textbook asks me to decide whether or not this expression is true: Given the function $f: X \to Y$ with $B_1 \subseteq Y $. $ f^{-1}(Y $ \ $ B_1) = X $ \ $f^{-1}(B_1) $ I was confused ...
1
vote
1answer
54 views

Showing $ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $ is false by giving a counterexample.

Show that $$ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $$ is false by giving a counterexample. I tried the following, but every time it keeps coming out as true (instead of false): If $R = \{(a,b), ...
3
votes
2answers
29 views

cardinality of infinite sets with cartesian product

claim: $A,B,C,D$ are infinite if $|A\times B|=|C\times D|$ then $|A|=|C|$, $|B|=|D|$ , prove or give a counter example. So imo, the claim is false, using $A=D=\mathbb{R}$ , $B=C=\mathbb{N}$ , is it ...
0
votes
2answers
61 views

Proof by contradiction for a set question

I have a statement I need to prove by contradiction: If A and B are sets then A intersect (B-A) = {} (empty set). None of the questions I've ever done for this class are like this so im not really ...
1
vote
0answers
34 views

On $\sigma$-algebra generated by sets

Given $\mathcal{S}$ a collection of subsets of $X$ and $A\subset X$. To show that $\sigma(\mathcal{S}\cap A)=\sigma(S)\cap A$, where for any collection of $\mathcal C$ of subsets of $X$, $\mathcal ...
1
vote
1answer
16 views

How can I show that this has a reflexive closure?

Assume R is a relation on A. Show that R ∪ ΔA is the reflexive closure of R. What I thought is, that if R is an union with ΔA, it must mean that all a in A are (a,a). But I don't know if this is ...
2
votes
1answer
27 views

Problem on number of elements in sets

This question in my text book chapter named "Permutation, Combination and Probability". But I am stuck with Permutation, Combination and probability. All things are seems same to me. As I am new in ...
1
vote
1answer
67 views

Why is this relation irreflexive? And how can I prove it?

Why is the relation R on A irreflexive if and only if ΔA ∩ R = ∅? I always thought the empty set is reflexive (and transitive, symmetric because it is vacuously true.)
0
votes
1answer
33 views

Zermelo-Fraenkel Set Theory Question regarding Ordered Pairs [closed]

Problem: Show that $\{x,\{y\}\}$ is not suitable as a definition of the ordered pair $(x,y)$, because it does not have the ordered pair property: For any sets $x,y,u,v$ if $( x,y ) = ( u,v )$, then ...
0
votes
1answer
68 views

How many curly brackets of the empty powerset?

The question is: How many curly brackets are there in the following, if $\varnothing$ counts as $\{ \}$ (=1 curly brackets) $$ \wp^5(\varnothing) $$ I calculated $p^2$, which was $4$ curly brackets, ...
0
votes
0answers
10 views

For which sets, $X$ the relation is a partial function

Given $T=\left\{\ \left<A,B\right> \in (P(X))^2 | A\subseteq B \right\}$ For which sets, $X$, the relation $(P(X))^2-T \cap (P(X))^2-T^{-1}$ is a partial function? Here's my solution: ...
0
votes
1answer
30 views

Prove the formula $ff^{-1}(B) = B \cap f(X) \subset B$ where $f: X\to Y$

Still struggling with proofs. This formula was presented as a given in my book and it wasn't intuitive to me at all, so I wanted to verify it as it seems images and inverse images play important roles ...
1
vote
1answer
45 views

show that for an infinite cardinal $k$, $k + k = k$

Show that for an infinite cardinal $k$, $k + k = k$ So far I have that $k + k = 2k$ Is it possible to somehow show that $2k = k$? I've been trying to understand some cardinal arithmetic, and I ...
3
votes
3answers
74 views

How to prove $ A \cup \{a\} \approx B \cup \{ b \} \Rightarrow A \approx B $

How to prove this without recurring to cardinality? $ A \cup \{a\} \approx B \cup \{ b \} \Rightarrow A \approx B $ Where by "$ \approx $" I mean that there exists a bijective function between A and ...
3
votes
2answers
39 views

Question about partitions in intervals of the real numbers.

I have to prove the following: Let $ \mathcal{D} $ be a partition of $ \mathbb{R} $ in intervals of any kind, except intervals containing a single element. Prove $ \mathcal{D} $ is countable. ...
1
vote
0answers
50 views

Formally prove set cardinality

I'm preparing my discrete mathematics exam. Take one of the questions: Given the two sets $$ A = \{ n \in \Bbb{N} | 1 \le n \le 18 \} = \{ 1, 2, \ldots, 18 \}\\B = \{ n \in A | (n, 18) = 2 \} = ...
2
votes
1answer
49 views

Ordinal $10^\omega$

$10^\omega$ = $10 \cdot 10 \cdot 10 \cdot ...= \lim_{\alpha \lt \omega} (10^\alpha) = \omega$. Are my thoughts correct? Is this sufficient explanation, given the ordinal arithemtic proved from ZFC?
2
votes
1answer
414 views

Biggest countable ordinal number

I need to find biggest countable ordinal number. But I am sure there is no one, if I understand proofs and definitions correctly. So here are my idea: Suppose there is biggest countable ordinal number ...
2
votes
1answer
110 views

Proof or find a counterexample:For all sets $A;B;C$ if $A\subseteq B,\ B\subseteq C,$ and $C\subseteq A,$ then $A=B=C.$

Proof or find a counterexample:For all sets $A;B;C$ if $A\subseteq B,\ B\subseteq C,$ and $C\subseteq A,$ then $A=B=C.$ My solution: True. Let $x\in A$, and since $A\subseteq B$ this implies that ...
0
votes
1answer
46 views

If we define for set $S,T$ that $ |S|-|T|=|S-T|$, is this well-defined?

Problem If we define for set $S,T$ that $|S|-|T|=|S\setminus T|$, then this is well-defined in the sense that for all sets $S,T,S',T'$, if $|S|=|S'|$ and $|T|=|T'|$, then $|S|-|T| =|S'|\setminus ...
0
votes
3answers
62 views

If $A$ is subset of $B$, $B$ is subset of $C$, and $C$ is subset of $A$, then $A = B = C$

For all sets $A$, $B$, $C$, if $A$ is subset of $B$, $B$ is subset of $C$, and $C$ is subset of $A$, then $A = B = C$. This is a true statement and I need to provide a proof? Thus, when a statement ...
-1
votes
1answer
30 views

Different types of well-ordering of $\mathbb{N}$

The question is: "Find 3 non-isomorpic with each other well-orderings of $\mathbb{N}$. Define their ordinals and arrange them in magnitude." The question in ZFC, but I only know that such ...
0
votes
3answers
40 views

Why is this relation anti-symmetric? [duplicate]

Why is the following relation anti-symmetric? {(1,2), (2,3), (3,4), (1,4), (1,3), (2,4)} From my understanding, it is anti-symmetric if: $$ (a, b) \in R, (b, a) ...
2
votes
0answers
37 views

How do I write a rigorous proof of the following problem: $(A \triangle B) \cup C \neq (A \cup C) \triangle (B \cup C)$

Question: How do I write a rigorous proof of the following problem: Does the following equality hold true for any sets $A$, $B$ and $C$: $$ (A \triangle B) \cup C = (A \cup C) \triangle (B \cup C) $$ ...
2
votes
1answer
27 views

A problem concerning a partially ordered in $\omega$ and two chains.

Assume that $P=\left\langle\omega, \preceq\right\rangle$ is a partially ordered set such that for each $n \in \omega$ there are two chains $A_n$ an $B_n$ in $P$ such that $n \subset A_n \cup B_n$. ...
0
votes
1answer
37 views

Exercise on subsets

Suppose that $n\in\mathbb{N}$. Find the greatest $m\in\mathbb{N}$ such as there exist distinct subsets $S_1,S_2,...,S_m\in[[1,n]]$ verifying $\forall i,j\in\left[|1,m|\right], i\neq j\Rightarrow |S_i ...
1
vote
2answers
45 views

How to prove or disprove $P(\overline A) = P(U) - P(A)$

Edit: P(U) and P(A) refer to Power Sets. I don't know how to prove, or disprove, $P(\overline A) = P(U) - P(A)$. My initial thoughts is that the statement is true: If I have a set A in universe U, ...
2
votes
1answer
49 views

Prove that $A\subseteq B$, $A\cap \overline{B}=\oslash$ and $\overline{A}\cup B=\mu$ are equivalent

I've been asked to Prove that $A\subseteq B$, $A\cap \overline{B}=\oslash$ and $\overline{A}\cup B=\mu$ are equivalent. I believe I have done so, but I expect that I have missed something critical. ...
1
vote
1answer
51 views

A* finite or infinite? (Set theory)

I have a question regarding the following: If A is a set, then by A* we mean the set of all finite rows of elements of A. Now suppose A is finite. How big is A*, and how can you see that? I ...
1
vote
1answer
71 views

Are there more rational or irrational numbers? [duplicate]

On the number line, are there more rational numbers or irrational numbers? I was told that there are equally many rational and irrational numbers. Is this correct? How could we prove that?
0
votes
2answers
28 views

Let A, B and C be sets. Prove that $A \cap (B-C) = (A \cap B) - (A \cap C)$

Someone please edit so the & symbol is the intersect (reverse of U). This is a recent question on proofs homework. From what I understand, intersect and minus symbols used in equations for sets ...
6
votes
1answer
67 views

Prove that the family of open sets in $\mathbb{R}$ has cardinality equal to $2^{\omega}$

Let $\mathcal{T}$ be the family of all open sets in $\mathbb{R}$. Show that $| \mathcal{T}|=2^{\omega}$ $\textbf{My Attempt:}$ I know that $\forall A \in \mathcal{T}$. $A$ is the countable union of ...
1
vote
1answer
28 views

what is the cardinal number of these sets?

I'm not sure about 2, and I really don't know how to begin 3, any ideas?. $\mathbb R^+=\{x\in\mathbb R\mid x>0\}$. $K=\{x\in\mathbb R^+\mid x^2\in\mathbb N\}$ $L=\{(x,y)\in\mathbb ...
2
votes
3answers
55 views

Prove there exists a countably infinite subset $A$ of $P(\mathbb{N})$ that satisfies given conditions [duplicate]

Prove that there exists a countably infinite set $A \subseteq $ $P(\mathbb{N})$ that satisfies all of the following conditions: $i)$ $X \cap Y = \emptyset$ for all $X, Y \in A$ such that $X \neq Y$ ...
2
votes
2answers
31 views

the set of all of infinite N subsets

I was thinking about this one for a while and can't find a proper function. let $M=${$A\in P(N)$|A And A' are infinite} (for example: the set of all even numbers will be in M, the complement of A ...
1
vote
2answers
42 views

Help finding this set

Lets define the following: Let A be a set. A is innumerable if and only if there exists a bijective function from A to $\mathbb{N}$ Proof that there exists an innumerable set $B \subseteq \mathcal P ...
-1
votes
1answer
45 views

Countability of Different Sets [duplicate]

(a) Prove that $N \times N$ is a countable set (b) Let T be the set of two element subsets of N. Prove that T is countable. This is a question in my exam review package. I missed the lesson on ...
1
vote
3answers
43 views

Proof that the combination formula actually gives you the number of combinations

Ok, there's no problem in defining a binomial coefficient the way it this: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$ I can also prove to myself that if I have $n$ elements, like: $\{a_1, a_2, \ldots, ...
1
vote
4answers
97 views

If $f \colon A \to B$, $g :\colon B \to C$ and $g\circ f \colon A \to C$ are bijections. Prove that $f $ is 1-1, $g$ is onto.

From what I understand, one-to-oneness means every element in $A$ is mapped to a unique element in $B$. To be onto, means for every $y$ in $B$, there exist at least one $x$ in $A$ from which it can ...
1
vote
3answers
65 views

Prove that $A \cup B = A$ if and only if $B$ is a subset of $A$

If $A \cup B = A$ then $A$ is a subset of $A$ and $B$ is a subset of $A$. Thus $A \cup B = A$. If $B$ is a subset of $A$ then it follows that $A \cup B$ is a subset of $A$. My solution. It seems ...
1
vote
3answers
98 views

Prove that the union of two disjoint countable sets is countable

This is a question from my proofs course review list that I have had trouble understanding. I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove ...